Davies' Attack
   HOME

TheInfoList



OR:

In
cryptography Cryptography, or cryptology (from "hidden, secret"; and ''graphein'', "to write", or ''-logy, -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of Adversary (cryptography), ...
, the Davies attack is a dedicated statistical
cryptanalysis Cryptanalysis (from the Greek ''kryptós'', "hidden", and ''analýein'', "to analyze") refers to the process of analyzing information systems in order to understand hidden aspects of the systems. Cryptanalysis is used to breach cryptographic se ...
method for attacking the
Data Encryption Standard The Data Encryption Standard (DES ) is a symmetric-key algorithm for the encryption of digital data. Although its short key length of 56 bits makes it too insecure for modern applications, it has been highly influential in the advancement of cryp ...
(DES). The attack was originally created in 1987 by
Donald Davies Donald Watts Davies, (7 June 1924 – 28 May 2000) was a Welsh computer scientist and Internet pioneer who was employed at the UK National Physical Laboratory (NPL). During 1965-67 he invented modern data communications, including packet s ...
. In 1994,
Eli Biham Eli Biham () is an Israeli cryptographer and cryptanalyst who is a professor at the Technion - Israel Institute of Technology Computer Science department. From 2008 to 2013, Biham was the dean of the Technion Computer Science department, afte ...
and
Alex Biryukov Alex Biryukov () is a cryptographer, currently a full professor at the University of Luxembourg. Biography His notable work includes the design of the stream cipher LEX, as well as the cryptanalysis of numerous cryptographic primitives. In 1998, ...
made significant improvements to the technique. It is a
known-plaintext attack The known-plaintext attack (KPA) is an attack model for cryptanalysis where the attacker has access to both the plaintext (called a crib) and its encrypted version (ciphertext). These can be used to reveal secret keys and code books. The term " ...
based on the non-uniform
distribution Distribution may refer to: Mathematics *Distribution (mathematics), generalized functions used to formulate solutions of partial differential equations *Probability distribution, the probability of a particular value or value range of a varia ...
of the outputs of pairs of adjacent
S-boxes In cryptography, an S-box (substitution-box) is a basic component of symmetric key algorithms which performs substitution. In block ciphers, they are typically used to obscure the relationship between the key and the ciphertext, thus ensuring Sha ...
. It works by collecting many known plaintext/ciphertext pairs and calculating the empirical distribution of certain characteristics. Bits of the key can be deduced given sufficiently many known plaintexts, leaving the remaining bits to be found through brute force. There are tradeoffs between the number of required plaintexts, the number of key bits found, and the probability of success; the attack can find 24 bits of the key with 252 known plaintexts and 53% success rate. The Davies attack can be adapted to other
Feistel cipher In cryptography, a Feistel cipher (also known as Luby–Rackoff block cipher) is a symmetric structure used in the construction of block ciphers, named after the German-born physicist and cryptographer Horst Feistel, who did pioneering resear ...
s besides DES. In 1998, Pornin developed techniques for analyzing and maximizing a cipher's resistance to this kind of cryptanalysis.


References

* * * Cryptographic attacks Data Encryption Standard {{crypto-stub