Symmetric Ciphers
| A symmetric cipher is a cipher in which encryption and decryption use the same key or keys that are mathematically related to one another in such a way that it is easy to compute one key from knowledge of the other, which is effectively a single key. Since the single key is the only secret to encryption and decryption, it is critical that this key be kept strictly private. Otherwise, an interloper could easily encrypt and decrypt messages at will, and we would be leaking information and accomplishing nothing. For this reason, symmetric ciphers are often referred to as private key, secret key, or shared key ciphers. In contrast, asymmetric ciphers involve the use of a pair of keys that are mathematically related , but it is intentionally very difficult to determine one key from knowledge of the other. As we shall see in Chapter 4, this makes it necessary only to keep one private key secret to one individual, and the corresponding public key can then be safely made available to everyone. Symmetric encryption and decryption are represented mathematically by the following, where E is an encryption function, D is a decryption function, k is the single shared secret key, M is a plaintext message, and C is the corresponding ciphertext message.
Figure 3-1 shows how symmetric cryptography works. Note that the sender and receiver (i.e., Bob and Alice) must agree beforehand on what secret key and what algorithm will be used. Along with the algorithm, there are associated details, such as the initialization vector, mode of operation, and padding convention that must also be agreed upon. These associated details are explained shortly. Figure 3-1. Symmetric cryptography. There are two basic types of symmetric algorithms: block ciphers and stream ciphers. A block cipher processes a block of bytes (usually 64 or 128 bits) at a time. A stream cipher processes a single byte or even a single bit at a time. We shall see that the distinction between block and stream ciphers is somewhat artificial, because certain modes of operation allow a block cipher to behave as a stream cipher. As we shall see in the next chapter, asymmetric ciphers solve several significant cryptographic problems; however, they tend to be less secure than symmetric ciphers (for a given key size), and symmetric ciphers tend to be faster, making them more suitable for encrypting large quantities of bulk data. It is important to recognize that symmetric and asymmetric ciphers are used to solve different security problems, and in fact their strengths are often complementary to one another. For this reason, there are several important cryptographic protocols that make use of a combination of both symmetric and asymmetric algorithms to accomplish sets of desirable security goals. Many symmetric ciphers have been developed throughout history, whereas asymmetric ciphers are a fairly recent invention. Symmetric ciphers improved slowly until just after World War II, when the advent of computers produced a rapid improvement in cipher designs that were developed secretly by several governments . By the late 1970s, private organizations began to discover and use powerful, modern symmetric ciphers that evolved from work done by Horst Feistel in 1967 at IBM. [1] In particular, the Data Encryption Standard (DES) algorithm was adopted as a standard by the U.S. government in 1977 to be used within the federal government for the protection of sensitive but unclassified data. Subsequently, DES was also used in the private sector for many security-related applications, especially in the areas of financial transactions and other banking applications.
DESDES is documented in the FIPS [2] PUB 46-3 document as well as in ANSI standard X9.32. Although DES is not considered to be ultra -secure [3] by today's standards, it is still heavily used. In fact, every time you use an ATM machine, you are probably using DES. It is still suitable for keeping secrets that are not extremely sensitive and valuable , especially where legacy software is being used, and it is still the most heavily used encryption scheme in commercial use. It was temporarily recommended that DES be replaced as a standard by the more powerful Triple DES algorithm in the 1990s, and subsequently it was formally replaced by the Rijndael algorithm, which is now the current U.S. government standard for symmetric encryption.
DES is a symmetric block cipher that transforms 64-bit data blocks using a 56-bit shared secret key, involving 16 rounds of permutation and substitution. As mentioned in Chapter 2, substitution (replacing bits within the data) adds confusion, since it makes the relationship between plaintext and ciphertext more complex. Transposition (moving bits within the data) results in diffusion, which spreads information throughout the ciphertext data block, making it more random and harder for a cryptanalyst to know if he or she is heading in the right direction when attempting to discover the plaintext. Mathematically, DES maps the set of all possible 64-bit numbers onto itself in a reversible manner. DES uses the same 56-bit key for both encryption and decryption (making it a symmetric algorithm). The key selects any one of 2 56 possible invertible mappings (i.e., one-to-one transformations). Selecting a key simply selects one of these invertible mappings. DES basically deals with 64-bit data blocks; however, since plaintext data is not typically a multiple of 64-bits, it must first be broken into 64-bit blocks, and then the last partial block must be padded with any required additional bits (there are several padding techniques in use). Each DES round takes the 64-bit block of input data, which is then partitioned into two 32-bit halves . The right half is encrypted with a specialized encryption function, using a subset of bits taken from the 56-bit key that is unique to the current round, and XORed with the left portion to form the new right portion for the next round. The previous right portion is then substituted into the left portion for the next round. Figure 3-2 shows the basic structure of a single round of DES. Figure 3-2. A single round of DES. Figure 3-3 shows the overall structure of the entire 16 rounds of DES. We do not show all of the details involved in the DES algorithm here. For example, the 48-bit subkeys for each round (K1 through K16) are generated from the original 56-bit key in a manner involving several bit manipulations that depend on which round they are applied to. We also do not go into other implementation details here, such as the specialized encryption function used in each round that includes an expansion permutation, an S-box substitution, and a P-box permutation in each round. To use DES in practical situations, these details are not very important; however, if you are interested, you may want to read the FIPS 46-3 [4] document for these DES design details.
Figure 3-3. Sixteen rounds of DES. Modes of OperationDES is a block cipher, and what we looked at in the previous section is just how DES works at the individual block level. However, arbitrary-length plaintext does not typically fit exactly within a single 64-bit data block. Therefore, block ciphers, such as DES and Rijndael, must be able to operate on sequences of input data blocks. To handle sequences of data blocks, these ciphers must operate according to certain agreed-upon rules, as defined by modes of operation. There are four standard DES modes of operation (ECB, CBC, CFB, and OFB) defined by FIPS PUB 81. [5] In addition, the CTS mode was developed for use with the RC5 cipher as defined in RFC 2040, but it can be adapted to other block ciphers as well. These five modes are defined by the CipherMode enumeration in the System.Security.Cryptography of the .NET Framework. Here are the full names for each of these modes:
It turns out that in the current release of the .NET Framework, only some of these modes are actually available with certain algorithms. ECB, CBC, and CFB currently work with the DES, Triple DES, and RC2 algorithms. Only ECB and CBC currently work with the Rijndael algorithm. OFB and CTS do not work with any algorithm yet; however, their inclusion in the CipherMode enumeration seems to imply that they might be supported eventually. It is also interesting to note that CTS was originally intended for use with the RC5 algorithm, which is entirely missing for the current release of the .NET Framework. In spite of some missing pieces, we look at four of these modes of operation in the next several sections in order to gain a more complete picture of operating modes. We will soon see an actual .NET program that demonstrates how to work with these operating modes. However, let's first look briefly at how these modes work at a conceptual level. In order to understand these details, take note of the following notation:
ECB MODEThe simplest mode, ECB, goes through the 16 Feistel rounds described above for each 64-bit block individually and independently. For a given 56-bit key, ECB mode always results in the same mapping between a given plaintext block and the corresponding ciphertext block, and bit errors are not propagated into subsequent blocks. The fact that blocks are processed independently is why this mode is named ECB, since a (very large) codebook could theoretically be created for each key. ECB has some advantages over other modes. For example, it allows you to randomly encrypt and decrypt blocks of data in a file or a database, since each block is processed independently of all other blocks. ECB also allows encryption and decryption to be performed on multiple blocks concurrently, assuming that you have a hardware implementation that can take advantage of this parallel processing. Unfortunately, the gains made by ECB in simplicity must be weighed against its slightly reduced security. The security problem with ECB is that an attacker could compile a codebook as plaintext/ciphertext pairs are guessed or discovered . These pairs may be obtained in various ways because of the repeating nature of certain byte sequences, such as message headers or common salutations. The interesting thing about this attack is that the key is never actually needed, but, as the codebook grows, it assists in further cryptanalysis, helping the codebook to grow further, with a snowballing positive-feedback effect. This is like the way a jigsaw puzzle gradually becomes easier as you continue to fit more pieces into the picture. Figure 3-4 shows how ECB mode works. Figure 3-4. ECB mode. As you can see from Figure 3-4, ECB has each block of the plaintext message M i transformed by the encryption function E k independently from other blocks. Of course, the decryption in ECB mode also has each ciphertext block C i decrypted independently of other blocks by the D k function. Mathematically, the ECB mode can be described as follows . ECB mode encryption:
ECB mode decryption:
CBC MODECBC is a more secure technique, which does not permit the construction of a codebook. CBC performs an XOR (exclusive-or) operation on each 64-bit plaintext block with the previous ciphertext block prior to going through the Feistel rounds. The first block is XORed with a random 64-bit initialization vector (IV), since the first plaintext block has no previous ciphertext block. You can think of the IV as nothing more than a dummy ciphertext block to prime the pump for this mode. Interestingly, the IV is not considered to be secret, and it may be safely transmitted in the clear. If this seems surprising, consider that the IV is effectively just another ciphertext block, not a secret key. Figure 3-5 shows how CBC mode works. Figure 3-5. CBC mode. As you can see from Figure 3-5, CBC takes each block of the plaintext message M i , which is first XORed with the previous ciphertext block C i “ 1 , and this result is then transformed by the encryption function E k to produce the ciphertext block C i . Decryption in ECB mode first decrypts the ciphertext block C i with the D k function, and this result is then XORed with the previous ciphertext block C i “ 1 to produce the plaintext block M i . Mathematically, CBC mode can be described as follows. The symbol CBC mode encryption:
CBC mode decryption:
CFB AND OFB MODESThere are two other standard DES modes, CFB mode and OFB mode, that allow you to deal with chunks of plaintext data that are less that the full 64-bit block size. This makes these modes useful as stream ciphers in which DES generates pseudorandom bits that are XORed with new plaintext as it becomes available to form new ciphertext data. [6] For example, 8-bit CFB can be used to encrypt and decrypt an ASCII or binary byte stream. ECB and CBC can process only 64-bit chunks at a time, but there are situations where you may need to immediately process smaller data chunks at a time. For example, a radar device may need to transmit individual encrypted bytes, one at a time, to a command and control system in real time, as they are generated. The system may not be able to tolerate waiting an arbitrary amount of time for a full 64-bit block, since it may need to react to information immediately as it is generated. ECB and CBC simply cannot deal with this type of situation satisfactorily, whereas CFB or OFB can.
For a given key, CBC and CFB modes do not result in a fixed mapping between plaintext blocks and ciphertext blocks, since it is affected by previous input blocks as well as by the IV used. This makes cryptanalysis harder, but it also means that a single bit error in a ciphertext block transmission corrupts both the current and the subsequent ciphertext block. For OFB, a single framing error (adding or losing bits in transmission) can corrupt all subsequent ciphertext blocks. An advantage of CFB over OFB is that CFB is self-synchronizing, meaning that even with a temporary loss of framing, it will automatically recover after one block of data. Figure 3-6 shows, in a simplified representation, how CFB works. The shift register makes it possible to use a moving subset of the previously generated output bits for XORing with the current input bits, as the algorithm proceeds. Not shown in this diagram is that only the leftmost subset of output bits from each previous stage is XORed with the input of the current stage. In other words, for 8-bit CFB, only the leftmost 8 bits of the previous output is XORed with the current 8 bits of the input data. There is nothing special about a step size of 8 bits, and, in fact, any bit size less than the DES block size of 64 bits may be used for each stage. By processing 8 bits at a time, 8-bit CFB effectively transforms DES, which is a block cipher, into a stream cipher. Figure 3-6. CFB mode. Mathematically, CFB mode can be described as follows. CFB mode encryption:
CFB mode decryption:
Figure 3-7 shows, in a simplified representation, how OFB mode works. As you can see, the basic idea is almost identical to what we just saw in CFB mode. The only difference is that in CFB mode the input to the shift register comes from bits in the previous stage after they are XORed. In contrast, OFB provides the input to the shift register from bits in the previous stage before they are XORed. Just as in the case of CFB, OFB allows the cipher to work on data in smaller pieces than the 64-bit block size that DES is based on. Figure 3-7. OFB mode. Mathematically, OFB mode can be described as follows. OFB mode encryption:
where R i “ 1 comes from the previous stage before the OFB mode decryption:
where R i “ 1 comes from the previous stage before the Triple DESThe banking industry has adopted the ANSI X9.52 [7] standard, also known as Triple DES, TDES, or 3DES. Triple DES was used as a more powerful interim alternative to DES. Triple DES is based directly on the basic design of DES and is quite backward-compatible with the original DES design and modes. The improvement comes from the fact that each 64-bit block of plaintext is encrypted three times, using the DES algorithm in which three distinct keys are used. Triple DES encrypts each block with the first key, then decrypts the result using the second key, and finally encrypts again using the third key. Triple DES increases the effective key size of DES, but the algorithm takes approximately three times as much time to compute compared to DES.
Triple DES encryption:
Triple DES decryption:
where k 1 , k 2 , k 3 are the three 56-bit keys. RijndaelMany experts now feel that DES is near the end of its useful life. In the late 1970s, a 56-bit key would have been viewed by many as sufficient for securing most sensitive commercial data, given the cost and speed of computers available at that time. Unfortunately, this is no longer quite so true, since computers are now much cheaper and faster. In general, you should always use encryption technology that will incur sufficient cost or time for potential attackers to consider it not worthwhile mounting an attack. With the doubling of digital circuit-switching speeds every 18 months, progress made in cryptanalysis research, along with the advent of inexpensive, customizable gate-array hardware and the massive distributed computing model made possible by the Internet, times have certainly changed. Triple DES was a very capable alternative, but it was only intended to be a temporary fix. A replacement for DES has recently gone through an international competition, and the official DES replacement, formerly referred to as AES (Advanced Encryption Standard), is the Rijndael algorithm. The Rijndael specification can be found in FIPS-197, [8] and, like its predecessor, it is intended for use by U.S. government organizations to protect unclassified sensitive information. It is expected that, over time, the Rijndael algorithm will have a huge impact on commercial software security, especially in financial applications.
Unlike the DES algorithm, which uses a fixed 56-bit key size, the Rijndael algorithm is more flexible in that it is able to use key sizes of 128, 192, or 256 bits (referred to as AES-128, AES-192, and AES-256, respectively). Whereas the data block size of DES was fixed at 64 bits, Rijndael can work with 128, 192, or 256 bit data blocks. Rijndael was originally designed to accommodate other key and block sizes, but the AES standard ignores these alternatives. The number of rounds in Rijndael depends on the block and key size. Nine rounds are used if the block and the key sizes are both 128 bits. Eleven rounds are used if either the block or the key size is greater than 128 bits but neither is greater than 192 bits. Thirteen rounds are used if either the block or key size is 256 bits. An additional modified final round is added to the end of the algorithm, so 10, 12, or 14 rounds are actually performed. The Rijndael algorithm is much more complex than DES, which was originally designed for simple and efficient digital-circuit hardware implementations . Rijndael involves advanced mathematical concepts, such as algebra on polynomials with coefficients in the Galois field GF (2 8 ), where the familiar concepts of addition and multiplication take on bizarre new meanings. These details are beyond the scope of this book; however, you are encouraged to read the FIPS-197 document for these details. Fortunately, you do not need to understand these gruesome details to use the Rijndael algorithm in your own .NET programs, since the .NET Framework hides the tough stuff quite nicely ! RC2RC2 is a registered trademark of RSA Data Security, Incorporated. The RC2 algorithm is a symmetric block cipher designed by Ronald Rivest in 1987, using a 64-bit input data block size. It was designed to be a drop-in replacement for DES, with improved performance, and a variable key size (from one byte up to 128 bytes) that allows for fine-tuning of its cryptographic strength. Effectively, RC2 can be made more or less secure than DES simply by choosing an appropriate key size. One of the strengths of RC2 is that it is designed to be about twice as fast as DES in typical software implementations. According to the folks at RSA Security, RC stands for either Ron's Code or Rivest's Cipher; however, it does not seem all that clear that they have settled the official story on this! RC2 is licensed for use in several commercial Internet software packages, including Lotus Notes, Microsoft Internet Explorer, Outlook Express, and Netscape Communicator. S/MIME (Secure/Multipurpose Internet Mail Extensions) allows for the choice of using RC2 (along with DES and Triple DES) to provide interoperable, secure email. The security services supported by RC2 in these applications are authentication via digital signatures and privacy via encryption. RC2 has been submitted to the IETF organization as a Request For Comment. For the detailed RC2 specification, see the RFC 2268 at http://www.ietf.org/rfc/rfc2268.txt.  |
represents the bitwise XOR operation, and 
EAN: 2147483647
Pages: 126