Triple DES

From Wikipedia, the free encyclopedia

Jump to: navigation, search
Triple Data Encryption Algorithm
General
First published 1998 (ANS X9.52)
Derived from DES
Cipher detail
Key sizes 168, 112 or 56 bits (Keying option 1, 2, 3 respectively)
Block sizes 64 bits
Structure Feistel network
Rounds 48 DES-equivalent rounds
Best public cryptanalysis
Lucks: 232 known plaintexts, 2113 operations including 290 DES encryptions, 288 memory; Biham: find one of 228 target keys with a handful of chosen plaintexts per key and 284 encryptions

In cryptography, Triple DES is the common name for the Triple Data Encryption Algorithm (TDEA) block cipher defined in each of:

It is so named because it applies the Data Encryption Standard (DES) cipher algorithm three times to each data block.

Triple DES provides a relatively simple method of increasing the key size of DES to protect against brute force attacks, without requiring a completely new block cipher algorithm.

Contents

[edit] Name of the algorithm

The earliest standard that defines the algorithm (ANS X9.52, published in 1998) describes it as the "Triple Data Encryption Algorithm (TDEA)" — i.e. three operations of the Data Encryption Algorithm specified in ANSI X3.92 — and does not use the terms "Triple DES" or "DES" at all. FIPS PUB 46-3 (1999) defines the "Triple Data Encryption Algorithm (TDEA)", but also uses the terms "DES" and "Triple DES". It uses the terms "Data Encryption Algorithm" and "DES" interchangeably, including starting the specification with:

The Data Encryption Standard (DES) shall consist of the following Data Encryption Algorithm (DES) and Triple Data Encryption Algorithm (TDEA, as described in ANSI X9.52).

NIST SP 800-67(2004, 2008[3]) primarily uses the term TDEA, but also refers to "Triple DES (TDEA)". ISO/IEC 18033-3 (2005) uses "TDEA", but mentions that:

The TDEA is commonly known as Triple DES (Data Encryption Standard).

[edit] Algorithm

Triple DES uses a "key bundle" which comprises three DES keys, K1, K2 and K3, each of 56 bits (excluding parity bits). The encryption algorithm is:

ciphertext = EK3(DK2(EK1(plaintext)))

I.e., DES encrypt with K1, DES decrypt with K2, then DES encrypt with K3.

Decryption is the reverse:

plaintext = DK1(EK2(DK3(ciphertext)))

I.e., decrypt with K3, encrypt with K2, then decrypt with K1.

Each triple encryption encrypts one block of 64 bits of data.

Note that in each case the middle operation is the reverse of the first and last. This improves the strength of the algorithm when using keying option 2, and provides backward compatibility with DES with keying option 3.

[edit] Keying options

The standards define three keying options:

  • Keying option 1: All three keys are independent.
  • Keying option 2: K1 and K2 are independent, and K3 = K1.
  • Keying option 3: All three keys are identical, i.e. K1 = K2 = K3.

Keying option 1 is the strongest, with 3 x 56 = 168 independent key bits.

Keying option 2 provides less security, with 2 x 56 = 112 key bits. This option is stronger than simply DES encrypting twice, e.g. with K1 and K2, because it protects against meet-in-the-middle attacks.

Keying option 3 is no better than DES, with only 56 key bits. This option provides backward compatibility with DES, because the first and second DES operations simply cancel out. It is no longer recommended by the National Institute of Science and Technology (NIST) [4] and not supported by ISO/IEC 18033-3.

[edit] Encryption of more than one block

As with all block ciphers, encryption and decryption of multiple blocks of data may be performed using a variety of modes of operation, which can generally be defined independently of the block cipher algorithm. However ANS X9.52 specifies directly, and NIST SP 800-67 specifies (via SP 800-38A[5]), that some modes shall only be used with certain constraints on them that do not necessarily apply to general specifications of those modes. For example, ANS X9.52 specifies that for cipher block chaining, the initialization vector shall be different each time, whereas ISO/IEC 10116[6] does not. FIPS PUB 46-3 and ISO/IEC 18033-3 define only the single block algorithm, and do not place any restrictions on the modes of operation for multiple blocks.

[edit] Security

In general Triple DES with three independent keys (keying option 1) has a key length of 168 bits (three 56-bit DES keys), but due to the meet-in-the-middle attack the effective security it provides is only 112 bits. Keying option 2, reduces the key size to 112 bits. However, this option is susceptible to certain chosen-plaintext or known-plaintext attacks[7][8] and thus it is designated by NIST to have only 80 bits of security.[9]

The best attack known on keying option 1 requires around 232 known plaintexts, 2113 steps, 290 single DES encryptions, and 288 memory[10] (the paper presents other tradeoffs between time and memory). This is not currently practical and NIST considers keying option 1 to be appropriate through 2030.[9] If the attacker seeks to discover any one of many cryptographic keys, there is a memory-efficient attack which will discover one of 228 keys, given a handful of chosen plaintexts per key and around 284 encryption operations.[11]

[edit] Usage

The electronic payment industry uses Triple DES and continues to develop and promulgate standards based upon it (e.g. EMV).[12]

[edit] See also

[edit] References and notes

  1. ^ ANSI's Standards Store website lists (in March 2009) the standard as ANSI X9.52, but a printed copied used for reference when writing this article is marked ANS X9.52.
  2. ^ Federal Register vol 70, number 96, Announcing Approval of the Withdrawal of Federal Information Processing Standard (FIPS) 46–3, Data Encryption Standard (DES); FIPS 74, Guidelines for Implementing and Using the NBS Data Encryption Standard; and FIPS 81, DES Modes of Operation
  3. ^ NIST SP 800-67 version 1 was published in May 2004. It was revised in May 2008, as version 1.1, making a correction and clarification to the list of weak and semi-weak keys. Both versions use the same terminology.
  4. ^ NIST SP 800-67
  5. ^ NIST Special Publication 800-38A, Recommendation for Block Cipher Modes of Operation, Methods and Techniques, 2001 Edition
  6. ^ ISO/IEC 10116:2006 Information technology — Security techniques — Modes of operation for an n-bit block cipher
  7. ^ Ralph Merkle, Martin Hellman: On the Security of Multiple Encryption (PDF), Communications of the ACM, Vol 24, No 7, pp 465–467, July 1981.
  8. ^ Paul van Oorschot, Michael J. Wiener, A known-plaintext attack on two-key triple encryption, EUROCRYPT'90, LNCS 473, 1990, pp 318–325.
  9. ^ a b NIST, Special Publication 800-57 Recommendation for Key Management—Part 1: general (PDF).
  10. ^ Stefan Lucks: Attacking Triple Encryption (PDF), Fast Software Encryption 1998, pp 239–253.
  11. ^ Eli Biham: How to Forge DES-Encrypted Messages in 228 Steps (PostScript), 1996.
  12. ^ EMV 4.2 Specifications, Book 2 - Security and Key Management, version 4.2, June 2008
Personal tools