Your continued donations keep Wikipedia running!

Block cipher modes of operation

From Wikipedia, the free encyclopedia

OFB redirects here. For other use, see Austrian Football Association.

In cryptography, a block cipher operates on blocks of fixed length, often 64 or 128 bits. To encrypt longer messages, several modes of operation may be used. The earliest modes described, such as ECB, CBC, OFB and CFB provide only confidentiality, and do not ensure message integrity. Other modes have been designed which ensure both confidentiality and message integrity, such as CCM mode, EAX mode and OCB mode. Tweakable narrow-block encryption (LRW) mode and wide-block encryption (CMC and EME) modes, designed to securely encrypt sectors of a disk, are described in the article devoted to disk encryption.

[edit]

Electronic codebook (ECB)

The simplest of the encryption modes is the electronic codebook (ECB) mode, in which the message is split into blocks and each is encrypted separately. The disadvantage of this method is that identical plaintext blocks are encrypted to identical ciphertext blocks; it does not hide data patterns. Thus, in some senses it doesn't provide message confidentiality at all, and is not recommended for cryptographic protocols.

Here's a striking example of the degree to which ECB can reveal patterns in the plaintext. A pixel-map version of the image on the left was encrypted with ECB mode to create the center image:


Original	Encrypted using ECB mode	Encrypted using other modes

The image on the right is how the image might look encrypted with CBC, CTR or any of the other more secure modes -- indistinguishable from random noise. Note that the random appearance of the image on the right tells us very little about whether the image has been securely encrypted; many kinds of insecure encryption have been developed which would produce output just as random-looking.

ECB mode can also make protocols without integrity protection even more susceptible to replay attacks, since each block gets decrypted in exactly the same way. For example, the Phantasy Star Online: Blue Burst online video game uses Blowfish in ECB mode. Before the key exchange system was cracked leading to even easier methods, cheaters repeated encrypted "monster killed" message packets, each an encrypted Blowfish block, to illegitimately gain experience points quickly.

[edit]

Cipher-block chaining (CBC)

In the cipher-block chaining (CBC) mode, each block of plaintext is XORed with the previous ciphertext block before being encrypted. This way, each ciphertext block is dependent on all plaintext blocks up to that point. Also, to make each message unique an initialization vector is used.

If the first block has index 1, the mathematical formula for CBC encryption is

$C_i = E_K(P_i \oplus C_{i-1}), C_0 = IV$

while the mathematical formula for CBC decryption is

$P_i = D_K(C_i) \oplus C_{i-1}, C_0 = IV$

CBC is the most commonly used mode of operation. Its main drawbacks are that encryption is sequential (cannot be parallelized), and that the message must be padded to a multiple of the cipher block size.

Note that a one-bit change in the plaintext affects all following ciphertext, but a block of plaintext can be recovered from just two adjacent blocks of ciphertext. As a consequence, decryption can be parallelized, and a one-bit change to the ciphertext causes complete corruption of the corresponding block of plaintext and inverts the corresponding bit in the following block of plaintext.

[edit]

Propagating cipher-block chaining (PCBC)

The propagating cipher-block chaining mode was designed to cause small changes in the ciphertext to propagate infinitely when decrypting, as well as when encrypting. Encryption and decryption routines are as follows:

$C_i = E_K(P_i \oplus P_{i-1} \oplus C_{i-1}), P_0 \oplus C_0 = IV$

$P_i = D_K(C_i) \oplus P_{i-1} \oplus C_{i-1}, P_0 \oplus C_0 = IV$

PCBC is notably used in Kerberos and WASTE, but otherwise is fairly uncommon.

[edit]

Cipher feedback (CFB)

The cipher feedback (CFB) mode is a close relative of CBC. The operation is very similar; in particular, CFB decryption is almost identical to CBC decryption performed in reverse:

$C_i = E_K (C_{i-1}) \oplus P_i$

$P_i = E_K (C_{i-1}) \oplus C_i$

$C_{0} = \ \mbox{IV}$

Like CBC mode, changes in the plaintext propagate forever in the ciphertext, and encryption cannot be parallelized. Also like CBC, decryption can be parallelized. When decrypting, a one-bit change in the ciphertext affects two plaintext blocks: a one-bit change in the corresponding plaintext block, and complete corruption of the following plaintext block. Later plaintext blocks are decrypted normally.

Because each stage of the CFB mode depends on the encrypted value of the previous ciphertext XORed with the current plaintext value, a form of pipelining is possible, since the only encryption step which requires the plaintext is the final XOR. This is useful for applications that require low latency between the arrival of plaintext and the output of the corresponding ciphertext, such as certain applications of streaming media.

CFB shares two advantages over CBC mode with the stream cipher modes OFB and CTR: the block cipher is only ever used in the encrypting direction, and the message does not need to be padded to a multiple of the cipher block size.

[edit]

Output feedback (OFB)

