Block and Stream Ciphers

The two most common types of encryption algorithm used in modern cryptography are the block and stream ciphers. The block cipher uses a deterministic algorithm that conducts operations on fixed-length groupings of bits, or blocks. By using a transformation specified by a symmetric key, a block cipher is able to encrypt bulk data, and is one of the basic components of many cryptographic protocols in use today. A stream cipher, on the other hand, takes plaintext characters or digits and combines them with a pseudo random cipher digit stream, or key stream.

Block Cipher Background

The block ciphers found in use today are based on the iterated product cipher concept. These ciphers were first discussed and later analyzed in 1949 by Claude Shannon. The iterated product cipher concept entails conducting encryption operations over multiple rounds. Each of the rounds is designed to use a different subkey that is created from the primary or original key of the cipher. One of the largest known implementations of this cipher was the Feistel network. The network was named for Horst Feistel and was also used in widely employed DES cipher.

The United States National Bureau of Standards (rebranded as the National Institute of Standards in Technology, or NIST today), published the DES cipher in 1977. This publication was predominant in helping the public understand how modern ciphers worked. The publication of DES also helped to influence the growth of cryptanalysis in the public domain and academia at the time. This work helped develop various attack methods that new block ciphers have to guard / be tested against today.

Today, secure block ciphers remain suitable for the encryption of one block of information using a fixed key. There have been numerous modes of operation developed for the cipher to allow repeated use in secure channels in order to achieve authenticity and confidentiality. Block ciphers have also been used as the foundation protocol in more complex cryptographic protocols to include pseudo-random number generators and universal hashing functions.

What is a Block Cipher?

Block ciphers include two paired algorithms today. One of the algorithms is used for decryption (D), and one for encryption (E). Each of the algorithms is able to accept two inputs for operations: 1 – A key size consisting of (K) bits, Each of these inputs will then produce an output block of the size of “N.” Similarly, the associated decryption algorithm in block ciphers is defined to consist of the inverse of the encryption function. Formally described by the equation, D = E-1.

Block Cipher Modes of Operation

When employing a block cipher in a stand-alone fashion, there is a limitation of only being able to encrypt a single block of data that is the length of the cipher’s block length. For variable length messages, information has to be split out into separate blocks of data appropriate for the block cipher.

Electronic Codebook Mode

The simplest method of running a block cipher is in the electronic codebook (ECB) mode. In this scheme, the message to be encrypted is first broken up into blocks of data equivalent to the cipher block size. If the fragment is less than this length, then padding can be used to ensure the entire block of information is filled. This method is typically insecure against modern cryptanalysis since the equal plaintext blocks always create equal ciphertext blocks using the same key. As a result, patterns from the plaintext message can be detected in the ciphertext output and ultimately be cracked.

Overcoming Electronic Codebook Mode Limitations

In order to overcome the limitations associated with ECB (Electronic Codebook), there have been several block cipher modes of operation developed. The over-reaching concept for these modes is to leverage the randomization of plaintext information based on an additional input value. This value is commonly referred to as an initialization vector that is used to help create probabilistic encryption.

The cipher block chaining (CBC) mode, the initialization vector is sent along with the plaintext message. The value of the initialization vector has to be a pseudo-random or random value. It is added to the first plaintext block using an XOR operation prior to the initial encryption operation. The ciphertext output from the first encryption block is subsequently used as the initialization vector for the next plaintext block meant to encrypt.

The OFB (output feedback) mode repeatedly encrypts the vector to help create a key stream to emulate a synchronous stream cipher. The CTR (new counter) mode also makes use of a key stream, but the required randomness of the vector is created by using the initialization vector as a block counter. This counter is then encrypted for each block of plaintext that requires encryption.

How Does Block Cipher Padding Work?

Some block cipher modes such as CBC, will only work when provided with a complete plaintext block of data. If the message is only extended to meet the length requirement by using zero bits, it will prove insufficient since a receiver is not able to differentiate between messages that only differ in the total number of padding bits. The use of zero bits also provides an attacker an opening to use the efficient padding oracle attack. As a result, a padding scheme that is not predictable is required to match the plaintext block of information to the required cipher block length. Although most solutions have proven to be susceptible to the padding oracle attack, the padding method 2 defined by ISO/IEC 9797-1 has been proven to be the most secure block cipher padding scheme. This method adds a “one-bit” and then extends the final block with zero bits.

Famous Block Ciphers

DES and Lucifer

The first civilian block cipher is generally recognized to be the Lucifer cipher created at IBM in the 1970s. The cipher was based on Horst Feistel’s work. This algorithm was subsequently revised and adopted as the U.S. Federal Information Processing Standard, otherwise referred to as DES (Data Encryption Standard). The United States National Bureau of Standards (NBS) selected the algorithm after making a very pubic invitation for submissions from industry and the public. Once the NBS (and allegedly the National Security Agency) made internal changes to the algorithm, DES was released to the public in 1976.

The DES algorithm was created to help make a cipher that was resistant to attacks that were only known to the NSA and later by IBM at the time of publication. These attacks would be “rediscovered” and later published by Adi Smair and Eli Biham in the late 1980s. The technique published was called differential cryptanalysis and continues to remain one of the effect attacks against block ciphers today. Another method used to attack block ciphers is linear cryptanalysis, but it is not known if this method was known by the NSA prior to the publication of the attack by Mitsuru Matsui. The publication of DES resulted in a significant amount of publications in the cryptography field and helped inspire new cipher designs in both industry and government circles.

