HTTP/1.1 200 OK Date: Tue, 09 Apr 2002 00:23:17 GMT Server: Apache/1.3.20 (Unix) Last-Modified: Mon, 03 May 1999 13:04:00 GMT ETag: "2e9b36-1b3c-372d9ec0" Accept-Ranges: bytes Content-Length: 6972 Connection: close Content-Type: text/plain Internet Draft Paul Hoffman draft-hoffman-des40-03.txt Internet Mail Consortium Russ Housley SPYRUS April 30, 1999 Expires in six months Creating 40-Bit Keys for DES Status of this memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. 1. Introduction This document describes an method for shortening DES keys from 56 bits to 40 bits. The shortened keys are generally known as "DES-40". The motivation for this weakening is that some localities give export preference to applications that use relatively weak encryption algorithms. Some implementors want to use DES with 40-bit keys instead of other algorithms with 40-bit keys because they already have DES coded into their products. The weakened keys are then used with the DES encryption algorithm in the same manner as full-strength keys. There are many possible methods for reducing a 56-bit key to a 40-bit key. The method in this draft was chosen because one method is needed for interoperability. Further, this method has been known to occasionally have been approved for export from the United States. 2. Creating 40-Bit Keys for DES DES [DES] uses a 56-bit key. The key consists of eight 8-bit bytes; however the last (eighth) bit of each byte is used for parity, leaving 56 bits of key. To weaken the 8-byte, 56-bit key into a 40-bit key, you set to zero the first four bits of every other byte in the key, starting with the first byte. Stated a different way, you take the bitwise logical AND of the key and the binary value: 0000111111111111000011111111111100001111111111110000111111111111 Another way to picture this is: Bit positions: 0000000000111111111122222222223333333333444444444455555555556666 0123456789012345678901234567890123456789012345678901234567890123 Use: zzzzKKKpKKKKKKKpzzzzKKKpKKKKKKKpzzzzKKKpKKKKKKKpzzzzKKKpKKKKKKKp Legend: z = zero bit K = key bit p = parity bit Some implementations of DES require the parity bit of each byte to be set correctly in order for the key to be accepted. DES requires that the last bit of each byte be a parity bit. DES uses odd parity, meaning that the number of 1 bits in each byte should be odd. Therefore, to complete the transformation to a 40-bit key, the software SHOULD cause the parity in each byte to be odd, changing the last bit if necessary. 3. Security Considerations Current computer technology makes a brute-force attack on ciphertext that is encrypted with a 40-bit key fairly quick. This is true for any encryption algorithms, not just DES. Thus, 40-bit keys result in only weak security against decryption. As computers get faster, this weak security will become even weaker. Thus, 40-bit keys should never be used with data that has a high value if it is decrypted by an adversary. However, encrypting data with 40-bit keys prevents passive snoopers from immediately reading a message without using some significant but not onerous decryption effort. Because of the ease of a brute-force attack on 40-bit keys, the 56-bit key from which a 40-bit key is derived must not also be used as a 56-bit key. This is due to a simple attack that first derives the 40-bit key, then fills in the remaining 16 bits by brute force. Systems that produce 40-bit keys from 56-bit keys must assume that the associated 56-bit key is only slightly harder to compromise than the 40-bit key. Note that short keys (and 40 bits is generally considered short) are subject to a variety of brute-force attacks that are not possible with longer keys, thus making them even more dangerous. For example, if a 40-bit algorithm is used and encrypted text includes a block of bytes known to the attacker, then the attacker can pre-compute all possible encryptions of that block and do a rapid comparison against the pre-computed ciphertexts. Further, it is likely that more attacks on short keys will appear in the future, thereby rendering them even less suitable for protecting data. The shortening method described in this draft causes a discernable pattern of zero bits in the resulting key. There is no known literature at this time that describes whether cyphertext encrypted with a key that has this pattern of zeros is easier to decrypt than cyphertext that has no pattern. However, because 40-bit keys are already inherently weak, a decrease in security from the pattern is not considered to be very important relative to the inherent weakness due to the short key length. There are other methods for converting longer keys to shorter ones. For example, IBM has created a patented (and significantly more complex) method called "Commercial Data Masking Facility", or CDMF [CDMF]; other methods probably exist. These methods might result in keys that produce cyphertext that is harder (or easier) to determine through brute-force. A quick comparison of CDMF and DES-40 shows that the brute-force attack against CDMF require one additional DES operation. Saving one DES operation does not seem to warrant the additional complexity. A. References [CDMF] "Design of the Commercial Data Masking Facility Data Privacy Algorithm", 1st ACM Conference on Computer and Communications Security, ACM Press, 1993. [DES] ANSI X3.106, "American National Standard for Information Systems-Data Link Encryption," American National Standards Institute, 1983. B. Object Identifier In general, the algorithm identifiers associated with DES are used with DES-40 since the algorithm is exactly the same except that 16 of the key bits have known values. However, there are a few instances (such as algorithm negotiation) where DES-40 needs to be specified. The following algorithm identifier has been assigned for these cases. Note that no mode of operation is associated with this algorithm identifier. id-alg-des40 OBJECT IDENTIFIER ::= { iso(1) identified-organization(3) dod(6) internet(1) security(5) mechanisms(5) pkix(7) alg(6) 1 } C. Authors' Addresses Paul Hoffman Internet Mail Consortium 127 Segre Place Santa Cruz, CA 95060 USA phoffman@imc.org Russ Housley SPYRUS 381 Elden Street, Suite 1120 Herndon, VA 20170 USA housley@spyrus.com