Abstract
Duplex-based authenticated encryption modes with a sufficiently large key length are proven to be secure up to the birthday bound \(2^{\frac{c}{2}}\), where c is the capacity. However this bound is not known to be tight and the complexity of the best known generic attack, which is based on multicollisions, is much larger: it reaches \(\frac{2^c}{\alpha }\) where \(\alpha \) represents a small security loss factor. There is thus an uncertainty on the true extent of security beyond the bound \(2^{\frac{c}{2}}\) provided by such constructions. In this paper, we describe a new generic attack against several duplex-based AEAD modes. Our attack leverages random functions statistics and produces a forgery in time complexity \(\mathcal {O}(2^{\frac{3c}{4}})\) using negligible memory and no encryption queries. Furthermore, for some duplex-based modes, our attack recovers the secret key with a negligible amount of additional computations. Most notably, our attack breaks a security claim made by the designers of the NIST lightweight competition candidate Xoodyak. This attack is a step further towards determining the exact security provided by duplex-based constructions.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The name “duplex”, that conveys the idea of a bidirectional process, reflects the fact that in such constructions both a data block injection and a data block extraction to/from the current state can potentially take place between two consecutive invocations of P.
- 2.
Note that in the attack considered in the sequel, \(t_{extra-op}\) will in practice be negligible compared to \(\sigma _e + \sigma _d + q_P\).
- 3.
In other words, the questions whether the “birthday term” \(\frac{2^c}{ \sigma _d}\) is an artifact of the proofs and whether the capacity value c can be safely dimensioned well below 2s, where s denotes the targeted security level remain open.
- 4.
In practice, our cryptanalysis can be easily adapted to attack modes which can process plaintexts of arbitrary length, but this requires a short case-by-case analysis which we provide in Sect. 5. Note that the resulting adjustments have a negligible impact on the complexity of our attack and do not impact its success probability.
- 5.
For more details see for example [27].
- 6.
Each parameter space is well defined according to the analysed AEAD scheme.
- 7.
In decryption queries, nonces can be repeated even in a nonce-respecting setting. For the purpose of our attack, \(x_0\) needs to behave as a point randomly sampled in the graph of \(P_{\beta }\). Thus, we can either require nonces to be randomly sampled or to be arbitrary distinct values.
- 8.
For modes other than the full-state duplex, we could set the associated data to any value. In the case of the full-state duplex, the associated data must be chosen carefully (typically, the attack applies when the AD is set to the empty string).
- 9.
Given a point of the graph x, the introduction of an algorithm which estimates x’s component’s size is going to significantly complicate our attack’s complexity analysis. We believe that we could have designed an attack without this extra algorithm by relying on the fact that a random component is large with great probability. However, unless increasing the complexity of the online phase, we would have then obtained lower success probabilities (roughly around 0.5 rather than close to 1).
- 10.
or greater than \(sn\), but too close to \(sn\) to make the algorithm stop.
- 11.
Note that \(\nu = \frac{1}{4}\) is not the fully optimal choice in general. Rather, the optimal choice for \(\nu \) is \(\nu = \frac{1}{2} \left( \frac{1}{2} - \log _{n}\left( \sqrt{2\pi } / (\sqrt{s^{+}(1-s^{+})}15)\right) \right) \). For example, for \(n = 2^{128}\), the optimal choice is approximately 0.256.
- 12.
The plaintext also allows to verify that the recovered state before the final phase is correct, making the key recovery possible with only a negligible amount of extra computations regardless of the tag length.
- 13.
Here, we make the assumption that the standard deviation for the tail length is the same as the cycle length’s. This assumption does not affect our attack, it only affects how to interpret our test results.
- 14.
To reduce the execution time of the implementation, to detect whether or not two points \(x,x'\) are in the same component, we checked whether \(\mu (x) = \mu (x')\) instead of doing the exhaustive verification made in is_big.
- 15.
Although the first mode that uses a feedback function is COFB [17], this mode is out of scope as it is not duplex-based (in fact, it is not even permutation-based but block-cipher based).
- 16.
For more details on Xoodyak’s specification, we refer to [18] at page 62 for the keyed mode together with pages 67 and 68 for the full description of what is relevant for our analysis. https://csrc.nist.gov/Projects/lightweight-cryptography/.
- 17.
Note that the rate called r in this paper is denoted by n in Xoodyak’s specification.
- 18.
This value is called \(\rho _{max}\) in [7, p. 335].
References
Aumasson, J.P., Jovanovic, P., Neves, S.: NORX v2. Submission to the Caesar competition (2015). https://competitions.cr.yp.to/round2/norxv20.pdf
Aumasson, J.P., Jovanovic, P., Neves, S.: NORX v3. Submission to the Caesar competition (2016). https://competitions.cr.yp.to/round3/norxv30.pdf
Banik, S., et al.: GIFT-COFB. Cryptology ePrint Archive, Report 2020/738 (2020). https://eprint.iacr.org/2020/738
Bao, Z., Guo, J., Wang, L.: Functional graphs and their applications in generic attacks on iterated hash constructions. IACR Trans. Symm. Cryptol. 2018(1), 201–253 (2018). https://doi.org/10.13154/tosc.v2018.i1.201-253
Beierle, C., et al.: Lightweight AEAD and hashing using the Sparkle permutation family. IACR Trans. Symm. Cryptol. 2020(S1), 208–261 (2020). https://doi.org/10.13154/tosc.v2020.iS1.208-261
Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: On the indifferentiability of the sponge construction. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 181–197. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78967-3_11
Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: Duplexing the sponge: single-pass authenticated encryption and other applications. In: Miri, A., Vaudenay, S. (eds.) SAC 2011. LNCS, vol. 7118, pp. 320–337. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-28496-0_19
Bertoni, G., Daemen, J., Peeters, M., Assche, G.V.: Sponge functions (2007). https://keccak.team/files/SpongeFunctions.pdf
Bertoni, G., Daemen, J., Peeters, M., Assche, G.V.: Cryptographic sponge functions (2011). https://keccak.team/files/CSF-0.1.pdf
Bertoni, G., Daemen, J., Peeters, M., Assche, G.V.: Permutation-based encryption, authentication and authenticated encryption (2012). http://www.hyperelliptic.org/djb/diac/record.pdf
Bertoni, G., Daemen, J., Peeters, M., Assche, G.V., Keer, R.V.: Ketje v1. Submission to Caesar competition (2014). http://competitions.cr.yp.to/round1/ketjev1.pdf
Bertoni, G., Daemen, J., Peeters, M., Assche, G.V., Keer, R.V.: Ketje v2. Round 3 candidate for the Caesar competition (2016). http://competitions.cr.yp.to/round3/ketjev2.pdf
Bertoni, G., Daemen, J., Peeters, M., Assche, G.V., Keer, R.V.: Keyak v2. Submission to the Caesar competition (2016). https://competitions.cr.yp.to/round3/keyakv22.pdf
Brent, R.P.: An improved monte carlo factorization algorithm. In: BIT Numerical Mathematics, Berlin, Heidelberg, p. 176–184 (1980). https://doi.org/10.1007/BF01933190
Chaigneau, C., Fuhr, T., Gilbert, H., Jean, J., Reinhard, J.-R.: Cryptanalysis of NORX v2.0. J. Cryptol. 32(4), 1423–1447 (2018). https://doi.org/10.1007/s00145-018-9297-9
Chakraborti, A., Datta, N., Nandi, M., Yasuda, K.: Beetle family of lightweight and secure authenticated encryption ciphers. IACR Trans. Cryptogr. Hardware Embed. Syst. 2018(2), 218–241 (2018). https://doi.org/10.13154/tches.v2018.i2.218-241, https://tches.iacr.org/index.php/TCHES/article/view/881
Chakraborti, A., Iwata, T., Minematsu, K., Nandi, M.: Blockcipher-based authenticated encryption: how small can we go? In: Fischer, W., Homma, N. (eds.) CHES 2017. LNCS, vol. 10529, pp. 277–298. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66787-4_14
Daemen, J., Hoffert, S., Peeters, M., Van Assche, G., Van Keer, R.: Xoodyak, a lightweight cryptographic scheme. IACR Trans. Symm. Cryptol. 2020(S1), 60–87 (2020). https://doi.org/10.13154/tosc.v2020.iS1.60-87
Daemen, J., Massolino, P.M.C., Mehrdad, A., Rotella, Y.: The subterranean 2.0 cipher suite. IACR Trans. Symm. Cryptol. 2020(S1), 262–294 (2020). https://doi.org/10.13154/tosc.v2020.iS1.262-294
Daemen, J., Mennink, B., Van Assche, G.: Full-state keyed duplex with built-in multi-user support. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10625, pp. 606–637. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70697-9_21
DeLaurentis, J.M.: Components and cycles of a random function. In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 231–242. Springer, Heidelberg (1988). https://doi.org/10.1007/3-540-48184-2_21
Dobraunig, C., Eichlseder, M., Mendel, F., Schläffer, M.: Ascon v1.2: lightweight authenticated encryption and hashing. J. Cryptol. 34(3), 1–42 (2021). https://doi.org/10.1007/s00145-021-09398-9
Flajolet, P., Odlyzko, A.M.: Random mapping statistics. In: Quisquater, J.-J., Vandewalle, J. (eds.) EUROCRYPT 1989. LNCS, vol. 434, pp. 329–354. Springer, Heidelberg (1990). https://doi.org/10.1007/3-540-46885-4_34
Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009). http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=9780521898065
Harris, B.: Probability distributions related to random mappings. Ann. Math. Stat. 31(4), 1045–1062 (1960). https://doi.org/10.1214/aoms/1177705677
Joux, A.: Algorithmic Cryptanalysis. Chapman and Hall/CRC, Boca Raton (2009). https://doi.org/10.1201/9781420070033
Jovanovic, P., Luykx, A., Mennink, B.: Beyond 2c/2 security in sponge-based authenticated encryption modes. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 85–104. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45611-8_5
Jovanovic, P., Luykx, A., Mennink, B., Sasaki, Yu., Yasuda, K.: Beyond conventional security in sponge-based authenticated encryption modes. J. Cryptol. 32(3), 895–940 (2018). https://doi.org/10.1007/s00145-018-9299-7
Leurent, G., Peyrin, T., Wang, L.: New generic attacks against hash-based MACs. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013. LNCS, vol. 8270, pp. 1–20. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-42045-0_1
Mennink, B., Reyhanitabar, R., Vizár, D.: Security of full-state keyed sponge and duplex: applications to authenticated encryption. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9453, pp. 465–489. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48800-3_19
Moon, J.W.: Counting Labelled Trees. Canadian Mathematical Congress 1970, William Clowes and Sons (1970)
Peyrin, T., Sasaki, Yu., Wang, L.: Generic related-key attacks for HMAC. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 580–597. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34961-4_35
Peyrin, T., Wang, L.: Generic universal forgery attack on iterative hash-based MACs. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 147–164. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-55220-5_9
Zhang, W., et al.: KNOT. Round 2 candidate for the NIST Lightweight Cryptography project (2019). https://csrc.nist.gov/CSRC/media/Projects/lightweight-cryptography/documents/round-2/spec-doc-rnd2/knot-spec-round.pdf
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 International Association for Cryptologic Research
About this paper
Cite this paper
Gilbert, H., Heim Boissier, R., Khati, L., Rotella, Y. (2023). Generic Attack on Duplex-Based AEAD Modes Using Random Function Statistics. In: Hazay, C., Stam, M. (eds) Advances in Cryptology – EUROCRYPT 2023. EUROCRYPT 2023. Lecture Notes in Computer Science, vol 14007. Springer, Cham. https://doi.org/10.1007/978-3-031-30634-1_12
Download citation
DOI: https://doi.org/10.1007/978-3-031-30634-1_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-30633-4
Online ISBN: 978-3-031-30634-1
eBook Packages: Computer ScienceComputer Science (R0)
