Convensional Block Ciphers.
The word ``conventional'' is typically the same as ``symmetric key'', or ``single key'', or ``classical'', indicating something from ancient history. But this is internet time, so in this case an ancient theory is anything dated before 1976. After that came the cryptosystems variously described as ``asymmetric'', or ``two-key'', or ``public key'' (actually mis-labeled, since this latter is a two-key system where one key is public and the other private). Later sections will describe asymmetric cryptosystems.
Block ciphers are in contrast to stream ciphers. A stream cipher handles one bit of key and one bit of plaintext at a time, usually combining them with an exclusive-or to produce one bit of ciphertext. Since the encryption cannot just depend on a single bit of key, the system must have state or memory, so that what is done with one bit depends on what was done before.
Block ciphers take a block of plaintext, whose size depends on the cryptosystem, and use a fixed key of some block length also depending on the cryptosystem, to produce a block of ciphertext, usually the same length as the block of plaintext. Such encryption is ``stand-alone'' and does not depend on what happened before. (Such a block cipher does not have state or memory.) Having ciphertext block size the same as plaintext block size is important, because then there is no data expansion with encryption.
The identical block size of plaintext and ciphertext should not be too small or the system would not be practical. In practice a convenient size is chosen, nowadays usually either 64 or 128 bits. The size of the key must be large enough to prevent brute-force attacks. Thus the ancient (25-year old) Data Encryption Standard (DES) had a 128-bit key and then 64 bits in the original proposals. This was finally cut to 56 bits on a transparently false pretext that eight out of 64 bits should be used for parity. It is now clear that the U.S. National Security Agency (NSA) wanted a key size that they could just barely break using a brute force attack and that no one else could break. A 64-bit key requires 256 times as much work to break as does a 56-bit one, but this is still obviously inadequate in today's world. The new U.S. Advanced Encryption Standard (AES) requires at least 128 bits in a key, and this is now regarded as a minimum desirable size. There has been recent talk that this latter size will also soon give way to a brute-force attack, but this is nonsense -- DES is still not trivial to break, and the AES would be at least 272 or roughly 4.722 * 1021 harder, a very large number. (Note that this estimate is just for a brute-force attack -- there might be easier ways to break any given system.) For additional security, the AES also has key sizes of 192 and 256 bits available.
The section describing Claud Shannon's noisy coding theorem used a random code for error correction of data sent over a noisy channel. In cryptography, a random code with no duplicate code words could be considered for a cryptographic code, but the code table would need to be unacceptably large, and the decoding algorithm would be difficult to make efficient. (Here the code table would take the place of the key.) Instead of using random ciphertexts, which is not practical, one wants to have ciphertexts that appear to be random.
Encryption itself provides a function from each possible plaintext block to a ciphertext block, with no duplicate values occurring. Similarly decryption gives the inverse mapping, which would not be uniquely defined if there were duplicates. Encryption in this type of cryptosystem is essentially a parameterized collection of encryption functions, one for each key value.
Possible Attacks.
The basic method used for encryption should not be secret, but instead all security should rely on the secrecy of the key. Thus opponents who know everything about the encryption and decryption algorithms should still not be able to break the system unless they know the particular key.
The key is now chosen large enough to eliminate brute-force attacks, but just a large key is not enough to ensure security of a cryptosystem. The opponent may have additional information about the cryptosystem. There are three simple types of attacks against a cipher (along with other fancier ones not described here):
- Ciphertext only: here the opponent has access only to any number of ciphertexts. This is the weakest assumption and would always be true. An opponent who cannot even intercept encrypted messages obviously cannot determine the plaintexts.
- Known plaintext: This case assumes that an opponent can obtain plaintext/ciphertext pairs. As an example, an embassy might first get permission for a press report by sending the report in encrypted form on one day, and then actually releasing the report the next.
- Chosen plaintext: This scenario assumes the opponents can ask for encryption of plaintexts of their choosing, and see the resulting ciphertexts. This is the strongest information normally assumed of opponents: that they essentially have access to an ``encryption box'' with the key buried inaccessibly inside.
One always wants a cryptosystem to be secure against a chosen plaintext attack, so of course the AES appears to resist this attack. Notice that a cryptosystem may often be strong (resistant to attacks) and yet not require as much work to break as a brute force attack. For example, the cryptograms in an earlier section have keys of size 26! or roughly 4.0329 * 1026. This is a very large key space for brute-force search, but in fact a cryptogram is easily broken.
In addition to trying to break the cipher, an opponent can attempt various replay attacks: retransmitting individual blocks or entire messages made up of many blocks. For example, on one day an army might receive an encrypted RETREAT message. The next day, when they are supposed to attack, the encrypted ATTACK message could be intercepted and replaced with the previous day's message. The army would decrypt the message and think they should again retreat.
There are several ways to protect against these replay attacks. Additional data could be included in each block, such as a sequence number, or the date. However, a better method, explained in detail in the section on ``modes of operation'' below, makes each encrypted block depend on all the previous blocks.
Other attacks include inserting, deleting or rearranging blocks of ciphertext, as well as ciphertext searching: looking for a block that matches the block in another encrypted message, without being able to decrypt the block.
Meet-In-the-Middle Attack on Double Encryption.
From the beginning, critics of the DES's short key were told that they could use double or triple DES encryption, thus using two or three 56-bit DES keys, and getting an effective key length of 112 or 168 bits. For example, double encryption uses two keys K1 and K2, encrypting first with the first key, and then encrypting the resulting ciphertext with the second key. A brute-force attack on all pairs of keys would indeed require 2112 steps, but such a double encryption should not be regarded as nearly as secure as a cryptosystem designed from scratch with a 112-bit key. In fact, there is a special attack on such a system, called meet-in-the-middle.
In order to carry out an attack, one needs enough information to recognize when the attack is successful. One possibility is that the plaintexts might have extra information (such as padding with 0 bits, or representing ASCII characters) that will allow their recognition. More common is a known plaintext attack: Suppose one has several pairs of corresponding plaintext / ciphertext from known plaintext information: P1 / C1, P2 / C2, etc. These correspond to double DES encryption using two unknown keys in succession: K1 and K2. The objective is to determine these unknown 56-bit keys.
First calculate the ciphertexts EK(P1) = C for all 256 possible keys K. These should be stored as a (very large) hash table to allow efficient lookup. Then for each possible key K, calculate C' = E-1K(C1). Look up each C' in the hash table. If an entry is found, then it satisfies: EK'(P1) = C' and EK''(C') = C1, for some keys K' and K''. This might represent a false alarm, so one needs to check these two keys against another plaintext / ciphertext pair as a second check. On the average, in 255 steps, the desired pair of keys will be found.
Thus, instead of 2112 steps (which is at present completely unrealistic), one can get by with at most 256 and 256 blocks of storage. Of course, these figures are also very large, but perhaps not so far beyond what is possible. There is also a refinement of this attack called the time-memory trade-off that uses 2x steps of execution and 2y blocks of storage, where x + y = 112. (See the Handbook of Applied Cryptography for details.) So even if 256 blocks of storage is not possible, one can trade a smaller amount of storage for a larger amount of execution time.
There are clever ways to use block ciphers, as illustrated in the next section, that will eliminate these meet-in-the-middle attacks.
Modes of Operation.
The discussion below assumes a fixed conventional (single key) block encryption scheme, such as the Advanced Encryption Standard discussed in a later section. The methods work for any such block cipher.
Electronic Codebook (ECB) Mode: The first method of using a block cipher is called The Electronic Codebook (ECB) Mode . In this method, each block is encrypted independently of each other block. This method obviously invites the replay of blocks mentioned earlier.
Cipher Block Chaining (CBC) Mode: This uses an Initialization Vector (IV) the size of one block. The IV is exclusive-ored with the first message block before encryption to give the first ciphertext block. Each subsequent message block is exclusive-ored with the previous ciphertext block. The process is reversed on decryption. Here is an illustration of the CBC mode (adapted from the Handbook of Applied Cryptography):
In the image above, a sequence of plaintext blocks: P1, P2, P3, ... is being encrypted using a key K and block encryption algorithm E. Step j of the algorithm uses plaintext Pj, key K, and the ciphertext Cj-1 produced by the previous step. Step 1 requires a special initialization vector IV = C0. As shown, step j of decryption uses the inverse decryption algorithm E-1 and the same key K, along with the ciphertext block Cj and the previous ciphertext block Cj-1.
This CBC mode has so many pleasant properties that no one should consider using ECB mode in its place.