33C3 CTF 2016 – beeblebrox (Crypto 350)

Make bad politicians resign!

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