Des

Data Encryption Standard Eric Conrad

Data Encryption Standard Introduction DES is the Data Encryption Standard, a United States government standard encryption algorithm for encrypting and decrypting unclassified data. DES is described by Federal Information Processing Standards (FIPS) 46; the most recent revision is FIPS 46-3.1 DES is based on IBM’s Lucifer cipher DES is a block cipher that takes a plaintext string as input and creates a ciphertext string of the same length. It uses a symmetric key, which means that the same key is used to convert ciphertext back into plaintext. The DES block size is 64 bits. The key size is also 64 bits, although 8 bits of the key are used for parity (error detection), which makes the effective DES key size 56 bits. A 56bit key length is now considered weak due to advances in computer processing power. With proper hardware, a brute force attack that systematically attempts all 2^56 (72 quadrillion) different DES keys is possible. One example of such hardware is Copacobana (Cost-Optimized Parallel COde Breaker)2, built by two German universities for roughly $10,000. It can crack a 56-bit DES key in an average of nine days. The Advanced Encryption Standard (AES) became the new FIPS-approved encryption standard on November 26, 2001, replacing DES3. Triple DES (described in FIPS 46-3) can still be used as a FIPS-approved algorithm. The term Data Encryption Algorithm (DEA) is sometimes used, which describes the actual algorithm (as opposed to the standard). In this context, TDEA is an acronym for Triple DES. ANSI X9.52-1998 describes Triple Data Encryption Algorithm Modes of Operation4 For the sake of consistency, this paper uses the term DES.

Modes of DES FIPS 81 describes four approved modes of DES: Electronic Codebook (ECB) mode, Cipher Block Chaining (CBC) mode, Cipher Feedback (CFB) mode, and Output Feedback (OFB) mode. 5 The National Institute of Standards and Technology (NIST) Special Publication 800-38A describes a 5th method, Counter (CTR).6 These modes can be used with both DES and Triple DES. Key differences in each mode are error propagation and block vs. stream ciphers. •

Error propagation means an error in a step of encryption or decryption (such as a bit flipped from 0 to 1) propagates to subsequent steps, which causes further errors.

1 FIPS 46-3. URL: http://csrc.nist.gov/publications/fips/fips46-3/fips46-3.pdf 2 http://www.copacobana.org 3 FIPS 197. URL: http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf 4 ANSI X9.52-1998. URL: http://webstore.ansi.org/ansidocstore/product.asp?sku=ANSI+X9.52-1998 5 FIPS 81. URL: http://csrc.nist.gov/publications/fips/fips81/fips81.htm 6 NIST SP 800-38a. URL: http://csrc.nist.gov/publications/nistpubs/800-38a/sp800-38a.pdf

• •

A block cipher encrypts a set block size of data (64 bits for ECB and CBC modes). A stream cipher encrypts bits or groups of bits (1–64 bits in CFB, OFB, and CTR modes). Although DES is a block cipher, it emulates stream ciphers in these modes.

Electronic Codebook (ECB) Mode Electronic Codebook is the DES native mode, “a direct application of the DES algorithm to encrypt and decrypt data.”7 In this mode, each block of plaintext is independently encrypted into a respective block of ciphertext. This is done via a Feistel (named after Horst Feistel, one of the creators of Lucifer) cipher, which creates 16 subkeys based on the symmetric key and encrypts the plaintext via 16 rounds of transformation. The same process is used (with the symmetric key) to convert ciphertext back into plaintext; the difference is the 16 subkeys are supplied in reverse order. Repeated blocks of identical plaintext result in repeated blocks of ciphertext, which can aid cryptanalysis of the ciphertext. This effect is best illustrated. The first image is the SANS logo (bitmap format); the second image is the SANS logo bitmap encrypted via DES ECB mode. Although the bitmap data is encrypted, the original pattern is clearly visible.

The pattern is visible because repeated blocks of plaintext pixels in the bitmap are encrypted into repeated blocks of respective ciphertext pixels. In this mode, errors do not propagate, as each block is encrypted independently. The term Codebook refers to cryptographic code books, which contain dictionaries of words or phrases (such as “Attack has begun”) with a coded equivalent (“The eagle has flown”).

Cipher Block Chaining (CBC) Mode Cipher Block Chaining Mode is a block cipher which XORs (exclusive OR) each new block of plaintext with the previous block of ciphertext (they are “chained” together). This means repeated blocks of plaintext do not result in repeated blocks of ciphertext. 7

FIPS 46-3, page 4

CBC also uses an initialization vector, which is a random initial block used to ensure that two identical plaintexts result in different ciphertexts (due to different initialization vectors). Here is the same SANS logo bitmap data, encrypted with DES CBC mode:

