Secrecy in Plain SIght

Security is a vastly important facet of our day to day lives.  It is so ubiquitous, few people recognize that they use it every day. However, if you ever visit a webpage that has “https” in the URL, you are using secure technology.  Most of the early security protocols require that two parties have a secret exchanged between them.  Unfortunately, if someone is listening to the key exchange, they can easily decrypt all of the messages sent between the two parties.  You may find yourself asking, “But isn’t there some better way to exchange secrets?” You’d be right!

The method is called Diffie-Hellman key exchange, and it relies heavily on modular arithmetic.  The amazing thing about this protocol is that the two parties, Alice and Bob (in keeping with the cryptographic tradition of keeping names simple) can even publish their communications in the newspaper.  Anyone can be listening to these two exchange their keys.

Here’s how it works:

First, Alice and Bob pick two numbers, p and g.  P is a prime number, and g is a primitive root mod p.  A primitive root mod p has a very special property, namely that every number that is coprime with p is congruent to some power of g[1].  For example, if we pick p=5, 3 is a primitive root mod p because:
1,2,3,4 are relatively prime to 5.
30 ≡ 1 mod 5
31 ≡ 3 mod 5
32 ≡ 4 mod 5
33 ≡ 2 mod 5

As you can see, each number that is relatively prime to 5 is represented by some power of 3.  Therefore, 3 is a suitable primitive root mod 5.

For this example, Alice and Bob will decide on p=17 and g = 7.  They can pick these numbers from a well-known list.  What’s more, they can even display these numbers in public.  These will form the foundation of their key.  Next, Alice and Bob both pick their own numbers and keep them secret.  We’ll call Alice’s secret number a, and Bob’s number b. (Original, right?)

Next, Alice determines ga mod p, and Bob determines gb mod p.  We’ll call these c and d, respectively.  Now, Alice and Bob will exchange their values.  Again, this can take place in the open.
Now, Alice has d, and Bob has c.  Next, Alice performs da mod p, and Bob performs ca mod p.  This has the net effect of giving both Alice and Bob the same number.  They are now both in possession of gab mod p.  What’s more, any attacker could have watched the entire exchange, and wouldn’t have gotten anything out of it.

caption

Secrecy in Plain Sight. Image: A.J. van Hinck, via Wikimedia Commons.

Back to the example:

Alice chooses 3 as her secret number.
Bob chooses 5 as his.
Alice’s transport number is 73 mod 17 ≡ 3
Bob’s transport number is 75 mod 17 ≡ 11
Alice gets 11, and performs 113 mod 17 ≡ 5
Bob gets 3 and performs 35 mod 17 ≡ 5

Alice and Bob now have the same number, which they can use for regular cryptography.  Obviously, in a real situation, Alice and Bob would have chosen much larger numbers, but this suffices for an example.

This is the foundation of cryptography – relying on operations that are easy to perform, but are nearly impossible to reverse.  In this case, exponentiation can be performed on a computer in a reasonable amount of time.  It’s not the fastest algorithm, but it’s far faster than performing the reverse of a modulo operation.  (Incidentally, that problem is called a discrete logarithm, and there is currently no way that it can be done in a reasonable amount of time.)

You may wonder, “I really want to steal nuclear secrets!  Is there some way that I can still eavesdrop on people using Diffie-Hellman?”  You’d be right!  Diffie-Hellman is vulnerable to what is known as a “man-in-the-middle” attack.  This is difficult, as it requires being present at the time the keys are exchanged.  However, the attack is simple.  All that needs to be done is that some attacker Eve (short for eavesdropper) intercepts Alice and Bob’s messages.  When Alice sends Bob her key, Eve steals it, and substitutes her own key.  Bob then responds, and Eve steals his response.  She then gives her own key to Alice.  Now, there are two unbreakable passwords, and Eve has both of them.  However, there is a limitation: Eve needs to be present for the entire conversation, or Alice and Bob will immediately know something is wrong.  This is because the key that Alice has is not compatible with the key Bob has.  Suddenly, all of their communication will be reduced to gibberish, and they will know that they are compromised.  However, it is possible for Eve to hijack their conversation, leaving none the wiser.

We may ask, why not use RSA?  Well, we do!  If we combine RSA with Diffie-Hellman, we gain protection against eavesdroppers and hijackers.  Diffie-Hellman is faster than RSA and can encode larger messages than RSA.  (The messages sent by RSA are limited in size, lest it become easy to crack.)  In addition, using these two approaches combined gives us the ultimate goal of cryptography:  Perfect Forward Secrecy!  If the secret numbers used by Alice and Bob are discarded, nobody can read the messages exchanged between the two, ever.  That’s right, 30 years down the line, when someone digs up Alice’s old machine out of some attic in Nebraska, they won’t be able to read the messages she shared with Bob.  This is the real advantage of Diffie-Hellman, and the reason that it will likely remain in use for a very long time.

Sources:

[1] http://en.wikipedia.org/wiki/Primitive_root_modulo_n

[2] http://en.wikipedia.org/wiki/Diffie–Hellman_key_exchange

Advertisements