Matasano Crypto Challenges, Set 5

This set was surprisingly easy, actually. The book Understanding Cryptography by Paar & Pelzl is an excellent intro to the basic maths needed for crypto — namely, the group theory and number theory necessary for RSA and Diffie-Hellman.

Let’s dive in!

Challenge 33 Implement Diffie-Hellman

Diffie-Hellman is a remarkably simple algorithm for two parties to jointly compute a shared secret key that may be used, for example, as a key for symmetric encryption.

Alice and Bob agree on an integer group of prime $p$, with a generator $g$. $g$ raised to every power in ${0...p-1}$, taken $\bmod p$, can produce every element of $p$. Hence, it is called a “generator” of the group.

So, Alice and Bob each choose a random group element and use that as a power of $g$.
Alice computes $A = g^a\bmod p$, $a \in Z_p^*$.
Bob computes $B = g^b\bmod p$, $b \in Z_p^*$.

What’s important to Diffie-Hellman is that, given $A$ and $g$, one cannot easily compute $a$. This is called the Discrete Log Problem. The value $A$ looks like a totally random element of $Z_p^*$!

Then, Alice sends $A$ to Bob and Bob sends $B$ to Alice. Alice computes $B^a \bmod p$ and Bob computes $A^b \bmod p$, which are equal, since $g^{ab} = g^{ba}$.

Implementing this is easy in python with the built-in pow function. However, for educational purposes, I wrote the modexp function for fast modular exponentiation.

The modexp function is taken from Paar and Pelzl. The exponent is converted to binary, and for each bit, we square the result. Also, if the bit is 1, we multiply the result by the base.

The final algorithm is

# Create secret keys, random values mod p
a = random.randint(0, p)
A = modexp(g, a, p)
b = random.randint(0, p)
B = modexp(g, b, p)

shared_key_a = modexp(A, b, p)

Challenge 34 Implement a MITM key-fixing attack on Diffie-Hellman with parameter injection

Again, pwntools to the rescue!

This challenge requires some client/server sockets, which I use the pwntools tubes library for.

At a high level, the challenge demonstrates that, if an attacker were able to sit in the middle of a DH key exchange session and modify the messages being passed, he can control the key and decrpyt all the traffic.

The client sends (p, g, A) to the server, and the server responds with B. If you recall, p and g are the public agreed-upon parameters for the group prime and generator. A is the Client’s piece of the secret key, and B is the Server’s piece.

If an attacker replaces A and B with p, then both Client and Server will compute the key to be $p^a \bmod p \ = p^b \bmod p = 0$. 0 is then hashed and used as the symmetric key for AES-encrypting messages, so the attacker can decrypt all the communications.

Challenge 35 Implement DH with negotiated groups, and break with malicious “g” parameters

Let’s see what happens when we choose different values for the generator $g$. When $g = 1$, all powers of $g$ are 1 as well, so the secret key is always $1$. When $g = p$, as we saw in the previous challenge, powers are all divisible by $p$, so the key is always $0$. When $g = p-1$ is raised to a power, all the terms with $p$ will be $0 \bmod p$, leaving either $1$ or $-1 = p-1 \bmod p$.

Challenge 36 Implement Secure Remote Password (SRP)

Secure Remote Password is really cool. It is a form of authentication in which the client does not need to reveal her password — a form of zero-knowledge.

The setup involves some large primes, and the security relies on discrete log, as before. A large prime modulus N is chosen, along with a generator g and a magic parameter $k$ that is generally set to 3.

The server stores a verifier for a client that wants to authenticate, $v = g^x$, where $x = H(salt|password)$. A salt is a random value used to safeguard the password hash from being easily identifiable in a hash lookup rainbow table.

After exchanging some parameters, both client and server produce a session key $K$. The server needs the verifier to get $K$, while the client needs the password. The server checks that the client’s $K$ is equal to the server’s computed $K$, and if so, successfully authenticates the client.

The full protocol can be seen on Wikipedia.

Challenge 37 Break SRP with a zero key

Some buggy implementations of SRP allow authentication without knowing the password, as this challenge illustrates.

The server produces the session key $K$ by

$$\begin{aligned} S\_{server} = (A\cdot v^u)^b \bmod N \\\\ K\_{server} = H(S) \end{aligned}$$

