August 15, 2019

Symmetric Encryption, Because it's Interesting

These days, there are two major "categories" of encryption. Symmetric key encryption and Asymmetric key encryption. Today we're going to talk about the symmetric side of things. What is it? How does it work? Examples, etc. Let's dive in.

What is it?

Symmetric encryption is any cipher algorithm where plaintext is both encrypted and decrypted with a single key. In other words, both the sender of the message and the receiver of the message need to know the secret key which is also symmetric encryption's major weakness. If anyone gets a hold of the key the strength of the algorithm is moot. Key distribution is your top concern here and there are entire industries built around transporting and storing keys securely.

Symmetric encryption was pretty much the only kid on the block until the 1970s when something called asymmetric encryption showed up on the scene and a distinction was required.

The most ancient forms of symmetric encryption are "substitution" ciphers. Encrypting plaintext with a substitution cipher means you substitute each letter in your alphabet with some other character in a "specific way." The "specific way" bit is what defines your key. One of the oldest and most well known substitution ciphers is the Caesar Cipher.

The Caesar Cipher

The Caesar cipher is a classic means of encryption. The algorithm's key is a "shift" value which means each letter in the alphabet gets substituted with another letter that is shifted n characters to the right. Say we choose an n of 3 (meaning our key would be the number 3).

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
---------------------------------------------------
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

The top is the alphabet we all know and love, the bottom is that same alphabet shifted by 3. So A becomes D, B becomes E and so on. Notice at the end it simply loops back around.

Now, say we want to encrypt the word FART with this shift. We'd look up the letter F in our regular ol' alphabet and see what the ciphertext character is. Looks like it's I yeah? So:

F -> I
A -> D
R -> U
T -> W

Therefore the plaintext FART encrypted via Caesar cipher with a key of 3 becomes IDUW. You pass this note to your buddy in the desk ahead of you and whisper the key real sneaky-like. At which point he begins to decipher this sucker. This is done by looking up the ciphertext letters in our shifted alphabet and piecing together the corresponding regular alphabet characters. So, we look up I in the cipher alphabet and see that it corresponds to F. Here's the rest:

I -> F
D -> A
U -> R
W -> T

Oh boy! That is funny isn't it! FART! Hahahaha! You two just laugh and laugh right up until the teacher throws you both through a window because this is like 1865 and that sort of thing isn't frowned upon yet. Anyway...

Why is this a terrible way to keep important stuff secret? Mainly, this method of substitution is weak against frequency analysis. In Caesar encrypted ciphertext you're still going to see the same letter frequency patterns as you would in the plaintext for whatever language you're working in. For a Caesar cipher in particular though, you don't even have to know what frequency analysis is. If you're working in English and you suspect you're looking at a Caesar ciphertext just grab a beer and try all 26 possible shifts. Whichever value deciphers the ciphertext to something that isn't nonsense is your key.

OK, how can we do better? Well, one of the next major revolutions in keeping secrets is known as the Vigenère cipher.

The Vigenère Cipher

This Italian cryptologist named Giovan Battista Bellaso was supposedly the first person to describe this revolutionary encryption algorithm. However, this other yahoo named Blaise de Vigenère got the attribution so that's where the name comes from.

Anyway, From Wikipedia:

The Vigenère cipher (French pronunciation: [viʒnɛːʁ]) is a method of encrypting alphabetic text by using a series of interwoven Caesar ciphers, based on the letters of a keyword.

The Vigenère cipher is a substitution cipher that uses many alphabets (the technical term is polyalphabetic). In Vigenère we use as many alphabets as there are letters in your alphabet. So, 26 for English. The strength here is that frequency analysis becomes really hard.

A Vigenère key can be any length, but if it's shorter than the plaintext, it repeats until it's equal. If the key is the same length of the cipher then this becomes a one time pad.

Note: I covered the Vigenère cipher some in my first few posts on repeating key XOR encryption. Some of this is going to be old hat, but there's also extra detail here that wasn't worth going into before.

So, say we have the following plaintext:

IFARTINYOURGENERALDIRECTION

And we've chosen the key PYTHON.

Notice that I've removed spaces. In these old school techniques spaces leak information if kept in the ciphertext, specifically word length. It's best to just get rid of them.

Since the key needs to be as long as our plaintext it gets repeated like so:

IFARTINYOURGENERALDIRECTION
---------------------------
PYTHONPYTHONPYTHONPYTHONPYT

And this gives us a proper Vigenère cipher key to match our plaintext. Once we've got this, we can then use what's called a tabula recta (sweet name, right?) to encrypt our text. Check this thing out:

The very top row, is a regular old alphabet from A-Z and this is used for plaintext characters. The leftmost column is another normal alphabet and we use that for key characters. All the other rows are the alphabet continuously shifted one char to the right and these make up our ciphertext characters. So, say we have the plaintext ATTACK with a key DAWN. If we repeat the key we get:

