Abstract
Feistel constructions have been shown to be indifferentiable from random permutations at STOC 2011. Whereas how to properly mix the keys into an un-keyed Feistel construction without appealing to domain separation technique to obtain a block cipher which is provably secure against known-key and chosen-key attacks (or to obtain an ideal cipher) remains an open problem. We study this, particularly the basic structure of NSA’s SIMON family of block ciphers. SIMON family takes a construction which has the subkey xored into a halve of the state at each round. More clearly, at the i-th round, the state is updated according to
For such key-alternating Feistel ciphers, we show that 21 rounds are sufficient to achieve indifferentiability from ideal ciphers with 2n-bit blocks and n-bit keys, assuming the n-to-n-bit round functions F 1,…,F 21 to be random and public and an identical user-provided n-bit key to be applied at each round. This gives an answer to the question mentioned before, which is the first to our knowledge.
A full version of this paper is available [16].
Chapter PDF
Similar content being viewed by others
References
Abed, F., List, E., Lucks, S., Wenzel, J.: Differential cryptanalysis of round-reduced simon and speck. In: Fast Software Encryption 2014. LNCS. Springer, Heidelberg (2014) (to appear)
Andreeva, E., Bogdanov, A., Dodis, Y., Mennink, B., Steinberger, J.P.: On the indifferentiability of key-alternating ciphers. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 531–550. Springer, Heidelberg (2013)
Andreeva, E., Bogdanov, A., Mennink, B.: Towards understanding the known-key security of block ciphers. In: Moriai, S. (ed.) FSE 2013. LNCS, vol. 8424, pp. 348–366. Springer, Heidelberg (2014)
Aysum, A., Gulcan, E., Schaumont, P.: Simon says, break the area records for symmetric key block ciphers on fpgas. Tech. rep., Cryptology ePrint Archive, Report 2014/237 (2014), http://eprint.iacr.org
Barbosa, M., Farshim, P.: The related-key analysis of feistel constructions. In: Fast Software Encryption 2014. LNCS. Springer, Heidelberg (2014) (to appear)
Beaulieu, R., Shors, D., Smith, J., Treatman-Clark, S., Weeks, B., Wingers, L.: The simon and speck families of lightweight block ciphers
Biryukov, A., Nikolić, I.: Complementing feistel ciphers. In: Moriai, S. (ed.) FSE 2013. LNCS, vol. 8424, pp. 3–18. Springer, Heidelberg (2014)
Biryukov, A., Roy, A., Velichkov, V.: Differential analysis of block ciphers simon and speck. In: Fast Software Encryption 2014. LNCS. Springer, Heidelberg (2014) (to appear)
Black, J.A.: The ideal-cipher model, revisited: An uninstantiable blockcipher-based hash function. In: Robshaw, M. (ed.) FSE 2006. LNCS, vol. 4047, pp. 328–340. Springer, Heidelberg (2006)
Bouillaguet, C., Dunkelman, O., Leurent, G., Fouque, P.-A.: Another look at complementation properties. In: Hong, S., Iwata, T. (eds.) FSE 2010. LNCS, vol. 6147, pp. 347–364. Springer, Heidelberg (2010)
Boura, C., Naya-Plasencia, M., Suder, V.: Scrutinizing and improving impossible differential attacks: Applications to CLEFIA, Camellia, LBlock and SIMON. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014, PART I. LNCS, vol. 8873, pp. 179–199. Springer, Heidelberg (2014)
Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. J. ACM 51(4), 557–594 (2004)
Coron, J.-S., Dodis, Y., Malinaud, C., Puniya, P.: Merkle-damgård revisited: How to construct a hash function. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 430–448. Springer, Heidelberg (2005)
Coron, J.-S., Patarin, J., Seurin, Y.: The random oracle model and the ideal cipher model are equivalent. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 1–20. Springer, Heidelberg (2008)
Demay, G., Gaži, P., Hirt, M., Maurer, U.: Resource-restricted indifferentiability. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 664–683. Springer, Heidelberg (2013)
Guo, C., Lin, D.: On the indifferentiability of key-alternating feistel ciphers with no key derivation. Cryptology ePrint Archive, Report 2014/786 (2014), http://eprint.iacr.org/
Holenstein, T., Künzler, R., Tessaro, S.: The equivalence of the random oracle model and the ideal cipher model, revisited. In: Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing, STOC 2011, pp. 89–98. ACM, New York (2011)
Lampe, R., Seurin, Y.: How to construct an ideal cipher from a small set of public permutations. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part I. LNCS, vol. 8269, pp. 444–463. Springer, Heidelberg (2013)
Lampe, R., Seurin, Y.: Security analysis of key-alternating feistel ciphers. In: Fast Software Encryption 2014. LNCS. Springer, Heidelberg (2014) (to appear)
Luby, M., Rackoff, C.: How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal on Computing 17(2), 373–386 (1988)
Mandal, A., Patarin, J., Seurin, Y.: On the public indifferentiability and correlation intractability of the 6-round feistel construction. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 285–302. Springer, Heidelberg (2012)
Maurer, U., Pietrzak, K.: The security of many-round luby-rackoff pseudo-random permutations. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 544–561. Springer, Heidelberg (2003)
Maurer, U.M., Renner, R.S., Holenstein, C.: Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 21–39. Springer, Heidelberg (2004)
Patarin, J.: Pseudorandom permutations based on the D.E.S. scheme. In: Charpin, P., Cohen, G. (eds.) EUROCODE 1990. LNCS, vol. 514, pp. 193–204. Springer, Heidelberg (1991)
Patarin, J.: Security of random feistel schemes with 5 or more rounds. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 106–122. Springer, Heidelberg (2004)
Ristenpart, T., Shacham, H., Shrimpton, T.: Careful with composition: Limitations of the indifferentiability framework. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 487–506. Springer, Heidelberg (2011)
Seurin, Y.: Primitives et protocoles cryptographiques àsécurité prouvée. Ph.D. thesis, PhD thesis, Université de Versailles Saint-Quentin-en-Yvelines, France (2009)
Sun, S., Hu, L., Wang, P., Qiao, K., Ma, X., Song, L.: Automatic security evaluation and (Related-key) differential characteristic search: Application to SIMON, PRESENT, lBlock, DES(L) and other bit-oriented block ciphers. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014, PART I. LNCS, vol. 8873, pp. 158–178. Springer, Heidelberg (2014)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 International Association for Cryptologic Research
About this paper
Cite this paper
Guo, C., Lin, D. (2015). On the Indifferentiability of Key-Alternating Feistel Ciphers with No Key Derivation. In: Dodis, Y., Nielsen, J.B. (eds) Theory of Cryptography. TCC 2015. Lecture Notes in Computer Science, vol 9014. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-46494-6_6
Download citation
DOI: https://doi.org/10.1007/978-3-662-46494-6_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-46493-9
Online ISBN: 978-3-662-46494-6
eBook Packages: Computer ScienceComputer Science (R0)