Demystifying Cryptography
To those not on the field, the word 'Cryptography' seems to be surrounded by some intangible mysticism. Media references, whether it is on the news, TV shows, movies, or videogames, use it as a hacker-related term when talking about cyber-attacks. I'm willing to bet that most people are aware that they use cryptography on their day to day life, however it is often perceived as this strange mathematical veil that protects us from spies and hackers when we are trying to buy some stuff or log in to see our bank account online. Yet who actually understands Cryptography? Well, clearly only geniuses in laboratories, hackers in dark basements, and 'James Bond'-style spies that are far more smarter than us mortals....
* Pause for Dramatic Fanfare *
However, the dirty little secret of Cryptography is that 99% of it is dead simple algebra. In fact, a cryptographic scheme that uses really complicated math will often be looked down upon because:
- Complex calculations take time and make for inefficient implementations on computer software/hardware.
- Complex calculations can obscure the scheme to a point where it is mathematically hard to prove it's security.
So at the end of the day, the schemes that end up working are actually dead simple. That isn't to say that coming up with the scheme is easy (That requires a lot of mathematical studies), however understanding the actual schemes tends to be easier than you would think.
So allow me, as an enthusiastic student of the field, to take you through an interesting tour of Cryptography. In this Crypto 101, I'm going to quickly give you a general overview of the field, and teach you the intuition behind the actual schemes you use on a day to day basis.
* Follow me for more crypto/hacking content! Follow @konukoii
What is Cryptography?
Cryptography is the study of secure communication on insecure channels. In other words, how do I transmit a message meant to be secret on a channel that has been compromised. A silly example would be when parents, who in an attempt to hide the secret message from their young child, start to spell words: "Honey, when is it that he has his D-E-N-T-I-S-T appointment?". The young child is perhaps unable to decipher that code, but as he grows older, parent's need to come up with better or more complicated schemes. In fact, that's a neat representation of how Cryptography works, first we create a cipher, then someone breaks it, then we create a new one, someone breaks it again, and so on and so forth. The history of cryptography is filled with this tug of war between creating and breaking ciphers. I heavily recommend reading Singh's The Code Book for a thrilling read as you see the effects of cryptography hiding behind very important moments in history. But I digress...
What are the goals of Cryptography?
Cryptographic schemes/protocols tend to focus on achieving different goals:
- Message Confidentiality: Assuring that only the authorized recipient is the only one able to extract the contents of the message from it's encrypted (hidden) form.
- Message Integrity: The recipient should be able to determine whether the message was tampered with.
- Sender Authentication: The recipient should be able to determine the identity of the sender.
- Sender Non-Repudiation: The sender should not be able to deny sending the message.
It's worth noting that different schemes will fulfill different goals, and in some cases different schemes/protocols can be merged to satisfy more of these goals.
As we venture into the world of cryptography it is easy to get lost in the vast amount of schemes, protocols, and mechanism that you can find in the wild: Digital Signature schemes, Hash functions, Encryption schemes, Random Number generators, among many others. However, I want to focus on two very commonly used tools in our cryptographic arsenal:
- Symmetric Key Encryption (SKE) schemes
- Key Exchange Protocols (KEX) schemes
Anatomy of a Secure Online Connection
Before we dig deep into these types of schemes, I want to motivate their importance. There is no better way than to explain this, than by explaining what happens when you securely connect to an online website.
Let's start with a simple analogy. Imagine you wish to securely communicate with your good friend "Bob" who happens to live on a different city. Lets assume you have at your disposal a box with a combination lock. To securely communicate you will first need to agree with Bob on a key/password/combination for the lock. Then you can just write your secret message, shove it inside the box and lock it. Then all Bob has to do is unlock the combo lock with the combination you guys previously agreed on and take out the message. This can go back and forth however many times.
That's kinda what happens in real life, first we choose a key using a Key Exchange Protocol and then you encrypt ("lock") the message using a Symmetric Key Encryption Scheme.
Key Exchange Protocol
The very first thing you have to do when initiating a secret communication is to agree upon a 'secret key' (the combination for the lock in the previous example). This process is a bit tricky since it is happening through an insecure channel, so you just can't say "Hey Bob, lets use 12345 as our secret key", cause everyone will hear you.
In reality we use something called Diffie-Hellman (or variations of DH). It essentially works by doing the following:
- Each user has a "Secret Key" number (\(a\) & \(b\)) that they decided before hand (and no one except them knows).
- There is a "Public" number (\(g\)) that is shared by everyone.
- When Alice and Bob want to connect, Alice calculates \(A= g^a\) and Bob calculates \(B=g^b\).
- They both exchange these \(A\) and \(B\) they just calculated
- Finally, Alice obtains the Shared Key by calculating \(B^a\) and Bob does the same with \(A^b\) to retrieve the same key (number).
This works because \((g^a)^b = (g^b)^a\). Furthermore, it is hard to figure out \(a\) and \(b\), because calculating \(a\) given \(g^a\) is computationally hard. (Aka. if \(g,a\) and \(b\) are really big numbers, it takes ages to factorize \(g^a\)). If you still have doubts, check out the example below (with simple numbers) or check out this amazing explanation from Khan Academy.
Try it: Diffie-Hellman over an open wire
The base \(g\) and prime \(p\) are public — everyone on the wire can see them, and the two values Alice and Bob shout across (\(A\) and \(B\)). Yet only Alice and Bob, each holding a private secret, can compute the same shared key. Drag the secret sliders, or press Step to advance through the five steps one at a time — the arrow shows where you are.
- 1 Secrets
- 2 Publics
- 3 Exchange
- 4 Compute
- 5 Shared key
Alice
Bob
Symmetric Key Encryption Scheme
Symmetric Key Encryption schemes are simply schemes that given a message and a key allow to encrypt and decrypt the message. Although there are a ton of different SKE schemes. Instead of going through some of the hardcore ones we use on the internet now a days, let's take a really simple one; The Caesar cipher.
SKE Example: Caesar Cipher
This is an encryption scheme said to be used by Julius Caesar to communicate top secret messages (ergo the name). The scheme attempts to achieve Message Confidentiality (although it was long broken). Like all SKE, it is comprised of 2 algorithms that allow to Encrypt and Decrypt.
Encrypt: We will take a password p (such that p is between 0 and 26) and a message that we want to decrypt. We will then encrypt by substituting each letter on the message by a letter that is p positions to the right of it on the alphabet (refer to picture below). So if we want to encrypt 'abc' with password p=1, we would get 'bcd'.
| plain | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| cipher | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C |
A Caesar shift: the cipher alphabet is the plain alphabet rotated by a fixed amount (shown here with a shift of 3, so each letter is replaced by the one three positions to its right).
Decrypt: To decrypt we do the exact opposite calculation, so instead we will substitute each letter on the message by a letter that is p positions to the left. So if we want to decrypt 'bcd' we with password p=1, we would get 'abc'
Not that hard, eh? Looking at this you might think its pretty silly, but amazingly, this was used time and time again to send sensitive messages during the times of the Roman Empire. Of course, someone along the line saw that you only needed to test for 26 keys (which you can test pretty fast) and the scheme was done for.
Conclusion
Hopefully, this small Crypto crash course has been useful to peek into the fascinating world of Cryptography. I'm not going to claim that Crypto is a breeze, but I don't think it is complex to the point of being un-understandable by the general public. Furthermore, since your life is surrounded by it, it is certainly useful to at least have a brief overview of what it is and how you are using it. If you have any questions or suggestions feel free to comment or contact me. Cheers!