Block Ciphers

The most important symmetric (meaning the same key is used for both encryption and decryption) algorithms are block ciphers. The general operation of all block ciphers is the same - a given number of bits of plaintext (a block) is encrypted into a block of ciphertext of the same size. Thus, all block ciphers have a natural block size - the number of bits they encrypt in a single operation. This stands in contrast to stream ciphers, which encrypt one bit at a time.

Any block cipher can be operated in one of several modes, defined in FIPS PUB 81. These diagrams are adapted from that document.

Electronic Codebook (ECB) Mode

ECB is the simplest mode of operation for a block cipher. The input data is padded out to a multiple of the block size, broken into a integer number of blocks, each of which is encrypted independently using the key. In addition to simplicity, ECB has the advantage of allowing any block to be decrypted independently of the others. Thus, lost data blocks do not affect the decryption of other blocks. The disadvantage of ECB is that it aids known-plaintext attacks. If the same block of plaintext is encrypted twice with ECB, the two resulting blocks of ciphertext will be the same.

Cipher Block Chaining (CBC) Mode

CBC is the most commonly used mode of operation for a block cipher. Prior to encryption, each block of plaintext is XOR-ed with the prior block of ciphertext. After decryption, the output of the cipher must then be XOR-ed with the previous ciphertext to recover the original plaintext. The first block of plaintext is XOR-ed with an initialization vector (IV), which is usually a block of random bits transmitted in the clear. CBC is more secure than ECB because it effectively scrambles the plaintext prior to each encryption step. Since the ciphertext is constantly changing, two identical blocks of plaintext will encrypt to two different blocks of ciphertext. The disadvantage of CBC is that the encryption of a data block becomes dependent on all the blocks prior to it. A lost block of data will also prevent decoding of the next block of data.

CBC can be used to convert a block cipher into a hash algorithm. To do this, CBC is run repeatedly on the input data, and all the ciphertext is discarded except for the last block, which will depend on all the data blocks in the message. This last block becomes the output of the hash function.

Feedback Modes

Output Feedback Mode (OFB) converts a block cipher into pseudo-random number generator. The output ciphertext is feed back into the input of the block cipher, and this process is repeated to produce a stream of pseudo-random bits. The bit stream is completely determined by the algorithm, the key, an initialization vector, and the number of bits (k) feed back into the cipher during each step. The stream of bits can then be XOR-ed into the plaintext to produce ciphertext, effectively converting the block cipher into a stream cipher.

Cipher feedback mode (CFB) differs from OFB in that the ciphertext (after the XOR step) is fed back rather than the output of the block cipher (before the XOR step). A block cipher operating in CFB mode can't be used as a random number generator.

Neither of the feedback modes is of much interest in common cryptographic applications, since dedicated stream ciphers exist which are much faster.

Feistel ciphers

• H. Feistel, "Cryptography and Computer Privacy," Scientific American, v. 228, n. 5, May 73, pp. 15-23.

The next diagram shows the general design of a Feistel cipher, a scheme used by almost all modern block ciphers. The input is broken into two equal size blocks, generally called left (L) and right (R), which are then repeatedly cycled through the algorithm. At each cycle, a hash function (f) is applied to the right block and the key, and the result of the hash is XOR-ed into the left block. The blocks are then swapped. The XOR-ed result becomes the new right block and the unaltered right block becomes the left block. The process is then repeated a number of times.

The hash function is just a bit scrambler. The correct operation of the algorithm is not based on any property of the hash function, other than it be completely deterministic; i.e, if it's run again with the exact same inputs, identical output will be produced. To decrypt, the ciphertext is broken into L and R blocks, and the key and the R block are run through the hash function to get the same hash result used in the last cycle of encryption; notice that the R block was unchanged in the last encryption cycle. The hash is then XOR'ed into the L block to reverse the last encryption cycle, and the process is repeated until all the encryption cycles have been backed out. The security of a Feistel cipher depends primarily on the key size and the irreversibility of the hash function. Ideally, the output of the hash function should appear to be random bits from which nothing can be determined about the input(s).

Data Encryption Standard (DES)

DES is a Feistel-type Substitution-Permutation Network (SPN) cipher, specified in FIPS PUB 46. The result of a 1970s effort to produce a U.S. encryption standard. DES uses a 56-bit key which can be broken using brute-force methods, and is now considered obsolete.

A 16 cycle Feistel system is used, with an overall 56-bit key permuted into 16 48-bit subkeys, one for each cycle. To decrypt, the identical algorithm is used, but the order of subkeys is reversed. The L and R blocks are 32 bits each, yielding an overall block size of 64 bits. The hash function "f", specified by the standard using the so-called "S-boxes", takes a 32-bit data block and one of the 48-bit subkeys as input and produces 32 bits of output. Sometimes DES is said to use a 64-bit key, but 8 of the 64 bits are used only for parity checking, so the effective key size is 56 bits.

Since the time DES was adopted (1977), it has been widely speculated that some kind of backdoor was designed into the cryptic S-boxes, allowing those "in the know" to effectively crack DES. Time has proven such speculation idle. Regardless of any backdoors in the hash function, the rapid advances in the speed of electronic circuitry over the last 20 years, combined with the natural parallelism of Feistel ciphers and DES's relatively small key size, have rendered the algorithm obsolete. In 1998, the Electronic Frontier Foundation built a DES Cracker (full specifications available online) for less than $250,000 that can decode DES messages in less than a week.

Triple DES

Triple DES was developed to address the obvious flaws in DES without designing a whole new cryptosystem. Triple DES simply extends the key size of DES by applying the algorithm three times in succession with three different keys. The combined key size is thus 168 bits (3 times 56), beyond the reach of brute-force techniques such as those used by the EFF DES Cracker. Triple DES has always been regarded with some suspicion, since the original algorithm was never designed to be used in this way, but no serious flaws have been uncovered in its design, and it is today (Spring 2001) a viable cryptosystem used in a number of Internet protocols.

Advanced Encryption Standard (AES) / Rijndael

In the late 1990s, the U.S. National Institute of Standards and Technology (NIST) conducted a competition to develop a replacement for DES. The winner, announced in 2001, is the Rijndael (pronounced "rhine-doll") algorithm, destined to become the new Advanced Encryption Standard. Rijndael mixes up the SPN model by including Galios field operations in each round. Somewhat similar to RSA modulo arithmetic operations, the Galios field operations produce apparent gibberish, but can be mathematically inverted.

Other block ciphers

Though DES and Triple DES are the most commonly used block ciphers, and Rijndael is DES's heir apparent, several alternative ciphers have been developed and deployed to various extents. CAST-128, documented in RFC 2144, is a 64-bit, 16 round SPN block cipher using a 128 bit key. It's quite similar to DES in its design, but is newer, uses a larger key size, and isn't subject to intellectual property restrictions. Blowfish, documented here is another unpatented Feistel algorithm using a variable length key.

The International Data Encryption Algorithm (IDEA), developed and patented by Ascom, is freely available for non-commercial use. Commercial use requires a license. IDEA's design is similar to DES, but uses a more complex round structure where each data block is broken into four, not two, sub blocks. RC5, developed by RSA Technology, is another proprietary SPN cipher.

Finally, I should note that publishing the design of a cipher inherently weakens it by providing an attacker with details of its operation. The most secure approach would be to design a cipher from scratch and keep both the algorithm and the keys secret. While designing a cryptosystem is fairly easy, evaluating it for loopholes is not. Governments and other very large institutions may have the resources to design and evaluate their own cryptosystem, but the rest of us are probably well advised to use published ciphers that have been publicly evaluated for weaknesses.