1. Introduction Algebraic Structure Defectoscopy (ASD Tests).pdf

Algebraic Structure Defectoscopy (ASD Tests) Sean O’Neil VEST Corporation S.A.R.L. Abstract: 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 al l 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 fata l structural flaws even in complete ciphers l ike LILI, KeeLoq or TEA in a matter of seconds. Cryptanalysts can save their valuable time by requiring that a l l 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. 1. Introduction First, the term defectoscopy means non-destructive analysis. It is the Latin ‘defectus’ (failure, lack, deficit) combined with the Greek ‘–scopy’ (viewing). The term defectoscopy first appears in a 1948 work of A.K. Trapeznikov, the Russian pioneer of non-destructive analysis by X-rays. X-rays and their medical use for non-destructive analysis of the body were first discovered by the German physicist Wilhelm Conrad R?ntgen in 1895. Defectoscopy is also the name of the annual international exhibition of non-destructive analysis equipment. 1.1 Background There are numerous references in the cryptographic papers to the famous Luby-Rackoff[1] (LR) theorem recommending for block ciphers 4 rounds of a mysterious round function that can be proven to be a PRF. However, the separation between these theoretical results and the real world ciphers led to the division of block cipher designers and analysts into three mai