Block cipher modes of operation

From Citizendium, the Citizens' Compendium
Jump to: navigation, search
This article is a stub and thus not approved.
Main Article
Talk
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
This editable Main Article is under development and not meant to be cited; by editing it you can help to improve it towards a future approved, citable version. These unapproved articles are subject to a disclaimer.
For more information, see: Cryptography.

A block cipher provides a way to encrypt blocks of plaintext to yield blocks of ciphertext. A block cipher mode of operation specifies how multiple block cipher operations are to be combined to accomplish some larger task such as encrypting a message or providing a pseudorandom number generator. Using the wrong mode for the task at hand may give an insecure system even if the cipher itself is secure.

Modes were originally defined for the Data Encryption Standard in a US Federal Information Processing Standard (FIPS) [1]. The most recent NIST recommendations are in "Recommendation for Block Cipher Modes of Operation" [2]

Any mode can be applied with any block cipher.

Traditional modes

In some modes, the cipher is used only for data secrecy. These are covered here. See the next section for modes which provide authentication as well.

Electronic Code Book, ECB

In Electronic Code Book mode, the cipher is just applied to each block of plaintext independently.

The disadvantage is that the same plaintext block always encrypts to the same ciphertext; this gives an enemy some information. If enough blocks are encrypted this way, the system becomes vulnerable to a code book attack. ECB is therefore generally not used.

Cipher Block Chaining, CBC

In cipher block chaining mode, the ciphertext output from the previous block is XORed into the plaintext before encryption. Encryption of block n is then:

 cn = encrypt( pn XOR cn-1)

For this to work for n=1, an initialisation vector (IV) must be provided to act as c0. This need not be secret, but it must be different for each message and should be random. If the same IV is repeatedly used, then if two or more messages start with the same text, they will encrypt identically for the first block or the first few blocks. This is an unnecessary weakness; using unique IVs is therefore standard practice.

CBC mode makes the encryption of any block depend on all blocks previously encrypted. A bit error in an encrypted block, such as might be caused by line noise, will cause the decryption of that block and the next to be garbled, but later blocks will not be affected. CBC is self-recovering against bit-flipping errors. However, loss of synchronisation is fatal; if even a single bit is dropped or added, then the affected block and all that follow it will be garbled. Authentication of the packet or message can prevent such problems if decryption is only applied to data that has passed authentication,

Cipher block chaining is much the most widely used mode. IPsec specifies it as the only permitted mode. PGP and TLS use it as well.

Cipher Feedback, CFB

In cipher feedback mode, the ciphertext output of the previous block is encrypted before being XORed onto the plaintext block. Encryption of block n is then:

 cn = pn XOR encrypt(cn-1)

As for CBC mode, an initialization vector c0 is needed, which must be different for each message. Decryption of block n is

 pn = cn XOR encrypt(cn-1).

Note that for decrypting a block, the encryption function is used. This has two implications: It is not necessary to know the inverse of the encryption function, and the encryption key must be secret.

Output Feedback, OFB

In output feedback mode, the output of the encryption function for one block is used as input for the next block. This effectively lets a block cipher be used as a stream cipher. A stream depending only on the key and the initialization vector o0 is generated as

 on = encrypt(on-1).

To encrypt, this stream is XOR-ed onto the plaintext to generate the ciphertext.

 cn = pn XOR on.

To decrypt, the same output stream is generated from the initialization vector, then XOR-ed onto the ciphertext to recover the plaintext. As in CFB mode, the encryption function is used to decrypt, with the same implications.

Counter, CTR

In counter mode, a counter is encrypted to generate a series of pseudo-random output blocks. It can be used to create a pseudorandom number generator or a stream cipher; if the block cipher is secure and is keyed and re-keyed appropriately, these will be secure as well.,

Counter mode is used in the Yarrow [3] random number generator and later variants.

It is possible to re-key using some of the system output as the new key; Yarrow does this every 10 iterations, just to complicate any analysis. However, this is not enough for security if large amounts of output are required; the cipher must also be re-keyed (much less often) from an external source of genuine random numbers. The Yarrow paper demonstrates an attack after 2keysize/3 outputs, so any use of counter mode should be externally re-keyed well before that.

Dual use modes

When a block cipher is used in a hybrid cryptosystem, a cryptographic hash is often used as well; the cipher provides secrecy and the hash provides authentication. However, this is somewhat inefficient; the system must make two passes through the data, one to encrypt it and one to hash it.

There is quite a bit of recent (roughly, since the turn of the century) work on the design of algorithms that can do both in one pass. Many of the proposed solutions take the form of new modes of operation for block ciphers. These are covered in this section.

Much of the work has been done in the context of Internet standards such as IPsec, where it addresses a significant performance issue. See RFC 5116 "An Interface and Algorithms for Authenticated Encryption" [4], RFC 5282 [5]. RFC 3686, RFC 4106, RFC 4309 and RFC 5084.

Tweakable modes

A recent development is the tweakable block cipher [6]. Where a normal block cipher has only two inputs, plaintext and key, a tweakable block cipher has a third input called the tweak. The tweak, along with the key, controls the operation of the cipher. If changing tweaks is sufficiently lightweight, compared to the key scheduling operation which is often fairly expensive, then some new modes of operation become possible. For example, instead of exclusive-OR-ing the previous ciphertext into the plaintext, you can use that ciphertext to change the tweak. Several other tweaked modes are possible; this is an active area of current research.

References

  1. (December 1980). FIPS 81: DES Modes of Operation.
  2. (2001). Recommendation for Block Cipher Modes of Operation. National Institute for Standards & Technology.
  3. J. Kelsey, B. Schneier, and N. Ferguson (1999). Yarrow-160: Notes on the Design and Analysis of the Yarrow Cryptographic Pseudorandom Number Generator.
  4. D. McGrew (January 2008), An Interface and Algorithms for Authenticated Encryption, RFC5116
  5. D. Black, D. McGrew (August 2008), Using Authenticated Encryption Algorithms with the Encrypted Payload of the Internet Key Exchange version 2 (IKEv2) Protocol, RFC5282
  6. M. Liskov, R. Rivest, and D. Wagner (2002), "Tweakable Block Ciphers", LNCS, Crypto 2002