Back

Matasano Crypto Challenges, Set 6

05-21-2017 Crypto

The last of the original crypto challenges… here we go!

Challenge 41 Implement unpadded message recovery oracle

Unpadded RSA is homomorphic, meaning that, if operations like multiplication and addition are carried out on ciphertext, it is as if the same operation were applied to the plaintext.

This can have many useful properties, but also produces some consequences. This challenge is analogous to a “security game” that tests for a property known as IND-CCA2 — indistinguishability under Chosen Ciphertext Attack, where the adversary has access to a decryption oracle. The challenger gives the adversary a ciphertext, and the adversary can ask for the encryption and decryption of anything he wants — except the challenge ciphertext, of course! If the adversary can learn any information about the ciphertext’s plaintext, then he wins the game.

A fully homomorphic scheme fails IND-CCA2 — the adversary can completely recover the message! The adversary can’t ask for the decryption of the challenge ciphertext, but he can ask for the decryption of 2ciphertext, or 3ciphertext, etc. and he knows that the result will be 2plaintext, 3plaintext. Just divide out the scaling factor, and you have the plaintext.

Challenge 42 Bleichenbacher’s e=3 RSA Attack

Another worry with low public exponent is that the message block, when encrypted, will not be large enough to wrap the modulus.

This blog illustrates an attack on the padding scheme PKCS#1 1.5. When signing a message using RSA, the key-holder generates m ^ d mod N, and the recipient uses (N, e) to check that (m ^ d) ^ e = m mod N. But, instead of signing the message, you sign the PKCS1.5 encoding of the message’s HASH.

In PKCS#1 1.5, you take the hash of the message you want to sign, and then you encode it like this:
00 01 FF FF ... FF FF 00 ASN.1 HASH

A faulty PKCS 1.5 padding verifier might not check that all the \xff bytes in the middle are present.

Here’s an example of two faulty verifier versions:

# Find the 00 separator between the padding and the payload
sep_idx = clearsig.index('\x00', 2)

# vulnerable python-rsa version, taking all the remainder of string after asn1 as the hash
signature_hash = clearsig[sep_idx+len(sha1_asn1)+1:]

# weaker version, taking only the next 20 bytes as hash, allowing us to append garbage
signature_hash = clearsig[sep_idx+len(sha1_asn1)+1:sep_idx+len(sha1_asn1)+1+20]

Looking at the weaker version, it’s very simple to construct a message block meeting those parameters.

1
2
3

msg_hash = hashlib.sha1(msg).digest()
garbage = '\x00'*75
forge_sig =  "\x00\x01\xff\x00" + sha1_asn1 + msg_hash + garbage

and then, we simply take the cube root of this forged sig, which undoes the encryption (a cubing).

1 2	(cube_root, exact) = gmpy2.iroot(forge_sig_num, 3) cube_root += 1

The cube root will verify to a valid signature in the faulty padding verifier.

Challenge 43 DSA key recovery from nonce

The DSA signature scheme uses two cyclic groups.

One large cyclic group, $Z_p^{*}$ , has an order of a 1024 bit prime. Another cyclic group, $Z_q^{*}$ , has an order of a 160 bit prime.

The key generation is:

Generate a 1024-bit prime $p$ .
Find a 160-bit prime divisor $q$ of $p-1$ .
Find an element $\alpha$ which generates the subgroup of $p$ with $q$ elements; i.e., $ord(\alpha) = q$ .
Choose a random $d$ with $0 < d < q$ .
Compute $\beta \equiv \alpha^{d}\bmod p$

The keys are now:
pub = $(p,q,\alpha,\beta)$
priv = $(d)$

A DSA signature is generated and verified as follows:

Signing:

Choose a random ephemeral key $0 < k_e < q$
Compute $r \equiv \alpha^{k_e} \bmod q$
Compute $s \equiv (SHA(x) + d\cdot r) k_e^{-1}\bmod q$

Verifying:

Compute aux value $w \equiv s^{-1} \bmod q$
Compute aux value $u_1 \equiv w \cdot SHA(x) \bmod q$
Compute aux value $u_2 \equiv w \cdot r \bmod q$
Compute $v \equiv (\alpha^{u_1}\cdot \beta ^{u_2} \bmod p) \bmod q$
Verify $v \equiv r \bmod q$

def dsa_sign(msg, d):
    k_e = random.randint(0, q)
    r = pow(g, k_e, p) % q
    x = bytes2int(hashlib.sha1(msg).digest())

    s = ((x + d*r)*modinv(q, k_e)) % q

    return (r,s)

