nach oben

Erschienen in:

2024 | OriginalPaper | Buchkapitel

The Multi-user Security of MACs via Universal Hashing in the Ideal Cipher Model

verfasst von : Yusuke Naito

Erschienen in: Topics in Cryptology – CT-RSA 2024

Verlag: Springer Nature Switzerland

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

The security of block-cipher-based hash-then-encrypt-type message authentication codes (MACs) has been proven with universal hash functions. Thus, the security of the underlying hash functions has been evaluated with the pseudo-random-permutation assumption, i.e., the block ciphers are replaced with random permutations to which an adversary cannot directly access. Due to a hybrid argument, this replacement offers tight multi-user bounds regarding online security. However, it degrades its offline security depending on the number of users \(u\): from \(k\) bits (key size) to \(k- \log _2 u\) bits.

We thus revise the definitions of universal hashing, \(\epsilon _1\)-regular and \(\epsilon _2\)-almost XOR universal, by involving ideal cipher, and show that multi-user security of several hash-then-encrypt-type MACs does not degrade from the single-user security.

Using the revised definitions, we evaluate the multi-user security of the following MAC, called \(\textsf{HtE}\): \(\textsf{HtE}_{K,L}(M) = E_K(H^E_L(M))\) where \(M\) is a message, \(E_K\) is an \(n\)-bit ideal cipher with a \(k\)-bit key \(K\), and \(H_L^E\) is an ideal-cipher-based hash function with a key \(L\). We derive the multi-user-bound \(O\left( q_uq\epsilon _2 + q\epsilon _1 + \frac{p+\ell q}{2^k} \right) \) where \(p\) (resp. \(q\)) is the number of primitive (resp. construction) queries, and \(q_u\) is the maximum number of construction queries within one user.
We next evaluate the multi-user security of another hash-then-encrypt-type MAC, called \(\textsf{HtXE}\). \(\textsf{HtXE}\) is a generalization of \(\textsf{XCBC}\) and \(\textsf{TMAC}\) where a single-key block cipher is used and another key is applied to the state before the last block-cipher call of \(\textsf{HtXE}\). We show that \(\textsf{HtXE}\) achieves the same level of security as \(\textsf{HtE}\).
Finally, we show regular and almost-XOR-universal bounds of \(\textsf{CBC}\). Combining the bounds with those of \(\textsf{HtE}\) and of \(\textsf{HtXE}\), we obtain the bound \(O\left( \frac{\ell q_uq}{2^n} + \frac{p}{2^k} \right) \) for \(\textsf{HtE}\) or \(\textsf{HtXE}\) with \(\textsf{CBC}\), including \(\textsf{EMAC}\), \(\textsf{XCBC}\), and \(\textsf{TMAC}\). If \(q_u\ll 2^{n/2}\), then they achieve beyond-birthday-bound security.

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 Computational Security Analysis of the Full EDHOC Protocol

Nächstes Kapitel Automated-Based Rebound Attacks on ACE Permutation

\(H_L\) is \(\epsilon \)-almost universal if for any distinct messages \(M,M^\prime \) and a random key \(L\) that is chosen independently of \(M\), \(\textrm{Pr}[H_L(M) = H_L(M^\prime )] \le \epsilon \).

Let \(\textsf {Time}\) be the running time of the PRP adversary in the single-user bound. Then, by the hybrid argument, the running time of the PRP adversary in the multi-user bound is \(\textsf {Time} + O(\sigma )\), where \(\sigma \) is the total number of block-cipher calls by construction queries.

In the ideal-cipher model and the single-user setting, the PRP-security advantage is \(\frac{p}{2^k}\). In the multi-user setting, the bound becomes \(\frac{u(p+ \sigma )}{2^k}\). Note that the key collision probability \(\frac{u^2}{2^k}\) is taken into account by the term \(\frac{u(p+ \sigma )}{2^k}\).

Note that the ideal-cipher assumption is only for the block cipher in the outer function and not for the hash function.

\(\textsf{GMAC}^+\) is designed as a KDF of the authenticated encryption AES-GCM-SIV.

\(H_L\) is \(\epsilon _2\)-AXU if for any \(M\) and Y, \(\textrm{Pr}[H_L(M) \oplus H_L(M^\prime ) = Y] \le \epsilon _2\) where \(L\) is chosen randomly and independently of \(M\) and Y.