The DES cipher includes a standard block size of 64 bits and a key size of only 56. The 64 bit size would become the de-facto standard block size in block ciphers subsequently created and modeled off of the DES algorithm. The 56 bit key size was mandated by government law and would ultimately prove crackable by the Electronic Frontier Foundation in 1998. As a result, DES was extended through the release of Triple DES. In Triple DES, each block is encrypted with three independent keys (of 168 and 112 bit lengths) or using two keys of 112 and 80 bits. Industry widely adopted triple DES as the replacement for single DES. At the time of this writing, Triple DES is considered secure; however, NIST does not recommend using the two-key version of the algorithm in the wild due to the lack of security inherent with the use of the 80 bit key.

IDEA

IDEA (International Data Encryption Algorithm) is a block cipher that was first described in 1991 by James Massey and Xuejia Lai as a potential replacement for DES. The IDEA algorithm uses a 128 bit key and works on 64 bit blocks of information. There are a total of eight transformations in a single round of encryption along with an output transformation that is referred to as a half-round. The encryption and decryption process for the algorithm is similar and the security of the cipher is aided through interleaving operations from different groups. These include modular multiplication and addition and the use of XOR.

RC5

Ronald Rivest designed the RC5 block cipher in 1994. A unique difference in RC5 when compared to other block ciphers is that it makes use of a variable key size (0 to 2040 bits) as well as a variable block size (32, 64, or 128 bits). The cipher is designed to also have a variable number of rounds ranging from zero to 255. The originally published settings for the algorithm were a 128 bit key, 64 bit data block, and 12 rounds of encryption. Today, 18-20 rounds of the algorithm are considered to be necessary to avoid being susceptible to a differential attack using chosen plaintexts.

The overall structure of the RC5 algorithm resembles a Feistel network and the encryption and decryption routines are able to be identified in a few lines of programming code. The key schedule expands on the primary key through the use of one-way functions that include the binary expansion of both e and the use of the golden ratio.

AES

DES was ultimately succeeded by NIST in 2001 by the Advanced Encryption Standard (AES). The AES algorithm was created by Vincent Rijmen and Joan Daemen under the original submission name of Rijndael. The published cipher includes key sizes of 128, 192, or 256 bits as well as a fixed block size of 128 bits. The original Rijindael algorithm was able to use any block and key size that was a multiple of 32 with a minimum size of 128 bits.

AES conducts operations on a 4×4 column that is a major order matrix of bytes that is called the “State.” The cipher uses the key size to determine the total number of repetitions of transformation rounds that will be used to convert plaintext to ciphertext. In AES, the following the total number of “cycles” conducted based on the key size:

10 cycles of repetition for 128-bit keys.

12 cycles of repetition for 192-bit keys.

14 cycles of repetition for 256-bit keys.

Every round of AES includes a number of processing actions. Each of these will include five different states that also includes one depending on the original encryption key. When decrypting ciphertext, reverse rounds are applied to transform ciphertext back to original plaintext using the same key for both operations.

Stream Cipher Background

Stream ciphers make use of a symmetric key that uses plaintext combined with a pseudorandom cipher digit stream also known as a keystream. Stream ciphers will encrypt plaintext digitse “one at a time” along with the corresponding figure of the keystream. The resulting output will provide the corresponding output of the ciphertext stream. Another name for the stream cipher is the state cipher since every digit is dependent on the current state of the cipher. Typically a digit will be a bit and the combination operation will use the XOR operation.

Pseudorandom keystreams are normally created from a random seed value that uses digital shift registers. The seed value will also function as the key for decrypting the cipher stream. Unlike block ciphers, stream ciphers represent a different approach to encrypting and decrypting information. In order to avoid being cracked, stream ciphers should not use the same seed twice or else and adversary may be able to crack the code.

What are the Types of Stream Ciphers?

Stream ciphers will create successive elements of keystreams based on their internal state. The state is updated either independently of the plaintext and ciphertext messages which is a synchronous stream cipher. Self-synchronizing stream ciphers on the other hand are able to update their state that is based on previous ciphertext digits.

Synchronous Stream Ciphers

Synchronous stream ciphers use a stream of pseudo-random digits that are created independently of the ciphertext and plaintext messages. These digits are subsequently combined with plaintext for encryption or with the ciphertext for decrypting information. In the most common implementation of the synchronous stream cipher, binary digits are used and the keystream is combined with plaintext using the XOR operation. The official term for the combination of this information is the binary additive stream stream.

For synchronous stream ciphers, both the sender and receiver must use the same information in order for decryption of the ciphertext to be successful. If synchronization between the sender and receiver is out of synch, there are a few approaches to resynch the two stations. First is the use of various offsets to use systematically until synchronization is achieved. Another approach to resynchronize the two stations is to tag ciphertext with markers at set points in the cipher output. If there is any digit corrupted in this transmission then only one digit will be corrupted in the plaintext and the error will not impact the remainder of the message. If the transmission error rate it high, this method is useful. As a result of this property; however, synchronous stream ciphers can be very susceptible to active attacks by adversaries with access to the stream.

Self-Synchronizing Stream Ciphers

The self-synchronizing stream cipher uses a number of the previous N ciphtertext digits to aid in the computation of the keystream. This scheme is known as the self-synchronizing stream cipher, or ciphertext autokey (CTAK). This concept was originally patented in 1946 and allows the receiver to automatically synchronize with the keystream generator after receiving N ciphertext digits. This makes it easier for a sender or receiver to recover if there are digits dropped or added to the message stream. In this scheme, the single-digit error will be limited in overall effect. A block cipher that operates in CFB (cipher feedback) mode is an example of a self-synchronizing stream cipher. RC4 is the most widely used stream cipher in software throughout the world. Other ciphers that use this technique include: A5/1, A5/2, Chameleon, FISH, Helix, ISAAC, MUGI, Panama, Phelix, Pike, SEAL, SOBER, SOBER-128 and the WAKE cipher.