Backdoor and ECDSA

8 replies 334 views
gw3i1337Full Member
Posts: 148 · Reputation: 495
#1May 14, 2024, 10:20 AM
Hey everyone. I found some code on GitHub related to a backdoor in ECDSA. I analyzed it with the rsz values I found, but I can't figure out what it all means. Can anyone explain what these leaked values are and their purpose? Any insights would be appreciated!
2 Reply Quote Share
paul2017Senior Member
Posts: 218 · Reputation: 1426
#2May 14, 2024, 11:44 AM
In short, the attacker influences the selection of the nonce in such a way that a portion of a secret can be derived from each signature. The secret to be leaked can be anything, but it is just a random value in the example code: The nonce, k, is computed by multiplying a small portion, si, of the secret, S, by a value, b, known only to the attacker. Since b is known by the attacker and si is a small value, k and si can be recovered. k = si * b obfuscates the fact that k is not random.
3 Reply Quote Share
eric.maxiMember
Posts: 35 · Reputation: 232
#3May 16, 2024, 08:43 PM
In a similar way I have a simulation script in python https://github.com/iceland2k14/rsz/blob/main/LLL_nonce_leakage.py  where some Random signatures are prepared with Leakage in 128 bits and then assuming they are are from Real Tx, they are solved using LLL reduction to print the PrivateKey.
3 Reply Quote Share
gw3i1337Full Member
Posts: 148 · Reputation: 495
#4May 17, 2024, 12:46 AM
can I use your script with real values? I couldn't find a way. So how can I find the value of b? Trial and error method for example? Is b an integer?
4 Reply Quote Share
paul2017Senior Member
Posts: 218 · Reputation: 1426
#5May 17, 2024, 04:15 AM
It is clearly stated that b is chosen by the attacker. Your questions indicate to me that it might help to learn more about cryptography before tackling the details of this subject.
3 Reply Quote Share
omega_bearFull Member
Posts: 116 · Reputation: 780
#6May 17, 2024, 07:46 AM
Someone really think , what without signing, sending coins or sending message from victim to attacker this code can be work ? if this code can work we can make fake publick key with some bits of victim publick key/private key,yes  ? how ? looks like this code , like a LLL dream.... LLL not work because all k in sighhnatuses have no 256 bit !
3 Reply Quote Share
omega_bearFull Member
Posts: 116 · Reputation: 780
#7May 17, 2024, 10:27 AM
Author was delete repo If someone interested, forked linck: https://github.com/Hurd8x/backdoor-ecdsa
4 Reply Quote Share
gw3i1337Full Member
Posts: 148 · Reputation: 495
#8May 19, 2024, 12:23 AM
Yes, I asked a question and it was deleted. I don't understand why. I've been searching on the internet, but I still haven't figured out how to use the leaked parts.
5 Reply Quote Share
omega_bearFull Member
Posts: 116 · Reputation: 780
#9May 21, 2024, 01:30 AM
hi use leaked parts for matrix GF[2],but bitcoin is a GF[7] using a GF[2] very interesting moment. And  I not understand what scryt find in final ? You know answer ? I ask openai and hi tell me what scrypt use for matrix differet r,s from different privkey-message pairs.... You undertand this momennt ? First, instead of s_i be just chunks of S, we set s_i to be the result of a vector-matrix multiplication over GF(2) s_i := S*[M]. Here [M] is a public matrix constructed from the message being signed m, with dimensions chosen so that s_i is only a few bits long. To reconstruct S from s_i, the backdoor designer just solves a linear system of equations over GF(2). The advantage here is that this method is resistant to loss of some s_i, and the order in which s_i are recovered does not matter. Also, the backdoor designer gets immediate feedback on how many bits are still to be guessed from S!
3 Reply Quote Share

Related topics