This was an enjoyable challenge. There is a python server.py that has a hard-coded target message which is known to you. The goal of the challenge is to provide a valid signature to the message, given
The server generates a 2048 bit RSA private key on startup, and upon connect it loops infinitely giving you three options:
[1] Sign[2] Verify[3] ExitThe first option will sign any message other than target message and provide you with two intermediate values used during the funky signature process, and the second option will give you the flag if you are able to come up with a signature for the target message.
My solution in raw uncommented code is available at attack.py. A weakness is exploited in the intermediate parameters that allows for the other factor q to be calculated, which gives us the full RSA private key and allows us to sign whatever messages we want.
Here is the signature logic:
msg = bytes_to_long(input('Message: ').encode())
if msg == message:
print('Invalid message!')
continue
n1 = [randint(0,11) for _ in range(29)]
n2 = [randint(0,2**(max(p.bit_length(),q.bit_length())-11)-1) for _ in range(29)]
a = sum(n1[i]*n2[i] for i in range(29))
enc = [pow(msg,i,n) for i in n2]
P = np.prod(list(map(lambda x,y: pow(x,y,p),enc,n1)))
Q = np.prod(list(map(lambda x,y: pow(x,y,q),enc,n1)))
b = inverse(e,(p-1)*(q-1))-a
sig1 = b%(p-1)+randint(0,q-2)*(p-1)
sig2 = b%(q-1)+randint(0,p-2)*(q-1)
print(sig1,sig2)
sp = pow(msg,sig1,n)*P%p
sq = pow(msg,sig2,n)*Q%q
s = (q*inverse(q,p)*sp + p*inverse(p,q)*sq) % n
print(s)
print("Signed!")
As you can see, there is a lot of strange math going on but at the end of the day a signature is obtained which is going to be the same value as any other signature $m^d \mod n$. I tried a number of different approaches, including passing in specially crafted inputs which cause strange behaviour but it turned out to be a pretty simple trick.
All that you need to know for my solution is that $a, r, s$ are random numbers smaller than $p$ which changes for every signature (assuming $p > q$ which is right half the time). The two special values given to us are the following, where $d$ is the private exponent:
\begin{align} x &= d-a + r*(p-1)\\ y &= d-a + s*(q-1) \end{align}The first exploitable weaknesses is the fact that given $x, p$ and $e$ we can calculate $a = e^{-1} - x \mod (p-1)$. This works because $d \equiv e^{-1} \mod (p-1)$ and $a < p$.
The second exploitable weakness is that knowing $a$ we can remove the random factor from $y$ and obtain $q$ through the greatest common denominator $\gcd(y_2'-y_1', y_3'-y_2')$ with $y_i'$ defined as follows:
\begin{align} y_i' &= y_i + a_i\\ y_i' &= d - a_i + s*(q-1) + a_i\\ y_i' &= d + s_i*(q-1)\\ \end{align}This works because by removing the randomness of $a$, the difference between $y_i$ and $y_j$ is always going to be a multiple of $q-1$.
\begin{align} y_i' - y_j' &= d + s_i*(q-1) - d - s_j*(q-1)\\ y_i' - y_j' &= s_i*(q-1) - s_j*(q-1)\\ y_i' - y_j' &= (s_i - s_j)*(q-1) \end{align}flag{random_flags_are_secure-2504b7e69c65676367aef1d9658821030011f8968a640b504d320846ab5d5029b}