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
- Choose a private signing key
and a prime number such that is a prime number as well - Choose a random nonce value
- Let
- Let
where is a hash function and denotes concatenation - Let
The signature is the pair
Challenge implementation
In this challenge, the class MD5chnorr
uses MD5 as hash function
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
Digital signature algorithms can be comprimised if a nonce value MD5chnorr
is the fact that
In fact,
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
Nonce reuse
Once we have two messages
Therefore, subtracting both equations we have
So we can isolate
Once we have
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 138.68.158.112:32096
[+] Opening connection to 138.68.158.112 on port 32096: Done
[+] HTB{w3ll_y3s_bu7_4c7ual1y_n0...}
[*] Closed connection to 138.68.158.112 port 32096
The full script can be found in here: solve.py
.