PriMeD5

Thanks to JosePisco for the very useful hint of "a property md5 has on collisions". Completely shifted my approach.

The server is signing the hash of the prime sent using RSA, and there is no information to figure out the private keys so we have to forge two numbers $n_1$$n_1$ and $n_2$$n_2$ such that $MD5(n_1)=MD5(n_2)$$MD5(n_1) = MD5(n_2)$.

Initially my approach is to use fastcoll to generate MD5 collisions with a given prefix, but this approach is just too unreliable, as the probability of finding a prime with some reasonably chosen prefix is too low - fastcoll always generate 1024-bit messages anyways. Obviously this is still possible, but this is too painful to go through.

My solution relies on the fact, from this paper on MD5 Hash Collisions. Given two inputs $M$$M$ and $N$$N$, if $MD5(M)=MD5(N)$$MD5(M) = MD5(N)$, in words, the MD5 hashes of $M$$M$ and $N$$N$ are the same, then for any input $T$$T$, we have:

where $||$$||$ denotes string concatenation. Hence, our task is to find some 64-byte $M$$M$ and $N$$N$ that have the same MD5 hash. $M$$M$ and $N$$N$ must be 64 bits long as the size of the prime sent can only be 128 bytes (1024 bits), and finding MD5 collisions involving a prime with a composite number is the same problem as the fastcoll solution above.

From a bit of Googling, we encounter this link providing the two 64-byte blocks that provide the same MD5 hash. From this, we can obtain the number representation of the two byte strings:

xxxxxxxxxx
from array import array 
from Crypto.Util.number import bytes_to_long, long_to_bytes

# From Crypto SE 
input1 = array('I',  [0x6165300e,0x87a79a55,0xf7c60bd0,0x34febd0b,0x6503cf04,
    0x854f709e,0xfb0fc034,0x874c9c65,0x2f94cc40,0x15a12deb,0x5c15f4a3,0x490786bb,
    0x6d658673,0xa4341f7d,0x8fd75920,0xefd18d5a])

input2 = array('I', [x^y for x,y in zip(input1, [0, 0, 0, 0, 0, 1<<10, 0, 0, 0, 0, 1<<31, 0, 0, 0, 0, 0])])

input1 = input1.tobytes()
input2 = input2.tobytes()

print(bytes_to_long(input1))
print(bytes_to_long(input2))

Finding the suffix is equivalent to finding the next prime starting from input1 (denote by $I$$I$ for easier typing) left shift by 512 bits. We are banking on the property that there should be a prime in the range of $I\ast 2^{512}$$I * 2 ^ {512}$ to $I\ast 2^{512}+2^{512}$$I * 2 ^ {512} + 2 ^ {512}$. The following Sage script does the job nicely:

xxxxxxxxxx
# Number representation of input1
a = 743140687776435453115395131302219352605044002412376165590801538600189325387599345380629804174290217588448884064540448333089825870048997971529022550430191

print(next_prime(a << 512))

This will provide the prime with the first 512 bits the same as input1. We can take the 512-bit suffix of the prime, then append to input2, in order to obtain a byte string having the same MD5 hash as the prime. The work left is simple, sent the prime to the server to obtain the signature, then send the other number (composite) to the server with the obtained signature to retrieve the flag.

Python Implementation:

xxxxxxxxxx
from array import array 
from Crypto.Util.number import bytes_to_long, long_to_bytes
from pwn import * 
import json

# From Crypto SE 
input1 = array('I',  [0x6165300e,0x87a79a55,0xf7c60bd0,0x34febd0b,0x6503cf04,
    0x854f709e,0xfb0fc034,0x874c9c65,0x2f94cc40,0x15a12deb,0x5c15f4a3,0x490786bb,
    0x6d658673,0xa4341f7d,0x8fd75920,0xefd18d5a])

input2 = array('I', [x^y for x,y in zip(input1, [0, 0, 0, 0, 0, 1<<10, 0, 0, 0, 0, 1<<31, 0, 0, 0, 0, 0])])

input1 = input1.tobytes()
input2 = input2.tobytes()

# For Sage script
# print(bytes_to_long(input1))
# print(bytes_to_long(input2))

prime = 9963887606631886904510816744076774312332177344481531803123536722374675497268512166355104569363455060680486552386910190260277286163274728336768970568461704559940243411194284876439012740935592693167681525648038101883475692410324531178122487559150159612652628935987989808447316201357606634199027879941123342577

# From this https://seedsecuritylabs.org/Labs_20.04/Files/Crypto_MD5_Collision/Crypto_MD5_Collision.pdf
# As md5(input1) == md5(input2), appending the same suffix k to both input1 and input2 will lead to a new 
# bytestring with the same MD5 hash, in other words md5(input1 || k) = md5(input2 || k)

# The prime have the same first 64 bytes as input1
input1 = long_to_bytes(prime)

# Appending the 64-byte suffix to the other number 
input2 = input2 + long_to_bytes(prime)[64:]

# print(bytes_to_long(input2)) # look up factordb for factorization
a = 1083337 # one of the factors

io = remote('socket.cryptohack.org', 13392)
io.recvline()

# Send prime for signing
to_send = dict()
to_send['option'] = 'sign'
to_send['prime'] = prime 
io.sendline(json.dumps(to_send).encode())
sig = json.loads(io.recvline().decode())['signature']

# Using the received signature for the other non-prime number input2
to_send['option'] = 'check'
to_send['prime'] = bytes_to_long(input2)
to_send['signature'] = sig
to_send['a'] = a 
io.sendline(json.dumps(to_send).encode())
io.interactive()