secret-key cryptography; High-Degree Indicator Matrix; Feistel Network; ANF; Linear Approximation Table; Walsh Spectrum; Division Property; Integral Attack
Résumé :
[en] We introduce the high-degree indicator matrix (HDIM), an object closely related with both the linear approximation table and the algebraic normal form (ANF) of a permutation. We show that the HDIM of a Feistel Network contains very specific patterns depending on the degree of the Feistel functions, the number of rounds and whether the Feistel functions are 1-to-1 or not. We exploit these patterns to distinguish Feistel Networks, even if the Feistel Network is whitened using unknown affine layers.
We also present a new type of structural attack exploiting monomials that cannot be present at round r-1 to recover the ANF of the last Feistel function of a r-round Feistel Network. Finally, we discuss the relations between our findings, integral attacks, cube attacks, Todo's division property and the congruence modulo 4 of the Linear Approximation Table.
Disciplines :
Sciences informatiques
Auteur, co-auteur :
PERRIN, Léo Paul ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
UDOVENKO, Aleksei ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
Co-auteurs externes :
no
Langue du document :
Anglais
Titre :
Algebraic Insights into the Secret Feistel Network
Date de publication/diffusion :
2016
Nom de la manifestation :
23rd International Conference on Fast Software Encryption
Organisateur de la manifestation :
International Association for Cryptologic Research (IACR)
Lieu de la manifestation :
Bochum, Allemagne
Date de la manifestation :
20-23 March 2016
Manifestation à portée :
International
Titre de l'ouvrage principal :
Fast Software Encryption - 23rd International Workshop, FSE 2016, Bochum, March 20-23, 2016
Biryukov, A., Khovratovich, D.: Decomposition attack on SASASASAS. IACR Cryptology ePrint Archive, report 2015/46 (2015)
Biryukov, A., Bouillaguet, C., Khovratovich, D.: Cryptographic schemes based on the ASASA structure: black-box, white-box, and public-key (extended abstract). In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 63-84. Springer, Heidelberg (2014)
Minaud, B., Derbez, P., Fouque, P.-A., Karpman, P.: Key-recovery attacks on ASASA. In: Iwata, T., et al. (eds.) ASIACRYPT 2015. LNCS, vol. 9453, pp. 3-27. Springer, Heidelberg (2015). doi:10.1007/978-3-662-48800-3_1
Biryukov, A., Leurent, G., Perrin, L.: Cryptanalysis of Feistel Networks with secret round functions. In: Dunkelman, O., et al. (eds.) SAC 2015. LNCS, vol. 9566, pp. 102-121. Springer, Heidelberg (2016). doi:10.1007/978-3-319-31301-6_6
Dinur, I., Dunkelman, O., Keller, N., Shamir, A.: New attacks on Feistel structures with improved memory complexities. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 433-454. Springer, Heidelberg (2015)
Canteaut, A., Duval, S., Leurent, G.: Construction of lightweight S-Boxes using Feistel and MISTY structures (full version). Cryptology ePrint Archive, report 2015/711 (2015). http://eprint.iacr.org/
Biryukov, A., Perrin, L., Udovenko, A.: Reverse-engineering the S-Box of Streebog, Kuznyechik and STRIBOBr1. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 372-402. Springer, Heidelberg (2016). doi:10.1007/978-3-662-49890-3_15
Todo, Y.: Structural evaluation by generalized integral property. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 287-314. Springer, Heidelberg (2015)
Knudsen, L.R.: DEAL: a 128-bit block cipher, AES submission (1998)
Biryukov, A., Perrin, L.: On reverse-engineering S-Boxes with hidden design criteria or structure. In: Gennaro, R., Robshaw, M. (eds.) Advances in Cryptology -CRYPTO 2015. Lecture Notes in Computer Science, vol. 9215, pp. 116-140. Springer, Berlin Heidelberg (2015)
Carlet, C.: Boolean functions for cryptography and error correcting codes. In: Boolean Models and Methods in Mathematics, Computer Science, and Engineering, vol. 2, pp. 257-397 (2010)
Perrin, L., Udovenko, A.: Algebraic insights into the secret Feistel network (full version). Cryptology ePrint Archive, report 2016/398 (2016). http://eprint.iacr.org/
Wu, W., Zhang, L.: LBlock: a lightweight block cipher. In: Lopez, J., Tsudik, G. (eds.) ACNS 2011. LNCS, vol. 6715, pp. 327-344. Springer, Heidelberg (2011)
Matsui, M.: New block encryption algorithm MISTY. In: Biham, E. (ed.) FSE 1997. LNCS, vol. 1267, pp. 54-68. Springer, Heidelberg (1997)
Beaulieu, R., Shors, D., Smith, J., Treatman-Clark, S., Weeks, B., Wingers, L.: The SIMON and SPECK families of lightweight block ciphers. IACR Cryptology ePrint Archive, report 2013/404 (2013)
U.S. Department of Commerce/National Institute of Standards and Technology: Data encryption standard. Publication, Federal Information Processing Standards (1999)
Biryukov, A., Shamir, A.: Structural cryptanalysis of SASAS. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 395-405. Springer, Heidelberg (2001)
ETSI/Sage: Specification of the 3Gpp confidentiality and integrity algorithms 128-EEA3 & 128-EIA3. Document 4: Design and Evaluation Report, Technical report, ETSI/Sage, September 2011. (http://www.gsma.com/aboutus/wp-content/uploads/2014/12/EEA3EIA3Design Evaluationv20.pdf)
The Sage Developers: Sage Mathematics Software (Version 6.8) (2015). http://www.sagemath.org
Todo, Y.: Integral cryptanalysis on full MISTY1. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 413-432. Springer, Heidelberg (2015)
