Class 15: Public-Key Revolution (Diffie-Hellman Key Exchange)

Overview: In this part we introduce the idea of asymmetric encryption schemes in which the receiver has a public key and a private key. The public information allows anyone to encrypt a message that the receiver can decrypt using their symmetric key. This is very different than using the same key to encrypt and decrypt.

So it's time to shift into a new mode of thinking. We'll end up talking about computational number theory and some beautiful mathematics. For now, let's jump in and start doing it.

First of all you'll notice that every one of our encryption schemes so far has had a shared secret. That is, some key which both encrypter and decrypter need for the scheme to succeed. How would that secret key be shared with your partner? Briefcases and spies have done the job before, but we're in the internet age.

Spys can do this job

Today I want to look at a method for sharing a private key over a public channel (our class chat for example). I imagine yelling out this information to the whole room and letting our partners work with us to get a secret shared.

A full conversation involves having four keys, a public and private pair for both Alice (sender) and Bob (recipient).

We won't yet understand every step of this process, but we'll have a good place to start our conversations.

The hard problem

Every public-key scheme is going to involve a "hard problem" that would crack the scheme. Ideally the designer of the scheme has set it up so that either your messages are secure OR the attackers have made a practical solution to a very tough computer science / math problem.

The first hard problem we face is called the Discrete Log problem. Which is this: Given \(A = g^{\alpha} \pmod{p}\) and \(g\) and \(p\) find \(\alpha\).

Discrete Log Starter: Suppose \(22 = 3^{x} \pmod{31}\). Find \(x\).

Discrete Log Thinking: If you were to solve a larger version, can you tackle it any easier than trying every value of \(x\)?

Overview: This part shows the details of publicly exchanging a private key using the Diffie-Hellman Key Exchange. The world uses this idea to setup all of our HTTPS connections. Once that key is exchanged we just switch to symmetric-key encryption with AES. So the public-key part is mostly just setting up the crypto we already know. Let's practice the transition.

This idea is important enough that we should try several approaches. Pay attention to which parts are secret and which parts are public.

1) Generate a public triplet

As the initiator (ALICE) we follow these steps to generate a discrete log problem and an answer (which we keep secret).

Generate a "Strong" prime (script below) \(p\)
Pick a "base" which can really just be the number \(g = 2\)
Generate a PRIVATE random number, \(a\), which shares no factors with \(p-1\) (recipe below)
Calculate the public exponent: \(A := g^a \pmod{p} \).
Publish your public key (triplet): \(p, g, A\) (DO NOT PUBLISH \(a\)!)

Generate a Public Key Triplet: also store the private key somewhere. Publish your triplet in the chat. You'll have to generate several private keys until the GCD is 1, make a while loop there.

The security of these scheme rests on an attacker's inability to figure out \(a\) given \(p, g, A\).

2) BOB's job: the recipient's role

Once Bob has your public-key triplet he can generate a new secret that can be publicly shared with ALICE.

Bob takes in \(p\), \(g\), and \(A\). Now Bob has to also generate a secret:

Generate a PRIVATE random number, \(b\), which shares no factors with \(p-1\).
Calculate the PUBLIC number \(B = g^b \pmod{p} \).
Calculate the PRIVATE shared secret \(K = A^b \pmod{p} \), note that this is really the number \(g^{ab} \pmod{p} \).
Publish to Alice: \(B\).

Be BOB: Take in the triplet \( (p, g, A) = (101, 2, 6) \) and generate a response \(B\) and a shared secret. (Little \(a\) was 70 if you want to confirm that you've got the mechanics down.)

3) Our prize: a shared secret

