8. RSA

Diffie Hellman gets attacked with -- Man in the Middle!

We saw in the previous lesson that the Diffie Hellman key exchange allowed two parties to arrive at the same secret key that they could use as an encryption key to encrypt their communication.

Diffie Hellman key exchange alone is not sufficient. It can be attacked with a man in the middle. Let us see what does that look like.

Ant asks Bug to establish a secret key using Diffie Hellman.

The man in the middle, the attacker, intercepts the message and replies to Ant. Ant thinks the reply is from Bug!

Ant thinks that he is talking to Bug.

Ant has no way to know that their communication is being intercepted by an attacker.

So, Ant exchanges a secret key using Diffie Hellman with the attacker who is impersonating to be Bug. They successfully exchange a secret key 13!

Now, the attacker says to Bug, that he is "Ant" and then exchanges a secret key 22 with Bug.

In Bug's mind it is Ant with whom he has exchanged the secret key. But in reality the attacker has impersonated as Ant!

Mayday, mayday, mayday! We are under attack!

Now, Ant sends an encrypted message to Bug using secret key 13 because according to Ant this secret key 13 has been exchanged with Bug. But in reality its the attacker with whom he has exchanged the key!

So, the attacker is able to decrypt Ant's message, modifies it and then encrypts it back with the secret key 22 he exchanged with Bug.

When Bug receives this encrypted message, Bug thinks that its from Ant. But we know the reality. The attacker impersonated as Ant and exchanged the secret key.

The attacker is able to decrypt and modify all messages between Ant and Bug without them realising this!

Ant and Bug both think that they have exchanged a secret key with each other but in reality the attacker exchanged the secret key first with Ant and then another secret key with Bug. So, the attacker is able to decrypt and modify all communication between Ant and Bug as he has the secret keys!

This way our whole communication has got compromised!

The Diffie Hellman key exchange was indeed one of the greatest step forward in secure network communication. But using Diffie Hellman key exchange alone is prone to Man in the Middle attack.

If there was a way for Ant to verify whether he is talking with Bug or with someone else then Man in the Middle can be stopped!

RSA quietly enters the room!

RSA is a public key encryption algorithm or asymmetric key encryption algorithm, both are same thing. RSA comes from the surnames of its inventors: Ron Rivest, Adi Shamir and Leonard Adleman. They were from MIT. Its inventors were greatly inspired by Diffie, Hellman and Merkle.

In symmetric encryption we studied that it had one key that we used to encrypt, as well decrypt.

In asymmetric key encryption algorithm like RSA, there are two keys. We call them as a key pair.

Out of the two keys, one is called as a private key and other is called as a public key. The public key can be shared with everyone.

But the private key is meant to be kept super secret! It MUST NEVER ever be revealed. As we will move forward you will realise whole lot of bad things happen if someone reveals their private key.

The interesting thing about asymmetric key encryption is that -- if a message is encrypted with the public key then it can ONLY be decrypted with the corresponding private key. No other key in this universe can decrypt it.

And it works the other way round too. If a message is encrypted with the private key then it can ONLY be decrypted using the corresponding public key.

The two keys -- public and private keys are mathematically linked with each other. One encrypts, the other decrypts.

The above is from the popular xkcd comic, the character there (named Cueball) is thinking to reveal his private key. That's the worst thing you can do to your computer's (or server's) security. This is what happens when we don't understand basic cryptography :)

How RSA solves Man in the Middle...?

One of the main motivations behind the development of RSA algorithm was to be able to sign messages with a digital signature.

Let us see how digital signature using RSA helps in making our Diffie Hellman immune to Man in the Middle attacks!

First, Bug generates his RSA key pair. He has distributed his public key to everybody and kept his private key just to himself.

This means Ant and the attacker has access to Bug's RSA public key.

Now Ant sends a message to Bug asking to start the Diffie Hellman key exchange process. Bug's computer generates base, modulus and his secret number, then it calculates (basebug's secret mod modulus) which comes out to be 215 mod 19 = 12.

Then Bug creates a message that contains base, modulus and 12 and then signs that message using his RSA private key.

But how does signing work?

Signing a message is a two step process. We first hash the contents of the message, in our case contents of the message are "2 19 12". Then the resulting hash value gets encrypted using Bug's RSA private key. The result of the encryption is the signature.

Signature is inserted to the end of the message and sent to Ant.

When Ant receives this signed message, he needs to verify whether the signature is valid or not.

Ant verifies the signature in two steps. First, he calculates the hash of the message contents: 2 19 12. Then signature is decrypted using Bug's public key, if the resulting value matches the hash value of the message contents then it means that the signature is verified!

If the signature is verified then it proves two heavily important things --

• First: the message contents are not modified by a middle man.
  
  During signature generation, Bug hashed the message contents 2 19 12 and encrypted this hash value. This encrypted hash value was sent as signature.
  
  Now when we decrypt the signature, we get the hash value that Bug calculated. Hence, the decrypted signature represents the message contents as it was on Bug's side.
  
  To verify, Ant again takes the message contents 2 19 12 and hashes it. If the hash value comes out to be same as the decrypted signature value then it means that we have received the message contents without any alteration!
  
  Let us suppose message's content was modifed by a man in the middle. The attacker changed the message to 4 19 14. When Ant will calculate the hash of this, its not going to match the decrypted signature value, which signals that the message contents are not same as how Bug wanted it to be so signature verification fails!
  
  
• Second: the message was sent by Bug. Nobody else could have sent this message.
  
  When the signature verification passed successfully this means that Ant was able to decrypt the signature perfectly fine with Bug's RSA public key.
  
  If Ant was successfully able to decrypt the signature with Bug's public key this means that it could only have been encrypted with the corresponding private key. And only Bug has access to his private key. This means only Bug could have sent this signed message!
  
  Now imagine, the man in the middle intercepts the message, changes the message contents, and calculates a new signature but with his own private key. This modified message with the attacker's signature gets forwarded to Ant.
  
  Since this evil message's signature was created with the attacker's private key, it can only be decrypted using attacker's public key. It cannot be decrypted using Bug's public key. So, when we try to decrypt this signature using Bug's public key, the decryption fails and thus resulting in a signature verification failure!
  
  

So, when the signature verification passes ✅, it means that -- the message contents are not modified by a Man in the Middle. And the message came from Bug only.

Now the Man in the Middle (our attacker) will not be able to impersonate as Ant or Bug also the attacker cannot modify their messages. This defeats the Man in the Middle attack badly!

Our RSA digital signature rocks! 🥂

Credits

Below are some resources I used to tighten my understanding. Again, you already know that you don't need to consume these. I have covered all the necessary concepts in this article. You are good to move to the next lesson. I add these resources because being a developer I believe in citing other's helpful work.

• The First Few Milliseconds of an HTTPS Connection by Moserware.
• My one of the favourite teacher's video on RSA. The first part and the second part .
• Khanacademy's cryptography curriculum. I studied the algorithms' internals from Khanacamedy way back when I contributed a short course to freeCodeCamp.org on cryptography.
• I read RSA's history from its Wikipedia entry.

I have worked hard to create this course. If you are getting some learnings from it, you should follow me on Twitter: twitter.com/vkwebdev. I try to be useful there :)