Rotors of M-209 cipher machine.

Diffie-Hellman Key Exchange

How can we safely agree on a shared secret when we are in an insecure environment?

If you don't have a secure channel, then how can you securely agree on a shared secret key for symmetric cryptography? Diffie-Hellman key exchange saves the day! It's really key agreement or key negotiation rather than key exchange. This is a case where a failed attempt to do one thing led to an enormously useful development in another area. Diffie and Hellman were trying to develop a practical system for asymmetric cryptography. Rivest, Shamir, and Adelman developed their RSA asymmetric cipher around that same time. Diffie and Hellman's accomplishment has been extremely useful for symmetric cryptography. The ElGamal symmetric cipher designed the following decade finally solved the original problem that Diffie and Hellman had been working on.

We have two players, Alice and Bob. They agree on a base, b, and a modulus, m. They can agree on the base and modulus in public. In fact, since there are better and worse forms for those values, they probably should do this in public, or simply choose a base and modulus in common use. For example, the modulus must be a prime number, and it is taken into account when choosing the base, see a detailed description for more on these choices. The modulus m should be a large prime, at least 300 digits, but b can (and usually is) a small number, 2 and 5 being the usual choices.

Alice and Bob each pick a secret number, Sa and Sb, respectively. Either of them can decide it's time to switch to a new key for their communication channel, making this a session key system. For security, these should also be large — at least 100 digits.

Each then calculates a public value from their secret value, by calculating Public = bSecret modulo m as follows:

Alice says:  Pa = ( bSa ) modulo m

Bob says:    Pb = ( bSb ) modulo m 

Now, because modulus of discrete logarithms is a one-way function — easy to calculate in one direction, but impractical or impossible to calculate in reverse — they can safely publish the base, modulus, and their public values and be confident that even highly motivated mathematicians could not discover their secret values. This includes Alice and Bob themselves — they cannot discover each other's secret values.

However, they can calculate a shared secret using the base, the modulus, the other party's public value, and their secret value. X.509v3 digital certificates let them make certain that they really have the public key of the other player, and not some "man in the middle" pretending to be the other end.

Alice calculates the shared secret this way:

Kalice,bob   =   [ PbSa ] modulo m
  =   [ ( [ bSb ] modulo m)Sa ] modulo m
  =   [ ( bSb )Sa ] modulo m
  =   [ b(SbSa) ] modulo m

Bob calculates the shared secret this way:

Kbob,alice   =   [ PaSb ] modulo m
  =   [ ( [ bSa ] modulo m)Sb ] modulo m
  =   [ ( bSa )Sb ] modulo m
  =   [ b(SaSb) ] modulo m

Since bSaSb = bSbSa, the two keys are equal. Since either of the two players must use their secret key in the calculation, it is a shared secret.

Note that each player must use the first form of the equation from each pair, as that form uses their secret and the other player's public value. The remaining lines are there for us to work through the equivalence. Note that any calculation of the shared secret requires some secret information, and thus an outsider cannot calculate it. Also, while an outsider might happen to guess the shared secret (although good choices of base and modulus make that extremely unlikely), the involvement of modulo arithmetic means that they would have no way of verifying that they had guessed correctly.

Security relies on:

Appropriate choice of base and modulus. The modulus should be a prime number with at least 300 digits. Surprisingly, the base can be small — values of 2 and 5 are commonly used.

Absolute secrecy of the secret values. They should also be appropriately large, at least 100 digits.

For a trivial example, not secure because of the small modulus and secrets:

Their shared secret key is 25.

Ephemeral Session Keys and Perfect Forward Secrecy

Once you have the ability to safely agree on a shared secret, you should take advantage of that and make your session keys ephemeral. That is, only used once.

Used correctly, ephemeral session keys lead to Forward Secrecy, sometimes called Perfect Forward Secrecy or PFS.

Forward Secrecy means that compromise of long-term keys does not compromise past session keys. That sounds contradictory! The important thing is that the long-term keys are used for authentication, and then a one-use-only session key is generated for each session, message, or file, using a non-deterministic algorithm.

Government-imposed backdoors and any form of key escrow for the session keys will destroy the Forward Secrecy.

Google introduced HTTPS by default and began moving toward Forward Secrecy in 2011.

Twitter enabled Forward Secrecy in October 2013, as reported in the New York Times and The Guardian.

EFF described Perfect Forward Secrecy and other crucial security mechanisms.

The Heartbleed vulnerability of 2014 emphasized the importance of Forward Secrecy.

Microsoft enabled PFS for email in July 2014.

In 2014 Yahoo (yes, they were still around in 2014) enabled HTTPS encryption by default for email but left out PFS.

How Can Several People Securely Share a Secret Key?

The secure sharing of secrets or access is an old problem! Here is a classic example:

Perugia is today the capital city of the Italian region of Umbria. But the modern country of Italy is a fairly new thing, with the peninsula organized under one government only in 1870. From the time the Roman Empire fell apart starting in the late 300s until then, the peninsula of Italy was a collection of many Papal regions, colonies of other empires, and powerful city-states, including that of Perugia.