ALICE receives \(B\) (she doesn't know \(b\))
ALICE computes \(K = (B)^{a} \pmod{p} \) which BOB already knows.
ALICE and BOB rejoice in their sneaky cleverness to have shouted information and secretly communicated.

The secret sauce was that anyone can see \(A = g^a \pmod{p}\) and not know \(a\), anyone can see \(B = g^b \pmod{p}\) and now know \(b\). Now only ALICE can compute \(B^a \pmod{p}\) and only BOB can compute \(A^b \pmod{p}\) since only ALICE knows \(a\) and only BOB knows \(b\). But \(B^a = (g^b)^a = g^{ab} \pmod{p} \) and \(A^b = (g^a)^b = g^{ab} \pmod{p} \).

Do a full exchange: Pretend to be Alice and Bob and generate a shared key. You could also do a swap in the chat channels.

CTF Problem for DHKE:

flag.php

Overview: In this part we accomplish two things. Get the idea across that after a key exchange we can switch to AES. The other goal is to practice full strength Key swaps using real tools. Let's do it!

Preface: Use private key

When you've done this key exchange you end up with a shared secret which is likely to have more bits than the typical AES secret key (we need more bits for public-key security than private-key security).

So at this stage I suggest you switch to AES in an appropriate mode (like CTR). For converting your shared secret into the key for AES you can use a hashing algorithm on the resulting bytes.

Generating Safe Primes

OK, so we've done some amateur DHKE, some basic number theory, and we're finally ready to explore the way this is really done.

Analysis question: We know that the hard problem is reversing \(g^{x} \pmod{p}\). If you were choosing the \(g\) to use would you rather have \(|g| = p-1\) or \(|g| = 2\)?

Create a generator: If I gave you a prime \(p\) and asked you to give me a generator of the multiplicative group \(\mathbb{Z}_p^{*}\) what would you do?

In the last part we used a library to generate a safe prime. Here is a look under the hood.

Safe Prime Explore: the answer that is done most in practice is to generate a safe prime, that is, \(p = 2\cdot q + 1\) where \(q\) is also prime. How would you generate a safe prime?

So the big idea is that if we find a 'safe prime' then we can find a generator with great ease. This is because there are very few subgroups in \(\mathbb{Z}_p^{*}\) just a subgroup of order 2, order \(q\), and order \(p-1\). That way if we just avoid the small subgroup we know we've got a brute-force space of at least size \(q\)!

Here is a safe-prime generating snippet:

SAGE Run it: That is some SAGE code, so run it at cloud.sagemath.com and see how long it takes when bits is small and now try it with bits at 1024 (the smallest "safe" prime size for DH). WARNING: be prepared to stop the process!

Working with SSL parameters

Let's learn how to leave it to the professionals:

OpenSSL: in a cloud9 run the following to generate a DH strength prime and a generator of the group \(\mathbb{Z}_p^{*}\): openssl dhparam -out dh1024.pem 1024 (marvel at the speed).

Interpret it two ways: the first way to read it is openssl asn1parse -in dh1024.pem

By hand using Base64: now that prime is stored in .pem format we can get access to it by reading base64. import base64 and run base64.standard_b64decode on the parts that matter. This gives you raw bytes. Your prime is at raw[6:6+129]. Get these bytes, convert to hex then an integer. The generator is probably the last byte (normally 2).

Confirm: use sage to confirm that \(p\) and \((p-1)/2\) are both prime.

Overview: This is a very useful trick for computational math, but it also unleashes a brutal attack on Diffie-Hellman and the general discrete log problem.

OK let's play a game. A random number is picked and you can only learn the remainder of that number modulo single digit moduli. Your goal is to find the number in the fewest number of guesses, here goes:

Once we're done with that let's talk CRT, the Chinese Remainder Theorem.

There is a perfect mapping from \(\mathbb{Z}_N \leftrightarrow \mathbb{Z}_{q_1} \times \cdots \mathbb{Z}_{q_k}\) whenever the pairwise GCD of \(q_i\) is 1 and \(N = q_1 \cdots q_k\).

Here is an example:

Given that \(x \equiv 2 \mod{5}, x \equiv 1 \mod{3}\) then \(x\) must be equivalent to \(7 \mod{15}\).

SAGE Cloud: You could code your own in Python (like https://rosettacode.org/wiki/Chinese_remainder_theorem ) but as we move into Number Theory I want to show you Python with super-powered math. Head to https://cloud.sagemath.com . Do the command CRT? once you've made a sage worksheet. Now compute the smallest positive number which is \(3 \mod{9}, 8\mod{13}, 6\mod{25}, 36\mod{121}\).

There are many great applications of the CRT, but in our case we're going to attack all of these schemes we've established when careful primes are not selected.

A Simple CRT Flag

Overview: This attack is important to understand because it doesn't show itself just by size of the key. You have to have more cleverness because of this attack so pay close attention.

I want to introduce a feasible attack on the discrete log problem. That is, given \(A := \alpha^x \mod{p}, p, \alpha\) find \(x\).

This attack will teach us about what makes a prime strong enough, cyclic groups, and the Chinese Remainder Theorem.

Real problem to solve: We are going to solve the following discrete log: \(p= 125301575591,\alpha = 115813337451, \alpha^x \mod{p} = 73973989900\). Compute \(x\). (Solve this after working the small example below.)

Now here is what we want to do. The problem is, given \(p, g, h:= g^x \mod{p}\) find \(x\).

The big idea is this, the multiplicative subgroup of integers mod \(p\) has size \(p-1\). If we know the factors of \(p-1\) (and they are all small) then we can convert this into a smaller problem.

Imagine that \(q | p-1\) then \((g^{(p-1)/q})^x = h^{(p-1)/q}\) is another equation involving \(x\) but now the possible answers for \(x\) aren't mod \(p-1\) but are mod \(q\).

A small worked example

Given \(p = 31, g = 3, h = 26 = g^x\) find \(x\).

We could try every value of \(x\) from 1 to 30 until we got 26 mod 31. In this case that would be cheap and not a problem, BUT it won't scale to the larger problem.

So we start by factoring \(p-1 = 30 = 2 \cdot 3 \cdot 5\). We will convert the discrete log problem into a three smaller problems that we can Chinese Remainder to find the final solution.

Start with \(q = 2\) which divides \(p-1\). Since we are looking for \(x\) which satisfies the relationship that \(3^x \equiv 26 \pmod{31}\) then if we replace \(3\) and \(26\) by \(3^{15}\) and \(26^{15}\) then we'll get another relationship \(3^{15x} \equiv 26^{15} \pmod{31}\).

If we look at this a little deeper we know that \(3^{30} \equiv 1 \pmod{31}\) based on what we know about cyclic groups. So this new relationship actually only gives us an answer mod 2. Here's what I mean. Suppose \(x\) were odd, then \(3^{15x}\) is exactly equivalent to \(3^{15}\) and if \(x\) is even then \(3^{15x}\) is always equivalent to \(1\). So either \(3^{15x}\) is equivalent to \(3^{15}\) or it is equivalent to \(1\). That means that we have learned a solution to the equation \(x \equiv r \pmod{2}\).

In this case we just check \(26^{15} \pmod{31}\) and we get \(30\) which matches \(3^{15} \pmod{31}\).

So we know that \(x \equiv 1 \pmod{2}\).

Now let's try \(q = 5\). We raise both \(3\) and \(26\) to the \((p-1)/5\)-th power. We get \(3^{6x} \equiv 26^{6} \equiv 1 \pmod{31}\). Now try every remainder of \(x \pmod{5}\) until we find the right power.

\(3^{0} \equiv 1, 3^6 \equiv 16, 3^{12} \equiv 8, 3^{18} \equiv 4, 3^{24} \equiv 2 \pmod{31}\), so we now know that \(x \equiv 0 \pmod{5}\) and that \(x \equiv 1 \pmod{2}\) which tells us that \(x \equiv 5 \pmod{10}\).

Why factors? Take a look at the results of the following quick loop. The number of 1s is 1 when we have a generator of \(Z_p^{*}\). What is the pattern?

      
      for j in range(1, 31):
          print j, [pow(3**j,i, 31) for i in range(30)].count(1)

Now you try: Using the last prime factor, 3, raise both \(3\) and \(26\) to the \( (p-1)/3 \) and deduce the remainder of \(x \pmod{3}\), and using all three clues deduce the value of \(x \pmod{30}\).

Now write a program to solve the larger problem we opened with. SAGE (or even Wolfram Alpha) can factor \(p-1\) for you.