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 pp, with a generator gg. gg raised to every power in 0...p1{0...p-1}, taken modp\bmod p, can produce every element of pp. 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 gg.
Alice computes A=gamodpA = g^a\bmod p, aZpa \in Z_p^*.
Bob computes B=gbmodpB = g^b\bmod p, bZpb \in Z_p^*.

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

Then, Alice sends AA to Bob and Bob sends BB to Alice. Alice computes BamodpB^a \bmod p and Bob computes AbmodpA^b \bmod p, which are equal, since gab=gbag^{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 pamodp =pbmodp=0p^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 gg. When g=1g = 1, all powers of gg are 1 as well, so the secret key is always 11. When g=pg = p, as we saw in the previous challenge, powers are all divisible by pp, so the key is always 00. When g=p1g = p-1 is raised to a power, all the terms with pp will be 0modp0 \bmod p, leaving either 11 or 1=p1modp-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 kk that is generally set to 3.

The server stores a verifier for a client that wants to authenticate, v=gxv = g^x, where x=H(saltpassword)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 KK. The server needs the verifier to get KK, while the client needs the password. The server checks that the client’s KK is equal to the server’s computed KK, 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 KK by

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

where AA and BB (aa and bb) are random one time ephemeral keys of the user and server, vv is the verifier, uu is a “scrambling parameter”.

If AA is 00 or a multiple of NN, then S_server=0S\_{server} = 0, and we can authenticate simply by sending K_client=H(0)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,ub, B, u, and saltsalt, then you can precompute the session keys KK 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 pp and qq, and compute n=pqn = pq. Then, we compute the totient, or Euler’s phi function, ϕ(n)=(p1)(q1)\phi(n) = (p-1)(q-1). The public key ee is usually a small number like 3 or 65537 that is coprime to nn, and we derive the private key dd such that de=1modϕ(n)d*e = 1 \bmod \phi(n). This is exactly the definition of a modular inverse, so dd is the modular inverse of ee.

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)=sn+te=1modngcd(n, e) = s\cdot n + t\cdot e = 1 \bmod n

The gcd is 1 because nn and ee are coprime. sn=0modns\cdot n = 0 \bmod n, so we are left with te=1modnt\cdot e = 1 \bmod n, directly giving us t=dt = 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=3e = 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.

C1=M3modN1C2=M3modN2C3=M3modN3\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 CC' that satisfies C=M3modN1N2N3C' = M^3 \bmod N_1N_2N_3, a solution to all the equations. We just need to calculate the CC' and take its cube root, recovering MM.

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

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"