DES-X: Difference between revisions
m I added a little bit of information about the subject in question. |
m link cryptanalysis |
||
| (21 intermediate revisions by 15 users not shown) | |||
| Line 1: | Line 1: | ||
{{Short description|Block cipher}} |
|||
In [[cryptography]], '''DES-X''' (or '''DESX''') is a variant on the [[Data Encryption Standard|DES]] (Data Encryption Standard) [[Symmetric-key algorithm|symmetric-key]] [[block cipher]] intended to increase the complexity of a [[brute |
In [[cryptography]], '''DES-X''' (or '''DESX''') is a variant on the [[Data Encryption Standard|DES]] (Data Encryption Standard) [[Symmetric-key algorithm|symmetric-key]] [[block cipher]] intended to increase the complexity of a [[brute-force attack]]. The technique used to increase the complexity is called ''[[key whitening]]''. |
||
The original DES algorithm was specified in 1976 with a 56-bit [[key size]]: 2<sup>56</sup> possibilities for the [[key (cryptography)|key]]. There was criticism that an exhaustive search might be within the capabilities of large governments, particularly the United States' [[National Security Agency]] (NSA). One scheme to increase the key size of DES without substantially altering the algorithm was DES-X, proposed by [[Ron Rivest]] in May 1984. |
The original DES algorithm was specified in 1976 with a 56-bit [[key size]]: 2<sup>56</sup> possibilities for the [[key (cryptography)|key]]. There was criticism that an exhaustive search might be within the capabilities of large governments, particularly the United States' [[National Security Agency]] (NSA). One scheme to increase the key size of DES without substantially altering the algorithm was DES-X, proposed by [[Ron Rivest]] in May 1984. |
||
The algorithm has been included in [[RSA Security]]'s BSAFE cryptographic library since the late 1980s. |
The algorithm has been included in [[RSA Security]]'s [[RSA BSAFE|BSAFE]] cryptographic library since the late 1980s. |
||
DES-X augments DES by [[XOR]]ing an extra 64 bits of key (K<sub>1</sub>) to the [[plaintext]] ''before'' applying DES, and then XORing another 64 bits of key (K<sub>2</sub>) ''after'' the encryption: |
DES-X augments DES by [[XOR]]ing an extra 64 bits of key (K<sub>1</sub>) to the [[plaintext]] ''before'' applying DES, and then XORing another 64 bits of key (K<sub>2</sub>) ''after'' the encryption: |
||
| Line 9: | Line 10: | ||
<math>\mbox{DES-X}(M) = K_2 \oplus \mbox{DES}_K(M \oplus K_1)</math> |
<math>\mbox{DES-X}(M) = K_2 \oplus \mbox{DES}_K(M \oplus K_1)</math> |
||
[[File:Xor Encrypt Xor |
[[File:Xor Encrypt Xor.svg]] |
||
The key size is thereby increased to 56 + (2 × 64) = 184 bits. |
The key size is thereby increased to 56 + (2 × 64) = 184 bits. |
||
However, the effective key size (security) is only increased to 56+ |
However, the effective key size (security) is only increased to 56+64−1−''lb(M)'' = 119 − ''lb(M)'' = ~119 bits, where ''M'' is the number of [[Chosen-plaintext attack|chosen plaintext/ciphertext pairs]] the adversary can obtain, and ''lb'' denotes the [[binary logarithm]]. Moreover, key size drops to 88 bits given 2<sup>32.5</sup> known plaintext and using advanced slide attack. |
||
DES-X also increases the strength of DES against [[differential cryptanalysis]] and [[linear cryptanalysis]], although the improvement is much smaller than in the case of brute force attacks. It is estimated that differential cryptanalysis would require 2<sup>61</sup> chosen plaintexts (vs. 2<sup>47</sup> for DES), while linear cryptanalysis would require 2<sup>60</sup> known plaintexts (vs. 2<sup>43</sup> for DES or 2<sup>61</sup> for DES with independent subkeys.<ref>{{cite |
DES-X also increases the strength of DES against [[differential cryptanalysis]] and [[linear cryptanalysis]], although the improvement is much smaller than in the case of brute force attacks. It is estimated that differential [[cryptanalysis]] would require 2<sup>61</sup> chosen plaintexts (vs. 2<sup>47</sup> for DES), while linear cryptanalysis would require 2<sup>60</sup> known plaintexts (vs. 2<sup>43</sup> for DES or 2<sup>61</sup> for DES with independent subkeys.<ref>{{cite journal | doi=10.1007/BF00630563 |doi-access=free | title=Differential cryptanalysis of DES-like cryptosystems | date=1991 | last1=Biham | first1=Eli | last2=Shamir | first2=Adi | journal=Journal of Cryptology | volume=4 | pages=3–72 | s2cid=33202054 }}</ref>) Note that with 2<sup>64</sup> plaintexts (known or chosen being the same in this case), DES (or indeed any other [[block cipher]] with a 64 bit [[block size (cryptography)|block size]]) is totally broken as the whole cipher's codebook becomes available. |
||
Although the differential and linear attacks, currently best attack on DES-X is a known-plaintext slide attack |
|||
discovered by Biryukov-Wagner <ref>{{cite book |url=https://www.iacr.org/archive/eurocrypt2000/1807/18070595-new.pdf |doi=10.1007/3-540-45539-6_41 |doi-access=free |isbn=978-3-540-67517-4 |chapter=Advanced Slide Attacks |title=Advances in Cryptology — EUROCRYPT 2000 |series=Lecture Notes in Computer Science |date=2000 |last1=Biryukov |first1=Alex |last2=Wagner |first2=David |volume=1807 |pages=589–606 }}</ref> which has complexity of 2<sup>32.5</sup> known plaintexts and 2<sup>87.5</sup> time of analysis. Moreover the attack is easily converted into a ciphertext-only attack with the same data complexity and 2<sup>95</sup> offline time complexity. |
|||
==See also== |
==See also== |
||
| Line 25: | Line 29: | ||
==References== |
==References== |
||
{{Reflist}} |
{{Reflist}} |
||
* {{cite book |doi=10.1007/3-540-68697-5_20 |doi-access=free |chapter=How to Protect DES Against Exhaustive Key Search |title=Advances in Cryptology — CRYPTO '96 |series=Lecture Notes in Computer Science |date=1996 |last1=Kilian |first1=Joe |last2=Rogaway |first2=Phillip |volume=1109 |pages=252–267 |isbn=978-3-540-61512-5 }} |
|||
* Joe Kilian and Phillip Rogaway, [http://www.cs.ucdavis.edu/~rogaway/papers/desx.pdf How to protect DES against exhaustive key search](PDF), Advances in Cryptology - Crypto '96, Springer-Verlag (1996), pp. 252–267. |
|||
* P. Rogaway, [ |
* P. Rogaway, [https://web.cs.ucdavis.edu/~rogaway/papers/cryptobytes.pdf The security of DESX] (PDF), CryptoBytes '''2'''(2) (Summer 1996). |
||
* A. Biryukov and D. Wagner, Advanced Slide Attacks, Eurocrypt 2000, Springer-Verlag (2000), pp. 589–606. |
|||
==External links== |
==External links== |
||
* [http://www.rsasecurity.com/rsalabs/node.asp?id=2232 RSA FAQ Entry] |
* [https://web.archive.org/web/20040618163311/http://www.rsasecurity.com/rsalabs/node.asp?id=2232 RSA FAQ Entry] |
||
{{Cryptography navbox | block}} |
{{Cryptography navbox | block}} |
||
Latest revision as of 15:06, 26 January 2024
In cryptography, DES-X (or DESX) is a variant on the DES (Data Encryption Standard) symmetric-key block cipher intended to increase the complexity of a brute-force attack. The technique used to increase the complexity is called key whitening.
The original DES algorithm was specified in 1976 with a 56-bit key size: 256 possibilities for the key. There was criticism that an exhaustive search might be within the capabilities of large governments, particularly the United States' National Security Agency (NSA). One scheme to increase the key size of DES without substantially altering the algorithm was DES-X, proposed by Ron Rivest in May 1984.
The algorithm has been included in RSA Security's BSAFE cryptographic library since the late 1980s.
DES-X augments DES by XORing an extra 64 bits of key (K1) to the plaintext before applying DES, and then XORing another 64 bits of key (K2) after the encryption:
The key size is thereby increased to 56 + (2 × 64) = 184 bits.
However, the effective key size (security) is only increased to 56+64−1−lb(M) = 119 − lb(M) = ~119 bits, where M is the number of chosen plaintext/ciphertext pairs the adversary can obtain, and lb denotes the binary logarithm. Moreover, key size drops to 88 bits given 232.5 known plaintext and using advanced slide attack.
DES-X also increases the strength of DES against differential cryptanalysis and linear cryptanalysis, although the improvement is much smaller than in the case of brute force attacks. It is estimated that differential cryptanalysis would require 261 chosen plaintexts (vs. 247 for DES), while linear cryptanalysis would require 260 known plaintexts (vs. 243 for DES or 261 for DES with independent subkeys.[1]) Note that with 264 plaintexts (known or chosen being the same in this case), DES (or indeed any other block cipher with a 64 bit block size) is totally broken as the whole cipher's codebook becomes available.
Although the differential and linear attacks, currently best attack on DES-X is a known-plaintext slide attack discovered by Biryukov-Wagner [2] which has complexity of 232.5 known plaintexts and 287.5 time of analysis. Moreover the attack is easily converted into a ciphertext-only attack with the same data complexity and 295 offline time complexity.
See also[edit]
References[edit]
- ^ Biham, Eli; Shamir, Adi (1991). "Differential cryptanalysis of DES-like cryptosystems". Journal of Cryptology. 4: 3–72. doi:10.1007/BF00630563. S2CID 33202054.
- ^ Biryukov, Alex; Wagner, David (2000). "Advanced Slide Attacks". Advances in Cryptology — EUROCRYPT 2000 (PDF). Lecture Notes in Computer Science. Vol. 1807. pp. 589–606. doi:10.1007/3-540-45539-6_41. ISBN 978-3-540-67517-4.
- Kilian, Joe; Rogaway, Phillip (1996). "How to Protect DES Against Exhaustive Key Search". Advances in Cryptology — CRYPTO '96. Lecture Notes in Computer Science. Vol. 1109. pp. 252–267. doi:10.1007/3-540-68697-5_20. ISBN 978-3-540-61512-5.
- P. Rogaway, The security of DESX (PDF), CryptoBytes 2(2) (Summer 1996).
