A Statistical Saturation Attack against the Block Cipher PRESENT
- 1 January 2009
- book chapter
- conference paper
- Published by Springer Science and Business Media LLC in Lecture Notes in Computer Science
Abstract
In this paper, we present a statistical saturation attack that combines previously introduced cryptanalysis techniques against block ciphers. As the name suggests, the attack is statistical and can be seen as a particular example of partitioning cryptanalysis. It extracts information about the key by observing non-uniform distributions in the ciphertexts. It can also be seen as a dual to saturation (aka square, integral) attacks in the sense that it exploits the diffusion properties in block ciphers and a combination of active and passive multisets of bits in the plaintexts. The attack is chosen-plaintext in its basic version but can be easily extended to a known-plaintext scenario. As an illustration, it is applied to the block cipher PRESENT proposed by Bogdanov et al. at CHES 2007. We provide theoretical arguments to predict the attack efficiency and show that it improves previous (linear, differential) cryptanalysis results. We also provide experimental evidence that we can break up to 15 rounds of PRESENT with 235.6 plaintext-ciphertext pairs. Eventually, we discuss the attack specificities and possible countermeasures. Although dedicated to PRESENT, it is an open question to determine if this technique improves the best known cryptanalysis for other ciphers.Keywords
This publication has 16 references indexed in Scilit:
- Multidimensional Linear Cryptanalysis of Reduced Round SerpentLecture Notes in Computer Science, 2008
- Improving the Time Complexity of Matsui’s Linear CryptanalysisPublished by Springer Science and Business Media LLC ,2007
- PRESENT: An Ultra-Lightweight Block CipherLecture Notes in Computer Science, 2006
- How Far Can We Go Beyond Linear Cryptanalysis?Lecture Notes in Computer Science, 2004
- On Multiple Linear ApproximationsLecture Notes in Computer Science, 2004
- Saturation Attacks on Reduced Round SkipjackLecture Notes in Computer Science, 2002
- A Statistical Attack on RC6Lecture Notes in Computer Science, 2001
- The block cipher SquarePublished by Springer Science and Business Media LLC ,1997
- Partitioning cryptanalysisLecture Notes in Computer Science, 1997
- A Generalization of Linear Cryptanalysis and the Applicability of Matsui’s Piling-up LemmaLecture Notes in Computer Science, 1995