The Basics of Crypto 4: Block Ciphers

Block cipher encryption systems are some of the most commonly found encryption systems in use today. Both AES and DES are block cipher encryption schemes with the former being developed in Belgium and the latter by the National Institute for Standards and Technology (NIST) in America. There are many other block cipher encryption schemes however these two are probably the most well known.

What is a Block Cipher

A block cipher consists of an algorithm that takes a plaintext of a specific size and performs an operation on it to encrypt it using a key (key size is normally equal to the block size) and decryption is the reverse where the cipher text and key is provided to the algorithm to return the plaintext.

Hint: Encryption: Ciphertext = Encryption-function(key, plaintext) Decryption: Plaintext = Decryption-function(key, ciphertext)

When implementing a block cipher it is important to select a scheme where the output of the algorithm is indistinguishable from random data, that there is no way to recover the key. Neither AES nor DES satisfy these requirements in totality so care must be given to the implementation of the system.

When implementing a block cipher crypto system it is important to select a suitable block size. Larger block sizes will increase resource overhead whilst smaller block sizes are easier to bruteforce all combinations and perform a lookup attack.

Hint: A lookup attack works on the basis that a block cipher given the same inputs will produce the same outputs, so if the key size is relatively small then it is possible for an attacker to compile a list of every potential ciphertext with it's corresponding plain text ahead of time and then compare a given ciphertext to this list to discover the plaintext.

A block cipher with a 16 bit block size has a lookup table (every single possible ciphertext) totalling 128KB. 128KB is easy to generate and can then be used to decrypt all other ciphertexts and retrieve the plaintext with relative ease. However using a 64bit block size has a lookup table which is 128 exabytes in size, this makes using a lookup table attack impractical and as such lookup table attacks are not a problem for larger block sizes.

Modes of Operation

In earlier installments of this series we covered how modes of operation allow symmetric key crypto systems to encrypt data of any length. In this section I will be covering some of the more common modes of operation and some of the things best avoided when implementing these systems. We shall start with the simplest AES mode of operation, the electronic codebook.

Electronic Codebook (ECB)

Electronic Cookbook (ECB) is the most basic of modes of operation and is essentially just "do nothing but the default AES algorithm" and as such is widely known for not being very good. ECB does not look at previous or following blocks and as such with the same input you get the same output, this means that blocks of repeating data are easily identifiable. So say if you encrypt an image file, coloured sections will come out identical, meaning the image will retain it's shape. This was done as an example of why ECB was bad through encrypting an image of the Linux penguin. Image below:

Cipher Block Chaining (CBC)

Cipher Block Chaining (CBC) is similar to ECB but better. CBC mode encrypts a block with a key in the exact same way as ECB does except that it then XOR's the block with the previously encrypted block. As you can probably imagine there is no previous block for the first block to be XORed against and as such CBC mode takes a random value equal to the block size called the initialization vector (IV) and this block is used for the first encrypted block to be XORed against. This ensures each ciphertext block is dependent on the previous block ensuring repeating data doesn't appear as identical blocks throughout the cipher text. The use of unique IV's for each ciphertext guarantees that no plaintext encrypted twice will generate the same ciphertext. These two benefits alone make CBC a dramatic improvement in security over ECB.

Padding: It is important to point out here whilst we are discussing block ciphers what padding is. A block cipher requires a set data size to be encrypted in order for the algorithm to work. As such if the data set to be encrypted is not the expected size it must be padded to fit in such a way that when decrypted it is obvious which bytes are padded. There are numerous padding schemes but we will quickly cover PKCS#7 as it is the most popular. PKCS#7 is simply "if padding by X bytes each byte should have the value X". So if you had a string that was "AAAAAA" and you wanted to pad it to 8 bytes you would use "AAAAAA22" since you need 2 additional bytes of padding.

The Counter (CTR) Mode

CTR mode is used to turn a block cipher into a stream cipher and many people believe this to be the only sensible and secure way to implement a block cipher. CTR mode uses a combination of counter and nonce to produce a random string of equal length to the plaintext and then XOR's the random string along with the plaintext similarly to how the one time pad works. The string is made up of a nonce and counter. For example, a 16 byte block cipher might use the high 8 bytes as a nonce, and the low 8 bytes as a counter. These bytes would then be expanded through repetition and incrementation of the counter bytes (just assume it is +1 each incrementation for this example) until the bytes were of equal length to the plaintext.

Next we go on to stream ciphers proper.