A long post today, we’ll recap of classic ciphers, look at the history of modern symmetric ciphers. Finally we’ll look at entropy, a way of telling if you actually have the real plain text after you have cracked a cipher.

Classic Ciphers

First let’s review encryption as we know it so far:

• Steganography – hiding messages in plain site
• Codes – substitution of words or letters for other letters, numbers or symbols.
• Old school ciphers, these were symmetric – the same key was used to encode and decode. These became quite good, but are no match for computers.

So we don’t use these anymore, but they can still be used at the end of our encryption process if we think they will add value.

New School

Asymmetric encryption is secure and stands up to computers, but it is hard to do and slow, it uses A LOT of computer power.

Is there a middle ground? YES!

1. The enigma machine was an early attempt, with lots of mechanical jumbling to make it more confusing and being mechanical it helped the operator do it and reduced errors. The cryptologists that worked on enigma believed it would be cracked within a year.
2. Session keys – also used by the Germans as their ‘daily code’ or machine initialisation settings on the Enigma. We do this with web sessions, a session key is shared via the public key, then that session key is used to communicate. Ah ha, I wondered about when we looked at RSA in Asymmetric Cryptography. Not only does this reduce computer time, but it actually increases security. A pair using a public-private key is only secure one way because anyone with the public key can decrypt the private key message. Now we just need secure asymmetric encryption.

History of Modern Symmetric Ciphers

Mechanical encryption was great in the age of pen and paper, but not in the age of computers. But things didn’t change much in the world of encryption after WWII until the 70s. Once banking started happening remotely and they wanted more security, cryptography became an academic field. NIST (National Institute of Standards and Technology) got involved in creating an encryption standard – they didn’t know what it would look like so they opened it out for  submissions. They received a submission after a while, Lucifer from IBM, which became DES (Data Encryption Standard). 

The NSA (The US National Security Agency) had a look and suggested a couple of tweaks to the s-boxes (these contribute to confusion, which makes it harder to work out the key from the ciphertext) and p-boxes (these contribute to diffusion, making it harder to work out the plaintext from the ciphertext). Until this time, no one really knew about the NSA and their involvement raised eyebrows. No-one knew why they made the tweaks or what the tweaks did, but the tweaks were adopted.

It was in use until the 90s until a few mathematicians were sure they could crack it with differential analysis. Until they realised that the NSA tweaks back in the 70’s protected against this attack!!! The NSA were at least 20 years ahead of civilians!  This sparked an increased interest in encryption and AES was soon developed.

Entropy

If we are cracking a cipher, we may get something that looks like English, but how do we know it is the actual plain text and not just a random output that looks like English? We can look at the entropy. For example a message 100 characters long.

• How many possible messages (actual English words)? 
  • English has about 20,000 words, average word length is ~5
  • So 20 words in 100 chars
  • 20,000²⁰ ~ 10⁸⁶
  • Note this is just real words, not looking at sentence structure
• How many possible keys (key space) – this is the possible number of keys for the system
  • Assume for Enigma, 6 rotors (10⁶) and the plugboard (10^14) so 10²⁰ possible keys
• How many different messages in total (just combinations of letters)?
  • 26¹⁰⁰ ~ 10¹⁴¹

So we have (10¹⁴¹ ÷ 10⁸⁶) 10⁵⁵ more random combinations than legitimate words. This is A LOT. 

Now we look at the key space. 10²⁰ keys is a lot less than 10⁵⁵ illegitimate combinations. From this we can deduce if the keyspace is smaller than the number of illegitimate combinations, we can assume that once we get an English plain text, we have the message!

Making it harder

What if we made it harder? What if we made it hard to tell if they had cracked it? With a larger keyspace, we could have more than one English plaintext and confuse the adversary.

A one time pad is an example of this, the keyspace is as big as the message. It is a perfect cipher.

Reflection

We can use a combination of asymmetric and symmetric ciphers for secure communication. We use an asymmetric cipher to establish our shared secret, then use a secure symmetric cipher for our communication. We can analyse the keyspace to determine if we have the actual plaintext. If the keyspace is less than the number of illegitimate combinations (total combinations – legitimate English word combinations) then we assume the first English plaintext is the original message. We can make our encryption harder to crack by increasing the keyspace.

And finally – the NSA were at least 20 years ahead of the rest of the world on encryption. So far advanced that they were able to suggest tweaks to the latest encryption to improve its security. These tweaks wouldn’t be understood for 20 years.

*English = whatever language your are decrypting.