<- CRYPTO

Colliding Heritage

6 minutes to read

We are provided with the server source code in Python:

#!/usr/bin/env python3

import signal
from secrets import randbelow
from hashlib import md5
from Crypto.Util.number import isPrime, getPrime, long_to_bytes, bytes_to_long  

FLAG = "HTB{???????????????????????????}"


class MD5chnorr:

    def __init__(self):
        # while True:
        #     self.q = getPrime(128)
        #     self.p = 2*self.q + 1
        #     if isPrime(self.p):
        #         break
        self.p = 0x16dd987483c08aefa88f28147702e51eb
        self.q = (self.p - 1) // 2
        self.g = 3
        self.x = randbelow(self.q)
        self.y = pow(self.g, self.x, self.p)

    def H(self, msg):
        return bytes_to_long(md5(msg).digest()) % self.q

    def sign(self, msg):
        k = self.H(msg + long_to_bytes(self.x))
        r = pow(self.g, k, self.p) % self.q
        e = self.H(long_to_bytes(r) + msg)
        s = (k - self.x * e) % self.q
        return (s, e)

    def verify(self, msg, sig):
        s, e = sig
        if not (0 < s < self.q):
            return False
        if not (0 < e < self.q):
            return False
        rv = pow(self.g, s, self.p) * pow(self.y, e, self.p) % self.p % self.q
        ev = self.H(long_to_bytes(rv) + msg)
        return ev == e


def menu():
    print('[S]ign a message')
    print('[V]erify a signature')
    return input('> ').upper()[0]


def main():
    md5chnorr = MD5chnorr()
    print('g:', md5chnorr.g)
    print('y:', md5chnorr.y)
    print('p:', md5chnorr.p)

    for _ in range(3):
        choice = menu()

        if choice == 'S':
            msg = bytes.fromhex(input('Enter message> '))
            if b'I am the left hand' in msg:
                print('No!')
            else:
                sig = md5chnorr.sign(msg)
                print('Signature:', sig)

        elif choice == 'V':
            msg = bytes.fromhex(input('Enter message> '))
            s = int(input('Enter s> '))
            e = int(input('Enter e> '))
            if md5chnorr.verify(msg, (s, e)):
                if msg == b'I am the left hand':
                    print(FLAG)
                else:
                    print('Valid signature!')
            else:
                print('Invalid signature!')

        else:
            print('Invalid choice...')


if __name__ == '__main__':
    signal.alarm(30)
    main()

Schnorr signature

The challenge implements a signing server using Schnorr signature. The algorithm to sign a message $m$ is the following:

  • Choose a private signing key $x$ and a prime number $p$ such that $q = \displaystyle\frac{p - 1}{2}$ is a prime number as well
  • Choose a random nonce value $k$
  • Let $r = (g^k \mod{p}) \mod{q}$
  • Let $e = H(r \;||\; m)$ where $H$ is a hash function and $||$ denotes concatenation
  • Let $s = k - xe$

The signature is the pair $(s, e)$.

Challenge implementation

In this challenge, the class MD5chnorr uses MD5 as hash function $H$ and the nonce value $k$ is not chosen randomly, but as $k = H(m \;||\; x)$:

    def H(self, msg):
        return bytes_to_long(md5(msg).digest()) % self.q  

    def sign(self, msg):
        k = self.H(msg + long_to_bytes(self.x))
        r = pow(self.g, k, self.p) % self.q
        e = self.H(long_to_bytes(r) + msg)
        s = (k - self.x * e) % self.q
        return (s, e)

The security flaw

The server allows us to use two options but only three times. The two options are to sign message and to verify a message. The flag will appear as long as we can verify a specific message ("I am the left hand"). Obviously, we can’t use option S to sign that specific message:

    for _ in range(3):
        choice = menu()

        if choice == 'S':
            msg = bytes.fromhex(input('Enter message> '))  
            if b'I am the left hand' in msg:
                print('No!')
            else:
                sig = md5chnorr.sign(msg)
                print('Signature:', sig)

        elif choice == 'V':
            msg = bytes.fromhex(input('Enter message> '))
            s = int(input('Enter s> '))
            e = int(input('Enter e> '))
            if md5chnorr.verify(msg, (s, e)):
                if msg == b'I am the left hand':
                    print(FLAG)
                else:
                    print('Valid signature!')
            else:
                print('Invalid signature!')

        else:
            print('Invalid choice...')

So, we will use option S two times and then V to send the required message but signed appropriately. Therefore, with the first two signatures, we must somehow find the private key $x$, needed to sign arbitrary messages.

Digital signature algorithms can be comprimised if a nonce value $k$ is reused in different message signatures. Since the only difference between Schnorr signature and MD5chnorr is the fact that $k$ is not chosen randomly, this must be the security flaw.

In fact, $k$ is the output of an MD5 hash, which is known to have collisions. I did a ton of research on ways to compromise this hash function and found HashClash. I also researched on chosen prefix and length extension attacks, but none of them was applicable to this challenge. Plus, the challenge has the word “Colliding”, so the intended way must involve a collision, probably in MD5.

