Nakahara, Jorge
Sepehrdad, Pouyan
Zhang, Bingsheng
Wang, Meiqin
Linear (Hull) and Algebraic Cryptanalysis of the Block Cipher PRESENT
Proceedings of CANS'09
5888
58-75
The contributions of this paper include the first linear hull and a revisit of the algebraic cryptanalysis of reduced-round variants of the block cipher PRESENT, under known-plaintext and ciphertext- only settings. We introduce a pure algebraic cryptanalysis of 5-round PRESENT and in one of our attacks we recover half of the bits of the key in less than three minutes using an ordinary desktop PC. The PRESENT block cipher is a design by Bogdanov et al., announced in CHES 2007 and aimed at RFID tags and sensor networks. For our linear attacks, we can attack 25-round PRESENT with the whole code book, 296.68 25- round PRESENT encryptions, 240 blocks of memory and 0.61 success rate. Further we can extend the linear attack to 26-round with small success rate. As a further contribution of this paper we computed linear hulls in practice for the original PRESENT cipher, which corroborated and even improved on the predicted bias (and the corresponding attack complexities) of conventional linear relations based on a single linear trail.
block ciphers, RFID, linear hulls, algebraic analysis, sys- tems of sparse polynomial equations of low degree;
NCCR-MICS, NCCR-MICS/Secu;
Springer Berlin / Heidelberg
2009
http://infoscience.epfl.ch/record/147374/files/cans09.pdf;