InCTFi 2019 huygens gebouw

In this challenge, we were given two python files and a service to connect.
ecc.py file is an implementation of elliptic curve arthimetic.
ecdsa.py file is the implementation of ECDSA algorithm.
The service is running the ecdsa.py file.

In the ecdsa.py file we can see that in order to get the flag we have to provide the signature of message “admin” signed by the server’s private key.

The parameters of Elliptic Curve used by server are

p = 2**256 - 2**224 + 2**192 + 2**96 - 1
a = p-3
b = 41058363725152142129326129780047268409114441015993725554835256314039467401291
n = 115792089210356248762697446949407573529996955224135760342422259061068512044369

Gx = 105628562773329337640893595054548446109845168797622368389180213953990926700662
Gy = 32408302692268607486270308925513058111871258446764614158480809006157801114098

By googling the params, we can check that given Elliptic Curve is a standard curve P-256.

P-256 is a safe curve and it has been standardised by NIST. So, we can leave the thought of solving Elliptic Curve discrete logarithm.

In the Private Key class in ecdsa.py the signing algorithm is defined as follow

def sign(self, m):
    e = sha256(m).digest()
    Ln = len(bin(self.n)[2:])
    z = bytes_to_long(slice_string(e, Ln))
    k = gen_rand(1, self.n-1)
    r = (k*self.G).x()
    assert GCD(k, self.n) == 1
    s = (inverse(k, self.n)*(z + r*self.d)) % self.n
    return (r, s)

Going through the function we can see that k is generated by gen_rand() function. If you have read about ECDSA in any article, definitely there will be a little part saying that k should be generated by a cryptographically secure random number generator.Let’s see if gen_rand() is a secure PRNG.

def gen_rand(lower_limit, upper_limit):
    _rand_num = random.randint(lower_limit, upper_limit)
    _rand_num = map(ord, list(long_to_bytes(_rand_num)))
    for i in range(len(_rand_num)):
        _rand_num[i] ^= _rand_num[-1]
        _rand_num[i] = ((_rand_num[i] << 1) + 3) % 256
    _rand_num = bytes_to_long("".join(map(chr, _rand_num)))
    return _rand_num

At first, I thought there’s nothing interesting in this function and moved to check other parts of code.
I noticed that the service can be used as a signature oracle i.e, if we give a message, it will give the corresponding signature and if we give a signature & it’s corresponding message, it will tell us whether it is a valid signature or not.

As i know the Bleichenbacher padding oracle attack on rsa, I searched to check if there is any attack on ECDSA in an oracle model and luckily i found a stack exchange post with heading How does the “biased-k attack” on (EC)DSA work?.

what ?? “biased-k attack” i never heard that name.so, i searched for it and found that there’s a challenge based on this attack in cryptopals set 8 62. Key-Recovery Attacks on ECDSA with Biased Nonces.

After reading the cryptopals challenge 62 description completely and reviewing the gen_rand function given in our challenge,guess what gen_rand function also generates random numbers in the same way with a little modification.

So, what is biased-k in our gen_rand function, last 8 bits of every number generated by that function are ‘00000011’. what can we do by knowing that the k which is used for signing every message contains ‘00000011’ as last 8 bits.

how can we use the property (last 8 bits as ‘00000011’) of k to extract the private key??

Answering this question brings up the most juicy and my favorite part i.e, math part

reviewing the signing algorithm

sign(m):
    k := random_scalar(1, n - 1)
    r := (k * G).x()
    s := (H(m) + d*r) * k^-1
    return (r, s)

As the last 8 bits of k are 00000011, we can write k as

k = b*(2^l) + c
where l = 8 and c = 3

k = b*(2^8) + 3

from the signing algorithm

s = (z + d*r) * k^-1
s = (z + d*r) * (b * (2^8) + 3)^-1

s * (b * (2^8) + 3) = z + d*r
s * b * (2^8) + s*3 = z + d*r

b + (3 / (2^8)) := (z / (s * (2^8))) + ((d * r) / (s * (2^8)))

d*(r / (s * (2^8))) := - (z / (s*(2^8))) + (3 / (2^8)) + b

now taking

t = (r / (s * (2^8)))
u = -(z / (s*(2^8))) + (3 / (2^8))

we can write

d * t = u + b

note that all the above computations are done modulo n, the order of the generator.

compared to other parameters b is of size n/(2^8) whereas t, u and the private key are of size n ,since b is so small we can ignore b and write the above equation as

d * t ~ u

The above equation holds over the group modulo n

we can write it as

d*t ~ u + m*n

0 ~ u + m*n - d*t

u + m * n - d * t is not zero but it is less than the bound n/(2^8)

we can extract private key d using more (u, t) pairs and LLL algorithm.

The part of constructing the basis of lattice and finding the solution has been explained excellently in the before mentioned cryptopals challenge, I won’t take the trouble of explaining that here.

Coming to the implementation part, I have written the sage script to construct the basis and reduce it using the LLL algorithm and find the private key.

Sentinel values used are ct = (1/ (2^8)) and cu = (1/(2^8))

signatures file contains a dictionary with message as keys and corresponding signature signed by the server as the values.

I was able to find the d with around 42 signatures.

private key is d = -12978944819504458167916888695353741508975746904433093121164615085423925141911
                 = 102813144390851790594780558254053832021021208319702667221257643975644586902458 (mod n)

we got the private key, all that’s required to get the flag is signing the message “admin” and sending it to server. After sending the signature, server greets us with the flag.

Files

• signatures
• solution.sage

FLAG : inctf{well_well_congratulations_ECDSA_biased_nonce_s0lver}