Block Ciphers

"The security of the encryption scheme must depend only on the secrecy of the key, and not on the secrecy of the algorithm." - Kerckhoff's Principle.

Introduction

Computers encrypt messages in binary format regardless of the symbols being represented. In other words, a message is reduced to a set of 0's and 1's via a standardized mapping such as ASCII (American Standard Code for Information Interchange) and then those 0's and 1's go through a series of transpositions and substitutions according to some encryption algorithm being used.

The block cipher encrypts a batch of plaintext symbols into an equal length of ciphertext symbols. The advantages of a block cipher are diffusion where bits or bytes are dispersed throughout the cipher text such that a single change of one bit affects the position of multiple bits during subsequent rounds. This is called the avalanche effect. The only drawbacks to block ciphers are that they are time consuming, compared to stream ciphers, and errors can spread easily such that one error can cause an entire block to be misinterpreted.

Feistel Cipher

Horst Feistel, who emigrated to the U.S. from Germany in 1934, came up with the Feistel Cipher, which was named "Lucifer". Horst did endure a rough time during WWII and was also constantly pressured by the NSA during the 1950's and 1960's. However, during the 1970's, Horst was able to build his cipher while working at IBM. The Feistel block cipher a.k.a. Feistel classical network underpins basically all modern symmetric block encryption algorithms such as DES because it can be adapted to defend against new cryptanalytic attacks. The Feistel classical network is based on Shannon's substitution-permutation process. This skeletal cipher can save time in designing a new cipher because it already has a provably strong defense base. Totally new cipher designs could be subjected to new types of attacks that could probably be thwarted off by a Feistel classical network.

Encryption

The Feistel Cipher takes a plaintext block as input and divides it in half to produce a left side L_n and a right side R_n. During encryption the R_n goes through the mangler function along with the round key. That result then gets Xor'ed with the L_n and then becomes the new right side R_n+1 of the output ciphertext. The original right side R_n then becomes the new left side L_n+1 with no transformation as shown in figure 1 below. Encryption is described as:

 Ln+1 = Rn
 Rn+1 = Ln Å f(Rn, Kn+1)

Decryption

For decryption the left side L_n+1 of the ciphertext block becomes the new right side R_n of the plaintext block and gets fed into the mangler function along with the round key. That result is Xor'ed with the right side R_n+1 to produce the new left side L_n as shown in figure 2 below. Decryption is described as:

 Ln = Rn+1 Å f(Ln+1, Kn+1)
 Rn = Ln+1

Figure 1, Encryption Round.   Figure 2, Decryption Round.
 

The Feistel cipher process can be applied repeatedly to produce a greater scrambling effect. The most unique aspect of the classical Feistel network is that any complex mangler function can be used. The mangler function, as described in more detail in the DES section for one particular type, provides the necessary confusion and diffusion techniques, and the inter-workings of the mangler function can be performed in the same order for both encryption and decryption.

DES

DES (Data Encryption Standard), first adopted in 1977 by the NIST (National Institute of Standards and Technology), is a widely used encryption cipher. DES encryption and decryption is a symmetric iterated block cipher process in that only one key is used to encrypt and decrypt the same message. Each round is based on the Feistel network of switching each half of the input but only one of the halves undergoes the mangler function. There are five steps to performing DES:

(1) Generate per round keys

(2) Initial Permutation

(3) 16 Mangler Rounds

(4) Left-Right Swap

(5) Inverse Permutation

Mangler Function

1. The mangler function first expands R_n (the right half of the input) from a 32-bit value into a 48-bit value, by breaking R_n into eight 4-bit chunks and expanding each of those chunks into 6-bits.

2. The 48-bit key K_n is broken down into eight 6-bit chunks and Xor'ed with each R_n 6-bit chunk.

3. This 6-bit output is then fed into one of eight S-boxes, which produces a 4-bit output. Each set of 6-bits has its own S-box. For example the 6-bit string 101101 uses its first 1 and last 1 to determine the row and the 2^nd through 5^th symbols to determine the column within the S-box table.

