Presentation on theme: "Cryptography and Network Security Chapter 6 Block Cipher Modes of Operation Lecture slides by Lawrie Brown for “Cryptography and Network Security”, 5/e,"— Presentation transcript:
1Cryptography and Network Security Chapter 6 Block Cipher Modes of Operation Lecture slides by Lawrie Brown for “Cryptography and Network Security”, 5/e, by William Stallings, Chapter 6 – “Block Cipher Operation”.
2Multiple Encryption & DES clear a replacement for DES was neededtheoretical attacks that can break itdemonstrated exhaustive key search attacksAES is a new cipher alternativeprior to this alternative was to use multiple encryption with DES implementationsTriple-DES is the chosen formGiven the potential vulnerability of DES to a brute-force attack,there has been considerable interest in finding an alternative. One approach is to design a completely new algorithm, of which AES is a prime example. Another alternative, which would preserve the existing investment in software and equipment, is to use multiple encryption with DES and multiple keys. We examine the widely accepted triple DES (3DES) approach.
3Double-DES? could use 2 DES encrypts on each block C = EK2(EK1(P))issue of reduction to single stageand have “meet-in-the-middle” attackworks whenever use a cipher twicesince X = EK1(P) = DK2(C)attack by encrypting P with all keys and storethen decrypt C with keys and match X valuecan show takes O(256) stepsThe simplest form of multiple encryption has two encryption stages and two keys - Double-DES.Have concern that there might be a single key that is equivalent to using 2 keys as above, not likely but only finally proved as impossible in 1992.More seriously have the “meet-in-the-middle” attack, first described by Diffie in It is a known plaintext attack (ie have know pair (P,C), and attempts to find by trial-and-error a value X in the “middle” of the double-DES encryption of this pair, and chances of this are much better at O(2^56) than exhaustive search at O(2^112).
4Triple-DES with Two-Keys hence must use 3 encryptionswould seem to need 3 distinct keysbut can use 2 keys with E-D-E sequenceC = EK1(DK2(EK1(P)))nb encrypt & decrypt equivalent in securityif K1=K2 then can work with single DESstandardized in ANSI X9.17 & ISO8732no current known practical attacksseveral proposed impractical attacks might become basis of future attacksTriple-DES with two keys is a popular alternative to single-DES, but suffers from being 3 times slower to run. The use of encryption & decryption stages are equivalent, but the chosen structure allows for compatibility with single-DES implementations. 3DES with two keys is a relatively popular alternative to DES and has been adopted for use in the key management standards ANS X9.17 and ISO Currently, there are no practical cryptanalytic attacks on 3DES. Coppersmith notes that the cost of a brute-force key search on 3DES is on the order of 2^112 (=5*10^33) and estimates that the cost of differential cryptanalysis suffers an exponential growth, compared to single DES, exceeding 10^52.There are several proposed attacks on 3DES that, although not currently practical, give a flavor for the types of attacks that have been considered and that could form the basis for more successful future attacks. See text for details.
5Triple-DES with Three-Keys although are no practical attacks on two-key Triple-DES have some indicationscan use Triple-DES with Three-Keys to avoid even theseC = EK3(DK2(EK1(P)))has been adopted by some Internet applications, eg PGP, S/MIMEAlthough the attacks currently known appear impractical, anyone using two-key 3DES may feel some concern. Thus, many researchers now feel that three-key 3DES is the preferred alternative. Three-key 3DES has an effective key length of 168 bits and is defined as shown. A number of Internet-based applications have adopted three-key 3DES, including PGP and S/MIME.
6Modes of Operation block ciphers encrypt fixed size blocks eg. DES encrypts 64-bit blocks with 56-bit keyneed some way to en/decrypt arbitrary amounts of data in practiseNIST SP A defines 5 modeshave block and stream modesto cover a wide variety of applicationscan be used with any block cipherDES (or any block cipher) forms a basic building block, which en/decrypts a fixed sized block of data. However to use these in practise, we usually need to handle arbitrary amounts of data, which may be available in advance (in which case a block mode is appropriate), and may only be available a bit/byte at a time (in which case a stream mode is used). To apply a block cipher in a variety of applications, five "modes of operation" have been defined by NIST (SP A). In essence, a mode of operation is a technique for enhancing the effect of a cryptographic algorithm or adapting the algorithm for an application, such as applying a block cipher to a sequence of data blocks or a data stream. The five modes are intended to cover a wide variety of applications of encryption for which a block cipher could be used. These modes are intended for use with any symmetric block cipher, including triple DES and AES. .
7Electronic Codebook Book (ECB) message is broken into independent blocks which are encryptedeach block is a value which is substituted, like a codebook, hence nameeach block is encoded independently of the other blocksCi = EK(Pi)uses: secure transmission of single valuesThe simplest mode is the electronic codebook (ECB) mode, in which plaintext is handled one block at a time and each block of plaintext is encrypted using the same key. The term codebook is used because, for a given key, there is a unique ciphertext for every b-bit block of plaintext. Therefore, we can imagine a gigantic codebook in which there is an entry for every possible b-bit plaintext pattern showing its corresponding ciphertext. For a message longer than b bits, the procedure is simply to break the message into b-bit blocks, padding the last block if necessary. Decryption is performed one block at a time, always using the same key. ECB is the simplest of the modes, and is used when only a single block of info needs to be sent (eg. a session key encrypted using a master key).
8Electronic Codebook Book (ECB) Stallings Figure 6.3 illustrates the Electronic Codebook (ECB) Mode.
9Advantages and Limitations of ECB message repetitions may show in ciphertextif aligned with message blockparticularly with data such graphicsor with messages that change very little, which become a code-book analysis problemweakness is due to the encrypted message blocks being independentmain use is sending a few blocks of dataFor lengthy messages, the ECB mode may not be secure. If the message is highly structured, it may be possible for a cryptanalyst to exploit these regularities. If the message has repetitive elements, with a period of repetition a multiple of b bits, then these elements can be identified by the analyst. This may help in the analysis or may provide an opportunity for substituting or rearranging blocks. Hence ECB is not appropriate for any quantity of data, since repetitions can be seen, esp. with graphics, and because the blocks can be shuffled/inserted without affecting the en/decryption of each block. Its main use is to send one or a very few blocks, eg a session encryption key.
10Cipher Block Chaining (CBC) message is broken into blockslinked together in encryption operationeach previous cipher blocks is chained with current plaintext block, hence nameuse Initial Vector (IV) to start processCi = EK(Pi XOR Ci-1)C-1 = IVuses: bulk data encryption, authenticationTo overcome the problems of repetitions and order independence in ECB, want some way of making the ciphertext dependent on all blocks before it. The CBC provides this, by combining the previous ciphertext block with the current message block before encrypting. In effect, we have chained together the processing of the sequence of plaintext blocks. The input to the encryption function for each plaintext block bears no fixed relationship to the plaintext block. Therefore, repeating patterns of b bits are not exposed. For decryption, each cipher block is passed through the decryption algorithm. The result is XORed with the preceding ciphertext block to produce the plaintext block. To produce the first block of ciphertext, an initialization vector (IV) is XORed with the first block of plaintext. On decryption, the IV is XORed with the output of the decryption algorithm to recover the first block of plaintext. The IV is a data block that is that same size as the cipher block, and is either well known (often all 0's), or otherwise is sent, ECB encrypted, just before starting CBC use. CBC mode is applicable whenever large amounts of data need to be sent securely, provided that all data is available in advance (eg , FTP, web etc).
12Message Paddingat end of message must handle a possible last short blockwhich is not as large as blocksize of cipherpad either with known non-data value (eg nulls)or pad last block along with count of pad sizeeg. [ b1 b2 b ]means have 3 data bytes, then 5 bytes pad+countthis may require an extra entire block over those in messagethere are other, more esoteric modes, which avoid the need for an extra blockOne issue that arises with block modes is how to handle the last block, which may well not be complete. In general have to pad this block (typically with 0's), and then must recognise padding at other end - may be obvious (eg in text the 0 value should usually not occur), or otherwise must explicitly have the last byte as a count of how much padding was used (including the count). Note that if this is done, if the last block IS an even multiple of 8 bytes or has exactly the same form as pad+count, then will have to add an extra block, all padding so as to have a count in the last byte. There are other, more esoteric, “ciphertext stealing” modes, which avoid the need for an extra block.
13Advantages and Limitations of CBC a ciphertext block depends on all blocks before itany change to a block affects all following ciphertext blocksneed Initialization Vector (IV)which must be known to sender & receiverif sent in clear, attacker can change bits of first block, and change IV to compensatehence IV must either be a fixed value (as in EFTPOS)or must be sent encrypted in ECB mode before rest of messageCBC is the block mode generally used. The chaining provides an avalanche effect, which means the encrypted message cannot be changed or rearranged without totally destroying the subsequent data. However there is the issue of ensuring that the IV is either fixed or sent encrypted in ECB mode to stop attacks on 1st block.
14Stream Modes of Operation block modes encrypt entire blockmay need to operate on smaller unitsreal time dataconvert block cipher into stream ciphercipher feedback (CFB) modeoutput feedback (OFB) modecounter (CTR) modeuse block cipher as some form of pseudo-random number generatorFor AES, DES, or any block cipher, encryption is performed on a block of b bits. However, it is possible to convert a block cipher into a stream cipher, using one of the three modes to be discussed in this and the next two sections: cipher feedback (CFB) mode, output feedback (OFB) mode, and counter (CTR) mode. A stream cipher eliminates the need to pad a message to be an integral number of blocks. It also can operate in real time. Thus, if a character stream is being transmitted, each character can be encrypted and transmitted immediately using a character-oriented stream cipher. Idea here is to use the block cipher essentially as a pseudo-random number, and to combine these "random" bits with the message. One desirable property of a stream cipher is that the ciphertext be of the same length as the plaintext. Thus, if 8-bit characters are being transmitted, each character should be encrypted to produce a ciphertext output of 8 bits. If more than 8 bits are produced, transmission capacity is wasted.
15Cipher FeedBack (CFB) message is treated as a stream of bits added to the output of the block cipherresult is feed back for next stage (hence name)standard allows any number of bit (1,8, 64 or 128 etc) to be feed backdenoted CFB-1, CFB-8, CFB-64, CFB-128 etcmost efficient to use all bits in block (64 or 128)Ci = Pi XOR EK(Ci-1)C-1 = IVuses: stream data encryption, authenticationCipher feedback (CFB) mode is one alternative. As with CBC, the units of plaintext are chained together, so that the ciphertext of any plaintext unit is a function of all the preceding plaintext. In this case, rather than units of b bits, the plaintext is divided into segments of s bits. The input to the encryption function is a b-bit shift register that is initially set to some initialization vector (IV). The leftmost (most significant) s bits of the output of the encryption function are XORed with the first segment of plaintext P1 to produce the first unit of ciphertext C1, which is then transmitted. In addition, the contents of the shift register are shifted left by s bits and C1 is placed in the rightmost (least significant) s bits of the shift register. This process continues until all plaintext units have been encrypted. For decryption, the same scheme is used, except that the received ciphertext unit is XORed with the output of the encryption function to produce the plaintext unit. Note that it is the encryption function that is used, not the decryption function.As originally defined, CFB was to "consume" as much of the "random" output as needed for each message unit (bit/byte) before "bumping" bits out of the buffer and re-encrypting. This is wasteful though, and slows the encryption down as more encryptions are needed. An alternate way to think of it is to generate a block of "random" bits, consume them as message bits/bytes arrive, and when they're used up, only then feed a full block of ciphertext back. This is CFB-64 or CFB-128 mode (depending on the block size of the cipher used eg DES or AES respectively). CFB is the usual choice for quantities of stream oriented data, and for authentication use.
16s-bit Cipher FeedBack (CFB-s) Stallings Figure 6.5 illustrates the operation of s-bit Cipher FeedBack (CFB) Mode.
17Advantages and Limitations of CFB appropriate when data arrives in bits/bytesmost common stream modelimitation is need to stall while do block encryption after every n-bitsnote that the block cipher is used in encryption mode at both endserrors propogate for several blocks after the errorCFB is the usual stream mode. As long as can keep up with the input, doing encryptions every 8 bytes. A possible problem is that if its used over a "noisy" link, then any corrupted bit will destroy values in the current and next blocks (since the current block feeds as input to create the random bits for the next). So either must use over a reliable network transport layer (typical) or use OFB/CTR.
18Output FeedBack (OFB) message is treated as a stream of bits output of cipher is added to messageoutput is then feed back (hence name)feedback is independent of messagecan be computed in advanceOi = EK(Oi-1)Ci = Pi XOR OiO-1 = IVuses: stream encryption on noisy channelsAn alternative to CFB is OFB. Here the generation of the "random" bits is independent of the message being encrypted. The output feedback (OFB) mode is similar in structure to that of CFB, except that the output of the encryption function is fed back to the shift register in OFB, whereas in CFB the ciphertext unit is fed back to the shift register. The other difference is that the OFB mode operates on full blocks of plaintext and ciphertext, not on an s-bit subset. The advantage is that firstly, they can be computed in advance, which is good for bursty traffic, and secondly, any bit error only affects a single bit. Thus this is good for noisy links (eg satellite TV transmissions etc).
20Advantages and Limitations of OFB needs an IV which is unique for each useif ever reuse attacker can recover outputsbit errors do not propagatemore vulnerable to message stream modificationsender & receiver must remain in synconly use with full block feedbacksubsequent research has shown that only full block feedback (ie CFB-64 or CFB-128) should ever be usedAs with CBC and CFB, the OFB mode requires an initialization vector. In the case of OFB, the IV must be a nonce; that is, the IV must be unique to each execution of the encryption operation. The reason for this is that the sequence of encryption output blocks, Oi. , depends only on the key and the IV, and does not depend on the plaintext. Therefore, for a given key and IV, the stream of output bits used to XOR with the stream of plaintext bits is fixed. If two different messages had an identical block of plaintext in the identical position, then an attacker would be able to determine that portion of the O stream.One advantage of the OFB method is that bit errors in transmission do not propagate. The disadvantage of OFB is that it is more vulnerable to a message stream modification attack than is CFB.OFB has the structure of a typical stream cipher, in that the cipher generates a stream of bits as a function of an initial value and a key, and that stream of bits is XORed with the plaintext bits. Hence the sender & receiver need to remain in sync, or all data is lost. Also, research has shown that you should only ever use a full block feedback ie OFB-64/128 mode. Hence OFB encrypts plaintext a full block at a time, where typically a block is 64 or 128 bits.
21Counter (CTR) a “new” mode, though proposed early on similar to OFB but encrypts counter value rather than any feedback valuemust have a different key & counter value for every plaintext block (never reused)Oi = EK(i)Ci = Pi XOR Oiuses: high-speed network encryptionsThe Counter (CTR) mode is a variant of OFB, but which encrypts a counter value (hence name). Although it was proposed many years before, it has only recently been standardized for use with AES along with the other existing 4 modes. It is being used with applications in ATM (asynchronous transfer mode) network security and IPSec (IP security). A counter, equal to the plaintext block size is used. The only requirement stated in SP A is that the counter value must be different for each plaintext block that is encrypted. Typically the counter is initialized to some value and then incremented by 1 for each subsequent block. As with the OFB mode, the initial counter value must be a nonce; be different for all of the messages encrypted using the same key. Further, all counter values across all messages must be unique. If, contrary to this requirement, a counter value is used multiple times, then the confidentiality of all of the plaintext blocks corresponding to that counter value may be compromised.
22Counter (CTR)Stallings Figure 6.7 illustrates the Counter (CTR) Mode.
23Advantages and Limitations of CTR efficiencycan do parallel encryptions in h/w or s/wcan preprocess in advance of needgood for bursty high speed linksrandom access to encrypted data blocksprovable security (good as other modes)but must ensure never reuse key/counter values, otherwise could break (cf OFB)CTR mode has a number of advantages in parallel h/w & s/w efficiency, can preprocess the output values in advance of needing to encrypt, can get random access to encrypted data blocks, and is simple. But like OFB have issue of not reusing the same key+counter value.
24Feedback Character-istics Note that, with the exception of ECB, all of the NIST-approved block cipher modes of operation involve feedback. This is clearly seen in Stallings Figure 6.8. To highlight the feedback mechanism, it is useful to think of the encryption function as taking input from a input register whose length equals the encryption block length and with output stored in an output register. The input register is updated one block at a time by the feedback mechanism. After each update, the encryption algorithm is executed, producing a result in the output register. Meanwhile, a block of plaintext is accessed. Note that both OFB and CTR produce output that is independent of both the plaintext and the ciphertext. Thus, they are natural candidates for stream ciphers that encrypt plaintext by XOR one full block at a time.