ATTACK
------
DAWNDA

To encrypt we first we look for the letter A (from our plaintext) in our topmost row. Then we look for the letter D (from our key) in the leftmost column. The character that these intersect is our new ciphertext character. Which, it turns out is D. Basically, this is encryption Battleship.

Look up the rest of ciphertext characters in the tabula recta yourself. I'll wait.

We continue this process for every plaintext character. Here's the entire process using the corresponding plaintext characters (ATTACK) from our repeating key (DAWNDA):

A -> D
T -> T
T -> P
A -> N
C -> F
K -> K

Notice how repeating plaintext characters don't encrypt to the same ciphertext character? T encrypts to T the first time and the second time it encrypts to P. This is the strength of the Vigenère cipher and polyalphabetic ciphers in general. These algorithms do a much better job of hiding character frequencies than simple substitution ciphers like Caesar. It's also interesting that the plaintext can encrypt to itself (like in the case of the first T above) but still we would have no idea that that was the case if we only had the ciphertext.

Now, if you've got the key and you want to decrypt the message, line your key and the ciphertext up:

D T P N F K
-----------
D A W N D A

Find the key char in the left column of the tabula recta and then (important distinction here) find where it intersects with the ciphertext char within the tabula recta. The value intersected in the top row is the plaintext character we are looking for.

So, using the key DAWNDA we find D (from this key) in the left column then we scan across that row until we find D (from the ciphertext) and see that, in the top row, A is intersected. We repeat the process with the next ciphertext letter, A, in the left column and scanning over to T which intersects T and so on until the whole damn thing is decrypted. Better settle in if you've got a lot of ciphertext.

D -> A
T -> T
P -> T
N -> A
F -> C
K -> K

There you have it. Now, see if you can encrypt and decrypt by hand our Monty Python quote with the key PYTHON. Properly encrypted the ciphertext should match this:

XDTYHVCWHBFTTLXYOYSGKLQGXMG

Though Vigenère was revolutionary and stumped crackers for over 300 years(!) it does have it's weaknesses. You can basically poke at it enough to determine a likely key length and once you have that, it starts to crumble. However, as I mentioned earlier, I wrote a 3 part series (starting here) on implementing and cracking what is basically a Vigenère cipher, called repeating key XOR. Check that out if you want more detail. In any case, this method was pretty amazing in it's day.

Modern Symmetric Cryptography

Now, let's skip a whole lot of super interesting cryptographic history and go straight to the 1970s. The dawn of modern computerized cryptography. With computers came more ways to transfer data, and with that the need for more ways to keep said data secret. We needed algorithms that worked at the bit level, could be implemented in hardware or software and couldn't (easily) be cracked by other computers. Block ciphers were one answer.

Block Ciphers

Block ciphers are encryption schemes that work on specifically sized chunks of data (depending on the algorithm). So if a block encryption cipher is said to be 128 bits that means that the algorithm encrypts your data in chunks that are 128 bits (or 16 bytes) wide, resulting in 128 bits of ciphertext. So, if your plaintext is 256 bits wide the algorithm would split it in two chunks and run the algorithm separately on each chunk. If your plaintext was some odd number of bytes, say 200, then it would first add what is called padding to the data to make it wide enough to be a multiple of 128 bits. So, the algorithm would pad your 200 bits of data to make it 256 bits wide.

Note that the method of padding may depend on the algorithm itself. Some algorithms (like AES) have different "modes" that can, among other things, change the way plaintext data gets padded. Also note that for some ciphers padding can be a source of weakness... i.e. it can leak information about the plaintext.

The two most famous examples of block ciphers are DES and AES. Let's check 'em out.

DES

Developed within IBM, the Data Encryption Standard or DES became a federally recognized standard for encryption in 1976, making it the first of it's kind. These days DES is easily crackable due to it's short key length (56 bits) and even though the length was criticized from the start it did it's duty for a lot of years and deserves some discussion.

The NSA had their hands all over this algorithm. Notably, they convinced IBM that 56 bits was long enough for keys so they could theoretically brute force crack DES ciphertexts if need be.

I hope to cover exactly how DES works in a later article but the gist is as follows:

