nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Encrypt or Decrypt? To Make a Single-Key Beyond Birthday Secure Nonce-Based MAC

verfasst von : Nilanjan Datta, Avijit Dutta, Mridul Nandi, Kan Yasuda

Erschienen in: Advances in Cryptology – CRYPTO 2018

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

At CRYPTO 2016, Cogliati and Seurin have proposed a highly secure nonce-based MAC called Encrypted Wegman-Carter with Davies-Meyer (\(\textsf {EWCDM}\)) construction, as \(\textsf {E}_{K_2}\bigl (\textsf {E}_{K_1}(N)\oplus N\oplus \textsf {H}_{K_h}(M)\bigr )\) for a nonce N and a message M. This construction achieves roughly \(2^{2n/3}\) bit MAC security with the assumption that \(\textsf {E}\) is a PRP secure n-bit block cipher and \(\textsf {H}\) is an almost xor universal n-bit hash function. In this paper we propose Decrypted Wegman-Carter with Davies-Meyer (\(\textsf {DWCDM}\)) construction, which is structurally very similar to its predecessor \(\textsf {EWCDM}\) except that the outer encryption call is replaced by decryption. The biggest advantage of \(\textsf {DWCDM}\) is that we can make a truly single key MAC: the two block cipher calls can use the same block cipher key \(K=K_1=K_2\). Moreover, we can derive the hash key as \(K_h=\textsf {E}_K(1)\), as long as \(|K_h|=n\). Whether we use encryption or decryption in the outer layer makes a huge difference; using the decryption instead enables us to apply an extended version of the mirror theory by Patarin to the security analysis of the construction. \(\textsf {DWCDM}\) is secure beyond the birthday bound, roughly up to \(2^{2n/3}\) MAC queries and \(2^n\) verification queries against nonce-respecting adversaries. \(\textsf {DWCDM}\) remains secure up to \(2^{n/2}\) MAC queries and \(2^n\) verification queries against nonce-misusing adversaries.

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 Multi-Input Functional Encryption for Inner Products: Function-Hiding Realizations and Constructions Without Pairings

Nächstes Kapitel Rasta: A Cipher with Low ANDdepth and Few ANDs per Bit

An AXU hash function is a keyed hash function such that for any two distinct messages, the probability, over a random draw of a hash key, of the hash differential being equal to a specific output is small.

Adversaries who never repeat the same value of N in their MAC queries.

For two variables, P, Q and \(\lambda \in \mathrm {GF}(2^n)\) we call an equation of the form \(P \oplus Q = \lambda \), a bi-variate affine equation.

For two variables, P, Q and \(\lambda \in \mathrm {GF}(2^n) \setminus 0^n\) we call \(P \oplus Q \ne \lambda \), an affine bi-variate non-equation and \(P \ne \lambda \) is an affine uni-variate non-equation.

Similar to nonce respecting adversary, we say that an adversary is nonce misusing if the adversary is not restricted to make queries to the MAC oracle with distinct nonces.

When we consider affine equation, we actually refer to the bi-variate affine equation.

We assume \(j > i\).

A Hash function H is said to be a \(\epsilon \) j-way regular hash function if for all distinct \((X_1, \ldots , X_j)\) and for any non-zero Y, \(\Pr [\textsf {H}(X_1) \oplus \ldots \oplus \textsf {H}(X_j) = Y] \le \epsilon \).

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). http://eprint.iacr.org/2013/404

Beierle, C., et al.: The SKINNY family of block ciphers and its low-latency variant MANTIS. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part II. LNCS, vol. 9815, pp. 123–153. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53008-5_5CrossRef

Bellare, M., Impagliazzo, R.: A tool for obtaining tighter security analyses of pseudorandom function based constructions, with applications to PRP to PRF conversion. Cryptology ePrint Archive, Report 1999/024 (1999). http://eprint.iacr.org/1999/024

Bellare, M., Canetti, R., Krawczyk, H.: Keying hash functions for message authentication. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 1–15. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-68697-5_1CrossRef

Bellare, M., Kilian, J., Rogaway, P.: The security of cipher block chaining. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 341–358. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-48658-5_32CrossRef

Bellare, M., Krovetz, T., Rogaway, P.: Luby-Rackoff backwards: increasing security by making block ciphers non-invertible. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 266–280. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0054132CrossRef

Bhattacharya, S., Nandi, M.: Full indifferentiable security of the Xor of two or more random permutations using the \(\chi ^2\) method. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part I. LNCS, vol. 10820, pp. 387–412. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78381-9_15CrossRef

Bhattacharya, S., Nandi, M.: Revisiting variable output length XOR pseudorandom function. IACR Trans. Symmetric Cryptol. 2018(1), 314–335 (2018)

Bogdanov, A., et al.: PRESENT: an ultra-lightweight block cipher. In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS, vol. 4727, pp. 450–466. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74735-2_31CrossRef

10.

De Cannière, C., Dunkelman, O., Knežević, M.: KATAN and KTANTAN — a family of small and efficient hardware-oriented block ciphers. In: Clavier, C., Gaj, K. (eds.) CHES 2009. LNCS, vol. 5747, pp. 272–288. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04138-9_20CrossRefMATH

