Internet Cryptography Demystified

About cryptography

While going through a set of configurations to connect on a remote machine I was asked to upload my public key and I realized that I didn’t really know what that was for. If you are asking yourself the same question, or need to convince your mom she can safely use her credit card online, here is brief summary of what’s going on behind the curtains.

Nowadays via the internet we need to constantly communicate to people we don’t know, sending messages that can be constantly spoofed by other people. It would be as if we were requested in a very crowded room to confidentially communicate with someone else on the other side of the room without having the other people guessing what we said.
As an foreigner I am able to do that with my friends from home, but in general it’s a tough challenge, that unveils a fascinating topic: Cryptography.

Let’s first list the main concepts that are needed to have a full end to end secure communication:

1. Secret key cryptography
2. Diffie-Hellman key exchange
3. Asymmetric cryptography: RSA
4. Certificates

The gist of all these different topics is the concept of a one way function. A one way function is a function f for which is easy to calculate f(x)=z but extremely hard guess what x was knowing f and z.

1. Secret key cryptography

Both Alice and Bob own an identical key that is used to encrypt and decrypt messages that they send to each other. The algorithm to encrypt and decrypt the messages is known, but the security is based on the fact that guessing the message from the encrypted message takes a huge computational effort. One intuitive example of a very simple symmetric encryption algorithm is the XOR function:

if we had a key of 8 bytes and split our message in 8 bytes chunks, we could encrypt it instantaneously, whereas an attacker would have to try 2^64 different possible keys. Actually with the XOR function, though still being quite hard to do, it is possible to notice patterns and make guesses based on characters that are more common in the alphabet, for example. The algorithms used nowadays (mainly AES, or Advanced Encryption System) are far more complex than the plain XOR function and decrypting a message would take hundreds of years to solve.

2. Diffie-Hellman key exchange

the problem raised from secret key cryptography is that Alice and Bob must exchange the key used for the encryption before they starting communicating. If they send that key over the internet, an eavesdropper, Eve, could easily spoof it and be able to decrypt later any message they send to each other. Here it comes: the Diffie-Hellman key exchange.
In the Diffie-Hellman key exchange both Alice and Bob create their own private key, say AK and BK, that they don’t share with each other. Their trick is to use a discrete exponent: x^y mod z, with z being prime with x so that we have the following properties:

• x^0=x^(z-1)=1
• given x^y mod z=res there is no known way (nowadays) to guess what y was knowing x, z and res other than trying to keep on multiplying x by itself until we find res.
• given y, calculating x^y mod z takes a number of multiplications that grows with the log base 2 of y. For example if y=25, x^y mod z doesn’t require us to do 24 multiplications of x, but can be calculated as x^16*x^8*x. So we calculate with 2 multiplication s= x^3. Then we calculate with one other multiplication t=s^2=x^16, and then with other two multiplications we obtain s*t*x=x^25, for a total of 5 multiplications.
• x^ab mod z = x^a^b mod z = x^b^a mod z = x^ba mod z

Now if Alice communicates to Bob, a common generator G and a base Z that also eavesdroppers can intercept, she can then send him the result of G^AK mod Z=D. Bob likewise sends Alice G^BK mod Z=E. Alice then calculates E^AK mod Z = (G^BK)^AK mod Z = G^BK*AK mod Z = G^AK*BK mod Z for the above mentioned properties. Bob as well calculates D^BK mod Z = (G^AK)^BK mod Z = G^AK*BK mod Z. They obtained a shared secret key. Note that Eve won’t be able to obtain the shared secret key from the information that she spoofed, as D^E mod Z != G^AK*BK mod Z.

3. Asymmetric cryptography: RSA

A flaw with the Diffie-Hellman key exchange is that it takes time, and in the practical situation where there’s a server and many clients communicating with it, there would need to be a key exchange for each of them. The RSA algorithm comes in place in this situation:
Instead of symmetrically obtaining the same key for the two parties involved, asymmetrically the encryption is obtained with a key that is different than the decryption one. This allows Alice, for example, to communicate the encryption key to the world and keep the decryption key to herself. Then, if Bob or Charles or anybody else wants to send a private message to Alice he will encrypt it with the public key that Alice has published and only Alice will be able to decrypt it being the only owner of the decryption private key.

The mirror usage of the same technique is used for authentication: Alice sends the  published decryption key and keeps the encryption key for herself. Hence Eve can’t send a message to Bob claiming to be Alice, as she wouldn’t have a way to encrypt it. For example when we create an account on github.com, we can also upload our public key. This way we won’t to authenticate each time that we need to exchange information with the server.
This is what happens with SSH:

One common misunderstanding is that the asymmetric cryptography is a better version of the secret symmetric one and hence replaced it. It is not! The vast majority of any secure communication is always obtained via symmetric cryptography due to its way faster nature:

4.Certificates

The main missing piece for a secure connection is the verification of identity. The question is how can we know that a website actually represents whom it claims to represent. The answer is through certificates. Certificates implement a chain of trust for which starting from a root authority trust is granted to other authorities which get delegated to either verify the correspondence of a domain with a business entity or to trust another authority and delegate this operation to it. It works something like this:

Though it doesn’t actually work this way, we can see that at this point if we held the public key of the root certificate authority, we could initiate a trusted connection with it and then get routed to the other trusted authorities, drilling down the chain of trust until we reach the website whose identity we are trying to verify (the digital signature process does involve the public key but is more complicated and is able to work even when the authorities in the chain are offline).
All the major operating systems hold the certificate of the root CA and so are able to perform this task.

Here is then what happens in a SSL communication:

1. A browser requests a secure page (usually https://).
2. The web server sends its public key with its certificate.
3. The browser checks that the certificate was issued by a trusted party (usually a trusted root CA), that the certificate is still valid and that the certificate is related to the site contacted.
4. The browser then use the public key, to encrypt a random symmetric encryption key and sends it to the server with the encrypted URL required and other encrypted http data.
5. The web server decrypts the symmetric encryption key using its private key, uses the symmetric key to decrypt the URL and http data.
6. The web server sends back the requested html document and http data encrypted with the symmetric key.
7. The browser decrypts the http data and html document using the symmetric key and displays the information.

We are hence able to safely send our credit card details to Amazon.com without any concern of them being intercepted. I hope this helps you better understand Internet cryptography and security.