\(H_L\) is \(\epsilon _1\)-regular if for any \(M\) and Y, \(\textrm{Pr}[H_L(M) = Y] \le \epsilon _1\) where \(L\) is chosen randomly and independently of \(M\) and Y.

We can derive the bounds of \(\textrm{Pr}[\textsf{bad}_1 \wedge \nu _\alpha \ne \nu _\beta ]\) and of \(\textrm{Pr}[\textsf{bad}_1 \wedge \nu _\alpha = \nu _\beta ]\) by another way that is a reduction from \(\textsf{bad}_1\) to the (IC-based) AXU or regular property.

As the evaluation of \(\textrm{Pr}[\textsf{bad}_1]\), we can derive the bound of \(\textrm{Pr}[\textsf{bad}_{3,2}]\) by a reduction from \(\textsf{bad}_{3,2}\) to the (IC-based) regular property.

As the evaluation of \(\textrm{Pr}[\textsf{bad}_1]\), we can derive the bound of \(\textrm{Pr}[\textsf{bad}_4]\) by a reduction from \(\textsf{bad}_4\) to the (IC-based) regular property.

If \(M^{(2)}\) is a suffix of \(M^{(1)}\) and \(Z=0^n\), then the condition that \(\textbf{A}\) wins becomes \(\textsf{CBC}[E_L](M_1^{(1)} \Vert \cdots \Vert M_{m_1-m_2}^{(1)}) \oplus \textsf{CBC}[E_L](\varepsilon ) = 0^n\).

When deriving the bound of \(\textrm{Pr}[\mu \text {-}\textsf{keys}]\) in Eq. (13), all possible tuples for \(M^\prime , M^*, Z^*\), and \(L_i^*\) are taken into account.

The block lengths of \(M^\prime \) and \(M^\prime \) are respectively at most \(\ell \), and each input-output tuple is defined by forward or inverse query.

Armknecht, F., Fleischmann, E., Krause, M., Lee, J., Stam, M., Steinberger, J.: The preimage security of double-block-length compression functions. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 233–251. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25385-0_13CrossRef

Bellare, M., Bernstein, D.J., Tessaro, S.: Hash-function based PRFs: AMAC and its multi-user security. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 566–595. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49890-3_22CrossRef

Bellare, M., Boldyreva, A., Micali, S.: Public-key encryption in a multi-user setting: security proofs and improvements. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 259–274. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-45539-6_18CrossRef

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., Pietrzak, K., Rogaway, P.: Improved security analyses for CBC MACs. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 527–545. Springer, Heidelberg (2005). https://doi.org/10.1007/11535218_32CrossRef

Biham, E.: How to decrypt or even substitute DES-encrypted messages in 2\({}^{\text{28 }}\) steps. Inf. Process. Lett. 84(3), 117–124 (2002)MathSciNetCrossRef

Black, J., Rogaway, P.: CBC MACs for arbitrary-length messages: the three-key constructions. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 197–215. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-44598-6_12CrossRef

Bose, P., Hoang, V.T., Tessaro, S.: Revisiting AES-GCM-SIV: multi-user security, faster key derivation, and better bounds. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10820, pp. 468–499. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78381-9_18CrossRef

Bosselaers, A., Preneel, B. (eds.): Integrity Primitives for Secure Information Systems. LNCS, vol. 1007. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-60640-8CrossRef

10.

Chakraborty, B., Chattopadhyay, S., Jha, A., Nandi, M.: On length independent security bounds for the PMAC family. IACR Trans. Symmetric Cryptol. 2021(2), 423–445 (2021)CrossRef

11.

Chatterjee, S., Menezes, A., Sarkar, P.: Another look at tightness. In: Miri, A., Vaudenay, S. (eds.) SAC 2011. LNCS, vol. 7118, pp. 293–319. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-28496-0_18CrossRef

12.

Chattopadhyay, S., Jha, A., Nandi, M.: Towards tight security bounds for OMAC, XCBC and TMAC. In: Agrawal, S., Lin, D. (eds.) Advances in Cryptology – ASIACRYPT 2022. ASIACRYPT 2022. LNCS, vol. 13791, pp. 348–378. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-22963-3_12

13.

Datta, N., Dutta, A., Nandi, M., Talnikar, S.: Tight multi-user security bound of DbHtS. IACR Trans. Symmetric Cryptol. 2023(1), 192–223 (2023)CrossRef