11.

Chen, S., Lampe, R., Lee, J., Seurin, Y., Steinberger, J.: Minimizing the two-round Even-Mansour cipher. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part I. LNCS, vol. 8616, pp. 39–56. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44371-2_3CrossRef

12.

Cogliati, B., Lampe, R., Patarin, J.: The indistinguishability of the XOR of \(k\) permutations. In: Cid, C., Rechberger, C. (eds.) FSE 2014. LNCS, vol. 8540, pp. 285–302. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46706-0_15CrossRef

13.

Cogliati, B., Seurin, Y.: EWCDM: an efficient, beyond-birthday secure, nonce-misuse resistant MAC. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part I. LNCS, vol. 9814, pp. 121–149. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53018-4_5CrossRef

14.

Cogliati, B., Seurin, Y.: Analysis of the single-permutation encrypted Davies-Meyer construction. Des. Codes Cryptogr. (2018, to appear)

15.

Daemen, J., Rijmen, V.: Rijndael for AES. In: AES Candidate Conference, pp. 343–348 (2000)

16.

Dai, W., Hoang, V.T., Tessaro, S.: Information-theoretic indistinguishability via the chi-squared method. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part III. LNCS, vol. 10403, pp. 497–523. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63697-9_17CrossRef

17.

Datta, N., Dutta, A., Nandi, M., Paul, G., Zhang, L.: Single key variant of PMAC\(\_\)plus. IACR Trans. Symmetric Cryptol. 2017(4), 268–305 (2017)

18.

Datta, N., Dutta, A., Nandi, M., Yasuda, K.: Encrypt or decrypt? To make a single-key beyond birthday secure nonce-based MAC. Cryptology ePrint Archive, Report 2018/500 (2018)

19.

Dutta, A., Jha, A., Nandi, M.: Tight security analysis of EHtM MAC. IACR Trans. Symmetric Cryptol. 2017(3), 130–150 (2017)

20.

Guo, J., Peyrin, T., Poschmann, A., Robshaw, M.J.B.: The LED block cipher. IACR Cryptology ePrint Archive, 2012:600 (2012)

21.

Iwata, T.: New blockcipher modes of operation with beyond the birthday bound security. In: Robshaw, M. (ed.) FSE 2006. LNCS, vol. 4047, pp. 310–327. Springer, Heidelberg (2006). https://doi.org/10.1007/11799313_20CrossRef

22.

Iwata, T., Mennink, B., Vizár, D.: CENC is optimally secure. IACR Cryptology ePrint Archive, 2016:1087 (2016)

23.

Lucks, S.: The sum of PRPs is a secure PRF. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 470–484. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-45539-6_34CrossRef

24.

Mennink, B., Neves, S.: Encrypted Davies-Meyer and its dual: towards optimal security using mirror theory. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part III. LNCS, vol. 10403, pp. 556–583. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63697-9_19CrossRef

25.

Minematsu, K., Iwata, T.: Building blockcipher from tweakable blockcipher: extending FSE 2009 proposal. In: Chen, L. (ed.) IMACC 2011. LNCS, vol. 7089, pp. 391–412. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25516-8_24CrossRef

26.

Naito, Y.: Blockcipher-based MACs: beyond the birthday bound without message length. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017, Part III. LNCS, vol. 10626, pp. 446–470. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70700-6_16CrossRef

27.

NIST: Recommendation for block cipher modes of operation: The CMAC mode for authentication. SP 800–38B (2005)

28.

Patarin, J.: A proof of security in O(2ⁿ) for the Xor of two random permutations. In: Safavi-Naini, R. (ed.) ICITS 2008. LNCS, vol. 5155, pp. 232–248. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85093-9_22CrossRefMATH

29.

Patarin, J.: The “Coefficients H” technique. In: Avanzi, R.M., Keliher, L., Sica, F. (eds.) SAC 2008. LNCS, vol. 5381, pp. 328–345. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04159-4_21CrossRef

30.

Patarin, J.: Introduction to mirror theory: analysis of systems of linear equalities and linear non equalities for cryptography. IACR Cryptology ePrint Archive, 2010:287 (2010)

31.

Patarin, J.: Security in o(2\({}^{\text{n}}\)) for the Xor of two random permutations - proof with the standard H technique. IACR Cryptology ePrint Archive, 2013:368 (2013)

32.

Patarin, J.: Mirror theory and cryptography. Appl. Algebra Eng. Commun. Comput. 28(4), 321–338 (2017)MathSciNetCrossRef

33.

Yasuda, K.: A new variant of PMAC: beyond the birthday bound. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 596–609. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22792-9_34CrossRef

Titel: Encrypt or Decrypt? To Make a Single-Key Beyond Birthday Secure Nonce-Based MAC
verfasst von: Nilanjan Datta
Avijit Dutta
Mridul Nandi
Kan Yasuda
Verlag: Springer International Publishing
Buch: Advances in Cryptology – CRYPTO 2018
Print ISBN: 978-3-319-96883-4

Electronic ISBN: 978-3-319-96884-1

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-96884-1_21

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"