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 designed by private key 'd' to message hash z , such that: k = 128 MSB bit of z + 128 bit MSB of d (privatekey) example:

d= private key in hex
z= message hash
k= nonce; where nonce is equal first 128 bit of z + 128 bit of d

d= 0x036ed4f5f383049827edc4fe337f46f83a240b124242620b02b97552b2fc11a4
z= f55ab477c48f9afaf1a72ab448bf96b4a05f336f7a1e27e08993308dfaa783b5
k = f55ab477c48f9afaf1a72ab448bf96b4 + 036ed4f5f383049827edc4fe337f46f8
k= 0xf55ab477c48f9afaf1a72ab448bf96b4036ed4f5f383049827edc4fe337f46f8

signature:
r= 62326678398279634483781267842729177896577268934832461436294590773005653623297
s= 78373122694400608572761948114834235891083358005495335895684705221713649603747
z= 110976909682006680432155795488402189554785886863009729379902726621537291961269

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.

Is there any way to calculate k or privatekey?

N: Finite field of the secp256k1

0

1 Answer 1

5

I believe this would be trivial to break.

Let's say that:

  • z = z0 + 2128z1, with 128-bit z0, z1.
  • d = d0 + 2128d1, with 128-bit d0, d1.

In that case, according to your construction, k = d1 + 2128z1.

For ECDSA signatures (r,s):

  • We know s = k-1(z + rd) (mod n) (the signing equation)
  • Put otherwise: sk = z + rd (mod n)
  • Substituting the above: s(d1 + 2128z1) = z0 + 2128z1 + r(d0 + 2128d1) (mod n).
  • Grouping: rd0 + (2128r - s)d1 = 2128z1(s - 1) - z0 (mod n).

All variables in the last equation above except for d0 and d1 are known. Finding solutions for those restricted to range [0,2128) is a simple lattice reduction, which likely has at most a few solutions. Those can be tested exhaustively.

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.