Structural Cryptanalysis of SASAS

  • Alex Biryukov
  • Adi Shamir
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2045)


In this paper we consider the security ofblo ck ciphers which contain alternate layers of invertible S-boxes and affine mappings (there are many popular cryptosystems which use this structure, including the winner of the AES competition, Rijndael). We show that a five layer scheme with 128 bit plaintexts and 8 bit S-boxes is surprisingly weak even when all the S-boxes and affine mappings are key dependent (and thus completely unknown to the attacker). We tested the attack with an actual implementation, which required just 216 chosen plaintexts and a few seconds on a single PC to find the 217 bits of information in all the unknown elements of the scheme.


Cryptanalysis Structural cryptanalysis block ciphers substitution permutation networks substitution affine networks Rijndael 


  1. 1.
    R. Anderson, E. Biham, L. Knudsen, Serpent: A Proposal for the AES, 1st AES Conference, 1998.Google Scholar
  2. 2.
    E. Biham, Cryptanalysis of Patarin’s 2-Round Public Key System with S-boxes (2R), proceedings of EUROCRYPT'2000, LNCS 1807, pp.408–416, Springer-Verlag, 2000.Google Scholar
  3. 3.
    J. Daemen, L. Knudsen, V. Rijmen, The Block Cipher Square, proceedings of FSE'97, LNCS 1267, pp.147–165, Springer-Verlag, 1997.Google Scholar
  4. 4.
    V. Rijmen, J. Daemen, AES Proposal: Rijndael, 1st AES Conference, 1998.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2001

Authors and Affiliations

  • Alex Biryukov
    • 1
  • Adi Shamir
    • 1
  1. 1.Computer Science departmentThe Weizmann InstituteRehovotIsrael

Personalised recommendations