Known-key distinguishing attack

In cryptography, a known-key distinguishing attack is an attack model against symmetric ciphers, whereby an attacker who knows the key can find a structural property in cipher, where the transformation from plaintext to ciphertext is not random. There is no common formal definition for what such a transformation may be. The chosen-key distinguishing attack is strongly related, where the attacker can choose a key to introduce such transformations.

These attacks do not directly compromise the confidentiality of ciphers, because in a classical scenario, the key is unknown to the attacker. Known-/chosen-key distinguishing attacks apply in the "open key model" instead. They are known to be applicable in some situations where block ciphers are converted to hash functions, leading to practical collision attacks against the hash.

Known-key distinguishing attacks were first introduced in 2007 by Lars Knudsen and Vincent Rijmen in a paper that proposed such an attack against 7 out of 10 rounds of the AES cipher and another attack against a generalized Feistel cipher. Their attack finds plaintext/ciphertext pairs for a cipher with a known key, where the input and output have s least significant bits set to zero, in less than 2^s time (where s is fewer than half the block size).

These attacks have also been applied to reduced-round Threefish (Skein) and Phelix.

See also

• Distinguishing attack
• Pseudorandom permutation
• Ciphertext indistinguishability

References

Further reading

• Yu Sasaki; Kan Yasuda. "Formalizing Known-Key "Distinguishers" - New Attacks on Feistel Ciphers" (PDF). Slides from CRYPTO 2010 Rump Session.