In fact, the solution is very simple because MD5 is very vulnerable to collisions. In Wikipedia we can find two slightly different hexadecimal strings that result in the same MD5 hash:

$ echo 'd131dd02c5e6eec4 693d9a0698aff95c 2fcab58712467eab 4004583eb8fb7f89
55ad340609f4b302 83e488832571415a 085125e8f7cdc99f d91dbdf280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e2b487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080a80d1e c69821bcb6a88393 96f9652b6ff72a70' | xxd -r -p | md5sum  
79054025255fb1a26e4bc422aef54eb4  -

$ echo 'd131dd02c5e6eec4 693d9a0698aff95c 2fcab50712467eab 4004583eb8fb7f89
55ad340609f4b302 83e4888325f1415a 085125e8f7cdc99f d91dbd7280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e23487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080280d1e c69821bcb6a88393 96f965ab6ff72a70' | xxd -r -p | md5sum
79054025255fb1a26e4bc422aef54eb4  -

What costed me a lot to figure out is that appending the same block to the above hexadecimal strings will still produce the same MD5 hash:

$ echo 'd131dd02c5e6eec4 693d9a0698aff95c 2fcab58712467eab 4004583eb8fb7f89
55ad340609f4b302 83e488832571415a 085125e8f7cdc99f d91dbdf280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e2b487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080a80d1e c69821bcb6a88393 96f9652b6ff72a70
0123456789abcdef 0123456789abcdef 0123456789abcdef 0123456789abcdef' | xxd -r -p | md5sum  
5e1b7ce6b54d7313d856753d9d48f17c  -

$ echo 'd131dd02c5e6eec4 693d9a0698aff95c 2fcab50712467eab 4004583eb8fb7f89
55ad340609f4b302 83e4888325f1415a 085125e8f7cdc99f d91dbd7280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e23487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080280d1e c69821bcb6a88393 96f965ab6ff72a70
0123456789abcdef 0123456789abcdef 0123456789abcdef 0123456789abcdef' | xxd -r -p | md5sum
5e1b7ce6b54d7313d856753d9d48f17c  -

This is the key to solve the challenge because the nonce $k = H(m \;||\; x)$, so if we enter the above special strings, we can be sure that both $k$ values will be equal and thus compromise the signature to find $x$.

Nonce reuse

Once we have two messages $m_1$ and $m_2$ that use the same nonce value $k$, we can use the following system of equations on variables $k$ and $x$:

$$ \begin{cases} s_1 = k - x e_1 \mod{q} \\ s_2 = k - x e_2 \mod{q} \\ \end{cases} $$

Therefore, substracting both equations we have

$$ s_1 - s_2 = x e_2 - x e_1 \mod{q} $$

So we can isolate $x$:

$$ x = (s_1 - s_2) \cdot (e_2 - e_1) \mod{q} $$

Once we have $x$, we are able to sign any message.

Python implementation

This is the main function of the solution script:

def main():
    host, port = sys.argv[1].split(':')
    io = remote(host, port)

    msg1 = 'd131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f8955ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5bd8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0e99f33420f577ee8ce54b67080a80d1ec69821bcb6a8839396f9652b6ff72a70'  
    msg2 = 'd131dd02c5e6eec4693d9a0698aff95c2fcab50712467eab4004583eb8fb7f8955ad340609f4b30283e4888325f1415a085125e8f7cdc99fd91dbd7280373c5bd8823e3156348f5bae6dacd436c919c6dd53e23487da03fd02396306d248cda0e99f33420f577ee8ce54b67080280d1ec69821bcb6a8839396f965ab6ff72a70'

    io.sendlineafter(b'> ', b'S')
    io.sendlineafter(b'Enter message> ', msg1.encode())
    io.recvuntil(b'Signature: ')
    s1, e1 = eval(io.recvline().decode())

    io.sendlineafter(b'> ', b'S')
    io.sendlineafter(b'Enter message> ', msg2.encode())
    io.recvuntil(b'Signature: ')
    s2, e2 = eval(io.recvline().decode())

    x = (s2 - s1) * pow(e1 - e2, -1, q) % q

    def sign(msg):
        k = H(msg + long_to_bytes(x))
        r = pow(g, k, p) % q
        e = H(long_to_bytes(r) + msg)
        s = (k - x * e) % q
        return (s, e)

    s, e = sign(b'I am the left hand')

    io.sendlineafter(b'> ', b'V')
    io.sendlineafter(b'Enter message> ', b'I am the left hand'.hex().encode())
    io.sendlineafter(b'Enter s> ', str(s).encode())
    io.sendlineafter(b'Enter e> ', str(e).encode())

    io.success(io.recvline().decode())

Flag

Once we run it, we will find the flag:

$ python3 solve.py 161.35.36.167:32629
[+] Opening connection to 161.35.36.167 on port 32629: Done  
[+] HTB{MD5_c0111510n_4nd_5chn022'5}
[*] Closed connection to 161.35.36.167 port 32629

The full script can be found in here: solve.py.