https://hal.inria.fr/hal-02396738Bonnetain, XavierXavierBonnetainSECRET - Security, Cryptology and Transmissions - Inria de Paris - Inria - Institut National de Recherche en Informatique et en AutomatiquePerrin, LéoLéoPerrinSECRET - Security, Cryptology and Transmissions - Inria de Paris - Inria - Institut National de Recherche en Informatique et en AutomatiqueTian, ShizhuShizhuTianState Key Laboratory of Information Security, Institute of Information Engineering - CAS - Chinese Academy of Sciences [Changchun Branch]School of Cyber Security - UCAS - University of Chinese Academy of Sciences [Beijing]SECRET - Security, Cryptology and Transmissions - Inria de Paris - Inria - Institut National de Recherche en Informatique et en AutomatiqueAnomalies and Vector Space Search: Tools for S-Box AnalysisHAL CCSD2019Shannon effectBCTVector space searchS-BoxBoolean FunctionsAnomaly[INFO.INFO-CR] Computer Science [cs]/Cryptography and Security [cs.CR][INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS][INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]Perrin, LéoSymmetric Cryptography in the Post-Quantum World - QUASYModo - - ERC-2016-STG2017-09-01 - 2022-08-31 - 714294 - VALID - 2019-12-06 10:53:282022-06-08 12:50:052019-12-06 11:08:37enConference papershttps://hal.inria.fr/hal-02396738/document10.1007/978-3-030-34578-5_8application/pdf1S-boxes are functions with an input so small that the simplest way to specify them is their lookup table (LUT). How can we quantify the distance between the behavior of a given S-box and that of an S-box picked uniformly at random? To answer this question, we introduce various "anomalies". These real numbers are such that a property with an anomaly equal to should be found roughly once in a set of $2^a$ random S-boxes. First, we present statistical anomalies based on the distribution of the coefficients in the difference distribution table, linear approximation table, and for the first time, the boomerang connectivity table. We then count the number of S-boxes that have block-cipher like structures to estimate the anomaly associated to those. In order to recover these structures, we show that the most general tool for decomposing S-boxes is an algorithm efficiently listing all the vector spaces of a given dimension contained in a given set, and we present such an algorithm. Combining these approaches, we conclude that all permutations that are actually picked uniformly at random always have essentially the same cryptographic properties and the same lack of structure.