From a naïve point of view, the fact that a message is encrypted ought to be sufficient to protect it from being tampered with. If the encryption method used has turned it into a completely unintelligible stream of bits to any eavesdropper, then how would such an eavesdropper be able to alter the encrypted message in any way useful to him?
If the attacker knows the plaintext of a message, however, then having the ciphertext encrypted using Output Feedback Mode, or Counter Mode, or even by a one-time-pad, the attacker can XOR a value with the ciphertext with the result that the decryptor will see the plaintext with that value XORed to it.
If Electronic Codebook Mode is used, one can scramble the order of blocks in a message. This doesn't sound too important, until one realizes that one can also use blocks from other messages encrypted with the same key. One example that is commonly given of the dangers of relying on the integrity of messages only enciphered with a block cipher in this mode are messages containing financial transactions, where the number of the bank account involved is in one block, and the type and amount of the transaction is in another block.
Cipher Block Chaining might seem to provide message integrity, but one can snip the first few blocks from a message encrypted in that mode without any garbled text being visible in the plaintext.
In addition, if one wants to be able to send data which is unrestricted in type by means of an encryption mode, of course, one can't rely on the plaintext having redundancy by which garbled text could be distinguished from genuine text, and so one cannot have message integrity under all conditions without having an explicit checksum.
Perhaps the first block cipher mode explicitly designed with data integrity in mind is a mode somewhat similar to CBC, called PCBC, for Propagating Cipher Block Chaining, XORs each plaintext block, before being encrypted normally by DES, with both the previous ciphertext block and the previous plaintext block.
Thus, it has the following appearance:
Plaintext
|--------- |------
| | |
--->XOR | -------->XOR
| | | |
----------- | | -----------
| DES | -->XOR | DES |
----------- | -----------
| | |
| | |
|-------------- |------
| |
| |
Ciphertext
If two adjacent ciphertext blocks are swapped, clearly the plaintext values to which they will decrypt will be wrong, since the values XORed to the plaintext on input to the DES encryption will differ. But because the outputs of the DES encryptions are not modified by any XOR operation, even though those encrypted outputs, as well as plaintext block values, are used by XOR to modify the input to the DES encryption, if the ciphertext blocks are the same, then the outputs of the DES decryptions used when deciphering a message will be the same.
Let us call the value which is XORed with plaintext block P(i) before it goes into the DES encryption to produce C(i) the value X(i). What is X(i+1)? The answer is, it is:
X(i+1) = P(i) XOR C(i) = C(i) XOR D(C(i),k) XOR X(i)
Thus, it is equal to X(i) XOR a function of C(i) only.
This is why it is the case that when two ciphertext blocks are swapped, while they will decrypt incorrectly, succeeding blocks will again decrypt normally, because the value of X(i+2) is:
X(i+2) = X(i) XOR C(i) XOR D(C(i),k) XOR C(i+1) XOR D(C(i+1),k)
and if C(i) and C(i+1) are interchanged, X(i+2) will stay the same. In fact, if the blocks in any contiguous stretch of blocks are transposed in any order, at most those blocks will be garbled.
As this mode was intended to take the place of the use of a checksum for guaranteeing message integrity, this characteristic was considered a flaw, and led to this mode's being abandoned in favor of ordinary CBC when Kerberos, the one well-known place where it was used, went from version 4 to version 5.
Here are two simple modes I would like to propose as addressing the various nagging questions that bother people about most of the existing simple modes.
In the first such mode, one begins by choosing an initial value for a counter, and transmitting that value in encrypted form, encrypted by the block cipher in use.
Then, the first block of the message is encrypted by first XORing it with the value of the counter, encrypting it with the block cipher, and then adding the counter value to the output, using modulo 2^128 addition if the block length is 128 bits, to produce the ciphertext.
For all succeding blocks, increment the counter. The value to be XORed with the current plaintext block before the block cipher operation, and added to the output of the block cipher operation to form the ciphertext block, will be the current counter value with the previous block cipher output rotated one position to the left subtracted from it using modulo 2^128 arithmetic.
In algebra, knowing a+b and a-b lets you find a and b, so if a and b are independent, so are a+b and a-b. In modulo 2^128 arithmetic, this isn't quite true; a+b and a-b still differ by 2 bits, so their last bits agree. Subjecting the previous block cipher output to a one-bit rotation in addition to switching from addition to subtraction, although fairly trivial, would seem to remove any relationship between the new value to be applied to the current block and the previous ciphertext which would be trivial enough to be useful.
In my second attempt at such a mode, which I will call Layered Counter Chaining, as illustrated below:
a random 128-bit initialization vector is again chosen. This is encrypted twice using the block cipher to be used, assumed to have a 128-bit block size.
The value after it has been encrypted once is used as the starting value of a counter; this counter is incremented once after each block (except the last) is encrypted.
The original value, before any encryption, initializes an accumulator. That accumulator has the counter value added to it after the counter is incremented.
Each plaintext block is XORed with the accumulator value before and after the block cipher. In addition, before the block cipher only, it is XORed with the previous block cipher output. (In the case of the first block, the once-encrypted initialization vector is used instead.)
This encryption mode allows recovery from a garbled block, since, knowing the counter, one can determine from the ciphertext what the unknown block cipher output will be. But, admittedly, it is not parallelizable.
It strongly resists chosen-plaintext attacks, since a quantity produced by the block cipher operation is applied to the plaintext before it is enciphered.
Although the second-layer counter has some simple properties - for example, its last bits belong to the sequence 1 1 0 0 1 1 0 0, although the phase in that sequence is not known - and is not in any way a secure keystream, it is true that neither the starting value, nor the relationship between any pair of values in the sequence of counter values is known. If the counter value were XORed into the accumulator, instead of being added to it, almost all the bits in the accumulator would be the same after two XOR operations, but with additions this problem is not present. This is sufficient to prevent some attacks.
This mode can easily be combined with a checksum included in the message to protect message integrity, or the keys of the encryption of the initialization vector can be made different from the regular encryption key, offering a chance of complicating a brute-force attack on the block cipher.
Mihir Bellare invented a technique, described in U. S. patent 5,673,319, which dates from 1997, and is owned by IBM, which involved encrypting a message in two passes with CBC mode. Because the last block of a message, as encrypted in CBC mode, depends on every block of the message, one can use CBC encryption as a hash function, known as CBC-MAC, by using a fixed value, instead of a random value, for the initialization vector, and using the last block only as one's result. A fixed, secret, value was apparently envisaged in the patent; the term CBC-MAC is now usually used to describe a version of this where the fixed value is defined as zero.
The patent covered encrypting a message without changing its length in the following fashion:
Use a fixed, secret value as the initialization vector, then perform CBC encryption of the message except for the first block with one key. Retain only the last block of the encrypted result.
XOR this result with the first block of the plaintext message. Use that as the initialization vector for the actual encryption of the plaintext of the message, with a second key, again in CBC mode.
Except when two messages are identical, the first block, being the result of a hash of the whole message, is essentially random, so one has the benefit of having a random IV without having to increase the length of the message.
This method of encryption has the advantage of ensuring that the first block of a message will be obviously garbled if the ciphertext is altered in any way. It avoids increasing the length of messages. In a later section, I note that the principle involved is useful because if an encryption program is designed so that its operation is strictly defined, and it is never allowed to append random data to messages, then it is much more difficult for a malicious programmer to include something in the program to vitiate its security, for example by hiding the key, in a coded form, in what is supposed to be the "random" initialization vector.
A technique related to this patent, but which does use a random IV, is OAEP, which is proposed as a way of using RSA in a safe and bandwidth-efficient manner.
Recently, as a postscript to the Advanced Encryption Standard (AES) process, a number of block cipher modes were proposed. Two of these modes, CTR mode, a mode for normal encryption, and OMAC, a mode for calculating a Message Authentication Checksum, have been accepted as new standard modes to recommend for use with the AES; of the original modes recommended with DES, CFB mode is no longer included. CTR mode is simply counter mode as described in the section on basic block cipher modes. A number of modes have been proposed that both encrypt a message and provide an integrity check on that message. Although none of these modes have been accepted, after first examining OMAC, we will look at several of the proposed modes.
Since this has been written, Galois/Counter Mode, GCM, has been tentatively accepted as an encryption mode providing both authentication and secrecy at the same time.
Although no integrity-aware encryption mode has been selected by NIST for use with AES, this mode of block cipher usage has been chosen as a method of calculating a secure checksum.
OMAC checksum calculation is similar to CBC mode encryption with only small modifications.
A message is enciphered using CBC mode, except:
The "no padding" modification of L is L shifted one bit left, XORed with 00...000100001111 if the first bit, discarded in shifting, was a 1, and the "with padding" modification of L is L shifted one bit right, XORed with 1000...0001000011 if the last bit, discarded in shifting, was a 1.
These operations are intended to perform multiplication and division, respectively, by the polynomial
128 7 2 x +x +x +1
which is the first order-128 irreducible (not primitive) polynomial in numerical order of its coefficient vector, referred to as lexicographic order; that is, dictionary order.
(If DES, a block cipher with a 64-bit block size, were used in OMAC, the two constants, now 64 bits in length, would be 00...000110111 and 1000...0001101 respectively, and if a block cipher with a 256-bit block size were used in the OMAC checksum-generation mode, the two 256-bit constants used would be 00...000100001001011 and 1000...0001000010010 respectively.)
As this mode doesn't expand the length of a message if the message occupies a whole number of blocks, which means that any change to the message would produce a garbled message rather than one marked as invalid, and the secret value on which the security in the case of a message of variable length depends would be output if the first block of a message, being known plaintext, happened to be all zeroes, and, even more importantly, as with CBC mode, XORing the ciphertext of one block with a vector simply garbles that block, modifying the plaintext of the next block by the chosen XOR vector, without causing the encryption of the last block to be wrong (this doesn't make it insecure as a checksum, because the intermediate values are not disclosed, and the plaintext being checksummed is instead to be transmitted in the clear, so that a forger doesn't know what the proper garble of the block preceding the one to be altered would be) it must be emphasized again that this is not an authentication plus encryption mode in the sense that some of the modes described above were intended to be, it is simply a method of producing an MAC, a message authentication code, consisting of the output from "encrypting" the last block.
Also, for use as any kind of an encryption mode at all, even with the modification of having an initialization vector, and with no expectation of integrity checking, it would be necessary to indicate the length of the message in bits, or at least whether or not it was padded, or decipherment would not be unambiguous.
Now, we will examine some of the new modes that have been proposed for use with the AES, but which have not yet been accepted, which combine verification of message integrity with encryption.
One mode was proposed by Lars Knudsen, called Accumulated Block Chaining (ABC).
This mode was based on a mode developed by Carl Campbell, called Infinite Garble Extension (IGE) mode.
In IGE mode, the plaintext is XORed, before encryption, with the previous ciphertext; after going through the block cipher, it is XORed with the previous plaintext:
Plaintext
|------------- |
| | |
--->XOR ------------->XOR
| | | |
----------- | | -----------
| AES | | | | AES |
----------- | | -----------
| | | |
--->XOR | -------->XOR
| | |
|--------- |-----
| |
| |
Ciphertext
ABC mode is similar to IGE mode, except that the plaintext blocks are first replaced by a series of hash blocks. Each hash block is the XOR of the current plaintext block with a function of the previous hash block. That function may be the identity function, but the recommended function is somewhat more complicated: rotation one bit left.
Plaintext
| |
--->XOR ------->XOR
| | |
|---(ROT)------ |------
| |
|------------- |
| | |
--->XOR ------------->XOR
| | | |
----------- | | -----------
| AES | | | | AES |
----------- | | -----------
| | | |
--->XOR | -------->XOR
| | |
|--------- |-----
| |
| |
Ciphertext
Another proposal was offered to NIST by two employees of the National Security Agency. This mode was called Dual Counter (DCTR) mode. It worked as follows: a secret starting value was fed into a constant (and presumably publicly known) shift register. The shift register was as long as the block size. When a block is enciphered, the process is as follows: XOR the block of plaintext with the shift register contents, encrypt the block in the block cipher (presumably Rijndael, the AES), XOR the result with the shift register contents. Cycle the shift register once between blocks.
The shift register is the one based on the polynomial
128 7 2 x +x +x +x+1
which is primitive, as required for a counter. Although this is not claimed, since this polynomial comes immediately after the lexcographically-first irreducible polynomial of order 128, it is likely to be the lexicographically-first primitive polynomial of order 128. The shift register is cycled to the left and is in Galois configuration.
This mode was submitted on July 4th, which is Independence Day, the American national holiday, which was also the day in a previous year that it was hoped the Viking lander would land on Mars. (It actually was delayed, and so it landed on July 20th, the anniversary of the landing of Apollo 11.) It had been one of the results of eighteen months of work to develop a secure encryption system for TCP/IP networks.
It was thought that with the block cipher encryption in between, the fact that the value being XORed would have many of the same bits from block to block, only shifted one place, could not be exploited. However, shortly after this mode was described, a paper was published demonstrating possible weaknesses in this mode of encryption and this resulted in the withdrawal of the submitted mode.
These possible weaknesses, however, depend on how this mode would be used in practice. I do not believe that when DCTR was proposed it was intended that multiple messages would be sent with the same initial counter value; instead, negotiating the initial counter value was simply treated as being beyond the scope of the encryption mode itself. Sending a new initial counter value, encrypted once with the block cipher, with each message would still avoid the multiple encryptions required with IAPM, so I cannot agree that doing so would materially affect the fact that DCTR is somewhat more efficient than IAPM: changing 0 to 1 is not nearly as big a change as changing 0 to 3 for messages up to 6 blocks long, 4 for messages up to 14 blocks long, 5 for messages up to 30 blocks long, and so on and so forth.
While DCTR would be secure in a program like PGP that actually encrypted real messages coming from individuals, if a "message" is simply a block containing messages from many different people, as may be the case for a link encryption system, then the objections to the security of DCTR as compared to that of IAPM would be applicable, however.
This mode, developed by Charanjit S. Jutla of IBM, was the first integrity-aware encryption mode which was successfully proven secure. It has since been superseded by more efficient modes which also have proofs of security, such as XECSB-XOR and OCB modes.
Given a message consisting of n blocks, expand it to n+2 blocks by appending at the beginning a random block, r, and appending at the end a block which is simply the XOR of all the blocks in the original message, which we will call X.
Two block cipher keys are used, k0 for preparing a set of whitening values, and k1 for the actual encryption of the message.
Let m be the number of bits in the binary representation of n+2.
W(j) is defined as E(r+j,k0), where r+j is calculated using ordinary 128-bit arithmetic addition. This is calculated for j=1 to m.
Then, S(0) through S(n+1) are calculated from the W(j) values using the Gray code as follows:
S( 0) = W(1) S( 1) = W(2) xor W(1) S( 2) = W(2) S( 3) = W(3) xor W(2) S( 4) = W(3) xor W(2) xor W(1) S( 5) = W(3) xor W(1) S( 6) = W(3) S( 7) = W(4) xor W(3) S( 8) = W(4) xor W(3) xor W(1) S( 9) = W(4) xor W(3) xor W(2) xor W(1) S(10) = W(4) xor W(3) xor W(2) S(11) = W(4) xor W(2)
and so on. The use of the Gray code here is not essential to the security of the cipher; the S(i) values would still be pairwise-independent (differing by at least one of the independent W values) if the W values used were chosen based on the binary representation of i+1. It is for reasons of efficiency that the Gray code is used, so that having S(i), S(i+1) can always be calculated from it with a single 128-bit wide XOR.
The first block, denoted block 0, of the encrypted message is E(r,k1).
Blocks 1 through n of the encrypted message are S(i) xor E(S(i) xor P(i),k1).
The last block of the encrypted message is S(0) xor E(S(n+1) xor X,k1).
IACBC mode is very similar to IAPM, except that m is now the number of bits in the binary representation of n+1, and instead of XORing S(i) to the block before and after encryption, S(i) is only XORed after encryption, and the previous ciphertext block (as in CBC mode) is XORed before encryption. The first block is still E(r,k1), and the change in the value of m comes about since only S(0) is used with the final block.
This integrity-aware encryption mode, devised by Virgil Gligor and Pompiliu Donescu, is quite simple to describe.
One complexity in the paper in which it is described is that its description explicitly includes three possible cases: when a random initialization vector is sent with the message in encrypted form; when a message number is sent with the message, and it is encrypted to produce the value used in the place of a random initialization vector; and when the random initialization vector is sent by means external to the mode, such as with the key by means of a public-key encryption system.
The simplest case, termed stateless XCBC, proceeds as follows:
A random block is generated. It is encrypted using the main key for encryption, and sent as the first block of the message. That same block, encrypted using a second key, is treated as the previous intermediate result for the encryption of the first block of plaintext.
Each block of plaintext is enciphered in two steps. First, the block cipher is applied to the current plaintext block XOR the previous intermediate result, producing the current intermediate result. Then, ciphertext block(i) is intermediate result(i) plus i times the random block. Only addition, not multiplication, is required for this, of course.
No checksum block is specified in the description of this mode; presumably, it simply guarantees the last block is garbled by any attempt at forgery, and so the last block of the plaintext can simply contain any conventional checksum. Also, presumably the random block must not be zero.
The same paper also discusses the XECB mode of operation; it is used both for producing a message digest, and for encryption.
Again, the value i times a random block is used in encrypting block i of the plaintext. This time, this value, plus another value, unique to the message, which can be the message number times a second constant random value, is added both to the input to the block cipher and to the output.
The XOR sum of all the blocks of the plaintext is encrypted using almost the same pattern, except that the addition of n+1 times the random block to the block cipher output is omitted, to produce block n+1 of the ciphertext.
This encryption mode, designed by Philip Rogaway, Mihir Bellare, John Black, and Ted Krovetz, is fairly complex to describe, but it is a highly efficient mode: as the operations it uses are well-suited to both hardware and software implementations, it may well be the one most likely to find common use.
The encryption of all the blocks of the message itself, except for the last block, is simple enough, however:
Plaintext
|
|
Z(n) ---> XOR
|
---------
| AES |
---------
|
Z(n) ---> XOR
|
|
Ciphertext
where Gray(1) is 000...001, Gray(2) is 000...011, Gray(3) is 000...010, Gray(4) is 000...110 and so on:
1 00001 2 00011 3 00010 4 00110 5 00111 6 00101 7 00100 8 01100
the simplest form of the Gray code as used with shaft encoders and the like, and Z(n) is equal to Gray(n) multiplied by the value R, using Galois field multiplication modulo the polynomial
128 7 2 x +x +x +x+1
that is, the two bit strings are multiplied as polynomials modulo 2, so that XOR replaces the addition operation, and there are no carries, and then the 129 bit long bit string 1000...00010000111 is shifted left until it coincides with the first 1 bit in the product, and is XORed with it and then shifted right to the first remaining 1 bit, until the product is reduced to 128 bits in length or less.
After the multiplication, then the result is XORed with the AES encryption of the all-zero block.
The message is prefixed with an initialization vector; the value R is calculated from the initialization vector by first XORing the intialization vector with the AES encryption of the all-zero block, and then encrypting the result in AES.
The AES encryption of the all-zero block is used again in the mode. It is multiplied by two (or, thought of as a polynomial, by x) by means of the same form of Galois Field multiplication as previously used. In this case, the bit string is simply shifted one bit left, and if the first bit of the 128 bits before shifting was 1, then that bit is discarded, and 10000111 is XORed with the value.
The result of that calculation, along with Z(n), is XORed with the length of the last block before it is encrypted. After encryption by the AES block cipher, however, Z(n) is not XORed in again; instead, the plaintext of the last block is XORed with the output of the AES block cipher. Since the length of the plaintext block and the length of the ciphertext block are equal, the plaintext of the last block is determined on decipherment by repeating the encipherment calculation, and then XORing the AES output with the last ciphertext block.
This description doesn't sound right. How can one encrypt anything with AES that isn't a full 128 bits in length? The input to the last encryption is the length of the last block, Z(n), and the Galois-multiplied encryption of the zero block. So these are all values all 128 bits of which are known, even if no part of the last ciphertext block was recieved. Thus, after the AES encipherment of these values is performed, the last plaintext block, if short, is XORed with the first few bits of the AES output, just as it would be for counter mode, OFB mode, or CFB mode.
A simple checksum is then encrypted in AES to verify that the block was recieved correctly. This simple checksum is the XOR of the following items:
This simple checksum is XORed with the same Z(n) as was used in producing the last ciphertext block, not the next one in the series, and is then encrypted in AES. If a checksum shorter than a full block is desired, the first few bits of the result of that encryption, instead of the whole block, serves as the integrity check for the message.
The description of this mode is rather complicated, but the little details are important for ensuring that the proof it really does provide message integrity is actually valid.
It should be noted that the IAPM, IACBC, XECB, XECSB-XOR, and OCB encryption modes, as well as other modes using comparable techniques, are protected by patents.
In this mode, encryption is done in counter mode. However, the counter has a special form: it consists of three fields, an eight bit prefix (10000000), an 88-bit nonce, which must be guaranteed to be unique to each message transmitted with a given key, and a 32-bit counter. The counter starts at 1 for the first block of the message, and the counter value 0 is used in producing the checksum word.
The checksum operates both on the encrypted message and on an unencrypted header associated with the message. Encrypting 1100...000 produces a value that can't be an encrypted counter output; the last 127 bits of this value are treated as x, and the associated data, padded with zeroes to a multiple of 96 bits in length, followed by the encrypted message, padded with zeroes to a multiple of 96 bits in length, form a string of bits which is then chopped into 96-bit pieces which are the coefficients of a polynomial in x, evaluated modulo 2^127-1. (The paper notes that the last piece could be allowed to be up to 128 bits in length without losing the benefits of chopping things up into 96-bit pieces instead of 128-bit pieces, but this is not done in the mode as defined.) The value of the polynomial is then encrypted in the block cipher, and then the result of that encryption is XORed with the zero counter value mentioned above for inclusion in the transmitted message.
Only the encrypted message (with other data sent in the clear) is used in calculating the checksum, which helps to avoid any possibility that the checksum might compromise the security of the cipher.
I suppose that keys which produce an x equal to zero must not be used, as I did not see instructions for dealing with that case.
(It should also be noted that it appears the developers of CWC mode wish CWC to be considered as the actual name of the mode, rather than CWC merely being an abbreviation for Carter-Wegman-Counter; rather, that the choice of these particular letters was in fact inspired by the fact that this mode combined a Carter-Wegman checksum with counter mode is to be treated as if it were happenstance.)
Also initially known as Whiting-Housley-Ferguson (WHF) mode, this mode has been proposed as an alternative to OCB mode.
The mode appears to operate as follows: CBC mode encryption is applied to a plaintext which consists of blocks whose first half is a counter, and whose second half contains the original plaintext.
Using half the block for a counter, but with ECB mode, was the original mode in which IBM proposed using the 128-bit LUCIFER cipher.
For header data, which needs to be authenticated but not encrypted, the encryption is still performed, but the plaintext is transmitted. As well, it is assumed that a full block of header data exists, so that the header data can serve as an initialization vector (IV).
This is the mode currently being considered for acceptance. It was devised by D. McGrew and J. Viega.
The counter that is used for the counter mode of encryption does not involve Galois fields: a 128 value is used as the starting point, and only its least significant 32 bits are incremented. This is to avoid slowing implementations down on some hardware to determine carries that will virtually never happen.
The Galois polynomial used for authentication is x^128 + x^127 + x^126 + x^121 + 1.
Modular multiplication for this standard is defined in terms of successive right shifts instead of successive left shifts. The product of two strings of bits, X and Y, is defined as the XOR of successive multiples of Y indicated by the bits of X, where a multiple of Y is obtained modulo the polynomial simply by determining if the least significant bit of Y is a 1, then shifting Y one place right, and then XORing the value 11100001 to the most significant byte of Y if the bit shifted out was a 1.
The cipher mode uses a 96-bit IV. That IV, concatenated with a 32-bit count with 1 as its starting value, is the 128 bit value whose last 32 bits are incremented.
The mode works as follows:
Next
Chapter Start
Skip to Next Chapter
Table of Contents
Main Page