challengename - bi0sCTF 2024

tl;dr

• appending same bytes to an existing collision results in a collision as well
• reusing nonce leads to secret leak

Challenge Points: 100
No. of solves: 54
Challenge Author: Hisoka

Challenge Description

challenge description

Handout : server.py

Initial analysis

The curve parameters seem to have been redacted so we need to recover the curve parameters first.

Initially, we seee a function that seems out of place, namely, bigsur().

The function is as follows :

def bigsur(a,b):
    a,b = [[a,b],[b,a]][len(a) < len(b)]
    return bytes([i ^ j for i,j in zip(a,bytes([int(bin(int(b.hex(),16))[2:].zfill(len(f'{int(a.hex(), 16):b}'))[:len(a) - len(b)] + bin(int(b.hex(),16))[2:].zfill(len(bin(int(a.hex(), 16))[2:]))[:len(bin(int(a.hex(), 16))[2:]) - len(bin(int(b.hex(), 16))[2:])][i:i+8], 2) for i in range(0,len(bin(int(a.hex(), 16))[2:]) - len(bin(int(b.hex(), 16))[2:]),8)]) + b)])

It’s hard to make sense out of this function by just looking at this code, but the intended behaviour of this function is to pad null bytes to the beginning of the shorter bytearray before xoring them together. This leads to some interesting characteristics that we can exploit later.

Let’s take a look at the signing function.

def sign(msg,nonce,privkey):
    hsh = md5(msg).digest()
    nunce = md5(bigsur(nonce,magic)).digest()
    sig = privkey.sign(bytes_to_long(hsh), bytes_to_long(nunce))
    return json.dumps({"msg": msg.hex(), "r": hex(sig.r), "s": hex(sig.s)})

The sign function takes the message, nonce and privkey as arguments. the nonce is generated by calling bigsur() with the arguments given nonce and magic bytes that were generated at the beginning. These magic bytes stay static throughout the session.
The hash is generated of the newly generated nonce which is used as the nonce for the signature.

The enc function:

def enc(privkey):
    x = int(flag.hex(),16)
    y = pow((x**3 + a*x + b) % p, (p+3)//4, p)
    F = ellipticcurve.Point('--REDACTED--'x,y)
    Q = F * privkey.secret_multiplier
    return (int(Q.x()), int(Q.y()))

It just lifts the flag on the curve to make a point, and multiplies it with the secret multiplier d.

pubkey, privkey = genkeys()
print("Public key:",(int(pubkey.point.x()),int(pubkey.point.y())))
print("Encrypted flag:",enc(privkey))

nonces = set()

for _ in '01':
    msg = bytes.fromhex(input("Message: "))
    nonce = bytes.fromhex(input("Nonce: "))
    if nonce in nonces:
        print("Nonce already used")
        continue
    nonces.add(nonce)
    print(sign(msg,nonce,privkey))

We are provided the Public key and the Encrypted flag as soon as we connect to the nc

We have 2 tries to query the oracle with our own Message and nonce. We cannot send the same nonce twice, as it would clearly lead to a nonce reuse.

Exploit

First and foremost, we need to recover the curve parameters. We can do this as we’re provided with two points initally (Encrypted flag and Public key).

assuming that the curve is in weistrass form

Now, let’s take a look at the signing function.

It takes the message, nonce (which we are in control of) and the privkey as arguments.
It calls bigsur() with the nonce provided and the magic bytes initially generated to generate a new nonce which is used for the signatures.

The intended behaviour of this function is to xor two bytearrays by padding the shorter one with null bytes at the beginning. So it would look something like this:

a = b"hel\x00\x00\x00"
b = b"lo!"

bigsur(a,b) --> b"hello!"

So, directly providing two nonces that result in a collision would not work.

Here is where multiple solution approaches arise.
There are a lot of unique solutions that the participants came up with during the ctf, but I’m going to be exploring the intended solution.

Now, since the null byes are padded at the beginning, if we concatenate 16 null bytes (length of the magic bytes generated) to the nonce we provide, it should concatenate the magic bytes to the nonce we provide.

So, if we provide the calculated collisions, but concatenate it with 16 null bytes, it should look something like this:

--sig1--
nonce = md5(coll1 | magic)

--sig2--
nonce = md5(coll2 | magic)

where md5(coll1) == md5(coll2)

Now, md5 is based on something called the Merkle-Damgard construction.

Essentially it means that if you concatenate the same bytes to the bytearrays of an existing collision, the resulting bytestrings result in a collision as well.

So, this means that the resulting nonces will be the same if we add 16 null bytes at the end of our inputs.

After all this is done, the challenge collapses into a simple nonce reuse attack. How it works is:

• We have two signatures (m1, r1, s1) and (m2, r2, s2) which use the same nonce k.
• This means we can form a pair of linear congruences and solve them for the secret d.

ecdsa:

where k is the nonce, and z is the hash of the message to be signed
The signature generated is the pair (r,s)

Now, if the nonce is reused, we have a pair of relations

So from there, it’s simple enough to recover k

From there, recovering the secret d is trivial.

The full exploit can be found here

Conclusion

This was supposed to be a challenge aimed towards beginners in ecdsa and hash algorithms. I hope you’ve learned something by trying to attempt this challenge. The other approaches were interesting to look at as well!

Flag: bi0sctf{https://bit.ly/3I0zwtG}