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$ and $n_2$ such that $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.
Clearly the scheme given is not a hash function, in the sense that it is very easy to invert the function to obtain the original message. Hence, with any arbitrary hash, we can easily construct a message with that hash by inverting the operation.
Python Implementation:
from pwn import * import json BLOCK_SIZE = 32 # Nothing up my sleeve numbers (ref: Dual_EC_DRBG P-256 coordinates) W = [0x6b17d1f2, 0xe12c4247, 0xf8bce6e5, 0x63a440f2, 0x77037d81, 0x2deb33a0, 0xf4a13945, 0xd898c296] X = [0x4fe342e2, 0xfe1a7f9b, 0x8ee7eb4a, 0x7c0f9e16, 0x2bce3357, 0x6b315ece, 0xcbb64068, 0x37bf51f5] Y = [0xc97445f4, 0x5cdef9f0, 0xd3e05e1e, 0x585fc297, 0x235b82b5, 0xbe8ff3ef, 0xca67c598, 0x52018192] Z = [0xb28ef557, 0xba31dfcb, 0xdd21ac46, 0xe2a91e3c, 0x304f44cb, 0x87058ada, 0x2cb81515, 0x1e610046] # Lets work with bytes instead!
We will exploit the fact that numpy’s array class is int64. So, what we’re gonna do is basically generate random passwords, with digits, lowercase and uppercase letters and hope that one of these passwords have both sum and product (overflowed) prime.
For this, we need password with three restrictions:
It is large enough for the overflow to occur All the digits are odd (if we have any even digit, the product will be even, and therefore not prime) The length must be odd, so the sum will also be odd, as prime numbers should be odd numbers only I guess the last criteria is luck.
The vulnerability of the code (and yes, as somewhat hinted at by the challenge description), is these two lines:
nonce = sha1(long_to_bytes(privkey.secret_multiplier) + hsh).digest() sig = privkey.sign(bytes_to_long(hsh), bytes_to_long(nonce)) sha1 produces a digest of only 160 bits (20 bytes). This is a big problem as it is required that the nonce is a number randomly generated in the range between 1 and the order of the elliptic curve. In the above code, the hash generated by sha1 is only 160 bits long.
There is a bug in the implementation, specifically
def recover_x(self, xbit, y): xsqr = (y**2 - 1)*inverse(1 + self.d*y**2, self.p) % self.p x = pow(xsqr, (self.p + 1)//4, self.p) if x**2 == xsqr : ... return 0 the function recover_x will always return 0, as the check is not done on modulo $p$. The challenge is now straightforward as the base point has a x-coordinate of 0. Indeed, and referencing from this paper, the scalar multiplication on Edwards curve of a point $0, y$ is: