10
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ It's not RSA. Here, it uses the hashed message as the exponent; if hashed message is h, it computes the h-root of a fixed value "S". $\endgroup$ – Thomas Pornin Jan 2 '17 at 20:08
  • 1
    $\begingroup$ Weird. Isn't 181 dividing phi a direct contradiction of the strong prime comment? $\endgroup$ – CodesInChaos Jan 2 '17 at 20:11
  • $\begingroup$ I also at first did not believe this to be rsa, but as far as I can tell c = m ^ e mod N and signature = pow(S, exponent, MODULUS) which means S is m and exponent is e. $\endgroup$ – arturh Jan 2 '17 at 20:11
  • $\begingroup$ Albeit formulated differently, this is essentially the same as "Here's a protocol I've designed; can you find flaws in it?", so voting to close as off-topic. $\endgroup$ – fkraiem Jan 2 '17 at 20:12
  • $\begingroup$ Also, how did you find something hashing to 181? That should be infeasible for good hashes. So perhapa ypu can pull off a colliaion attaxk. $\endgroup$ – CodesInChaos Jan 2 '17 at 20:18
11
$\begingroup$

The challenge asks you to break the Gennaro-Halevi-Rabin signature scheme with a broken primality test.

Lines 56 and 57 of the server code are

            if not pow(a, n-1, n) != 1:
                    return False

but the Fermat test should return "composite" if $a^{n-1}\bmod n$ does not equal 1. Thus, you can get the server to sign messages for you whose hash is not prime; in fact, almost all odd composite numbers are wrongly categorized as "prime" by that code.

Now the key to the solution of the challenge is described on page 93 of the paper Security Analysis of the Gennaro-Halevi-Rabin Signature Scheme:

An opponent willing to forge a signature without solving the strong-RSA problem can try to find messages $m,m_1,\dots,m_r$ such that $H(m)$ divides the least common multiple of $H(m_1),\dots,H(m_r)$. In this case, we say that a division-collision for $H$ was exhibited. Using Euclid's algorithm the opponent can obtain $a_1,\dots,a_r,k$ such that: $$ \frac{a_1}{H(m_1)}+\dots+\frac{a_r}{H(m_r)} = \frac1{\operatorname{lcm}(H(m_1),\dots,H(m_r))}$$ and forge the signature $\sigma$ of $m$ from the signatures $\sigma_i$ of messages $m_i$ by: $$\sigma = \Big(\prod_{i=1}^r\sigma_i^{a_i}\Big)^k\bmod n$$

In the context of the challenge, this yields the following algorithm to forge a signature for a given message $\mathtt{target}$:

  1. Using brute force, find a counter $\mathtt{ctr}$ such that $T:=\mathtt{hash}(\mathtt{target},\mathtt{ctr})$ is odd and smooth, i.e., only has small prime factors $p_1,\dots,p_r$. For the sake of simplicity (and since it is feasible to find such $T$), we shall assume that $T$ is square-free, i.e., its prime divisors are distinct, but that is not necessary in general.
  2. For each of the prime factors $p_i$ of $T$, find (again by brute force) a message $m_i$ and counter $c_i$ such that $h_i:=\mathtt{hash}(m_i, c_i)$ is a multiple of $p_i$. Sending this to the signing oracle gives us back the value $\sigma_i:=\mathtt{S}^{h_i^{-1}\bmod\varphi(n)}$. Write $e_i:=h_i^{-1}\bmod\varphi(n)$.
  3. Write $\bar h_i$ for the product of all $h_j$ except $h_i$. Euclid's algorithm (or, more abstractly, Bézout's lemma) gives us coefficients $a_i\in\mathbb Z$ such that $$ \sum_i a_i\bar h_i = \gcd(\bar h_1,\dots,\bar h_r). $$

    Note that this equation implies (via dividing both sides by the product of all $h_i$) that the congruence $$ \sum_{i=1}^r a_ie_i \equiv \frac1{\operatorname{lcm}(h_1,\dots,h_r)} $$ holds modulo $\varphi(n)$.

  4. By construction, $\operatorname{lcm}(h_1,\dots,h_r)$ is a multiple of $T$; let $k:=\operatorname{lcm}(h_1,\dots,h_r)/T$. Thus, $$ \sum_{i=1}^r a_ie_i \equiv \frac1{kT} \pmod{\varphi(n)} $$
  5. Finally, compute the value $$ \sigma := \Big(\prod_{i=1}^r \sigma_i^{a_i}\Big)^k\bmod n \text. $$ It is a forged signature for $\mathtt{target}$ with the counter $\mathtt{ctr}$.
    Proof. (All congruences modulo $n$.) $$ \sigma^T \equiv \Big(\prod_{i=1}^r \sigma_i^{a_i}\Big)^{kT} \equiv \Big(\prod_{i=1}^r \mathtt{S}^{a_ie_i}\Big)^{kT} \equiv \big(\mathtt{S}^{\sum_{i=1}^ra_ie_i}\big)^{kT} \equiv \mathtt{S}^{kT\cdot\sum_{i=1}^ra_ie_i} \equiv \mathtt{S} \text. $$
$\endgroup$
  • 2
    $\begingroup$ Thank you very much, this will take me a while to work through, I will give it another try armed with all this math :) $\endgroup$ – arturh Jan 2 '17 at 21:32

Not the answer you're looking for? Browse other questions tagged or ask your own question.