End To End Encryption Isn’t Really End To End. The Crytography Stairway Story.
Today, I’ll tell you another tale. The Stair Story. I always wanted to create my own application for texting because why not, that’s the whole point of being a developer. We create things (maybe, my 50 other projects in the D:/ Drive and the 3 domains i bought would like to argue). I like to assume most of us trust the companies when they say, “Oh, Our Application is End-To-End Encrypted.” This is a “fr fr ong” moment for my gen z friends out there and a “We promise you.” moment for other’s. This problem of End-To-End Encryption really left me wondering of, “Hey Ayush, What actually goes on behind the scenes. Are my messages really secure.” and Oh, Boy I went down the mathematics lane. Today I’ll break it down for you in hopefully concise words and maybe you’ll learn a thing and if not hopefully you’ll enjoy this blog. Let’s break it down. 😎🪚
The Problem
Upon a general look (days of research), I found that cryptography has had their fair share of lessons over the course of time. From the very old days of ROT-13 to using Vignere Cipher which is just ROT-13 with one extra step, we have had problems on How To Secretly Store Something and more Importantly the problem. “How can two people have a secret coversation without anyone else knowing it?”. This problem is very easy to solve in person, since you can be sure that no one else is present in the room other than you and the person you would like to have a secret conversation with. but,
What about Internet?
How do you solve this problem on the internet? This question ate my mind just like I eat noodles. Before I continue further, I want you take a moment to think, “How would you solve this problem on the internet? Is there really a way to make sure two parties on the internet can talk to each other without anyone else evasdropping?”. Let me know in comment’s below.
Spoiler: It all come’s down to the stair story.
Did you guess and comment? Let’s analyze the problem. I’ll first let you know that i’ll obey cryptography traditions and only bother Bob and Alice here. Ok, so here we go.
The Problem: We have a person say Alice and she would like to talk to another person say Alice’s close friend Bob about a secret birthday party she had planned for her another friend Rio. Alice wants to do this over the internet. How could she tell Bob without anyone else knowing about Alice’s secret birthday party plan for Rio?
“Oh my, What a huge problem”. It really isn’t. I’ll help you. Let’s disect it together.
Alice want’s to tell Bob her plans to celebrate Rio’s upcoming birthday and she want’s to do this over the Internet. You’d think “Oh, she could just send the message? Can’t she?”. Well yes, She could but “What If someone intercepts her connection with Bob and read’s every message?”. See we got ourselves in a little mud here but don’t worry I’ll walk you out.
A Brief History On Cryptography
It’s hard to cover everything in one blog as there is so much to look at. I’ll keep it short and only mention one notable event on the timeline.
It was 1918 and a German Engineer Arthur Scherbius invented the famous Enigma Machine. If you’re anywhere intrested in Computer Science or Cryptography, you’ll have definately encountered this term. The famous Enigma Cipher. There is so much history behind it. You can read it here. The German Military was so impressed by the engineering of it. They used it to send secret messages during the war.
Later, in 1932, A Polish Mathematician Marian Rejewski was the first person to successfully figure our how Enigma works. As quoted by a historian,
“…was Rejewski’s own stunning achievement, one that elevates him to the pantheon of the greatest cryptanalysts of all time.” — David Kahn
This was a significant achievement which later proved so helpful for Alan Turing to crack the key which changed daily during Second World War. It turned the tide in the favor of allied powers.
Encryptions, Cipher’s and Cryptography has a really strong foundation in our species. The governments and the royals have used it for centuries to send information across different channels. The introduction of internet to common people raised some serious questions on “How to have be safe and secure on the internet”. This have put scientists and cryptologists in thoughts over the years.
The modern day has seen various techniques such as Asymmetric Encryption and Symmetric Encryption. Before I even start to explain them. I’ll cover a few different techniques in this blog including how they came by. Let’s get into it.
The problem with the ciphers and encryptions upto this point was that the numbers were pre-concieved & known to group of people (although classified but the mechanism was known and the numbers were pre-concieved, such as how many turns this rotar would rotate etc). Here came in *slow claps* Diffie Hellman Key Exchange Whitepaper.
Diffie Hellman Key Exchange
According To Wikipedia,
Traditionally, secure encrypted communication between two parties required that they first exchange keys by some secure physical means, such as paper key lists transported by a trusted courier. The Diffie–Hellman key exchange method allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure channel. This key can then be used to encrypt subsequent communications using a symmetric-key cipher.
In 1976, Whitfield Diffie and Martin Hellman published a research paper on what would be defined as the Diffie-Hellman key exchange. This was the first time for general public to have an encryption technique in which the numbers didn’t have to be pre-concieved or known. Here the numbers were mathematically linked. The two numbers were known as a Public Key and a Private Key. Both of the key’s had a mathematical relationship with each other. Here is the original Diffie Hellman whitepaper if you’re intrested in the depths. Diffie Hellman Key Exchange proved to be a significant contribution to Cryptography in General. Let me bother my volunteer’s for today’s blog. Alice and Bob and Alice’s party plan for Rio.
Recount from when I told you that Alice want’s to tell Bob her plans for Rio’s Upcoming Birthday Party? Yes, We’re one step closer.
Let’s first setup our environment. There is Alice on her phone, Bob on his phone and they’re connected via a server. A server is a computer that is public and can either return responses or act as a bridge between two people across the world. It is exactly how all your favourite website work. A server can do so many amazing things. It’s like the brain of all the apps but it’s still just a computer sitting somewhere in the corner of a whole bunch of computers called a datacenter. Now You’ll have this picture in your mind for the rest of this blog.
You might ask, “Hey Ayush, What is ‘a’ here? What is that ‘g’ and ’n’ here? I have so many questions right now.” Relax. I’ll guide you through. Let’s start from left. You’ll see Alice. The “a” is just a number. This number is very secret to Alice and we’ll assume that she never shares it with anyone. On the right, you’ll notice our Bob. The “b” is also just another number. This number is also very secret to Bob and we’ll again assume that he will never share it to anyone. Let’s now jump in the middle and you’ll find “g” and “n”. I’ll call “g” the generator, and “n” a fvery large prime number.
The relationship between ‘g’ and ’n’ is mathematical. Here ‘n’ is a very large prime number and ‘g’ is the primitive root modulo ’n’.
I hope you’re now clear about all the terms in the above image and also clear about the environment we are in right now. Remember,
Everything is a number. — Me 2022
In this context, we’ll assume that ‘g’ and ’n’ are number’s which are chosen by Bob and Alice before the start of their secret message exchange. Let’s now move forward with our first step in Diffie Hellman Key Exchange.
Step 1. Alice and Bob both request the server (which is in public) for the mutually agreeed upon number ‘g’. The server responds to their request and send’s them the number respectively. This step happens publicly.
Step 2. Alice and Bob now mix the number ‘g’ with their private number ‘a’ and ‘b’ to make a new number ‘ag’ (Alice’s new number) and ‘bg’ (Bob’s new number), let’s call it a “generated number”. This step is done by both communicating parties privately.
Step 3. Alice and Bob now share their new ‘generated number’ with each other over the public server. This step also happens publicly.
Step 3. Alice and Bob now recieve each other’s ‘generated numbers’ and now combine them again with their private number’s using the exact same process. This should mathematically result in same.
- For Alice, It would turn out to be Alice’s Private Number + Bob’s Generated Number which is, ‘a’ + ‘bg’ = abg.
- For Bob, It would turn out to be Bob’s Private Number + Alice’s Generated Number which is, ‘b’ + ‘ag’ = bag.
You can definately see how this is turning out, as abg = bag = gab = however you want to write it. It really doesn’t matter how you write it. All Thanks to mathematics and associative properties.
Notice that the Step 1 and Step 3 where public actions are performed. We only have four values that are ever made public. Namely, ‘g’, ’n’, ‘ag’, ‘bg’. You can combine them in any way you’d like but it’ll so hard for you that you’ll never try to find ‘bag’ or ‘abg’. (It is possible however, it would take so much time that the universe would end. It’s practically impossible for you. This is also known as discrete log problem. No one has been able to solve it yet. If you’d like to read more. Wikipedia is your friend. Here.
Great, Did you notice something. Both the communicating parties. Our Alice and Bob now have a number in common which they could use to encypt the messages with. The more amazing part of Diffie Hellman is that this was all done over an insecure channel (our public server). The whitepaper was truly amazing stepping stone in cryptography. So now you might think, Oh, that was easy. Problem Solved yay!. Let’s call it a day and let Alice text Bob about Rio’s upcoming Birthday Party Plans.
Well, No!! There is a problem. Did you notice it?
Today in this blog, we have another secret volunteer Charlie. Both Alice and Bob don’t know that Charlie, one of their friend’s is here today. Let’s take it a little further and ask Charlie to do his magic.
Let’s go back and modify our environment a little bit and add Charlie into the game. Remember our initial environment?
We’ll add charlie in the public but remember both Alice and Bob don’t know about Charlie.
Our new environment would look something like this.
You might be wondering, What Is ‘c’? Here ‘c’ is Charlie’s own secret number, just like Bob has ‘b’ and Alice has ‘a’.
Now Let’s perform Diffie Hellman Again.
Step 1. Alice and Bob both request the server (which is in public) for the mutually agreeed upon number ‘g’. The server responds to their request and send’s them the number respectively. This step happens publicly.
Step 2. Alice and Bob now mix the number ‘g’ with their private number ‘a’ and ‘b’ to make a new number ‘ag’ (Alice’s new number) and ‘bg’ (Bob’s new number), let’s call it a “generated number”. This step is done by both communicating parties privately.
Step 3. You’ll instantly notice that instead of forming ‘abg’ now after the introduction of Charlie a completely different shared secret key is formed at Bob’s end. Our new ‘bcg’ (instead of our ‘bag’ in our normal diffie hellman above).
Yes, you guessed it correctly. Charlie does the same with Alice.
You can already guess where this is heading and maybe even guess the trick Charlie is trying to play. Yes!! Charlie is trying to form a bridge between the conversation.
Do you wanna know what happens next? Here you go.
Step 4. When Alice send’s her text encrypted with the shared number that is now with Charlie instead of Bob. Charlie can simply intercept the message. Decrypt it with own secret number and then again encrypt it and send it over to Bob. In this way Charlie can secretly listen to all of Alice’s plans for Rio that were meant for Bob without Alice and Bob ever realising that they are being secretly listened.
Awesome! You’ve successfully breached Diffie Hellman Key Exchange with Man In The Middle (MITM) Attack.
Another Step on The Stair and a Question.
Now you might have a question. “How do we prevent this?”. The truth is, We can’t. We can never be sure of who is in the middle of the conversation. Let’s make the problem a little harder for our Charlie Here.
The First Step In Our Stairway: RSA
Enter *slow claps* RSA (Rivest Shamir Adleman). RSA is an asymmetric encryption algorithm that uses a public key and a private key which are inverse’s of each other mathematically.
From Wikipedia,
In a public-key cryptosystem, the encryption key is public and distinct from the decryption key, which is kept secret (private). An RSA user creates and publishes a public key based on two large prime numbers, along with an auxiliary value. The prime numbers are kept secret. Messages can be encrypted by anyone, via the public key, but can only be decoded by someone who knows the prime numbers.
Ah, Only If I could understand that (I do sort of). Let’s break it down now. RSA on it’s own is quite powerful but over the internet if not implemented properly it could cause so much trouble.
How does RSA fit in Diffie Hellman? RSA make’s it harder for the attacker ( our Charlie) to do the process instantly by adding an extra step. Now charlie has to also sign a digital certificate everytime with his own RSA key pair. This is computationally expensive and take’s time. RSA is also used as a digital signature.
You can definately see how adding an extra step slows down Charlie by a lot but the problem still remain’s unsolved. What stops Charlie from creating his own key pair?
Remember the goal for adding RSA here is not encrypting but adding slowdown’s for Charlie. This act’s like another stair and so began’s our stair story. I know you’re wondering, “Oh gosh, That took so long to start the story”. I promise you the story is short from now on. We’ve covered a lot already.
Now the Final Question, “So how do we solve this problem”. I have told you before we can’t atleast for now.
The Second Step: Certificate Authorities
This is where Certificate Authorities Step In. To solve the issue, we created some organizations which the whole world could trust that have their own private RSA key pair’s. They’re in the form of certificate’s. For some amount of money, They offer you a certifcate which signed by their private key which could be used by you in your website to make secure connections. This system is largely trust dependent as you’ve seen we’ve shifted the problem. How does this work?
Let’s look at it.
- When you install a browser or an operating system. Your Browser/Opearting System has a Certificate Trust Store called ‘root’.
The name of the Trusted Root Certification Authorities certificate store is root.
- These are like piggybanks that store all the certificate’s (which are just key’s) that you’re browser and operating system trusts. When a site stablishe’s an HTTP’s connection. The browser verifies the certificate’s digital signature, which is nothing but a signed private key returned from the server of the website to one of the public key’s that is already stored in the opearting system or browser’s certificate store.
- If confirmed, You can be sure that the person is your dear friend Bob or Alice. Othewise good luck!
Oh yeah, and you noticed. Alice can now send Rio’s upcoming birthday plans to Bob over the internet thanks to HTTP’s and SSL which is a Certificate Issued by Certificate Authorities (which I’ll assume we trust).
Fun Fact: StartCom was a Certificate Authority that lost it’s trust. Here’s a good News Article If you want to read about it more. You can also read about the controversies on Wikipedia surrounding StartCom which led to it’s distrust among all browser’s. StartCom never recovered. It just show’s that is all a game of trust until we acutally manage to solve the problem instead of shifting it up a stair and extend our stairway.
Conclusion
To put it simply, Your End-To-End is encryption is only encrypted as long as we all trust Certificate Authorities. A single breach could bring down the entire house. To me, It’s like a house of cards that is bound to fall unless we actually solve the problem instead of shifting it up another stair. Generally, This is also what you see in HTTP’s. The Connection is made on first request and a encrpytion suite is agreed upon. HTTP’s with it’s SSL and Certificate Authority act as a first line of defense and top of that our RSA and Diffie Hellman act as a second line of protection to our encryption.
This problem largely reamins unsolved for now. I hope we can find a better mathematically proven way to establish a relationship between two numbers irrpective or the location. Oh, This give’s me an idea. Maybe Quantum Properties would help us here. How about Quantum Entanglement where we know the value of the other bit if the value of the first bit that is entangled with the other bit. Hehe! I’m not sure though. Where cryptography proceed’s further. However, I’ll sure keep an eye as security belongs to everyone and we all deserve it. For now, this is it. I’ll follow this article up later with more encryptions as I learn them.
If you enjoyed this long post I wrote (took me so much time & work). You can thank me on twitter by giving me a follow. I go by @is_it_ayush over on twitter. I also hope you learned something new or just enjoyed it. Let me know below too. I’ll definately follow up this article with more encryptions, cipher’s and topics as there is so much I could talk about with you but until then take care! stay safe. ❤