You take 64 bits of plaintext and a 56 bit key and send those into the DES algorithm.
The plaintext bits are shuffled into a different order defined by the algorithm (the key is not in play yet).
Some code (that I'll call a "key processor") generates unique 48 bit wide permutations of the key that will be used in "the pipeline."
The shuffled bits go into a pipeline where it is processed 16 times. Each time it is processed in the same way but using one of those unique 48 bit keys generated by the key processor.
Once out of the pipeline the bits are shuffled again (like step 2)
A 64 bit block of ciphertext is outputted and appended to the previous block.
Repeat for every 64 bit block until complete.

In block cipher encryption schemes keys are usually randomly generated.

If you've got the key, you can do the exact same process in reverse to decrypt a DES encrypted ciphertext.

Now, as I mentioned earlier, the 56 bit key makes DES insecure. A key of this length means there are 2⁵⁶ (72,057,594,037,927,936) possible keys. This sounds like a lot but it turns out that this is not a huge number when it comes to computer processing speeds. DES was first brute forced in 1997 by the DESCHALL Project and it took them 96 days. It was cracked again in 1998 by Deep Crack in 56 hours. Hours! Not days. Then in 1999 distributed.net and the Electronic Frontier Foundation cracked it in 22 hours and 15 minutes. That's all over 20 years ago as of this writing and I'm pretty sure computers have advanced a bit since.

It was time for something better. What did we get?

AES

The National Institute of Standards and Technology (NIST) put out the word for all interested parties to try their hand at coming up with the next standard. Long story short, Rijndael (pronounced rain-dahl) won the day. Named after it's creators, Vincent Rijmen and Joan Daemen, Rijndael is really a whole bunch of cipher algorithms. They all work in the same fundamental way but the rules change a bit depending on the key size and block length. NIST settled on using Rijndael as defined by a single block size of 128 bits and 3 possible key sizes of 128, 192 and 256 bits. This became AES128, AES192 and AES256, respectively.

Here's an overview of how AES works (for simplicity we'll just consider AES128):

The first 128 bits of plaintext along with a random 128 bit key go into the algorithm.
Some code (that I'll again call a "key processor") generates unique 128 bit wide permutations of the key that will be used in all steps of the process.
The plaintext and a key from the key processor go into a step where they are XOR'd together.
The result and a new key permutation is pushed into the first of 9 repeating ciphers on the previous 9 ciphers. Each result is used as the plaintext for the next round along with another key from the key processor.
The result from those 9 steps then goes into a 10th step that is a slight variation from the previous ones.
Repeat for each 128 chunk of plaintext.

Now, what is happening in those ciphers in step 4 you might ask? Well without getting too far into the weeds, the plaintext is:

Run through a substitution algorithm.
The result is run through a transposition algorithm (meaning the resulting bytes are simply moved around in a defined way).
That result is run through another more complex substitution algorithm.
Finally, what we get from step 3 is then XOR'd with the current key from the key processor.

The 10th cipher simply skips step 3.

If I ever buy an iPad and an Apple Pencil I'll actually draw some diagrams to help clarify this but the spirit of this algorithm is quite similar to DES. You push the key and plaintext through a whole series of transformations and on the other end you have something that's pretty damn encrypted (assuming the implementation of AES you are using is bug free, but that's an entirely different article).

Now, why is AES better than DES?

Most importantly, the wider key makes it wayyy stronger. The time it would take to brute force a 56 bit key vs. the time it would take to brute force a 128 bit key is pretty shocking. Like, we're talking minutes vs. heat death of the universe time scales on today's computing power. Quantom computing is the main potential threat in this regard.

Secondly, and for reasons that I don't totally understand, DES was only efficient in hardware applications. NIST required that whatever would replace it be practical in both software and hardware and, apparently, AES fits the bill.

Thirdly, AES encrypts and decrypts faster. The algorithm is just more efficient.

What do we use AES for?

Since AES is fast it's usually used for encrypting large pieces of data. Like, say, your hard drive if you're using FileVault on your mac. 1password also uses AES under the hood. The NSA uses it to encrypt classified and top secret information and, when someone talks about "bank-level security" they mean AES256.

Any situation where you have a way to handle key distribution and you want something fast for large quantities of data, AES is your huckleberry.

Stream Ciphers

Because I'm tired of writing this article I'm going to leave the breakdown of what stream ciphers are as an exercise for you, dear reader. The gist though is that a stream cipher is a single key based cipher (like block ciphers) but your plaintext is encrypted 1 key bit or byte at a time. The key is "streamed" during the process, generating key bits/bytes in an unpredictable way for, theoretically, an infinite amount of time, or as long as you have plaintext.

There You Go

I hope you got something out of that. One of the craziest things to me is how these modern symmetric ciphers are compositions of a whole bunch of smaller/simpler ciphers and those smaller/simpler ciphers are typically variations on the theme of:

Substitution
Transposition
Bit manipulation (using XOR)

Before all this I would have guessed that you basically plug your key and plaintext into some uber elegant math problem and out comes a provably unbreakable (aside from brute force) ciphertext. Nope, basically you throw it through a rock tumbler of an algorithm and out comes something so tangled up you wouldn't be able to unravel it before the sun burns out.

The other wild thing is that no one has proven (and perhaps no one can prove) that there isn't some fancy math or technique that could indeed destroy DES or AES as we know it. We're just pretty sure because no one has been able to pull it off... as far as we know.

Carter Bancroft

Home

Blog

Good Books

Subscribe

Music