Baignères, ThomasVaudenay, Serge2006-07-142006-07-142006-07-14200510.1007/11693383_5https://infoscience.epfl.ch/handle/20.500.14299/232611WOS:0002369889000058549In this paper we study the substitution-permutation network (SPN) on which Rijndael is based. We introduce Rijndael*, a SPN identical to Rijndael except that fixed S-boxes are replaced by random and independent permutations. We prove that this construction resists linear and differential cryptanalysis with 4 inner rounds only, despite the huge cumulative effect of multipath characteristics that is induced by the symmetries of Rijndael. We show that the DP and LP terms both tend towards 1/(2¹²⁸-1) very fast when the number of round increases. This proves a conjecture by Keliher, Meijer, and Tavares. We further show that Rijndael* is immune to any iterated attack of order 1 after 10 rounds only, which substantially improves a previous result by Moriai and Vaudenay.Differential CryptanalysisLinear CryptanalysisDifferentialsLinear HullsProvable SecurityRijndaeltext::conference output::conference proceedings::conference paper