where $A$ and $B$ ($a$ and $b$) are random one time ephemeral keys of the user and server, $v$ is the verifier, $u$ is a “scrambling parameter”.

If $A$ is $0$ or a multiple of $N$, then $S\_{server} = 0$, and we can authenticate simply by sending $K\_{client} = H(0)$ without knowing the password!

Challenge 38 Offline dictionary attack on simplified SRP

This problem isn’t really that interesting, so I skipped it. But here’s the lowdown: if you get MITM on SRP and thus can control the values for some parameters, $b, B, u$, and $salt$, then you can precompute the session keys $K$ for common dictionary words. Doing the bruteforce cracking is not really that interesting, though.

Challenge 39 Implement RSA

The security of RSA is not based on the discrete log problem, but rather on the difficulty of factoring large numbers.

We choose two large primes $p$ and $q$, and compute $n = pq$. Then, we compute the totient, or Euler’s phi function, $\phi(n) = (p-1)(q-1)$. The public key $e$ is usually a small number like 3 or 65537 that is coprime to $n$, and we derive the private key $d$ such that $d*e = 1 \bmod \phi(n)$. This is exactly the definition of a modular inverse, so $d$ is the modular inverse of $e$.

I implement the Extended Euclidean Algorithm to find the modular inverse of a number, using the algorithm in Pelzl.

The EEA will compute the coefficients of the equation

$$gcd(n, e) = s\cdot n + t\cdot e = 1 \bmod n$$

The gcd is 1 because $n$ and $e$ are coprime. $s\cdot n = 0 \bmod n$, so we are left with $t\cdot e = 1 \bmod n$, directly giving us $t = d$.

Here’s my EEA:

def egcd(r0, r1):
   '''
   takes the modulus in r0, and the element in r1
   returns tuple of (gcd, coefficient 1, coefficient 2) s.t. s0*r0 + t0*r1 = gcd
   if first value is a modulus, gcd = 1 and t0 is modinv of r1
   '''
   old_r0, old_r1 = r0, r1
   s0, s1 = 1, 0
   t0, t1 = 0, 1

   while r1 != 0:
       remainder = r0%r1
       q = (r0-remainder)/r1

       assert q*r1 + remainder == r0

       r0, r1 = r1, remainder

       new_s = s0 - q*s1
       new_t = t0 - q*t1

       assert new_s*old_r0 + new_t*old_r1 == remainder

       s0, s1 = s1, new_s
       t0, t1 = t1, new_t

   return (r0, s0, t0)

and the driver function that returns the modular inverse:

def modinv(mod, a):
    (gcd, a, b) = egcd(mod, a)

    if gcd != 1:
        return None
    return b % mod

With the modinv function, the rest of RSA is straightforward.

Challenge 40 E=3 RSA Broadcast Attack

20 Years of Attacks on RSA describes some great attacks on RSA that come in CTFs as well as Matasano challenges.

One of the simplest is Hastad’s broadcast attack, which allows us to recover a message that has been encrypted with RSA pubkeys that are very small, such as $e = 3$.

The Chinese Remainder Theorem is the key to this problem.

As the paper describes, we only need the same message encrypted with the same public key (but different moduli) to recover the plaintext.

$$\begin{aligned} C_1 = M^3 \bmod N_1 \\\\ C_2 = M^3 \bmod N_2 \\\\ C_3 = M^3 \bmod N_3 \\\\ \end{aligned}$$

The CRT tells us that there exists some value $C'$ that satisfies $C' = M^3 \bmod N_1N_2N_3$, a solution to all the equations. We just need to calculate the $C'$ and take its cube root, recovering $M$.

The challenge just gives you the CRT equation to solve for $C'$.

m_s_1 = N2*N3
y1 = ctext1 * m_s_1 * modinv(N1, m_s_1)

m_s_2 = N1*N3
y2 = ctext2 * m_s_2 * modinv(N2, m_s_2)

m_s_3 = N2*N1
y3 = ctext3 * m_s_3 * modinv(N3, m_s_3)

mod_prod = N1*N2*N3

result = (y1 + y2 + y3) % mod_prod

Python’s cube root (**(1/3.)) is not entirely precise, so I use the gmpy multiple-precision library.

cube_root = gmpy.mpz(result).root(3)[0].digits()
decrypted_text = binascii.unhexlify(str(hex(int(cube_root))[2:]))

assert decrypted_text == "can't touch this"