×

Cryptanalytic time-memory-data trade-offs for FX-constructions and the affine equivalence problem. (English) Zbl 1457.94123

Summary: The FX-construction was proposed in [J. Kilian and P. Rogaway, CRYPTO 1996, Lect. Notes Comput. Sci. 1109, 252–267 (1996; Zbl 1329.94067)] as a generalization of the DESX scheme. The construction increases the security of an \(n\)-bit core block cipher with a \(\kappa\)-bit key by using two additional \(n\)-bit masking keys. Recently, several concrete instances of the FX-construction were proposed, including PRINCE, PRIDE and MANTIS (presented in [J. Borghoff et al., ASIACRYPT 2012, Lect. Notes Comput. Sci. 7658, 208–225 (2012; Zbl 1292.94035); C. Beierle et al., CRYPTO 2016, Lect. Notes Comput. Sci. 9815, 123–153 (2016; Zbl 1372.94412); E. Barkan et al., CRYPTO 2006, Lect. Notes Comput. Sci. 4117, 1–21 (2006; Zbl 1161.94384)], respectively). In this paper, we devise new cryptanalytic time-memory-data trade-off attacks on FX-constructions. By fine-tuning the parameters to the recent FX-construction proposals, we show that the security margin of these ciphers against practical attacks is smaller than expected. Our techniques combine a special form of time-memory-data trade-offs, typically applied to stream ciphers, with a cryptanalytic technique by P.-A. Fouque et al. [ASIACRYPT 2014, Lect. Notes Comput. Sci. 8873, 420–438 (2014; Zbl 1306.94053)]. In the final part of the paper, we show that the techniques we use in cryptanalysis of the FX-construction are applicable to additional schemes. In particular, we use related methods in order to devise new time-memory trade-offs for solving the affine equivalence problem. In this problem, the input consists of two functions \(F,G: \{0,1\}^n \rightarrow \{0,1\}^n\), and the goal is to determine whether there exist invertible affine transformations \(A_1, A_2\) over \(\mathrm{GF}(2)^n\) such that \(G = A_2 \circ F \circ A_1\).

MSC:

94A60 Cryptography
94A62 Authentication, digital signatures and secret sharing

Software:

