User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

A statistical saturation attack against the block cipher PRESENT

Primary tabs

download
  • Open access
  • PDF
  • 958.05 K
Collard, Baudoin [UCL] Standaert, François-Xavier [UCL]

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.

Document type Communication à un colloque (Conference Paper) – Présentation orale avec comité de sélection
Access type Accès libre
Publication date 2009
Conference "Topics in Cryptology - CT-RSA 2009", San Francisco, CA, USA (20-24 April 2009)
Peer reviewed yes
Host document Fischlin, M.; ; "Topics in Cryptology - CT-RSA 2009"- p. 195-210 (ISBN : 978-3-642-00861-0)
Publisher Springer-verlag
Affiliation UCL - FSA/ELEC - Département d'électricité
Links
  1. Anderson, R., Biham, E., Knudsen, L.: Serpent: A Proposal for the Advanced Encryption Standard. In: The proceedings of the First Advanced Encryption Standard (AES) Conference, Ventura, CA (August 1998)
  2. Baignères Thomas, Junod Pascal, Vaudenay Serge, How Far Can We Go Beyond Linear Cryptanalysis?, Advances in Cryptology - ASIACRYPT 2004 (2004) ISBN:9783540239758 p.432-450, 10.1007/978-3-540-30539-2_31
  3. Biryukov Alex, De Cannière Christophe, Quisquater Michaël, On Multiple Linear Approximations, Advances in Cryptology – CRYPTO 2004 (2004) ISBN:9783540226680 p.1-22, 10.1007/978-3-540-28628-8_1
  4. Bogdanov A., Knudsen L. R., Leander G., Paar C., Poschmann A., Robshaw M. J. B., Seurin Y., Vikkelsoe C., PRESENT: An Ultra-Lightweight Block Cipher, Cryptographic Hardware and Embedded Systems - CHES 2007 ISBN:9783540747345 p.450-466, 10.1007/978-3-540-74735-2_31
  5. Collard Baudoin, Standaert F. -X., Quisquater Jean-Jacques, Improving the Time Complexity of Matsui’s Linear Cryptanalysis, Lecture Notes in Computer Science ISBN:9783540767879 p.77-88, 10.1007/978-3-540-76788-6_7
  6. Daemen Joan, Knudsen Lars, Rijmen Vincent, The block cipher Square, Fast Software Encryption (1997) ISBN:9783540632474 p.149-165, 10.1007/bfb0052343
  7. Gilbert Henri, Handschuh Helena, Joux Antoine, Vaudenay Serge, A Statistical Attack on RC6, Fast Software Encryption (2001) ISBN:9783540417286 p.64-74, 10.1007/3-540-44706-7_5
  8. Harpes Carlo, Kramer Gerhard G., Massey James L., A Generalization of Linear Cryptanalysis and the Applicability of Matsui’s Piling-up Lemma, Advances in Cryptology — EUROCRYPT ’95 (1995) ISBN:9783540594093 p.24-38, 10.1007/3-540-49264-x_3
  9. Harpes Carlo, Massey James L., Partitioning cryptanalysis, Fast Software Encryption (1997) ISBN:9783540632474 p.13-27, 10.1007/bfb0052331
  10. Hermelin Miia, Cho Joo Yeon, Nyberg Kaisa, Multidimensional Linear Cryptanalysis of Reduced Round Serpent, Information Security and Privacy ISBN:9783540699712 p.203-215, 10.1007/978-3-540-70500-0_15
  11. Hwang Kyungdeok, Lee Wonil, Lee Sungjae, Lee Sangjin, Lim Jongin, Saturation Attacks on Reduced Round Skipjack, Fast Software Encryption (2002) ISBN:9783540440093 p.100-111, 10.1007/3-540-45661-9_8
  12. Kaliski Burton S., Robshaw M. J. B., Linear Cryptanalysis Using Multiple Approximations, Advances in Cryptology — CRYPTO ’94 ISBN:9783540583332 p.26-39, 10.1007/3-540-48658-5_4
  13. Knudsen Lars, Wagner David, Integral Cryptanalysis, Fast Software Encryption (2002) ISBN:9783540440093 p.112-127, 10.1007/3-540-45661-9_9
  14. Matsui Mitsuru, Linear Cryptanalysis Method for DES Cipher, Advances in Cryptology — EUROCRYPT ’93 ISBN:9783540576006 p.386-397, 10.1007/3-540-48285-7_33
  15. Minier Marine, Gilbert Henri, Stochastic Cryptanalysis of Crypton, Fast Software Encryption (2001) ISBN:9783540417286 p.121-133, 10.1007/3-540-44706-7_9
  16. Vaudenay, S.: An experiment on DES - Statistical Cryptanalysis, in the third ACM Conference on Computer Security, New Dehli, India, pp. 139–147 (March 1996)
  17. Wang Meiqin, Differential Cryptanalysis of Reduced-Round PRESENT, Progress in Cryptology – AFRICACRYPT 2008 ISBN:9783540681595 p.40-49, 10.1007/978-3-540-68164-9_4
Bibliographic reference Collard, Baudoin ; Standaert, François-Xavier. A statistical saturation attack against the block cipher PRESENT.Topics in Cryptology - CT-RSA 2009 (San Francisco, CA, USA, 20-24 April 2009). In: Fischlin, M.;, Topics in Cryptology - CT-RSA 2009, Springer-verlag2009, p. 195-210
Permanent URL http://hdl.handle.net/2078.1/67573