Experimenting with Block Ciphers

NOTE - These HTML formatted notes are significantly outdated, contain various errors now corrected, and are replaced by the current OpenOffice/PDF/Powerpoint versions. The reason for keeping this version on the site is because many relevant articles are linked directly from this version.

The Ceasar Cipher

Cryptography is a complex subject. So in order better to understand what it is now, let's start at the beginning and see how it developed.

Many children have played games using the Ceasar Cipher. This is a simple substitution cipher. Each letter in the message is substituted within the alphabet by a fixed number of positions. ROT1 means that a is changed for b, b is changed for c etc, until z is changed for a. The message HAL becomes IBM.

In order to decrypt a Ceasar Cipher, the rotation is reversed, so that b becomes a, c becomes b etc. Of course we are not restricted to using a key of 1. If we use a key of 2, during encryption a becomes c, b becomes d etc, y becomes a and z becomes b. Using a Ceasar Cipher with a key of 2 is called ROT2. 26 rotations exist, but ROT0 is a null cypher in the sense that the plaintext and cryptotexts are the same.

The advantage of having program source code is that we can experiment in a way that cuts out the manual effort.

A suitable programming language for study and experimentation purposes is Python due to its relative simplicity and ease of use. Here is an implementation of the Caesar Cipher in Python.

Caesar Cipher Implementation in Python

Source Code

caesar source view

Test Code

The programming style used by many leading Pythonistas generally involves hard coding test cases. This makes it easier to improve a program and to retest all existing components with minimum effort. The test cases also help those developing applications which use a set of library classes and functions by providing suitable examples.

def test(case="caesar"):
  # test plan consisting of a number of cases
  if(case == "caesar"):
    key=17
    plaintext="this is a message"
    cryptotext=caesar(plaintext,key)
    decrypt=caesar(cryptotext,key,decrypt=True)
    print "plaintext: "+plaintext
    print "cryptotext: "+cryptotext
    print "decrypt: "+decrypt

Test Results