def dsa_verify(msg, r, sig, B):
    x = bytes2int(hashlib.sha1(msg).digest())

    #compute aux value w
    s_inv = modinv(q, sig)
    u_1  = s_inv*x % q
    u_2  = s_inv*r % q

    v = (pow(g, u_1, p) * pow(B, u_2, p) % p) % q

    return v == r%q

To recover the private key if we know $k$ , we just solve for $x$ in the equation for $s$ :

d = \frac{s\cdot k_e - SHA(x)}{r} \bmod q

Challenge 44 DSA nonce recovery from repeated nonce

Let’s work out how we can recover the k given a pair of messages that use repeated k.

\begin{aligned} s_1 - s_2 &= (m_1 + dr)k^{-1} - (m_2 + dr)k^{-1} \\\\ &= (m_1 - m_2)k^{-1} \\\\ k &= \frac{m_1 - m_2}{s_1 - s_2} \end{aligned}

Challenge 45 DSA parameter tampering

If we make the generator equal to $p+1$ , then raising it to any power mod p will be 1.

This allows us to forge a signature for any message.

Challenge 46 RSA parity oracle

The idea is to multiply the message by successive powers of 2, and using our parity oracle to check whether the result is even or odd. This allows us to update the upper or lower bound — if odd, the multiplication wrapped the modulus, and we update the lower bound. If even, we didn’t wrap the modulus, and we have a tighter higher bound.

The answer at this StackExchange post allows us to see why. Briefly, when we multiply by 2 and then 4, if we get (even, even) then we haven’t wrapped the modulus, and the message is < N/4. If we get (odd, odd), then we know that we’ve wrapped the modulus twice — only possible if 3/4N < P < N. Make sure you see why: the result of the first doubling will be between 1/2N and N, so the second doubling will again wrap the modulus.

Do this iteratively, until you tighten the bounds enough to get every byte of the message, which will be discovered byte-by-byte.

Challenge 47-48 Bleichenbacher’s attack

Bleichenbacher’s attack shows how we can break RSA+PKCS1 padding using an adaptive chosen-ciphertext attack and a PKCS oracle. The PKCS oracle will tell you whether a ciphertext decrypts to a plaintext with the following structure:

The first two bytes are \x00\x02
There is at least one null byte after the first null byte

Here’s the attack — the description in the original paper is good:

The attacker tries to find small values $s_i$ for which the ciphertext $c_0(s_i)^e \bmod n$ is PKCS conforming. For each successful value for $s_i$ , the attacker computes, using previous knowledge about $m_0$ , a set of intervals that must contain $m_0$ … The third phase starts when only one interval remains. Then, the attacker has sufficient information about $m_0$ to choose $s_i$ such that $c_0(s_i)^e \bmod n$ is much more likely to be PKCS conforming than is a randomly chosen message. The size of $s_i$ is increased gradually, narrowing the possible range of $m_0$ until only one possible value remains.

The paper splits this up into four steps, which we can each implement as separate functions directly. The first step, blinding, is not really that important — it asks you to choose random integers $s_0$ until you find one s.t. $c(s_0)^e \bmod n$ is PKCS-conforming. But, you can just make sure that $c$ is already PKCS-conforming (by PKCS-padding the corresponding plaintext $p$ ), so $s_0$ is trivially 1.

Most difficulties you might encounter when implementing this attack are with regards to the bounds. You have to be very careful about correctly handling all the $\leq$ and interval bounds.

Other things to note when reading the four steps to implement in the paper:

As the prompt says, “a PKCS#1v1.5 conformant plaintext, one that starts with 00:02, must be a number between 02:00:00…00 and 02:FF:FF…FF — in other words, 2B and 3B-1, where B is the bit size of the modulus minus the first 16 bits”. You must see why this is true.
In step 2c, you just need to find one next $s_i$ . Iterate over each $r_i$ , and then iterate over all $s_i$ ’s possible for that $r_i$ .
In step 3, the most important step, you narrow the intervals in which the message can exist. Each interval is a pair $(a,b)$ , and you iterate over all $r$ for each $(a,b)$ pair.

Finally, once we have just one interval with one value $a$ left, we’re done! We can recover the original plaintext from the answer $a \equiv c\cdot s_0 \bmod n$ and $m \equiv a\cdot s_0^{-1} \bmod n$ .

if len(m_intervals) == 1 and m_intervals[0][0] == m_intervals[0][1]:
    # We're done!
    a = m_intervals[0][0]
    m = a * modinv(n, 1)
    return m

1	assert found_msg == b"kick it, CC"