Limited Entropy Dot Com Not so random thoughts on security featured by Eloi Sanfèlix

Crypto Series: New Directions in Cryptography

As some of you might have noticed already by looking at the title, this post will be the first one talking about public key cryptography.  Today, I'll introduce the basic ideas around public key crypto and the ideas proposed by Diffie and Hellman in their famous paper 'New Directions in Cryptography' from 1976.

In subsequent posts, we well look at the discrete logarithm problem and the factorization problem. We'll also look into some public key cryptosystems, such as El-Gamal and RSA. And after that, we'll look at Elliptic Curve Cryptography. With all this, the algorithms part of this series will be considered closed and I'll move into cryptographic systems and protocols ;-). Stay tuned!

So, what did Diffie and Hellman exactly propose? Well, let me first tell you why they wanted to change the way cryptography worked. As you know, with symmetric crypto we need a shared key between two ends communicating. This works fine and is easy to maintain when we have a few parties taking place in a communication system.

However, with the advent of global communication systems, the Internet and all that stuff you all know, this turns out to be unmanageable. A symmetric system with n users requires a unique key per pair of users, which means keys.

Therefore, the main motivation for public key cryptography is the reduction of the number of keys needed for a cryptosystem, reducing the complexity of key management. Now, how do we achieve this? Basically, Public Key Cryptography is based in the existence of two different algorithms: a public algorithm for encryption, and a private algorithm for decryption.

So, let's say you want to encrypt something for a given person. Then, you retrieve this person's public key and apply the public algorithm for encryption. You send your encrypted message to that person, and once received, they will apply the private algorithm with their private part of the key.

This implies that the public encryption algorithm, , and the private decryption algorithm are inverse operations (in order to provide the ability to recover the plaintext). Further, the computation must be easy (or inexpensive) so that it can be efficiently applied. Finally, it should be infeasible to compute the decryption part of the algorithm given the encryption part .

Trapdoor functions

So, we need a function that is easy to compute, but its inverse is difficult to compute. That's a one-way function (such as a cryptographic hash function)... but wait, we also need it to be easy to compute for the other party. So, we will add some extra component (namely a key) which makes the inverse computation easy: a trapdoor!

We'll see how to construct these kind of functions in our coming posts about different public key cryptosystems ;-). For now, I'll only say that these functions can be constructed based on integer exponentiation modulo p or operations in Elliptic Curve groups.

Diffie-Hellman key exchange

So finally, we reach the Diffie-Hellman key exchange or key agreement. This is a protocol to jointly compute a shared key between two entities over an insecure channel, using only public data.

The DH key exchange works under the assumption that the discrete logarithm (DL) problem is difficult to solve. The DL problem is stated as follows:

Given , compute x

Where g is a generator and p is a big prime number. So, we assume that this problem is hard to solve (I'll talk about methods to solve it in my next post), and have two parties Alice and Bob who wish to communicate security. Then, Alice generates a random number modulo p-1 and computes from it. In turn, Bob does the same, generating and accordingly.

Now, Alice and Bob exchange their public part of the key and perform the computation of the shared key as:

Note that Alice and Bob are able to compute the shared key only from the public key of the other party and their own private key, which they don't disclose to anyone. Also, note that under the DL assumption it is infeasible to compute the private key of these parties from their public key.

However, here the attacker has more knowledge than in a simple DL problem, and this requires a stricter assumption: the DH assumption. The DH assumption means that we assume that given and it is hard to compute .

Note that this is different from the DL assumption, since you might be able to compute the result without going through the trouble of computing x or y individually. However, as far as I know, this problem turns out to be a difficult one at least in the groups of integers modulo some big prime number. Therefore, this guarantees the confidenciality of the key agreed by our two parties, Alice and Bob.

The Man in The Middle problem

I said this guarantees the confidentiality of the agreed key, but that's not completely true... it only does if the received public key really comes from the intended party. And since this key exchange doesn't do anything to guarantee the authenticity of the key, there is a clear man in the middle problem.

Imagine an attacker, either Eve or Mallory or whatever you like to call your attacker, sitting in the middle of the communication between Alice and Bob. This attacker is not only able to receive the communication contents, but to modify them. Then, the attacker is able to send its own public key to Alice and Bob, and keep their respective public keys for himself.

This would result in the attacker generating a secure channel between Alice and himself, and another one between Bob and himself. Whatever Alice or Bob send, he can decrypt, read and modify if he wishes.

To solve this problem, it is obvious that we need to add authentication to the key exchange. This is something that could be done with MAC or HMAC constructions as we learnt before, but then we get into a chicken and egg problem: we use the Diffie-Hellman key echange to avoid sharing a secret key, but then we want to authenticate the messages with a MAC or HMAC, which requires sharing a secret key!

This is where digital signatures, as the public key solution to authentication, will come handy. We'll see them in further posts, I think we all had enough for today ;-).