No pattern is visible. This is true for all DES modes other than ECB. In this mode, errors propagate, as each previous step’s encrypted output is XORed (“chained”) with the new block of plaintext.

Cipher Feedback (CFB) Mode Cipher Feedback mode is a stream cipher that encrypts plaintext by breaking it into units of X (from 1 to 64) bits. This allows bit or byte-level encryption. CFB mode uses a random initialization vector, and previous units of ciphertext are XORed with subsequent units of plaintext (the cipher is “fed back” to the plaintext). As with CBC, errors propagate.

Output Feedback (OFB) Mode Like CFB mode, Output Feedback mode uses a random initialization vector and encrypts plaintext by breaking it down into a stream by encrypting units of X (from 1 to 64) bits of plaintext. OFB mode differs from CFB mode by creating a pseudo-random stream of bits (called “output”), which is XORed with the plaintext during each step (the “output” is “fed back” to the plaintext). Because the output (and not ciphertext) is XORed to the plaintext, errors do not propagate.

Counter (CTR) Mode Counter mode is a stream cipher like OFB mode; the key difference is the addition of counter blocks. The counter can be added or concatenated to a nonce (a random value that is used once), and then incremented for each unit of plaintext that is encrypted. The first counter block acts as an initialization vector. In each round, the counter blocks are XORed with plaintext.

The addition of counter blocks allows breaking up encryption or decryption into parallel stages, boosting performance on appropriate hardware. Also, errors do not propagate.

DES Mode Summary Table 1: DES Mode Summary

Type ECB CBC CFB OFB CTR

Block Block Stream Stream Stream

Initialization Vector None Yes Yes Yes Counter

Errors Propagate No Yes Yes No No

Triple DES (TDES) FIPS 46-3 describes the Triple DES algorithm (also known as TDES).8 It can be used as a FIPS-approved encryption algorithm until 2030 to allow transition to AES.9 Note that Double DES is not used due to a meet-in-the-middle attack, which makes the effective key size 57 bits (it is essentially twice as hard to crack as DES, not exponentially harder).\ TDES uses three rounds of DES encryption and has a key length of 168 bits (56 * 3). Theoretical attacks can reduce the effective key length of TDES to roughly 112 bits10, although brute force attacks against TDES are currently not practical. The FIPS-approved implementation of TDES11 uses three rounds applied in encrypt – decrypt – encrypt (EDE) order. This might seem confusing, as the second round doesn’t actually decrypt: Decrypting with a different key simply scrambles the plaintext even more. EDE order also allows backwards compatibility with DES (see below). FIPS 46-3 also lists three keying options: three different keys (3TDES EDE), two different keys (2TDES EDE; the same key is used for rounds one and three), and one key (1TDES EDE; the same key used for three rounds).12 Here is 3TDES EDE encryption:

Here is 2TDES EDE encryption: 8

The acronym ‘3DES’ is sometimes used in the industry. It should be avoided, as it causes confusion with respect to keying options like 3TDES (see below). 9 NIST SP 800-67, page viii. URL: http://csrc.nist.gov/publications/nistpubs/800-67/SP800-67.pdf 10 Lucks, Stefan. Attacking Triple Encryption. URL: http://th.informatik.uni-mannheim.de/People/Lucks/papers/pdf/3des.pdf.gz 11 FIPS 46-3, page 15 12 FIPS 46-3, page 16

1TDES EDE is functionally the same as DES. Assuming a plaintext string of “SECRET”: 1. “SECRET” becomes ciphertext. 2. Ciphertext becomes “SECRET.” 3. “SECRET” becomes ciphertext. Step 3 is identical to Step 1. Given the same plaintext and key, cipherhext generated with 1TDES is identical to DES-generated ciphertext. 3TDES EDE is the strongest form. 2TDES EDE is frequently used in the banking industry, using common hardware, such as the IBM 4758 PCI Cryptographic Coprocessor13. 1TDES EDE exists for backwards compatibility with legacy systems using DES and should not be used for secure applications. Other modes that are not FIPS-approved are also used in the industry. The most common is 3TDES EEE (3-key Triple DES in Encrypt – Encrypt – Encrypt order).

Summary Although there is no silver bullet when it comes to network security, cryptography can play a key role in protecting critical information. There are three general types of cryptography: symmetric, asymmetric, and hash. This paper focused on one of the key symmetric key algorithms: DES.

13

Bond, Mike and Clayton, Richard. “Experience Using a Low-Cost FPGA Design to Crack DES Keys” URL: http://www.cl.cam.ac.uk/~rnc1/descrack/DEScracker.html