# 33C3 CTF 2016 – beeblebrox (Crypto 350)

nc 78.46.224.72 2048

files

Summary: factorization-based attack on a signature method

In this challenge we have access to a signature oracle, who does not sign a special message. Our goal is to obtain a valid signature for that special message.

Code for the oracle:

... # msg and ctr are sent by the client ctr = decode(ctr, 0, 2**32) # allowed range h = hash(msg, ctr) if msg == TARGET_MSG or not is_prime(h, 128): self.send_msg("Sorry, I can't sign that.") else: exponent = modinv(h, PHI) signature = pow(S, exponent, MODULUS) self.send_msg("Here you are, darling!") self.send_msg(encode(signature, 256)) ...

And for the challenge:

ctr = decode(ctr, 0, 2**32) signature = decode(signature, 2, MODULUS) h = hash(TARGET_MSG, ctr) 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.")

So far so good, but let’s look at the is_prime function:

def is_prime(n, c): if n <= 1: return False if n == 2 or n == 3: return True if n % 2 == 0: return False for _ in range(c): a = random.randrange(1, n) if not pow(a, n-1, n) != 1: return False return True

It is just a Fermat primality test! We could try to use Carmichael numbers, but hardly any hash of the TARGET_MSG with one of the $2^{32}$ nonces will be a Carmichael number.. Wait.. Look at this line: if not pow(a, n-1, n) != 1:. The condition is inverted! The not should not be there!

It turns out that is_prime accepts only odd composite numbers (not equal to 3). How can we use it?

The signatures look like this:

$sig(msg) = S^{1/h(msg,nonce)} \mod N$.

Since the primality test is wrong, we want to use factorizations. Indeed, if we know $S^{1/(kp)}$ we can compute

$(S^{1/(kp)})^k \mod N = S^{1/p} \mod N$.

In such a way we can collect $S^{1/p}$ for many small primes and hope that $h(msg,nonce)$ will be smooth, that is will contain only those small primes in its factorization.

But how do we combine signatures for two primes? That’s slightly tricker. We don’t have much options. Let’s try to multiply the signatures:

$S^{1/p} S^{1/q} = S^{\frac{p+q}{pq}}$.

Not the $S^{1/(pq)}$ that we wanted.. But can we change $p+q$ to 1 somehow? Indeed, let’s generalize our multiplication:

$(S^{1/p})^a (S^{b/q})^b = S^{a/p} S^{b/q} = S^{\frac{bp+aq}{pq}}$.

If $p$ and $q$ are coprime, then we can use the Extended Euclidian Algorithm to find parameters $a,b$ such that $bp+aq=1$ and we are done!

#### Data

We found that H = hash(TARGET_MSG, nonce=35856) has the following factorization:

sage: factor(15430531282988074152696358566534774123) 3 * 11 * 19 * 137 * 173 * 337 * 7841 * 107377 * 206597 * 3446693 * 5139341

And hash(“blah”, nonce) gives us all these prime factors for the following nonces:

nonces = [ 464628494, # 3 513958308, # 11 584146771, # 19 501252653, # 137 836242304, # 173 119438940, # 337 242937565, # 7841 853304146, # 107377 642736722, # 206597 836398440, # 3446693 54720172 , # 5139341 ]

After implementing and running the attack, we get the flag: 33C3_DONT_USE_BRUTE_FORCE_AGAINST_POLITICIANS