4. All eight 4-bit outputs are combined into a 32-bit quantity whose bits are then permuted to ensure good diffusion and the avalanche affect.

Key Expansion

Initially a permutation is performed on the key. Next, for each round, the key undergoes a bitwise left circular shift and a permutation to produce an output (essentially a sub-key) that's applied to the complex function (as described above). Each sub-key is different because of the repeated bit shifts.

Triple-DES

Considering Moore’s Law, DES has been vulnerable to a brute-force attack because of its small key size of 56-bits. A Double DES approach sounds good because two 56-bit keys are used, therefore increasing the key size to 112 bits. However, given a known plaintext-ciphertext pair a "meet-in-the-middle" brute force attack can be achieved by only a factor of two. One can initially encrypt the plaintext with all 2⁵⁶ possible key values (where one result is a matching decryption of the ciphertext). An adversary can then decrypt the ciphertext using all possible 2⁵⁶ key values until a result matches the encrypted plaintext. Then the key can be obtained.

As a result Triple DES came about. The DES algorithm is used in sequence three times in an Encrypt-Decrypt-Encrypt fashion for encryption and for decryption the inverted D-E-D is used. Triple DES uses two 56-bit keys, for instance when encrypting a plaintext, key one is used, key two, and then key three is used for the E-D-E process respectively. Conceptually, a message is scrambled from the first key, it then gets even more scrambled with the second key, and then scrambled yet one more time with the first key to produce the final ciphertext.

AES

AES can also be referred to as the American Encryption Standard. The NIST (American National Institute of Standards and Technology) began an international competition in 1997 with the goal of setting a new symmetric encryption standard to surpass DES. By 1999 only 5 out of 15 competitors remained: MARS of IBM, RC6 of RSA Labs, Serpent of Ross Anderson, et. al., Twofish of Bruce Schneier et. al. and finally Rijndael of Joan Deamon & Vincent Rijmen from Belgium, who actually won the competition. Rijndael was chosen as the standard because it had the best combination of security, efficiency, performance, flexibility and is easy to implement.

AES Process

Not every detail of AES is covered here. However, the entire specification for AES can be found at the NIST web site under FIPS 197 at http://csrc.nist.gov/publications. AES is a restricted version of Rijndael. Rijndael is a symmetric block encryption cipher that actually does not build upon the classical Feistel network. Rijndael takes a variable input size of 128, 192 or 256-bit word along with a variable key size of either 128, 192 or 256 bits. All combinations of block and key lengths are possible, however. A block of plaintext is encrypted via several rounds with repetitive variable functions. The total number of rounds depends on block and key lengths as described in the following table:

Block length =	128	192	256
Key length 128	10 rnds	12 rnds	14 rnds
Key length 192	12 rnds	12 rnds	14 rnds
Key length 256	14 rnds	14 rnds	14 rnds

Links

http://www.schneier.com/paper-unbalanced-feistel.html
http://www.x5.net/faqs/crypto/q56.html
http://www.cs.sjsu.edu/faculty/stamp/SecurityEngineering/chapter5/feistel.html
http://searchsecurity.techtarget.com/sDefinition/0,,sid14_gci213893,00.html
http://www.rsasecurity.com/rsalabs/faq/2-1-4-1.html

http://www.eff.org/Privacy/Crypto_misc/DESCracker/

http://www.eff.org/DEScracker/

http://www.itl.nist.gov/fipspubs/fip46-2.htm

http://searchsecurity.techtarget.com/sDefinition/0,,sid14_gci213893,00.html 

http://csrc.ncsl.nist.gov/cryptval/des/des.txt

http://www.x5.net/faqs/crypto/q56.html

http://www.geocities.com/SiliconValley/Code/4704/Feistel.html

http://www.bletchleypark.net/crypt/aes_header.txt
http://www.bletchleypark.net/crypt/aes_cpp.txt
http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf
http://csrc.nist.gov/encryption/aes/aesfact.html
http://csrc.nist.gov/encryption/aes/rijndael
http://csrc.nist.gov/encryption/aes/rijndael/Rijndael.pdf