Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Boosting Authenticated Encryption Robustness with Minimal Modifications Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

Indifferentiability of Iterated Even-Mansour Ciphers with Non-idealized Key-Schedules: Five Rounds Are Necessary and Sufficient

verfasst von : Yuanxi Dai, Yannick Seurin, John Steinberger, Aishwarya Thiruvengadam

Erschienen in: Advances in Cryptology – CRYPTO 2017

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We prove that the 5-round iterated Even-Mansour (IEM) construction with a non-idealized key-schedule (such as the trivial key-schedule, where all round keys are equal) is indifferentiable from an ideal cipher. In a separate result, we also prove that five rounds are necessary by describing an attack against the corresponding 4-round construction. This closes the gap regarding the exact number of rounds for which the IEM construction with a non-idealized key-schedule is indifferentiable from an ideal cipher, which was previously only known to lie between four and twelve. Moreover, the security bound we achieve is comparable to (in fact, slightly better than) the previously established 12-round bound.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Information-Theoretic Indistinguishability via the Chi-Squared Method
Nächstes Kapitel Encrypted Davies-Meyer and Its Dual: Towards Optimal Security Using Mirror Theory
Fußnoten
1
Some SPNs do not adhere to the key-alternating abstraction because they introduce the key at the permutation stage as well—e.g., by using keyed S-boxes.
 
2
Actually we consider a slight variant of the trivial key-schedule where the first and last round keys are omitted, but both our negative and positive results are straightforward to extend to the “standard” trivial key-schedule. See Sect. 2 for a discussion.
 
3
While the difference between a table-defined and table-undefined 2chain will be important in the formal proof, we ignore this subtlety for the moment.
 
4
Again, there is a slight subtlety for the left endpoint of a (1, 2)-2chain and the right endpoint of a (4, 5)-2chain since this involves the ideal cipher, but we ignore it here.
 
5
In the randomness mapping, we will need to convert an arbitrary distinguisher to one that “completes all paths”. If the distinguisher is only allowed q arbitrary queries in total, the number of queries will balloon up to 6q; but if D is given extra power as described here, the reduction only increases q to 2q.
 
6
Probabilistically speaking, this trivially holds if \(P_4\) is a random partial permutation defined at only polynomially many points, though our proof is made more complicated by the fact that \(P_4\) also contains “adapted” queries.
 
7
As argued within the proof, this ordering issue does not actually introduce an extra factor of two into the bounds.
 
8
Or more exactly, to at most \(2q(2q-1)\) path completions, which leads to slightly better bounds used in the proof.
 
9
For a query cycle, these \(\mathrm {Enc}/\mathrm {Dec}\) queries are made by the simulator, while for a cipher query cycle, a single call to \(\mathrm {Enc}\) or \(\mathrm {Dec}\) is made by the distinguisher.
 
10
Since \(\mathcal {H}\), \(\mathcal {K}\), \(\mathcal {E}\), \(\mathcal {P}\), \(\mathcal {P}^*\), \(\mathcal {A}\) and \(\mathcal {C}\) are multisets, two distinct elements may be equal. Because of the distinctness requirement, we have \(\mathcal {H}^{\oplus 2} \ne \mathcal {H}\oplus \mathcal {H}\), etc.
 
11
Indeed, detecting all paths of length 3 would also be problematic for the termination argument, given the larger number of rounds.
 
