User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Revisiting Key-Alternating Feistel Ciphers for Shorter Keys and Multi-user Security

Primary tabs

download
  • Open access
  • PDF
  • 733.03 K
Guo, Chun [UCL] Wang, Lei [Shanghai Jiao Tong University, Shanghai, China - Westone Cryptologic Research Center, Beijing, China]

Key-Alternating Feistel (KAF) ciphers, a.k.a. Feistel-2 models, refer to Feistel networks with round functions of the form Fi(ki⊕xi), where ki is the (secret) round-key and Fi is a public random function. This model roughly captures the structures of many famous Feistel ciphers, and the most prominent instance is DES. Existing provable security results on KAF assumed independent round-keys and round functions (ASIACRYPT 2004 & FSE 2014). In this paper, we investigate how to achieve security under simpler and more realistic assumptions: with round-keys derived from a short mainkey, and hopefully with identical round functions. For birthday-type security, we consider 4-round KAF, investigate the minimal conditions on the way to derive the four round-keys, and prove that when such adequately derived keys and the same round function are used, the 4-round KAF is secure up to 2n/2 queries. For beyond-birthday security, we focus on 6-round KAF. We prove that when the adjacent round-keys are independent, and independent round-functions are used, the 6 round KAF is secure up to 22n/3 queries. To our knowledge, this is the first beyond-birthday security result for KAF without assuming completely independent round-keys. Our results hold in the multi-user setting as well, constituting the first non-trivial multi-user provable security results on Feistel ciphers. We finally demonstrate applications of our results on designing key-schedules and instantiating keyed sponge constructions.