PRINCE; SKINNY
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] M.R. Albrecht, B. Driessen, E.B. Kavun, G. Leander, C. Paar, T. Yalçin, Block ciphers—focus on the linear layer (feat. PRIDE), in J.A. Garay, R. Gennaro, editors, Advances in Cryptology—CRYPTO 2014—34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part I. Lecture Notes in Computer Science, vol. 8616 (Springer, 2014), pp. 57-76 · Zbl 1317.94079
[2] E. Barkan, E. Biham, A. Shamir, Rigorous bounds on cryptanalytic time/memory tradeoffs, in C. Dwork, editor, CRYPTO. Lecture Notes in Computer Science, vol. 4117 (Springer, 2006), pp. 1-21 · Zbl 1161.94384
[3] C. Beierle, J. Jean, S. Kölbl, G. Leander, A. Moradi, T. Peyrin, Y. Sasaki, P. Sasdrich, S.M. Sim, The SKINNY family of block ciphers and its low-latency variant MANTIS, in M. Robshaw, J. Katz, editors, Advances in Cryptology—CRYPTO 2016—36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part II. Lecture Notes in Computer Science, vol. 9815 (Springer, 2016), pp. 123-153 · Zbl 1372.94412
[4] A. Biryukov, C.D. Cannière, A. Braeken, B. Preneel, A toolbox for cryptanalysis: linear and affine equivalence algorithms, in E. Biham, editor, Advances in Cryptology—EUROCRYPT 2003, International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, May 4-8, 2003, Proceedings. Lecture Notes in Computer Science, vol. 2656 (Springer, 2003), pp. 33-50 · Zbl 1038.94521
[5] A. Biryukov, A. Shamir, Cryptanalytic time/memory/data tradeoffs for stream ciphers, in T. Okamoto, editor, ASIACRYPT. Lecture Notes in Computer Science, vol. 1976 (Springer, 2000), pp. 1-13 · Zbl 0980.94013
[6] A. Biryukov, A. Shamir, D. Wagner, Real time cryptanalysis of A5/1 on a PC, in B. Schneier, editor, FSE. Lecture Notes in Computer Science, vol. 1978 (Springer, 2000), pp. 1-18 · Zbl 0994.68640
[7] A. Biryukov, D. Wagner, Advanced slide attacks, in B. Preneel, editor, EUROCRYPT. Lecture Notes in Computer Science, vol. 1807 (Springer, 2000), pp. 589-606 · Zbl 1082.94506
[8] Bitcoin network graphs. http://bitcoin.sipa.be/
[9] J. Borghoff, A. Canteaut, T. Güneysu, E.B. Kavun, M. Knezevic, L.R. Knudsen, G. Leander, V. Nikov, C. Paar, C. Rechberger, P. Rombouts, S.S. Thomsen, T. Yalçin, PRINCE—a low-latency block cipher for pervasive computing applications—extended abstract, in X. Wang, K. Sako, editors, ASIACRYPT. Lecture Notes in Computer Science, vol. 7658 (Springer, 2012), pp. 208-225 · Zbl 1292.94035
[10] J. Borst, B. Preneel, J. Vandewalle, On the time-memory tradeoff between exhaustive key search and table precomputation, in Proceedings of 19th Symposium in Information Theory in the Benelux, WIC (1998), pp. 111-118
[11] Brinkmann, M.; Leander, G., On the classification of APN functions up to dimension five, Des. Codes Cryptogr., 49, 1-3, 273-288 (2008) · Zbl 1184.94227
[12] A. Canteaut, J. Roué, On the behaviors of affine equivalent sboxes regarding differential and linear attacks, in Oswald, Fischlin [24], pp. 45-74 · Zbl 1365.94411
[13] J. Daemen, Limitations of the Even-Mansour construction, in ASIACRYPT, pp. 495-498 (1991) · Zbl 0825.94187
[14] I. Dinur. Cryptanalytic time-memory-data tradeoffs for FX-constructions with applications to PRINCE and PRIDE, in Oswald, Fischlin [24], pp. 231-253 · Zbl 1370.94504
[15] I. Dinur, An improved affine equivalence algorithm for random permutations, in J.B. Nielsen, V. Rijmen, editors, Advances in Cryptology—EUROCRYPT 2018—37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29-May 3, 2018 Proceedings, Part I. Lecture Notes in Computer Science, vol. 10820 (Springer, 2018), pp. 413-442 · Zbl 1423.94067
[16] O. Dunkelman, N. Keller, A. Shamir, Minimalism in cryptography: the Even-Mansour scheme revisited, in D. Pointcheval, T. Johansson, editors, EUROCRYPT. Lecture Notes in Computer Science, vol. 7237 (Springer, 2012), pp. 336-354 · Zbl 1297.94065
[17] Even, S.; Mansour, Y., A Construction of a Cipher from a Single Pseudorandom Permutation, J. Cryptology, 10, 3, 151-162 (1997) · Zbl 1053.94552
[18] P. Fouque, A. Joux, C. Mavromati, Multi-user collisions: applications to discrete logarithm, Even-Mansour and PRINCE, in P. Sarkar, T. Iwata, editors, Advances in Cryptology—ASIACRYPT 2014—20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014. Proceedings, Part I. Lecture Notes in Computer Science, vol. 8873 (Springer, 2014), pp. 420-438 · Zbl 1306.94053
[19] Hellman, ME, A cryptanalytic time-memory trade-off, IEEE Transactions on Information Theory, 26, 4, 401-406 (1980) · Zbl 0436.94016
[20] J. Kilian, P. Rogaway, How to protect DES against exhaustive key search, in N. Koblitz, editor, CRYPTO. Lecture Notes in Computer Science, vol. 1109 (Springer, 1996), pp. 252-267 · Zbl 1329.94067
[21] G. Leander, A. Poschmann, On the classification of 4 bit s-boxes, in C. Carlet, B. Sunar, editors, Arithmetic of Finite Fields, First International Workshop, WAIFI 2007, Madrid, Spain, June 21-22, 2007, Proceedings. Lecture Notes in Computer Science, vol. 4547 (Springer, 2007), pp. 159-176 · Zbl 1184.94239
[22] W. Michiels, P. Gorissen, H.D.L. Hollmann, Cryptanalysis of a generic class of white-box implementations, in R.M. Avanzi, L. Keliher, F. Sica, editors, Selected Areas in Cryptography, 15th International Workshop, SAC 2008, Sackville, New Brunswick, Canada, August 14-15, Revised Selected Papers. Lecture Notes in Computer Science, vol. 5381 (Springer, 2008), pp. 414-428 · Zbl 1256.94058
[23] N. I. of Standards and Technology. Recommendation for Key Management—Part 1: General (Revision 3). NIST Special Publication 800-57 (2012)
[24] E. Oswald, M. Fischlin, editors. Advances in Cryptology—EUROCRYPT 2015—34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part I. Lecture Notes in Computer Science, vol. 9056 (Springer, 2015) · Zbl 1321.94011
[25] J. Patarin, Hidden fields equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms, in U.M. Maurer, editor, Advances in Cryptology—EUROCRYPT ’96, International Conference on the Theory and Application of Cryptographic Techniques, Saragossa, Spain, May 12-16, 1996, Proceeding. Lecture Notes in Computer Science, vol. 1070 (Springer, 1996), pp. 33-48
[26] R.L. Rivest. DESX. Never Published (1984)
[27] F.-X. Standaert, G. Rouvroy, J.-J. Quisquater, J.-D. Legat, A time-memory tradeoff using distinguished points: new analysis & FPGA results, in B.S.K. Jr., Çetin Kaya Koç, C. Paar, editors, CHES. Lecture Notes in Computer Science, vol. 2523 (Springer, 2002), pp. 593-609 · Zbl 1020.94526
[28] van Oorschot, PC; Wiener, MJ, Parallel Collision Search with Cryptanalytic Applications, J. Cryptol., 12, 1, 1-28 (1999) · Zbl 0992.94028
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.