Literatur
1.
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. LNCS, vol. 8042, pp. 531–550. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-40041-4_​29 CrossRef
2.
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). doi:10.​1007/​978-3-662-43933-3_​18
3.
Bellare, M., Kohno, T.: A theoretical treatment of related-key attacks: RKA-PRPs, RKA-PRFs, and applications. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 491–506. Springer, Heidelberg (2003). doi:10.​1007/​3-540-39200-9_​31 CrossRef
4.
Bellare, M., Pointcheval, D., Rogaway, P.: Authenticated key exchange secure against dictionary attacks. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 139–155. Springer, Heidelberg (2000). doi:10.​1007/​3-540-45539-6_​11 CrossRef
5.
Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: ACM Conference on Computer and Communications Security, pp. 62–73 (1993)
6.
7.
8.
Biryukov, A., Khovratovich, D., Nikolić, I.: Distinguisher and related-key attack on the full AES-256. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 231–249. Springer, Heidelberg (2009). doi:10.​1007/​978-3-642-03356-8_​14 CrossRef
9.
Black, J.: 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). doi:10.​1007/​11799313_​21 CrossRef
10.
Black, J., Rogaway, P., Shrimpton, T.: Black-box analysis of the block-cipher-based hash-function constructions from PGV. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 320–335. Springer, Heidelberg (2002). doi:10.​1007/​3-540-45708-9_​21 CrossRef
11.
Bogdanov, A., Knudsen, L.R., Leander, G., Standaert, F.-X., Steinberger, J., Tischhauser, E.: Key-alternating ciphers in a provable setting: encryption using a small number of public permutations - (Extended abstract). In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 45–62. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-29011-4_​5 CrossRef
12.
13.
14.
15.
16.
Coron, J., Holenstein, T., Künzler, R., Patarin, J., Seurin, Y., Tessaro, S.: How to build an ideal cipher: the indifferentiability of the Feistel construction. J. Cryptol. 29(1), 61–114 (2016)MathSciNetCrossRefMATH
17.
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). doi:10.​1007/​11535218_​26 CrossRef
18.
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). doi:10.​1007/​978-3-540-85174-5_​1 CrossRef
19.
Dai, Y., Seurin, Y., Steinberger, J.P., Thiruvengadam, A.: Five rounds are sufficient and necessary for the indifferentiability of iterated Even-Mansour. IACR Cryptology ePrint Archive, Report 2017/042 (2017). http://​eprint.​iacr.​org/​2017/​042
20.
21.
22.
Desai, A.: The security of all-or-nothing encryption: protecting against exhaustive key search. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 359–375. Springer, Heidelberg (2000). doi:10.​1007/​3-540-44598-6_​23 CrossRef
23.
Dodis, Y., Stam, M., Steinberger, J., Liu, T.: Indifferentiability of confusion-diffusion networks. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 679–704. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-49896-5_​24 CrossRef
24.
Dunkelman, O., Keller, N., Shamir, A.: Minimalism in cryptography: the Even-Mansour scheme revisited. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 336–354. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-29011-4_​21 CrossRef
25.
Even, S., Mansour, Y.: A construction of a cipher from a single pseudorandom permutation. J. Cryptol. 10(3), 151–162 (1997)MathSciNetCrossRefMATH
26.
27.
Fiat, A., Shamir, A.: How To prove yourself: practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987). doi:10.​1007/​3-540-47721-7_​12 CrossRef
28.
29.
30.
31.
Hoang, V.T., Tessaro, S.: Key-alternating ciphers and key-length extension: exact bounds and multi-user security. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9814, pp. 3–32. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-53018-4_​1 CrossRef
32.
Holenstein, T., Künzler, R., Tessaro, S.: The equivalence of the random oracle model and the ideal cipher model, revisited. In: Fortnow, L., Vadhan, S.P. (eds.) Symposium on Theory of Computing - STOC 2011, pp. 89–98. ACM (2011). Full version http://​arxiv.​org/​abs/​1011.​1264
33.
Iwata, T., Kohno, T.: New security proofs for the 3GPP confidentiality and integrity algorithms. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 427–445. Springer, Heidelberg (2004). doi:10.​1007/​978-3-540-25937-4_​27 CrossRef
34.
Kilian, J., Rogaway, P.: How to protect DES against exhaustive key search. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 252–267. Springer, Heidelberg (1996). doi:10.​1007/​3-540-68697-5_​20
35.
36.
37.
Lampe, R., Patarin, J., Seurin, Y.: An asymptotically tight security analysis of the iterated Even-Mansour cipher. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 278–295. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-34961-4_​18 CrossRef
38.
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. LNCS, vol. 8269, pp. 444–463. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-42033-7_​23 CrossRef
39.
40.
Maurer, U., Renner, R., 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). doi:10.​1007/​978-3-540-24638-1_​2 CrossRef
41.
42.
Preneel, B., Govaerts, R., Vandewalle, J.: Hash functions based on block ciphers: a synthetic approach. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 368–378. Springer, Heidelberg (1994). doi:10.​1007/​3-540-48329-2_​31 CrossRef
43.
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). doi:10.​1007/​978-3-642-20465-4_​27 CrossRef
44.
Seurin, Y.: Primitives et protocoles cryptographiques à sécurité prouvée. Ph.D. thesis, Université de Versailles Saint-Quentin-en-Yvelines, France (2009)
45.
46.
Winternitz, R.S.: A secure one-way hash function built from DES. In: IEEE Symposium on Security and Privacy, pp. 88–90 (1984)
Metadaten
Titel
Indifferentiability of Iterated Even-Mansour Ciphers with Non-idealized Key-Schedules: Five Rounds Are Necessary and Sufficient
verfasst von
Yuanxi Dai
Yannick Seurin
John Steinberger
Aishwarya Thiruvengadam
Copyright-Jahr
2017
Buch
Advances in Cryptology – CRYPTO 2017

Print ISBN: 978-3-319-63696-2

Electronic ISBN: 978-3-319-63697-9

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-63697-9_18

Premium Partner

    Bildnachweise