The output feedback (OFB) mode makes the block cipher into a stream cipher: it generates keystream blocks, which are then XORed with the plaintext blocks to get the ciphertext. Just as with other stream ciphers, flipping a bit in the ciphertext produces a flipped bit in the plaintext at the same location. This property allows many error correcting codes to function normally even if applied before encryption.

Because of the symmetry of the XOR operation, encryption and decryption are exactly the same: $C_i = P_i \oplus O_i$

$P_i = C_i \oplus O_i$

$O_i = \ E_K (O_{i-1})$

$O_{0} = \ \mbox{IV}$

Each output feedback block cipher operation depends on all previous ones, so cannot be performed in parallel.

[edit]

Counter (CTR)

Note: CTR mode is also known as Segmented Integer Counter (SIC) mode

Like OFB, counter mode turns a block cipher into a stream cipher. It generates the next keystream block by encrypting successive values of a "counter". The counter can be any simple function which produces a sequence which is guaranteed not to repeat for a long time, although an actual counter is the simplest and most popular. CTR mode has very similar characteristics to OFB, but also allows a random access property for decryption and is probably secure if the block cipher is strong. Note that nonce in this graph is the same thing as the initialization vector (IV) in the other graphs. The IV/nonce and the counter can either be concatenated, added or XORed together to produce the actual unique counter block to encrypt.

[edit]

Integrity protection and error propagation

The block cipher modes of operation presented above provide no integrity protection. This means that an attacker who does not know the key may still be able to modify the data stream in ways useful to them. It is now generally well understood that wherever data is encrypted, it is nearly always essential to provide integrity protection for security. For secure operation, the IV and ciphertext generated by these modes should be authenticated with a secure MAC, which is checked before decryption.

Before these issues were well understood, it was common to discuss the "error propagation" properties of a mode of operation as a means of evaluating it. It would be observed, for example, that a one-block error in the transmitted ciphertext would result in a one-block error in the reconstructed plaintext for ECB mode encryption, while in CBC mode such an error would affect two blocks:

Some felt that such resilience was desirable in the face of random errors, while others argued that it increased the scope for attackers to modify the message to their own ends.

However, when proper integrity protection is used such an error will result (with high probability) in the entire message being rejected - if resistance to random error is desirable, error-correcting codes should be applied after encryption.

Some modes of operation have been designed to combine security and authentication. Examples of such modes are: IACBC, IAPM, OCB mode, EAX, CWC, and GCM. These authenticated encryption modes are either classified as single pass modes or double pass modes. Some modes also allow for the authentication of unencrypted associated data, and these are called AEAD (Authenticated-Encryption with Associated-Data) schemes. For example, EAX mode is a double pass AEAD scheme while OCB mode is single pass.

[edit]

Initialization vector (IV)

Main article: Initialization vector

All modes (except ECB) require an initialization vector, or IV - a sort of dummy block to kick off the process for the first real block, and also provide some randomisation for the process. There is no need for the IV to be secret, but it is important that it is never reused with the same key. For CBC and CFB, reusing an IV leaks some information about the first block of plaintext and any common prefix shared by the two messages. For OFB and CTR, reusing an IV completely destroys security. In CBC mode, the IV must be randomly generated at encryption time.

[edit]

Padding

Main article: Padding

Because a block cipher works on units of a fixed size, but messages come in a variety of lengths, some modes (mainly CBC) require that the final block be padded before encryption. Several padding schemes exist. The simplest is simply to add null bytes to the plaintext to bring its length up to a multiple of the block size, but care must be taken that the original length of the plaintext can be recovered; this is so, for example, if the plaintext is a C style string which contains no null bytes except at the end. Slightly more complex is the original DES method, which is to add a single one bit, followed by enough zero bits to fill out the block; if the message ends on a block boundary, a whole padding block will be added. Most sophisticated are CBC-specific schemes such as ciphertext stealing or residual block termination, which do not cause any extra ciphertext expansion, but these schemes are relatively complex.

CFB, OFB and CTR modes do not require any special measures to handle messages whose lengths are not multiples of the block size, since they all work by XORing the plaintext with the output of the block cipher. The last partial block of plaintext is XORed with the first few bytes of the last keystream block, producing a final ciphertext block that is the same size as the final partial plaintext block. This characteristic of stream ciphers makes them suitable for applications that require the encrypted ciphertext data to be the same size as the original plaintext data, and for applications that transmit data in streaming form where it is inconvenient to add padding bytes.

Block ciphers edit

Retrieved from "http://en.wikipedia.org/wiki/Block_cipher_modes_of_operation"

Categories: Cryptographic algorithms

Block cipher modes of operation

From Wikipedia, the free encyclopedia

Contents

Electronic codebook (ECB)

Cipher-block chaining (CBC)

Propagating cipher-block chaining (PCBC)

Cipher feedback (CFB)

Output feedback (OFB)

Counter (CTR)

Integrity protection and error propagation

Initialization vector (IV)

Padding

Views

Personal tools

Navigation

Search

Toolbox

In other languages