Baby crypto revisited Writeup

LINE CTF 2022 - crypto 138 - 48 solves

Last time, our side-channel attack was quite easy. But our victim found out about our sneaky attack and increased the size of nonce. Fortunately, we could still capture the first half of the nonce, which is 64-bit this time. Now please help us to find out the encryption key again. The victim is using the secp160r1 curve. The following is the captured data: r, s, k, and hash respectively. Flag is LINECTF{}, e.g. LINECTF{0x1234}

Babycrypto_revisited_b1f108dea290b83253b80443260b12c3cadc0ed7.txt

Analysis

ECDSA signature pair r, s with partial nonce k_ and message hash h are given. There are num_samples = 100 pairs given. According to the description, nonce size is 128 bits, but we know the half of it. Curve order size of secp160r1 is 160 bits, so 160 - 64 = 96 bit is known. Our goal is to recover the private key d.

Reduction: Biased Nonce Attack

Because we know the MSBs of k, we can generate new signature/message pairs which their MSBs are fixed.

Let k = k_ + a, where a is 64 bits. k and k_ are 128 bit size each. We can make signature r_new, s_new which are generated using nonce a with hash h_new using r, s, h, k_. How?

r     = (k * G).x()
# k * G can be recovered although we do not know k, by using r which is x coord of EC
r_new = (a * G).x() = (k * G - k_ * G).x()
s     = kinv * (h + r * d)
s * k = h + r * d
s * (k_ + a) =  h + r * d
s * a = h - s * k_ + r * d
rinv * r_new * s * a = rinv * r_new * (h - s * k_) + rinv * r_new * r * d
rinv * r_new * s * a = rinv * r_new * (h - s * k_) + r_new * d

New signature is finally derived as below:

r_new = (k * G - k_ * G).x()
s_new = rinv * r_new * s
h_new = rinv * r_new * (h - s * k_)

By converting given signatures using above derivation, we get num_sample signatures, which uses biased nonce. The nonce's upper 96 bits will be set to zero. Biased nonce attack time! Solve Hidden number problem using LLL to obtain secret key d. 100 sample was sufficient to recover the hidden number.

LINECTF{0xd77d10fec685cbe16f64cba090db24d23b92f824}

Problem output: Babycrypto_revisited_b1f108dea290b83253b80443260b12c3cadc0ed7.txt

exploit driver code: solve.sage