14.

Dworkin, M.J.: Recommendation for Block Cipher Modes of Operation: the CMAC Mode for Authentication. SP 800-38B (2005)

15.

Dworkin, M.J.: Recommendation for block cipher modes of operation: the CMAC mode for authentication. Technical report, NIST, 2016. Supersedes SP 800-38B (2016)

16.

Guo, T., Wang, P.: A note on the security framework of two-key dbhts macs. Cryptology ePrint Archive, Report 2022/375 (2022). https://ia.cr/2022/375

17.

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). https://doi.org/10.1007/978-3-662-53018-4_1CrossRef

18.

Hoang, V.T., Tessaro, S.: The multi-user security of double encryption. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10211, pp. 381–411. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56614-6_13CrossRef

19.

Hoang, V.T., Tessaro, S., Thiruvengadam, A.: The multi-user security of GCM, revisited: tight bounds for nonce randomization. In: CCS 2018, pp. 1429–1440. ACM (2018)

20.

ISO/IEC: Information Technology - Security Techniques - Message Authentication Codes (MACs) - Part 1: Mechanisms Using a Block Cipher. Technical report, ISO/IEC (2011)

21.

Iwata, T., Kurosawa, K.: OMAC: one-key CBC MAC. In: Johansson, T. (ed.) FSE 2003. LNCS, vol. 2887, pp. 129–153. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-39887-5_11CrossRef

22.

Jha, A., Nandi, M.: Revisiting structure graphs: applications to CBC-MAC and EMAC. J. Math. Cryptol. 10(3–4), 157–180 (2016)MathSciNet

23.

Kurosawa, K., Iwata, T.: TMAC: two-key CBC MAC. In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 33–49. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36563-X_3CrossRef

24.

Luykx, A., Mennink, B., Paterson, K.G.: Analyzing multi-key security degradation. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10625, pp. 575–605. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70697-9_20CrossRef

25.

Bellare, M., Tackmann, B.: The multi-user security of authenticated encryption: AES-GCM in TLS 1.3. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9814, pp. 247–276. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53018-4_10CrossRef

26.

Mouha, N., Luykx, A.: Multi-key security: the Even-Mansour construction revisited. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 209–223. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47989-6_10CrossRef

27.

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

28.

Naito, Y., Sasaki, Y., Sugawara, T., Yasuda, K.: The multi-user security of triple encryption, revisited: exact security, strengthening, and application to TDES. In: CCS 2022, pp. 2323–2336 (2022)

29.

Nandi, M.: Improved security analysis for OMAC as a pseudorandom function. J. Math. Cryptol. 3(2), 133–148 (2009)MathSciNetCrossRef

30.

NIST: FIPS 113, Computer data authentication. Federal Information Processing Standards Publication 113, U. S. Department of Commerce/National Bureau of Standards, National Technical Information Service, Springfield, Virginia (1985)

31.

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

32.

Shen, Y., Wang, L., Gu, D., Weng, J.: Revisiting the security of DbHtS MACs: beyond-birthday-bound in the multi-user setting. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12827, pp. 309–336. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84252-9_11CrossRef

33.

Shen, Y., Wang, L., Weng, J.: Revisiting the Security of DbHtS MACs: Beyond-Birthday-Bound in the Multi-User Setting. IACR Cryptol. ePrint Arch., p. 1523 (2020)

34.

Wegman, M.N., Carter, L.: New hash functions and their use in authentication and set equality. J. Comput. Syst. Sci. 22(3), 265–279 (1981)MathSciNetCrossRef

35.

Yasuda, K.: The sum of CBC MACs is a secure PRF. In: Pieprzyk, J. (ed.) CT-RSA 2010. LNCS, vol. 5985, pp. 366–381. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-11925-5_25CrossRef

36.

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: The Multi-user Security of MACs via Universal Hashing in the Ideal Cipher Model
verfasst von: Yusuke Naito
Verlag: Springer Nature Switzerland
Buch: Topics in Cryptology – CT-RSA 2024
Print ISBN: 978-3-031-58867-9

Electronic ISBN: 978-3-031-58868-6

Copyright-Jahr: 2024
DOI: https://doi.org/10.1007/978-3-031-58868-6_3

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"

Premium Partner