2

My question is related to weak signature vulnerability testing where a hypothetical attacker does not know the values of the nonce or private key itself, but can determine that the nonce 'k1' is increased by private key 'd' to create k2, such that: k2 = k1+d.

I have searched the stack exchanges and various articles and research papers and have not found a workable solution to this problem. My own linear algebra is not as strong as I would like it (it's been a number of years), and my attempts have not been successful. I have used the k2 = k1+1 equations but they do not specifically produce the necessary solution of k2-k1 = d. Other solutions for solving for k did not work, either.

Is there a way to find the difference of k2-k1 = d, where k1, k2, and d are unknown, where k2 = k1+d, but all other values (r, s, z) are known?

(I have provided the values of d, k1, and k2 for verification of possible solutions, but for the purposes of the question, assume an attacker does not know the values but can spot a relationship).

Let:

N: Finite field of the secp256k1

d: Private key

B(x,y): Public key coordinates

k: Private key of ECDSA nonce

R(x,y): Public key coordinates of nonce

r: R.x integer

s: signature integer

z: Hash value of message

N= 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

B.x= 0x7697a1f8d952c373285bd441b1716344a61748b48279be15b03538d80e60f901

B.y= 0x431aed8857c99064b316a0c9fb6e7cba3eeade88f44d2c31dee4fa8965740f54

d= 0x8b5069be43c35cbc6530d473a9f102dc57f8f5771982eba3988a7588c6e284a7

k1= 0x248548dcbf7ff4b25134ee12f78fadaa8283025734b905640b8c400580b869e

s1= 0xec585a4b0317e38b75008930607a32224b3d11a8a373ed15da32723b1418f852

z1= 0x12dd3658e48a15016dc1f5af7725ad3a5e7b2d6a52112dbd4a0d6df8772a141a

R1x= 0xb2dcf2acc6fdd003e65e8d9d77ee4d84a9c0cccbac8eb43bdeeecb69a35bab4b

R1y= 0x4a8774fd7ac69caf2d92154324c2280b5f29652b7f458baa28545f1b38d969b8

############################

k2= 0x8d98be4c0fbb5c078a442354d969fdb70021259c8cce7bf9d94339891eee0b

s2= 0x2df1c9e8b3984088ec521c92e9f001b836841e8a14cda6977072d5b23bed171e

z2= 0xdae540b9f50337b2dab2f226a687084e8a1758dbc73505b7ff288b01cc4dae3f

R2x= 0x37df00ccef04bfcf0f2b0da82a685125ddd67b9f66320a9619e6e4df7bd57439

R2y= 0x5ff78c4ef0caf4eff68f938ee475e2e99a7b9be31642eb0e5cb68b30a843b46b

Basic signature equations:

d= (k * s - z) * r^-1 mod N

k= (d * r + z) * s^-1 mod N - or- (d * a + b) mod N

s= (d * r + z) * k^-1 mod N

r= (k * s - z) * d^-1 mod N

z= (k * s) - (d * r) mod N

a= r * s^-1 mod N

b= z * s^-1 mod N

Is there a way to solve this to obtain the value k2-k1=d (k1+d-k1=d) given the equations above, or to solve either k1 or k2, or would the k generation scheme be relatively secure from attack?

Improve this question

1 Answer 1

Reset to default
5

This is trivially broken.

Given:

  • (1) s1 = (z1 + r1d) / k1
  • (2) s2 = (z2 + r2d) / k2
  • (3) k2 = k1 + d

Substituting (3) into (2), eliminating k2:

  • (4) s2 = (z2 + r2d) / (k1 + d)

Solving (1) for k1:

  • (5) k1 = (z1 + r1d) / s1

Substituting (5) into (4), eliminating k1:

  • (6) s2 = (z2 + r2d) / ((z1 + r1d) / s1 + d)

Solving (6) for d:

  • (7) d = (z2s1 - z1s2) / (s2(r1 + s1) - r2s1)

The right hand side of which only contains public information.

Note that all these variables are elements of F, so the division symbol above refers to multiplication with the modular inverse of the denominator modulo N.

k2= 0x8d98be4c0fbb5c078a442354d969fdb70021259c8cce7bf9d94339891eee0b

I believe you're missing a "45" after those digits.

Improve this answer
9
  • 2
    You are correct, there was a 45 on the end of the hex string, but the secp256k1 calculator would produce the incorrect result when running through the Generator Point while that was appended. I don't know the particular reason for this, but, deleting the 45 in the calculator produced the correct R(x,y) values. Thank you for your answer, I can see where my error was in my equations.
    – Alfhilðr ínn Seiðkona
    Commented Jun 9, 2022 at 19:18
  • Would solution (7) still hold true for k2=k1+d+1, if (7) were modified to: d=(z2*s1-z1*s2)/(s2*(r1+S1) - 1-r2*s1-1) mod N? I am manipulating the parameters on the small curve [N=79, P=67,G=(2,22), d=7, k1=19, r1=38, s1=36, z1=23 | k2=27, r2=17, s2=4, z2= 68].
    – Alfhilðr ínn Seiðkona
    Commented Jun 11, 2022 at 19:58
  • You cannot fix this. If your nonce values satisfy a simple polynomial expression, it will either be trivial to break, or at least be impossible to prove it is secure. If you want a provably secure technique, your nonces need to be actually unpredictable (e.g. computed using hashes with secret input, or randomly).
    – Pieter Wuille
    Commented Jun 11, 2022 at 20:20
  • 1
    I can generate secure random nonces without any issues. That is not the problem. I am trying to generate a decent honeypot for my employer so that potential employees can demonstrate their abilities. Thus, I am playing around with signature equations and I have honestly noticed and developed a lot of different patterns (granted, using the small curve) and equations to match. Back to your answer, I generate nonces using randomness on secp256k1 calculator, and then sign per protocols. This question is simply for my further education. Thank you so very much, I really appreciate you.
    – Alfhilðr ínn Seiðkona
    Commented Jun 11, 2022 at 21:00
  • It appears stackexchange butchered my earlier URL. Retry: tinyurl.com/429ye2ye gives the solution for k2 = a*k1 + b*d + c, with known constants a, b, c.
    – Pieter Wuille
    Commented Jun 12, 2022 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.