Paper 2009/064

On the Data Complexity of Statistical Attacks Against Block Ciphers (full version)

Céline Blondeau and Benoît Gérard

Abstract

Many attacks on iterated block ciphers rely on statistical considerations using plaintext/ciphertext pairs to distinguish some part of the cipher from a random permutation. We provide here a simple formula for estimating the amount of plaintext/ciphertext pairs which is needed for such distinguishers and which applies to a lot of different scenarios (linear cryptanalysis, differential-linear cryptanalysis, differential/truncated differential/impossible differential cryptanalysis). The asymptotic data complexities of all these attacks are then derived. Moreover, we give an efficient algorithm for computing the data complexity accurately.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
statistical cryptanalysisiterated block cipherdata complexity.
Contact author(s)
celine blondeau @ inria fr
History
2009-02-12: last of 2 revisions
2009-02-10: received
See all versions
Short URL
https://ia.cr/2009/064
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/064,
      author = {Céline Blondeau and Benoît Gérard},
      title = {On the Data Complexity of Statistical Attacks Against Block Ciphers (full version)},
      howpublished = {Cryptology ePrint Archive, Paper 2009/064},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/064}},
      url = {https://eprint.iacr.org/2009/064}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.