Skip to main content
Springer Nature Link
Log in

Nostradamus Goes Quantum

  • Conference paper
  • First Online:
Advances in Cryptology – ASIACRYPT 2022 (ASIACRYPT 2022)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13793))

Abstract

In the Nostradamus attack, introduced by Kelsey and Kohno (Eurocrypt 2006), the adversary has to commit to a hash value y of an iterated hash function \(\textsf{H}\) such that, when later given a message prefix \(P\), the adversary is able to find a suitable “suffix explanation” \(S\) with \(\textsf{H}(P\left. \right\| {S})=y\). Kelsey and Kohno show a herding attack with \(2^{2n/3}\) evaluations of the compression function of \(\textsf{H}\) (with n bits output and state), locating the attack between preimage attacks and collision search in terms of complexity. Here we investigate the security of Nostradamus attacks for quantum adversaries. We present a quantum herding algorithm for the Nostradamus problem making approximately \(\root 3 \of {n}\cdot 2^{3n/7}\) compression function evaluations, significantly improving over the classical bound. We also prove that quantum herding attacks cannot do better than \(2^{3n/7}\) evaluations for random compression functions, showing that our algorithm is (essentially) optimal. We also discuss a slightly less tight bound of roughly \(2^{3n/7-s}\) for general Nostradamus attacks against random compression functions, where \(s\) is the maximal block length of the adversarially chosen suffix \(S\).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
€32.70 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
EUR 29.95
Price includes VAT (France)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 93.08
Price includes VAT (France)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 116.04
Price includes VAT (France)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Unless stated otherwise, all bounds refer to expected numbers of evaluations.

  2. 2.

    Available via https://git.rwth-aachen.de/marc.fischlin/quantum-nostradamus.

  3. 3.

    Note that we simply identify a node with its hash value label. Formally, to make nodes with identical hash values distinct, we add a position in the tree to each node (given by the level and its order within the nodes of the same level) but usually omit mentioning the position value.

  4. 4.

    https://qiskit.org/.

