MMACTF 2015 1st: Signer and Verifier

We are given two ports on a server, Sign and Verify. Sign will sign an integer using the RSA signature scheme and Verify asks us to sign an integer providing the the public modulus and exponent. Sign it correctly and the server will give us the flag. The tricky part is that Sign won’t sign any of the messages given to us by Verify, so we need to trick it into signing our message using an RSA blinding attack.

Blind Signatures

Blind signatures are signatures generated when the signer is supposed unaware of the contents of what they are signing.

To accomplish RSA blind signatures, first a random number is chosen that is relatively prime to . This is the blinding factor. The blinded message is then calculated by:

where is the original message, is the public exponent, and is the public modulus.

Then the blinded signature, is calcuated by the signer:

Now the unblinded-signature can be calculated knowing :

The reason this works is because the signer is really just decrypting the message with their secret key, so we can say:

Now the RSA decryption gives us that making our equation:

and since the we now are left with:

which brings us the equation from earlier:

Implementing the Attack

While we can do all the math by hand in Sage, the server gives us a new number to sign each time we connect and also has a timer running. This means that we need to write a program to connect and calculate the signature for us, so I again opted to use a (messy) Sage Script.

The Code:
#!/usr/bin/env sage -python2
import socket
from sage.all import *

#Sign a value
def sign(msg):
    sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    sock.connect(('cry1.chal.mmactf.link', 44815))
    sock.sendall(str(msg)+'\r\n')
    resp = sock.recv(4096).strip('\n')
    sock.close()
    return long(resp)

#Blinding Factor
r = 3
#Public Exponent
e = 65537
#Public Modulus
N = long(167891001700388890587843249700549749388526432049480469518286617353920544258774519927209158925778143308323065254691520342763823691453238628056767074647261280532853686188135635704146982794597383205258532849509382400026732518927013916395873932058316105952437693180982367272310066869071042063581536335953290566509)

#Get the Encrypted Message
pipe = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
pipe.connect(('cry1.chal.mmactf.link', 44816))
M = pipe.recv(4096).strip('\n')
M = long(M[M.index('!')+1:])
print "Get the signature on: " + str(M)

#M' = M*r^e mod(N)
mBlinded = Mod(r^e*M,N)

#S' = M'^d mod (N)
sBlinded = sign(mBlinded)

#S = (S' / r) mod (N)
S = (sBlinded / r) % N

#Capture the flag
pipe.sendall(str(S)+'\r\n')
flag = pipe.recv(4096).strip('\n')
pipe.close()
print "\n\nFLAG: "+flag

Running this prevents us with the flag:

MMA{homomorphic_challengers}