I recently participated in the 33c3 ctf competition and tried to solve the beeblebrox challenge but could not crack it and nobody posted a writeup/exploit of it so far so I want to get help solving it (the competition is long over). You can get the server code here.
The server works the following way, when connected we get a conversation going like this:
Hi Baby!
Ever met someone from another planet? ;)
I certainly have never met a hot babe like you out there in this little galaxy!
I'm actually the president of the universe, you know?
Want an autograph? (mDi9iaiHMy)
The given challenge takes a few seconds to a few minutes on my machine but is trivial to calculate.
Next we can specify a message (and a counter) and get it signed for us. The end goal is to get the following message signed:
I, Zaphod Beeblebrox, hereby resign from my office as president of the Galaxy.
But damn it, Zaphod is not stupid and refused to sign it ;)
Looking at the crypto, we are given MODULUS and S while P and Q are read from files hidden from us:
MODULUS = 16536507737844787892641865661863462397631522150212024091004887310964200827020178668239882145253630803151168956393779505928808506196120351189499349932786784708370138096658243543880715379147242259129181920278789039223128954389992858894196591733488967188941263924281855801225333337971369346979277183346095695839072573619497479683662969453719477093511680505106353869706149218300987922266699186873224155102741256320112045419277230096733452241250195932716682446395562027663309040452928460169789196285753228735312068600940483519875428506460333422009758551679944423660319026521184358407797626088473071231220477237579974133813
S = 2279870349089594676078131957223427526372940435342871764510345335207700176127662830938770929147412047169033459649625173227912122654011065802421796926972585798820409017163625434862756489760448381608543257498933257519457833349391617168881001250072857294234191917642557763462668502951731492599248590640073798156146984110885838926659848552808727770775032147602500322865941084978965993286193260974797123500037313973609102107825877355293422553505328529637538623308810977388182025133271286463800018303412599528683244178480216737543334821269172129558292624827118889631230859505678242114445252685966124989815656101539186906614
P = int(open("P.txt", "r").read())
Q = int(open("Q.txt", "r").read())
# Note: P and Q are strong primes
PHI = (P-1)*(Q-1)
# SANITY CHECKS
assert(MODULUS == P * Q)
assert(S < MODULUS)
The obvious question is what S is supposted to be. It turns out S is the text which is always signed while the "message" we can give the server is used to determine the public & private key together with the counter.
Sign Code:
h = hash(msg, ctr) # public key
if msg == TARGET_MSG or not is_prime(h, 128):
self.send_msg("Sorry, I can't sign that.")
else:
exponent = modinv(h, PHI) # private key
signature = pow(S, exponent, MODULUS)
self.send_msg("Here you are, darling!")
self.send_msg(encode(signature, 256))
Verify Code:
h = hash(TARGET_MSG, ctr) # public key
if msg == TARGET_MSG and pow(signature, h, MODULUS) == S and is_prime(h, 128):
self.send_msg("Okay, I give up :(")
self.send_msg("Here's your flag: " + FLAG)
else:
self.send_msg("No.")
I looked through all the common rsa attacks which might be useful but as far as I can see neither the Common Modulus attack can be used (because we can get no information about the variable exponent which holds the private key) nor can Blinding be used because the input is hashed and the same message is always signed so tricking the server into signing some known values is impossible. Other attacks rely on small exponents which could possibly be done by choosing cnt so h is small, maybe even 3 which would enable some attacks but it seems unlikely to succeed.
The only other clue I have about solving this challange is the oracle given by the following line:
exponent = modinv(h, PHI)
This will throw an exception when h and PHI have no gcd != 1 so we get a "Goodbye!" response instead of "Here you are, darling!" + signature.
This allows us to test for prime factors of PHI by only asking with a cnt value which produces a known h which we for example pick so that is has a prime factor of 181 and satisfies is_prime. That way I found out that 181 is a prime factor of PHI because the exception is thrown.
But because we need to send a proof of work to try and this takes quite a while we didn't find out another one yet. If I understand everything correctly if we were to know all prime factors of PHI we would know PHI which would make the challenge trivial to solve.
Any ideas or tips on how to proceed?