Internet Draft Paul Hoffman draft-hoffman-des40-00.txt Internet Mail Consortium Russ Housley SPYRUS May 14, 1996 Expires six months later Creating 40-Bit Keys for DES Status of this memo This document is an Internet-Draft. 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." To learn the current status of any Internet-Draft, please check the "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe), munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or ftp.isi.edu (US West Coast). 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 (such as the United States) give special preference to applications that use 40-bit keys. 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 occaisionally have been approved for export from the United States. 1.1 Discussion of this Draft This draft is being discussed on the "ietf-smime" mailing list. To subscribe, send a message to: ietf-smime-request@imc.org witht the single word subscribe in the body of the message. There is a Web site for the mailing list at . 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. 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 additonal 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. Authors' Addresses Paul Hoffman Internet Mail Consortium 127 Segre Place Santa Cruz, CA 95060 (408) 426-9827 phoffman@imc.org Russ Housley SPYRUS PO Box 1198 Herndon, VA 20172 (703) 435-7344 housley@spyrus.com