Document type Communication à un colloque (Conference Paper) – Présentation orale avec comité de sélection
Access type Accès libre
Publication date 2018
Language Anglais
Conference "24th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2018)", Brisbane, QLD (Australia) (du 02/12/2018 au 06/12/2018)
Journal information "Lecture Notes in Computer Science" - Vol. 11272, no.816, p. 213-243 (2018)
Peer reviewed yes
issn 0302-9743
e-issn 1611-3349
Publisher Springer (Heidelberg)
Publication status Publié
Affiliation UCL - SST/ICTM/ELEN - Pôle en ingénierie électrique
Keywords Blockcipher; Provable security; Multi-user security Key-alternating cipher; Feistel cipher; Key-schedule design Keyed sponge
Links
  1. Andreeva Elena, Daemen Joan, Mennink Bart, Van Assche Gilles, Security of Keyed Sponge Constructions Using a Modular Proof Approach, Fast Software Encryption (2015) ISBN:9783662481158 p.364-384, 10.1007/978-3-662-48116-5_18
  2. Bar-On Achiya, Biham Eli, Dunkelman Orr, Keller Nathan, Efficient Slide Attacks, 10.1007/s00145-017-9266-8
  3. Barbosa Manuel, Farshim Pooya, The Related-Key Analysis of Feistel Constructions, Fast Software Encryption (2015) ISBN:9783662467053 p.265-284, 10.1007/978-3-662-46706-0_14
  4. Beaulieu, R., Shors, D., Smith, J., Treatman-Clark, S., Weeks, B., Wingers, L.: The SIMON and SPECK families of lightweight block ciphers. Cryptology ePrint Archive, Report 2013/404 (2013). https://eprint.iacr.org/2013/404.pdf
  5. Bellare Mihir, Boldyreva Alexandra, Micali Silvio, Public-Key Encryption in a Multi-user Setting: Security Proofs and Improvements, Advances in Cryptology — EUROCRYPT 2000 (2000) ISBN:9783540675174 p.259-274, 10.1007/3-540-45539-6_18
  6. Bellare Mihir, Tackmann Björn, The Multi-user Security of Authenticated Encryption: AES-GCM in TLS 1.3, Advances in Cryptology – CRYPTO 2016 (2016) ISBN:9783662530177 p.247-276, 10.1007/978-3-662-53018-4_10
  7. Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: Sponge functions. In: Ecrypt Hash Workshop 2007 (2007)
  8. Biham Eli, How to decrypt or even substitute DES-encrypted messages in 228 steps, 10.1016/s0020-0190(02)00269-7
  9. Biryukov Alex, Nikolić Ivica, Complementing Feistel Ciphers, Fast Software Encryption (2014) ISBN:9783662439326 p.3-18, 10.1007/978-3-662-43933-3_1
  10. Biryukov Alex, Wagner David, Advanced Slide Attacks, Advances in Cryptology — EUROCRYPT 2000 (2000) ISBN:9783540675174 p.589-606, 10.1007/3-540-45539-6_41
  11. Bogdanov Andrey, Knudsen Lars R., Leander Gregor, Standaert Francois-Xavier, Steinberger John, Tischhauser Elmar, Key-Alternating Ciphers in a Provable Setting: Encryption Using a Small Number of Public Permutations, Advances in Cryptology – EUROCRYPT 2012 (2012) ISBN:9783642290107 p.45-62, 10.1007/978-3-642-29011-4_5
  12. Bose Priyanka, Hoang Viet Tung, Tessaro Stefano, Revisiting AES-GCM-SIV: Multi-user Security, Faster Key Derivation, and Better Bounds, Advances in Cryptology – EUROCRYPT 2018 (2018) ISBN:9783319783802 p.468-499, 10.1007/978-3-319-78381-9_18
  13. Canetti Ran, Goldreich Oded, Halevi Shai, The random oracle methodology, revisited, 10.1145/1008731.1008734
  14. Chen Shan, Lampe Rodolphe, Lee Jooyoung, Seurin Yannick, Steinberger John, Minimizing the Two-Round Even–Mansour Cipher, 10.1007/s00145-018-9295-y
  15. Chen Shan, Steinberger John, Tight Security Bounds for Key-Alternating Ciphers, Advances in Cryptology – EUROCRYPT 2014 (2014) ISBN:9783642552199 p.327-350, 10.1007/978-3-642-55220-5_19
  16. Cogliati Benoît, Lampe Rodolphe, Seurin Yannick, Tweaking Even-Mansour Ciphers, Lecture Notes in Computer Science (2015) ISBN:9783662479889 p.189-208, 10.1007/978-3-662-47989-6_9
  17. Cogliati Benoît, Seurin Yannick, Beyond-Birthday-Bound Security for Tweakable Even-Mansour Ciphers with Linear Tweak and Key Mixing, Advances in Cryptology – ASIACRYPT 2015 (2015) ISBN:9783662487990 p.134-158, 10.1007/978-3-662-48800-3_6
  18. Daemen Joan, Rijmen Vincent, Probability distributions of correlation and differentials in block ciphers, 10.1515/jmc.2007.011
  19. Dai Yuanxi, Seurin Yannick, Steinberger John, Thiruvengadam Aishwarya, Indifferentiability of Iterated Even-Mansour Ciphers with Non-idealized Key-Schedules: Five Rounds Are Necessary and Sufficient, Advances in Cryptology – CRYPTO 2017 (2017) ISBN:9783319636962 p.524-555, 10.1007/978-3-319-63697-9_18
  20. Dodis, Y., Katz, J., Steinberger, J., Thiruvengadam, A., Zhang, Z.: Provable security of substitution-permutation networks. Cryptology ePrint Archive, Report 2017/016 (2017). http://eprint.iacr.org/2017/016.pdf
  21. Dunkelman Orr, Keller Nathan, Shamir Adi, Slidex Attacks on the Even–Mansour Encryption Scheme, 10.1007/s00145-013-9164-7
  22. Even Shimon, Mansour Yishay, A construction of a cipher from a single pseudorandom permutation, 10.1007/s001459900025
  23. Gaži Peter, Pietrzak Krzysztof, Tessaro Stefano, The Exact PRF Security of Truncation: Tight Bounds for Keyed Sponges and Truncated CBC, Lecture Notes in Computer Science (2015) ISBN:9783662479889 p.368-387, 10.1007/978-3-662-47989-6_18
  24. Gentry Craig, Ramzan Zulfikar, Eliminating Random Permutation Oracles in the Even-Mansour Cipher, Advances in Cryptology - ASIACRYPT 2004 (2004) ISBN:9783540239758 p.32-47, 10.1007/978-3-540-30539-2_3
  25. Gilboa Shoni, Gueron Shay, Nandi Mridul, Balanced Permutations Even–Mansour Ciphers, 10.3390/cryptography1010002
  26. Gueron, S., Lindell, Y.: Better bounds for block cipher modes of operation via nonce-based key derivation. CCS 2017, 1019–1036 (2017)
  27. Guo Chun, Lin Dongdai, On the Indifferentiability of Key-Alternating Feistel Ciphers with No Key Derivation, Theory of Cryptography (2015) ISBN:9783662464939 p.110-133, 10.1007/978-3-662-46494-6_6
  28. Guo, C., Wang, L.: Revisiting key-alternating Feistel ciphers for shorter keys and multi-user security. Cryptology ePrint Archive, Report 2018/816 (2018). http://eprint.iacr.org/2018/816.pdf . The full version of this paper
  29. Guo Jian, Jean Jérémy, Nikolić Ivica, Sasaki Yu, Meet-in-the-Middle Attacks on Generic Feistel Constructions, Lecture Notes in Computer Science (2014) ISBN:9783662456071 p.458-477, 10.1007/978-3-662-45611-8_24
  30. Guo Jian, Peyrin Thomas, Poschmann Axel, The PHOTON Family of Lightweight Hash Functions, Advances in Cryptology – CRYPTO 2011 (2011) ISBN:9783642227912 p.222-239, 10.1007/978-3-642-22792-9_13
  31. Hoang Viet Tung, Rogaway Phillip, On Generalized Feistel Networks, Advances in Cryptology – CRYPTO 2010 (2010) ISBN:9783642146220 p.613-630, 10.1007/978-3-642-14623-7_33
  32. Hoang Viet Tung, Tessaro Stefano, Key-Alternating Ciphers and Key-Length Extension: Exact Bounds and Multi-user Security, Advances in Cryptology – CRYPTO 2016 (2016) ISBN:9783662530177 p.3-32, 10.1007/978-3-662-53018-4_1
  33. Isobe Takanori, Shibutani Kyoji, Generic Key Recovery Attack on Feistel Scheme, Advances in Cryptology - ASIACRYPT 2013 (2013) ISBN:9783642420320 p.464-485, 10.1007/978-3-642-42033-7_24
  34. Izadi Maryam, Sadeghiyan Babak, Sadeghian Seyed Saeed, Khanooki Hossein Arabnezhad, MIBS: A New Lightweight Block Cipher, Cryptology and Network Security (2009) ISBN:9783642104329 p.334-348, 10.1007/978-3-642-10433-6_22
  35. Jager Tibor, Stam Martijn, Stanley-Oakes Ryan, Warinschi Bogdan, Multi-key Authenticated Encryption with Corruptions: Reductions Are Lossy, Theory of Cryptography (2017) ISBN:9783319704999 p.409-441, 10.1007/978-3-319-70500-2_14
  36. Lampe Rodolphe, Seurin Yannick, Security Analysis of Key-Alternating Feistel Ciphers, Fast Software Encryption (2015) ISBN:9783662467053 p.243-264, 10.1007/978-3-662-46706-0_13
  37. Luby Michael, Wigderson Avi, Pairwise Independence and Derandomization, 10.1561/0400000009
  38. Luby M, Rackoff C, Pseudo-random permutation generators and cryptographic composition, 10.1145/12130.12167
  39. Mandal Avradip, Patarin Jacques, Seurin Yannick, On the Public Indifferentiability and Correlation Intractability of the 6-Round Feistel Construction, Theory of Cryptography (2012) ISBN:9783642289132 p.285-302, 10.1007/978-3-642-28914-9_16
  40. Maurer Ueli, Pietrzak Krzysztof, The Security of Many-Round Luby-Rackoff Pseudo-Random Permutations, Lecture Notes in Computer Science (2003) ISBN:9783540140399 p.544-561, 10.1007/3-540-39200-9_34
  41. Miles Eric, Viola Emanuele, Substitution-Permutation Networks, Pseudorandom Functions, and Natural Proofs, Lecture Notes in Computer Science (2012) ISBN:9783642320088 p.68-85, 10.1007/978-3-642-32009-5_5
  42. Mouha Nicky, Luykx Atul, Multi-key Security: The Even-Mansour Construction Revisited, Lecture Notes in Computer Science (2015) ISBN:9783662479889 p.209-223, 10.1007/978-3-662-47989-6_10
  43. Mouha Nicky, Mennink Bart, Van Herrewege Anthony, Watanabe Dai, Preneel Bart, Verbauwhede Ingrid, Chaskey: An Efficient MAC Algorithm for 32-bit Microcontrollers, Selected Areas in Cryptography -- SAC 2014 (2014) ISBN:9783319130507 p.306-323, 10.1007/978-3-319-13051-4_19
  44. Nachef Valerie, Patarin Jacques, Volte Emmanuel, Feistel Ciphers, ISBN:9783319495286, 10.1007/978-3-319-49530-9
  45. Nandi Mridul, The Characterization of Luby-Rackoff and Its Optimum Single-Key Variants, Progress in Cryptology - INDOCRYPT 2010 (2010) ISBN:9783642174001 p.82-97, 10.1007/978-3-642-17401-8_7
  46. Nandi Mridul, On the Optimality of Non-Linear Computations of Length-Preserving Encryption Schemes, Advances in Cryptology – ASIACRYPT 2015 (2015) ISBN:9783662487990 p.113-133, 10.1007/978-3-662-48800-3_5
  47. Patarin Jacques, How to Construct Pseudorandom and Super Pseudorandom Permutations from One Single Pseudorandom Function, Advances in Cryptology — EUROCRYPT’ 92 ISBN:9783540564133 p.256-266, 10.1007/3-540-47555-9_22
  48. Patarin, J.: Improved security bounds for pseudorandom permutations. In: CCS 1997, pp. 142–150. ACM (1997)
  49. Patarin Jacques, Security of Random Feistel Schemes with 5 or More Rounds, Advances in Cryptology – CRYPTO 2004 (2004) ISBN:9783540226680 p.106-122, 10.1007/978-3-540-28628-8_7
  50. Ramzan Zulfikar, Reyzin Leonid, On the Round Security of Symmetric-Key Cryptographic Primitives, Advances in Cryptology — CRYPTO 2000 (2000) ISBN:9783540679073 p.376-393, 10.1007/3-540-44598-6_24
  51. Rotaru, D., Smart, N.P., Stam, M.: Modes of operation suitable for computing on encrypted data. IACR Trans. Symmetric Cryptol. 2017(3), 294–324 (2017)
  52. Sadeghiyan Babak, Pieprzyk Josef, A Construction for Super Pseudorandom Permutations from A Single Pseudorandom Function, Advances in Cryptology — EUROCRYPT’ 92 ISBN:9783540564133 p.267-284, 10.1007/3-540-47555-9_23
  53. Soni Pratik, Tessaro Stefano, Public-Seed Pseudorandom Permutations, Lecture Notes in Computer Science (2017) ISBN:9783319566139 p.412-441, 10.1007/978-3-319-56614-6_14
  54. Standaert François-Xavier, Pereira Olivier, Yu Yu, Leakage-Resilient Symmetric Cryptography under Empirically Verifiable Assumptions, Advances in Cryptology – CRYPTO 2013 (2013) ISBN:9783642400407 p.335-352, 10.1007/978-3-642-40041-4_19
  55. Suzaki, T., Minematsu, K., Morioka, S., Kobayashi, E.: $$\mathit{TWINE}$$ : a lightweight block cipher for multiple platforms. In: Knudsen, L.R., Wu, H. (eds.) SAC 2012. LNCS, vol. 7707, pp. 339–354. Springer, Heidelberg (2013)
  56. Tessaro Stefano, Optimally Secure Block Ciphers from Ideal Primitives, Advances in Cryptology – ASIACRYPT 2015 (2015) ISBN:9783662487990 p.437-462, 10.1007/978-3-662-48800-3_18
  57. Wu Wenling, Zhang Lei, LBlock: A Lightweight Block Cipher, Applied Cryptography and Network Security (2011) ISBN:9783642215537 p.327-344, 10.1007/978-3-642-21554-4_19
Bibliographic reference Guo, Chun ; Wang, Lei. Revisiting Key-Alternating Feistel Ciphers for Shorter Keys and Multi-user Security.24th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2018) (Brisbane, QLD (Australia), du 02/12/2018 au 06/12/2018). In: Lecture Notes in Computer Science, Vol. 11272, no.816, p. 213-243 (2018)
Permanent URL http://hdl.handle.net/2078.1/211893