References

  1. Amy, M., Matteo, O.D., Gheorghiu, V., Mosca, M., Parent, A., Schanck, J.M.: Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3. In: Avanzi, R., Heys, H.M. (eds.) Selected Areas in Cryptography - SAC 2016–23rd International Conference, St. John’s, NL, Canada, 10–12 August 2016, Revised Selected Papers. Lecture Notes in Computer Science, vol. 10532, pp. 317–337. Springer (2016). https://doi.org/10.1007/978-3-319-69453-5_18

  2. Andreeva, E., Bouillaguet, C., Dunkelman, O., Kelsey, J.: Herding, second preimage and trojan message attacks beyond Merkle-damgård. In: Jr., M.J.J., Rijmen, V., Safavi-Naini, R. (eds.) Selected Areas in Cryptography, 16th Annual International Workshop, SAC 2009, Calgary, Alberta, Canada, 13–14 August 2009, Revised Selected Papers. Lecture Notes in Computer Science, vol. 5867, pp. 393–414. Springer (2009). https://doi.org/10.1007/978-3-642-05445-7_25

  3. Andreeva, E., Mennink, B.: Provable chosen-target-forced-midfix preimage resistance. In: Miri, A., Vaudenay, S. (eds.) Selected Areas in Cryptography - 18th International Workshop, SAC 2011, Toronto, ON, Canada, 11–12 August 2011, Revised Selected Papers. Lecture Notes in Computer Science, vol. 7118, pp. 37–54. Springer (2011). https://doi.org/10.1007/978-3-642-28496-0_3

  4. Banegas, G., Bernstein, D.J.: Low-communication parallel quantum multi-target preimage search. In: Adams, C., Camenisch, J. (eds.) Selected Areas in Cryptography - SAC 2017–24th International Conference, Ottawa, ON, Canada, 16–18 August 2017, Revised Selected Papers. Lecture Notes in Computer Science, vol. 10719, pp. 325–335. Springer (2017). https://doi.org/10.1007/978-3-319-72565-9_16

  5. Bellare, M., Kohno, T.: Hash function balance and its impact on birthday attacks. In: Cachin, C., Camenisch, J. (eds.) Advances in Cryptology - EUROCRYPT 2004. Lecture Notes in Computer Science, vol. 3027, pp. 401–418. Springer, Heidelberg, Germany, Interlaken, Switzerland, 2–6 May 2004. https://doi.org/10.1007/978-3-540-24676-3_24

  6. Bernstein, D.: ChaCha, a variant of Salsa20 (2008). https://cr.yp.to/chacha/chacha-20080128.pdf

  7. Bernstein, D.J.: Cost analysis of hash collisions : will quantum computers make SHARCS obsolete? In: SHARCS 2009 Workshop Record (Proceedings 4th Workshop on Special-purpose Hardware for Attacking Cryptograhic Systems, Lausanne, Switserland, 9–10 September 2009), pp. 105–116 (2009)

    Google Scholar 

  8. Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: Sponge functions. Ecrypt Hash Workshop (2007)

    Google Scholar 

  9. Blackburn, S.R., Stinson, D.R., Upadhyay, J.: On the complexity of the herding attack and some related attacks on hash functions. Des. Codes Cryptogr. 64(1–2), 171–193 (2012)

    Article  MATH  Google Scholar 

  10. Boneh, D., Dagdelen, Ö., Fischlin, M., Lehmann, A., Schaffner, C., Zhandry, M.: Random oracles in a quantum world. In: Lee, D.H., Wang, X. (eds.) Advances in Cryptology - ASIACRYPT 2011–17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, 4–8 December 2011. Proceedings. Lecture Notes in Computer Science, vol. 7073, pp. 41–69. Springer (2011). https://doi.org/10.1007/978-3-642-25385-0_3

  11. Bonnetain, X., Jaques, S.: Quantum period finding against symmetric primitives in practice. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2022(1), 1–27 (2022)

    Google Scholar 

  12. Boyer, M., Brassard, G., Høyer, P., Tapp, A.: Tight bounds on quantum searching. Fortschritte der Physik 46(4–5), 493–505 (1998)

    Article  Google Scholar 

  13. Brassard, G., Høyer, P., Tapp, A.: Quantum cryptanalysis of hash and claw-free functions. In: Lucchesi, C.L., Moura, A.V. (eds.) LATIN 1998: Theoretical Informatics, Third Latin American Symposium, Campinas, Brazil, 20–24 April 1998, Proceedings. Lecture Notes in Computer Science, vol. 1380, pp. 163–169. Springer (1998). https://doi.org/10.1007/BFb0054319

  14. Chailloux, A., Naya-Plasencia, M., Schrottenloher, A.: An efficient quantum collision search algorithm and implications on symmetric cryptography. In: Takagi, T., Peyrin, T. (eds.) Advances in Cryptology - ASIACRYPT 2017–23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, 3–7 December 2017, Proceedings, Part II. Lecture Notes in Computer Science, vol. 10625, pp. 211–240. Springer (2017). https://doi.org/10.1007/978-3-319-70697-9_8

  15. Damgård, I.: A design principle for hash functions. In: Brassard, G. (ed.) Advances in Cryptology - CRYPTO’89. Lecture Notes in Computer Science, vol. 435, pp. 416–427. Springer, Heidelberg, Germany, Santa Barbara, CA, USA, 20–24 August 1990. https://doi.org/10.1007/0-387-34805-0_39

  16. Dang, Q.: Secure hash standard. Federal Inf. Process. Stds. (NIST FIPS), National Institute of Standards and Technology, Gaithersburg, MD (2015–08-04 2015)

    Google Scholar 

  17. Dean, R.D.: Formal Aspects of Mobile Code Security. Ph.D. thesis, Computer Science Department, Princeton University (1999)

    Google Scholar 

  18. Dong, X., Sun, S., Shi, D., Gao, F., Wang, X., Hu, L.: Quantum collision attacks on AES-like hashing with low quantum random access memories. In: Moriai, S., Wang, H. (eds.) Advances in Cryptology - ASIACRYPT 2020, Part II. Lecture Notes in Computer Science, vol. 12492, pp. 727–757. Springer, Heidelberg, Germany, Daejeon, South Korea, 7–11 December 2020. https://doi.org/10.1007/978-3-030-64834-3_25

  19. Dong, X., Zhang, Z., Sun, S., Wei, C., Wang, X., Hu, L.: Automatic classical and quantum rebound attacks on aes-like hashing by exploiting related-key differentials. In: Tibouchi, M., Wang, H. (eds.) Advances in Cryptology - ASIACRYPT 2021–27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, 6–10 December 2021, Proceedings, Part I. Lecture Notes in Computer Science, vol. 13090, pp. 241–271. Springer (2021). https://doi.org/10.1007/978-3-030-92062-3_9

  20. Dworkin, M.: SHA-3 standard: permutation-based hash and extendable-output functions. Federal Inf. Process. Stds. (NIST FIPS), National Institute of Standards and Technology, Gaithersburg, MD (2015–08-04 2015)

    Google Scholar 

  21. Efthymiou, S., et al.: Qibo: An open-source full stack API for quantum simulation and quantum hardware control (2022). https://github.com/qiboteam/qibo

  22. Flórez-Gutiérrez, A., Leurent, G., Naya-Plasencia, M., Perrin, L., Schrottenloher, A., Sibleyras, F.: New results on Gimli: full-permutation distinguishers and improved collisions. In: Moriai, S., Wang, H. (eds.) Advances in Cryptology - ASIACRYPT 2020, Part I. Lecture Notes in Computer Science, vol. 12491, pp. 33–63. Springer, Heidelberg, Germany, Daejeon, South Korea, 7–11 December 2020. https://doi.org/10.1007/978-3-030-64837-4_2

  23. Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Miller, G.L. (ed.) Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, 22–24 May 1996, pp. 212–219. ACM (1996)

    Google Scholar 

  24. Hosoyamada, A., Sasaki, Y.: Finding hash collisions with quantum computers by using differential trails with smaller probability than birthday bound. In: Canteaut, A., Ishai, Y. (eds.) Advances in Cryptology - EUROCRYPT 2020, Part II. Lecture Notes in Computer Science, vol. 12106, pp. 249–279. Springer, Heidelberg, Germany, Zagreb, Croatia, 10–14 May 2020. https://doi.org/10.1007/978-3-030-45724-2_9

  25. Hosoyamada, A., Sasaki, Y.: Quantum collision attacks on reduced SHA-256 and SHA-512. In: Malkin, T., Peikert, C. (eds.) Advances in Cryptology - CRYPTO 2021, Part I. Lecture Notes in Computer Science, vol. 12825, pp. 616–646. Springer, Heidelberg, Germany, Virtual Event, 16–20 August 2021. https://doi.org/10.1007/978-3-030-84242-0_22

  26. Kelsey, J., Kohno, T.: Herding hash functions and the nostradamus attack. In: Vaudenay, S. (ed.) Advances in Cryptology - EUROCRYPT 2006, 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, 28 May–1 June 2006, Proceedings. Lecture Notes in Computer Science, vol. 4004, pp. 183–200. Springer (2006). https://doi.org/10.1007/11761679_12

  27. Kelsey, J., Schneier, B.: Second preimages on n-bit hash functions for much less than 2\({}^{\text{n}}\) work. In: Cramer, R. (ed.) Advances in Cryptology - EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, 22–26 May 2005, Proceedings. Lecture Notes in Computer Science, vol. 3494, pp. 474–490. Springer (2005). https://doi.org/10.1007/11426639_28

  28. Kortelainen, T., Kortelainen, J.: On diamond structures and trojan message attacks. In: Sako, K., Sarkar, P. (eds.) Advances in Cryptology - ASIACRYPT 2013–19th International Conference on the Theory and Application of Cryptology and Information Security, Bengaluru, India, 1–5 December 2013, Proceedings, Part II. Lecture Notes in Computer Science, vol. 8270, pp. 524–539. Springer (2013). https://doi.org/10.1007/978-3-642-42045-0_27

  29. Liu, Q., Zhandry, M.: On finding quantum multi-collisions. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11478, pp. 189–218. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17659-4_7

    Chapter  Google Scholar 

  30. Merkle, R.C.: A certified digital signature. In: Brassard, G. (ed.) Advances in Cryptology - CRYPTO’89. Lecture Notes in Computer Science, vol. 435, pp. 218–238. Springer, Heidelberg, Germany, Santa Barbara, CA, USA, 20–24 August 1990

    Google Scholar 

  31. Ni, B., Dong, X., Jia, K., You, Q.: (quantum) collision attacks on reduced simpira v2. IACR Trans. Symmetric Cryptol. 2021(2), 222–248 (2021)

    Google Scholar 

  32. Pointcheval, D., Stern, J.: Security arguments for digital signatures and blind signatures. J. Cryptol. 13(3), 361–396 (2000)

    Article  MATH  Google Scholar 

  33. Ramos-Calderer, S., Bellini, E., Latorre, J.I., Manzano, M., Mateu, V.: Quantum search for scaled hash function preimages. Quantum Inf. Process. 20(5), 1–28 (2021). https://doi.org/10.1007/s11128-021-03118-9

    Article  Google Scholar 

  34. Wang, R., Li, X., Gao, J., Li, H., Wang, B.: Quantum rotational cryptanalysis for preimage recovery of round-reduced keccak. IACR Cryptol. ePrint Arch, p. 13 (2022). https://eprint.iacr.org/2022/013

  35. Weizman, A., Dunkelman, O., Haber, S.: Efficient construction of diamond structures. In: Patra, A., Smart, N.P. (eds.) Progress in Cryptology - INDOCRYPT 2017–18th International Conference on Cryptology in India, Chennai, India, 10–13 December 2017, Proceedings. Lecture Notes in Computer Science, vol. 10698, pp. 166–185. Springer (2017). https://doi.org/10.1007/978-3-319-71667-1_9