rich@saturn:~/devel/cipher$ python
Python 2.4.4c1 (#2, Oct 11 2006, 21:51:02)
[GCC 4.1.2 20060928 (prerelease) (Ubuntu 4.1.1-13ubuntu5)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import ciph
>>> ciph.test()
plaintext: this is a message
cryptotext: kyzj zj r dvjjrxv
decrypt: this is a message
>>>     

The fact that the decrypt operation reverses the encrypt operation and uses the same key makes the Caesar Cypher symmetrical.

Lessons learned

We obviously wouldn't use this one for more than kids games, but how to break it shows us the beginnings of cryptanalysis.

For trivial ciphers like this one, the brute force cracking approach could involve ciphertexts being decrypted for all possible keys and checked manually for readability. For ciphers involving more keys than for which manual checking of all decrypts is feasible, the decrypts could be automatically scanned against spelling dictionaries containing language words likely to be present in the plaintext.

Developing an automated checker is left as an exercise for students.

Substitution Ciphers in General

The obvious problem with the Caesar Cipher is that the range of possible keys is trivially small. Let's suppose we don't have to rotate each letter by the same amount. This could give us a substitution table as in the following program generated example:

>>> import ciph
>>> ciph.test("gen_subst_key")
abcdefghijklmnopqrstuvwxyz
lqrzoghnfwybuitdepacxjmvks

Here I wrote a function that generated a substitution cipher key so that a in the plaintext is substituted by l in the ciphertext, b in the plaintext is substituted by q in the ciphertext etc. The program I used to generate this key made sure that the substitution key contains every letter in the alphabet exactly once. The encryption key is the 26 character string:

lqrzoghnfwybuitdepacxjmvks

How many possible values for this key are there ? If a letter is allowed to substitute as itself, there are 26 possible substitutes for a, 25 for b and 1 for z: 26 x 25 x 24 ... x 1 or factorial(26) which gives: 403291461126605635584000000 possible values. This is the number of possible ordered permutations of the set of all characters in the range a-z. In practice I am going to use factorial(25) possible keys, because it might not be a good idea to allow a character to substitute for itself.

Substitution key generation

Source Code

Generating a valid key as in the above example needed a little more coding than the cipher itself.

gen_subst_key source

This doesn't guarantee that z will substitute to a different letter, but does guarantee all other letters will. Modifying this code to remove this bug by testing the value given to z and swapping this with another letter if it does map itself to avoid this problem is left as an exercise for the reader.

Test Code

  elif case == "gen_subst_key":
    print alphabet
    print gen_subst_key()

Test Results

test case: gen_subst_key
abcdefghijklmnopqrstuvwxyz
nofgvuadhlreywpcsqtmbkxjiz
press enter to continue

Source code for the substitution cipher

subst source

Test Code

  elif case == "subst":
    key=gen_subst_key()
    plaintext="the quick brown fox jumps over the lazy dog"
    ciphertext=subst(plaintext,key)
    decrypt=subst(ciphertext,key,decrypt=True)
    print "key: "+key
    print "plaintext: "+plaintext
    print "ciphertext: "+ciphertext
    print "decrypt: "+decrypt 

Test Results

test case: subst
key: rslwjpobnydkhauxcmivtgzefq
plaintext: the quick brown fox jumps over the lazy dog
ciphertext: vbj ctnld smuza pue ythxi ugjm vbj krqf wuo
decrypt: the quick brown fox jumps over the lazy dog
press enter to continue

Weaknesses of substitution ciphers

This approach is stronger than the Caesar cipher in the sense that there is a very much greater number of possible keys. Of course a 26 character key is harder to remember. Any single letter substition cipher is going to be vulnerable to letter frequency analysis. In the English language, letters 't' and 'e' occur more frequently than letters 'q' and 'z'. An attacker having access to enough cryptotext can work out its letter frequency and start making guesses, starting with the cryptotext letters that occur most or least often.

You might want to include punctuation within the alphabet or better still get rid of punctation altogether by compressing the input message. Or you might consider treating the alphabet as being all possible values for an 8 bit byte. Compressing the input gives you the advantage of balancing the plaintext letter frequency. The fact that the letter 'r' occurs on its own in the cryptotext above gives the game away as the only single letter word in English is 'a'. Without input compression, the character frequency attack still exists, in the sense that each input plaintext character still substitutes for the same output ciphertext character. The above approach also still suffers from the weakness of allowing punctuation to go straight through unchanged from the plaintext to the ciphertext.

Transposition Ciphers

In the substitution ciphers described above, the encoded information for each letter in the plaintext was contained within its own position within the ciphertext. In a transposition cipher, the positions of letters are swapped for each other based on the key. A trivial example of a transposition cipher might swap letters with odd and even positions with each other.

Plaintext:  this is a message

Ciphertext: htsii  s aemssga e

Of course just swapping odd and even positions in blocks of 2 is weak, but this illustrates the concept. Also, punctuation if included within the plaintext, has to be handled as part of the encrypted message. Decryption simply involves reversing the swaps. Another feature of this is that because the plaintext had a message size of 17, which was not a multiple of the blocksize, which is 2, the message had to be padded with an extra space prior to encryption, so that the message to be encrypted would be an exact multiple of the blocksize.

In our general purpose substitution cipher our key was effectively a substitution table, giving a replacement for each character in our alphabet, such that every replacement character was used to replace exactly one letter in the alphabet, so that no information would be lost during a complete encrypt decrypt cycle. If during encryption, a single replacement letter had been used for more than one plaintext letter, then decryption could not have been done without losing some of the letters in the original message.

If we construct a replacement table showing for each block of plaintext characters the positions these are swapped into, and each from and to positions are used exactly once, this transposition will also not lose any information and is reversible. Let's suppose we count the positions in each block 0-9 and use blocks of 10 characters. This gives us 10 x 9 x 8 ... x 1 possible keys which is factorial(10) or 3628800. In practice to avoid characters replacing themselves you would use factorial(9) possible keys. This is the number of possible ordered permutations of the set of numerals 0-9.

In a production environment we might be better off using a larger block size, but having a numeric key with 10 digits makes this easier to process and see what is happening for now, as the decimal digits in this key gives us the transposition table directly. Also to avoid the end of the message being more obvious, and this making the key easier to discover, we are going to transfer the message size along with the ciphertext, and pad the message with random characters to an exact multiple of the blocksize before encryption. Using the message size, we will be able to strip the extra padding following decryption.

The transposition key generation function

Source Code

Test Code

  elif case == "gen_transp_key":
    blockpos="0123456789"
    print blockpos 
    print gen_transp_key()

Test Results

test case: gen_transp_key
0123456789
4670281539
press enter to continue

The padding function

Source Code

Test Code

  elif case == "pad":
    message="this is a message not of multiple 10"
    padmessage=pad(message,10,len(message))
    stripmessage=pad(padmessage,10,len(message),pad=False)
    print "message: "+message 
    print "length of message: "+str(len(message))
    print "padmessage: "+padmessage 
    print "stripmessage: "+stripmessage 

Test Results

test case: pad
message: this is a message not of multiple 10
length of message: 36
padmessage: this is a message not of multiple 10gryj
stripmessage: this is a message not of multiple 10

The transposition function

Source Code

Test Code

  elif case == "trans":
    plaintext="prime numbers may contain the secrets of the universe"
    key=gen_transp_key()
    padplain=pad(plaintext,10,len(plaintext))
    ciphertext=trans(padplain,key)
    decryptpad=trans(ciphertext,key,decrypt=True)
    decrypt=pad(decryptpad,10,len(plaintext),pad=False)
    print "key: "+key
    print "plaintext: "+plaintext
    print "length of plaintext: "+str(len(plaintext))
    print "padplain: "+padplain
    print "ciphertext: "+ciphertext
    print "decryptpad: "+decryptpad 
    print "decrypt: "+decrypt 

Test Results

test case: trans
key: 3905871624
plaintext: prime numbers may contain the secrets of the universe
length of plaintext: 53
padplain: prime numbers may contain the secrets of the universepzhvhih
ciphertext: mbp murnie oeac rysmi n ehttanrfsto esceee uvitnh phrhihsvez
decryptpad: prime numbers may contain the secrets of the universepzhvhih
decrypt: prime numbers may contain the secrets of the universe

Weaknesses of transposition ciphers

Just as substitution ciphers are susceptible to letter frequency analysis, transposition ciphers are susceptible to letter adjacency analysis. In English, certain letter pairs are unlikely and some are very likely. For example the letter 'a' is unusual in that it can be followed by any other letter - but some combinations e.g. the dipthong "ae" as in "Caesar" are much less common than the pair "oa" as in "broad". "Q" is almost always followed by "u", and some pairs almost never occur, e.g. "jk" as in Dijkstra. Pairs "th" and "ch" are common. A frequency analysis of enough letter pairs seperated by 0 .. n other characters within the cryptotext is likely to disclose a blocksize much less than n.

A first block cipher attempt

For this cipher, we are going to first substitute the plaintext letters, and then transpose them. The decryption will reverse this sequence. This is easy, as we already have the substitution and transposition functions needed. The key required for this cipher will be a string combining a transposition table key and a substitution table key, with a comma between the 2.

Source Code

Test Code

  elif case == "block":
    # generate combined key
    skey=gen_subst_key()
    tkey=gen_transp_key()
    key=skey+","+tkey
    plaintext="the quick brown fox jumps over the lazy dog"
    ciphertext=block(plaintext,key)
    decrypt=block(ciphertext,key,decrypt=True)
    print "key: "+key
    print "plaintext: "+plaintext
    print "ciphertext: "+ciphertext
    print "decrypt: "+decrypt 

Test Results

test case: block
key: qiacyjnohkzuftmreslvwdxgbp,2739185406
plaintext: the quick brown fox jumps over the lazy dog
ciphertext: 43,ya  ozwevhmmx sg tijfdrswy lkmopy vbu  qnvqlmfzace
decrypt: the quick brown fox jumps over the lazy dog

ciph.py

The program snippets described above are downloadable. Students are encouraged to download and run this program during a tutorial session.

Just because the ciphers combined above would be difficult to decrypt manually without knowing the key doesn't mean a computer cracking program couldn't make very short work of them. Unfortunately there is too much of this kind of software being sold whose distributors seem to have little idea of the risks being taken and who manage to persuade naive customers that this kind of toy can be used for protecting confidential information. If this particular crypto learning toolkit encourages you to develop a program which automatically cracks the ciphertext and uncovers the key, or which exploits some of the weaknesses in the key generation algorithms, do please let me know.

Comments

Questions

Q. Why can't we assume that the algorithm can be kept secret ?

A. If very few people use a program that implements a particular algorithm, it might be possible to keep this a secret. However, if just one copy of a program that implements this algorithm gets into the hands of an determined attacker, then every instance of this program would then be compromised, if the security of the system doesn't depend upon other secrets, i.e. the encryption/decryption keys.

It is obviously a lot cheaper to change the key if a key is disclosed or lost, than to install new software or cryptographic hardware every time one instance of a program or machine in wide use is obtained by an attacker. The fact that reverse engineering is possible makes it unwise to rely on the secrecy of the algorithm to protect the secrecy of messages encrypted using this algorithm.

Q. Wouldn't it improve security if the algorithm could be kept secret ?

A. Firstly this presumes that an attacker can't obtain an instance or couldn't reverse engineer one if he did obtain one.

A more serious problem is that the users of a system which has not yet been cracked can never be sure about how easy or difficult it might be to crack it, and a system that has been cracked isn't useful. Even if all the world's best cryptanalytic talent tries their hand at cracking a system and honestly report that they have not yet succeeded, this still doesn't guarantee that noone else will try their hand at cracking this system and succeed where others have failed.

The level of confidence that can be obtained in a system is dependent upon the amount of talent unsuccessfully directed towards trying to break it so far. If an algorithm is successfully kept secret this reduces the critical review of this system, which reduces the level of confidence anyone can objectively have in it.

For futher reading see Kerckhoffs' principle.

One Time Pad

This approach to cryptography is very simple, and in some contexts provably secure. The idea is that the key has the same length as the plaintext. The key must never be reused. If the key is entirely random, it can be used to encrypt the plaintext, e.g. by combining the key and plaintext using a bitwise sequence of XOR (exclusive OR) boolean operations. The message recipient, if able to XOR the key material with the ciphertext in the same sequence as it was combined, is able to recover the plaintext.

plaintext bits 1 0 1 0
key bits 0 0 1 1
ciphertext bits 1 0 0 1
decrypt bits 1 0 1 0

In practice the need to use the key once and once only, to destroy the key securely after use and to have the same quantity of key material available as messages to be transmitted shifts the security requirement from keeping the message transmission channel secret to keeping the key distribution channel as well as all points of key storage secret. In most situations this doesn't give any useful security advantage. This technique might be used in situations where opportunites exist securely to transfer key material between secure storage locations in one direction, e.g. between a government and one of its embassies abroad, where urgent messages may need transmitting in the opposite direction using an insecure channel when no trusted courier is available, or more quickly than the courier can travel.

Stream Cipher

The idea of a stream cipher arises from the need to use communications channels in such a manner that the optimal packet sizes within the communication channel do not correspond to multiples of the block cipher blocksize. The way in which a particular bit sent to the communications channel is encrypted will depend upon how previous bits were encrypted. In this sense, a stream cipher might be considered stateful. One approach is for a random nonce (number used once) to be appended to a timestamp and hashed together with a shared secret key at both ends of the communications channel.

This hash value can then be used to seed a cryptographically strong pseudo-random number generator, based on the use of a block cipher. The pseudo random number sequence could then be used to encrypt and decrypt the message stream in a manner similar to the one-time pad.

The Data Encryption Standard

This block cipher has been in use since the 1970ies, having been approved as a US Federal Information Processing Standard in 1976. It uses a 56 bit key and 64 bit message blocks. Internaly DES uses a Feistel network which has the advantage of using the same permutation and shuffling algorithms in the encrypt and decrypt stages, but with the subkey sequences reversed. This makes building custom DES hardware relatively cheap, and makes DES software simpler to program and validate.

DES is no longer considered secure against attack using a moderate sized network of modern computers. The Electronic Freedom Foundation built custom hardware in 1998 for $250,000 which could brute force DES in a few days. More recently it was discovered that minor changes to the DES design would have made it much less resistant to differential cryptanalysis which implies that this technique of code breaking was known about at the time DES was designed.

Triple DES

In order to make DES more resistant to brute force attacks, Triple DES was developed. This involves 3 chained DES processes, and uses 3 x 56 bit single DES subkeys making a 168 bit key. This is believed to give effectively 112 bits of security in response to meet in the middle attacks. Triple DES enabled older DES hardware to continue in use for longer, and is cheaper to implement in hardware than the stronger AES block cipher.

AES The Advanced Encryption Standard

AES was developed in the late 1990ies and became a standard in 2002. It uses a 128 bit blocksize and a keysize of either 128 or 192 or 256 bits, involving 10, 12 or 14 rounds, or stages of encryption or decryption respectively. AES which is also known as Rijndael, uses a substitution permutation network.

Some Recommended Reading on Block Ciphers