The Cathedral of San Lorenzo in Perugia, Umbria, Italy, home of a purported engagement ring of the Virgin Mary.

The Cathedral of San Lorenzo in Perugia, Umbria, Italy, housing what purports to be the Virgin Mary's engagement ring, and in front of it, the Fontana Maggiore.

In the 1400s, the city of Chiusi had many visitors who came to see that city's prized relic — what purported to be the Virgin Mary's engagement ring. This was a jade disc about 6-7 cm in diameter and a little over 1 cm thick. Before complaining about the discomfort of wearing such a thing as a ring, or the lack of jade trading routes between China and Palestine in the first century BC, remember that this was in Renaissance Italy and dubious relics were common.

The leaders of Perugia decided that they should go to Chiusi in force and steal Mary's engagement ring so that Perugia could get all the benefits. Not just the income from pilgrimage tourism, but also the sacred bonus points for owning such a relic (and how that favor might be offset by their having stolen the ring through military force didn't seem to enter into the equation). So, they attacked Chiusi in 1473 and stole the ring.

Cesare Borgia, master conspirator of Renaissance Italy.

Cesare Borgia — do not give the key to this guy!

Their immediate worry was that a bigger city, maybe Florence, would then attack Perugia and steal the ring away. So they should get a local blacksmith to make a very sturdy box that would be attached into the stonework of their Cathedral of San Larenzo and locked with a strong lock.

But then who would hold the key to the lock? This was the era of the Borgias and conspiracy was common in Italy. No single person could be trusted to hold the key to the box.

So the blacksmith was directed to make a fairly large iron box with straps to be fastened around structural elements of the cathedral. The box had a very large hasp with fifteen holes, and fifteen locks were then used to lock the lid closed. Fifteen reasonably trustworthy citizens were selected, and each received the key to one of those locks.

So, a few times a year, at the pilgrimage seasons, these fifteen reasonably trustworthy citizens brought their keys to the cathedral, collectively unlocked all those locks, and the ring was displayed for the visitors.

If you are interested in more details about Perugia, Umbria, and travel in Italy, click here.

The leaders of Perugia had devised a M-of-N secret-sharing mechanism. No one person could had access. The access mechanism, a collection of keys, was distributed across a group of N (15) people, and some subset M (actually all 15 of them in this case) could combine their partial access to access the protected secret.

What if one of those supposedly upstanding Perugians had died of the plague? If the family couldn't find the key, they would have to get the blacksmith to cut into the box (and here we see that we have to trust the providers of the security technology). A better solution would have been to make it a true subset, M out of N where M < N. You can do that with combinations of chains and locks, but physical M-of-N control quickly becomes complicated.

Mathematics to the rescue! There are several ways to accomplish M-of-N secret key sharing, this is just one of the more commonly used methods:

Adi Shamir's method ["How to Share a Secret", Communications of the ACM, v.24, n.11, Nov 1979, pp 612-613] starts by choosing some prime p which is larger than the largest possible secret key. Remember, if a key is a string of k bits, it can be thought of as a number in the range 0 through 2k - 1.

Then generate an arbitrary polynomial of degree M - 1. Let's be a little less paranoid (smaller N) and more careful (M<N in case of plague loss), use a 5-of-7 scheme. So, N = 7 and M = 5. Here is our polynomial, where S is the secret number:

F(x) = (ax4 + bx3 + cx2 + dx + S) mod p

The coefficients a, b, c, d are chosen randomly, and they must be kept secret.

Now, we said we wanted to share the secret among seven people, so we just need to generate seven "shadow" values:
ki = F(xi)

We could simply evaluate our polynomial for x = 1, ,2, ..., and give each result to one of our seven people. Our polynomial has five unknowns: a, b, c, d, S, and so you could solve for those with any five output values.

Here is an example:
Secret: S = 42
Prime: p = 101
5-of-7 sharing
Random coefficients: 4, 13, 9, 25
Polynomial: F(x) = (4x4 + 13x3 + 9x2 + 25x + 42) mod 101

Generate six shadow values:
F(1) = (4*14 + 13*13 + 9*12 + 25*1 + 42) mod 101 = 93
F(2) = (4*24 + 13*23 + 9*22 + 25*2 + 42) mod 101 = 94
F(3) = (4*34 + 13*33 + 9*32 + 25*3 + 42) mod 101 = 25
F(4) = (4*44 + 13*43 + 9*42 + 25*4 + 42) mod 101 = 37
F(5) = (4*54 + 13*53 + 9*52 + 25*5 + 42) mod 101 = 73
F(6) = (4*64 + 13*63 + 9*62 + 25*6 + 42) mod 101 = 74
F(7) = (4*74 + 13*73 + 9*72 + 25*7 + 42) mod 101 = 76

Distribute the shadow values to the seven individuals. In the future, any five of their shadow values can be used to create and solve a set of five linear equations in five unknowns.

Next — Cryptographic Hash Functions