Download references

Acknowledgments

We thank the anonymous reviewers for valuable comments.

This research work has been funded by the German Federal Ministry of Education and Research and the Hessian Ministry of Higher Education, Research, Science and the Arts within their joint support of the National Research Center for Applied Cybersecurity ATHENE.

Author information

Authors and Affiliations

  1. Cryptoplexity, Technische Universität Darmstadt, Darmstadt, Germany

    Barbara Jiabao Benedikt, Marc Fischlin & Moritz Huppert

Authors
  1. Barbara Jiabao Benedikt
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Marc Fischlin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Moritz Huppert
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Barbara Jiabao Benedikt .

Editor information

Editors and Affiliations

  1. Indian Institute of Technology Madras, Chennai, India

    Shweta Agrawal

  2. Chinese Academy of Sciences, Beijing, China

    Dongdai Lin

Rights and permissions

Reprints and permissions

Copyright information

© 2022 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Benedikt, B.J., Fischlin, M., Huppert, M. (2022). Nostradamus Goes Quantum. In: Agrawal, S., Lin, D. (eds) Advances in Cryptology – ASIACRYPT 2022. ASIACRYPT 2022. Lecture Notes in Computer Science, vol 13793. Springer, Cham. https://doi.org/10.1007/978-3-031-22969-5_20

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-22969-5_20

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-22968-8

  • Online ISBN: 978-3-031-22969-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation