Paper 2007/378

Algebraic Structure Defectoscopy

Sean O'Neil


We present a novel instrument of automated cryptanalysis suitable for measuring the number of rounds that can build one PRF round, so that 4 such rounds could be recommended as a Luby-Rackoff cipher secure against adaptive attacks. ASD tests can detect structural flaws in all kinds of cryptographic primitives and their implementations. We present our results for some of the well-known ciphers and hash functions and for some of the eSTREAM candidates. Our tools can distinguish complete Achterbahn, Grain v1 and Grain-128 from random, detect weak keys in the complete IDEA cipher and find fatal structural flaws even in complete ciphers like LILI, KeeLoq or TEA in a matter of seconds. Cryptanalysts can save their valuable time by requiring that all new ciphers must pass not only randomness tests, but also automated cryptanalysis tests like ours before they could be considered interesting for manual cryptanalytic study.

Note: Results of these tests applied to the AES candidates first appeared on in 1999. This paper was first submitted to the SASC 2007 workshop in December 2006 with a lot more technical information, but was rejected in January 2007. The results presented in this paper first appeared on in January 2007.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Tools for Cryptanalysis 2007 Workshop
ANFautomated cryptanalysisrandomness testsluby-rackoff cipherssecurity of ciphersblock ciphersstream ciphershash functions
Contact author(s)
sean @ cryptolib com
2007-12-12: last of 4 revisions
2007-09-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sean O'Neil},
      title = {Algebraic Structure Defectoscopy},
      howpublished = {Cryptology ePrint Archive, Paper 2007/378},
      year = {2007},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.