In part one of this series, we saw how Julius Caesar used a simple alphabet shift (substitution) to encrypt his messages, and how the German Enigma machine was used to securely communicate during World War 2. Next we'll see how computers changed the way in which we communicate, and thus how we secured such messages.
The digital age
With the advent of digital technology, instead of relying on alphabets, we suddenly shift gear and start using binary representations for characters. The American Standard Code for Information Interchange (ASCII) is one such standard which translates English characters (and punctuation) into electronic binary representation i.e. ones and zeros. With binary signals (streams of binary) such as this, most modern ciphers make use of the XOR (exclusive-OR) function.
The XOR logic gate takes two inputs which are either 1 or 0. The logic in an XOR logic gate says that if both the inputs are the same value (i.e. "1 and 1" or "0 and 0") output "0", and where they are different output "1".
To encrypt the plaintext with the key all we need to do is apply the XOR function to each sequential and corresponding value in the plaintext and the key respectively, to get
Even though the plaintext is very regular, you can see that it's totally illegible as ciphertext, which is desirable as it masks completely the structure of our plaintext message. In fact, statistically speaking, it should have the same entropy (randomness) as the key. So, so long as the key is random, so will my ciphertext appear equally random and unintelligible.
Now, if we XOR the ciphertext with the key again, in the same way as we did when we encrypted it, we get…
My plaintext! Wahoo!
For this reason XOR is widely considered the only truly unbreakable crypto-scheme in terms of cryptanalysis since the only method of breaking it is brute force, hence it is used as the rock solid basis for building more practical ciphers. However it suffers from one problem: the key needs to be the same length as the plaintext. This means that every message we want to transmit needs to be accompanied by (or have previously shared) a key of the same size… which rather defeats the point. Added to the fact that reusing a key provides attackers with a treasure-trove of information, the use of One-Time-Pads such as this are too impractical to be of much use.
So we cheat!
Having keys as long as the plaintext while 100% secure, is not a great solution to the mass encryption of any data. After all, to encrypt a 500Gb harddrive you'd need another 500Gb harddrive to store the key! To tackle this most ciphers use key expansion techniques to create multiple variations of a much shorter key while retaining all the random qualities we like in our keys. So long as the key expansion is done the same way during encryption as it is in decryption, the algorithm will always be able to reproduce the same stream of random gibberish as the key. One of the more popular modern ciphers, and one that uses key expansion, is DES.
The DES (Data Encryption Standard) cipher was originally conceived in 1975 (and published in 1977) as a result of a US government computer security request. The processing of DES is reasonably simple, but the use of computers and silicon chip meant that already complex scrambling could be automated and combined. The key in a DES cipher is effectively 56bits (a string of 56 ones and zeros) long (the other bits bulking the key to 64bits are used as error checking to make sure the key hasn't been tampered with, or corrupted in transmission). Let's take a look at the steps in the DES algorithm:
1) Initially the DES cipher cuts the plaintext into "blocks" of 64-bits.
2) Each 64-bit block is then processed in as two 32-bit chunks, each half alternately through the following encryption function.
3) Feistel function (F-function)
a. First we combine the 32-bit plaintext chunk with the key using an expansion mechanism (to make them both the same length) and a XOR function.
b. A substitution cipher is then applied to each 6-bit chunk by individually configured functions (called S-boxes), much the same as an Enigma rotor. This results in a 4-bit chunk for each S-box being generated.
c. The output of each S-box is then rearranged using a permutation cipher (called a P-box), much like the Caesar Cipher, so everything is totally scrambled.
4) Step 3 is then repeated 16 times, feeding the output of one round, into the input for the next.
In case your brain hadn't already tuned to mush, and to add further complexity to the algorithm, the key used in the F-function is itself scrambled during each round through a series of transpositions, in much the same way as the rotors in the Enigma machine sequentially rotated against each other.
One major advantage to DES over many other similar ciphers is that to decrypt a DES encrypted message you simply feed the ciphertext with the key into the same function (albeit with a reversed key transposition) and #tada# out pops the plaintext!
O'Connor, Lynam and Clarke
In 1998 it was decided that DES was too easy to brute-force, and so developed a scheme called Triple-DES (or 3DES). In this scheme, the DES function is sequentially applied three times, with three different keys. Interestingly though it is configured so that the algorithm is run in encrypt, decrypt, encrypt rather than encrypt, encrypt, encrypt. This was chosen so that 3DES silicon can effectively perform single DES functionality by using the same sub-key for each step, providing support for legacy systems that used DES with the same silicon.
3DES is used for most electronic payments, and is used in the EMV standard which is what Chip-and-PIN uses. In fact in my experience many retail banks are still reliant on 3DES for much of their secure communication and storage. There are still some commercial applications that make use of 3DES, but they are becoming few and far between mainly due to a better and more secure alternative.
So we've seen the beginnings of digital cryptography with the introduction of XOR for encryption and DES as a cryptographic standard, and we can see how mechanisms we saw in Part One (substitution and permutation) are still being used in these ciphers. Next time we'll look at the equivalent mechanisms being used to protect your data both at rest and in transit as you conduct business over the internet.