zbMATH — the first resource for mathematics

Breaking symmetric cryptosystems using quantum period finding. (English) Zbl 1391.94766
Robshaw, Matthew (ed.) et al., Advances in cryptology – CRYPTO 2016. 36th annual international cryptology conference, Santa Barbara, CA, USA, August 14–18, 2016. Proceedings. Part II. Berlin: Springer (ISBN 978-3-662-53007-8/pbk; 978-3-662-53008-5/ebook). Lecture Notes in Computer Science 9815, 207-237 (2016).
Summary: Due to Shor’s algorithm, quantum computers are a severe threat for public key cryptography. This motivated the cryptographic community to search for quantum-safe solutions. On the other hand, the impact of quantum computing on secret key cryptography is much less understood. In this paper, we consider attacks where an adversary can query an oracle implementing a cryptographic primitive in a quantum superposition of different states. This model gives a lot of power to the adversary, but recent results show that it is nonetheless possible to build secure cryptosystems in it.
We study applications of a quantum procedure called Simon’s algorithm (the simplest quantum period finding algorithm) in order to attack symmetric cryptosystems in this model. Following previous works in this direction, we show that several classical attacks based on finding collisions can be dramatically sped up using Simon’s algorithm: finding a collision requires \(\varOmega (2^{n/2})\) queries in the classical setting, but when collisions happen with some hidden periodicity, they can be found with only \(O(n)\) queries in the quantum model.
We obtain attacks with very strong implications. First, we show that the most widely used modes of operation for authentication and authenticated encryption (e.g. CBC-MAC, PMAC, GMAC, GCM, and OCB) are completely broken in this security model. Our attacks are also applicable to many CAESAR candidates: CLOC, AEZ, COPA, OTR, POET, OMD, and Minalpher. This is quite surprising compared to the situation with encryption modes: Anand et al. show that standard modes are secure with a quantum-secure PRF.Second, we show that Simon’s algorithm can also be applied to slide attacks, leading to an exponential speed-up of a classical symmetric cryptanalysis technique in the quantum model.
For the entire collection see [Zbl 1344.94002].

94A60 Cryptography
Full Text: DOI
[1] Abed, F., Fluhrer, S.R., Forler, C., List, E., Lucks, S., McGrew, D.A., Wenzel, J.: Pipelineable on-line encryption. In: Cid and Rechberger [17], pp. 205–223. http://dx.doi.org/10.1007/978-3-662-46706-0_11 · Zbl 1382.94036 · doi:10.1007/978-3-662-46706-0_11
[2] Alagic, G., Broadbent, A., Fefferman, B., Gagliardoni, T., Schaffner, C., Jules, M.S.: Computational security of quantum encryption. arXiv preprint (2016). arXiv:1602.01441 · Zbl 1407.94068
[3] Anand, M.V., Targhi, E.E., Tabia, G.N., Unruh, D.: Post-quantum security of the CBC, CFB, OFB, CTR, and XTS modes of operation. In: Takagi, T., et al. (eds.) PQCrypto 2016. LNCS, vol. 9606, pp. 44–63. Springer, Heidelberg (2016). http://dx.doi.org/10.1007/978-3-319-29360-8_4 · Zbl 1405.81023 · doi:10.1007/978-3-319-29360-8_4
[4] Andreeva, E., Bogdanov, A., Luykx, A., Mennink, B., Tischhauser, E., Yasuda, K.: Parallelizable and authenticated online ciphers. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part I. LNCS, vol. 8269, pp. 424–443. Springer, Heidelberg (2013). http://dx.doi.org/10.1007/978-3-642-42033-7_22 · Zbl 1327.94026 · doi:10.1007/978-3-642-42033-7_22
[5] Bellare, M., Kilian, J., Rogaway, P.: The security of the cipher block chaining message authentication code. J. Comput. Syst. Sci. 61(3), 362–399 (2000). http://dx.doi.org/10.1006/jcss.1999.1694 · Zbl 0970.68054 · doi:10.1006/jcss.1999.1694
[6] Bernstei, D.J.: Introduction to post-quantum cryptography. In: Bernstein, D.J., Buchmann, J., Dahmen, E. (eds.) Post-Quantum Cryptography, pp. 1–14. Springer, Heidelberg (2009) · Zbl 1158.81311 · doi:10.1007/978-3-540-88702-7_1
[7] Biryukov, A., Wagner, D.: Slide attacks. In: Knudsen, L.R. (ed.) FSE 1999. LNCS, vol. 1636, pp. 245–259. Springer, Heidelberg (1999). http://dx.doi.org/10.1007/3-540-48519-8_18 · Zbl 0942.94020 · doi:10.1007/3-540-48519-8_18
[8] Biryukov, A., Wagner, D.: Advanced slide attacks. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 589–606. Springer, Heidelberg (2000). http://dx.doi.org/10.1007/3-540-45539-6_41 · Zbl 1082.94506 · doi:10.1007/3-540-45539-6_41
[9] Black, J.A., 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). http://dx.doi.org/10.1007/3-540-44598-6_12 · Zbl 0995.94545 · doi:10.1007/3-540-44598-6_12
[10] Black, J.A., Rogaway, P.: A block-cipher mode of operation for parallelizable message authentication. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 384–397. Springer, Heidelberg (2002). http://dx.doi.org/10.1007/3-540-46035-7_25 · Zbl 1056.94520 · doi:10.1007/3-540-46035-7_25
[11] Boneh, D., Dagdelen, Ö., Fischlin, M., Lehmann, A., Schaffner, C., Zhandry, M.: Random oracles in a quantum world. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 41–69. Springer, Heidelberg (2011). http://dx.doi.org/10.1007/978-3-642-25385-0_3 · Zbl 1227.94033 · doi:10.1007/978-3-642-25385-0_3
[12] Boneh, D., Zhandry, M.: Quantum-secure message authentication codes. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 592–608. Springer, Heidelberg (2013). http://dx.doi.org/10.1007/978-3-642-38348-9_35 · Zbl 1312.94111 · doi:10.1007/978-3-642-38348-9_35
[13] Boneh, D., Zhandry, M.: Secure signatures and chosen ciphertext security in a quantum computing world. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part II. LNCS, vol. 8043, pp. 361–379. Springer, Heidelberg (2013). http://dx.doi.org/10.1007/978-3-642-40084-1_21 · Zbl 1317.81074 · doi:10.1007/978-3-642-40084-1_21
[14] Brassard, G., Høyer, P., Kalach, K., Kaplan, M., Laplante, S., Salvail, L.: Merkle puzzles in a quantum world. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 391–410. Springer, Heidelberg (2011) · Zbl 1287.94057 · doi:10.1007/978-3-642-22792-9_22
[15] Broadbent, A., Jeffery, S.: Quantum homomorphic encryption for circuits of low t-gate complexity. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 609–629. Springer, Heidelberg (2015) · Zbl 1369.94521 · doi:10.1007/978-3-662-48000-7_30
[16] Carter, L., Wegman, M.N.: Universal classes of hash functions (extended abstract). In: Hopcroft, J.E., Friedman, E.P., Harrison, M.A. (eds.) Proceedings of the 9th Annual ACM Symposium on Theory of Computing, Boulder, Colorado, USA, 4–6 May 1977, pp. 106–112. ACM (1977). http://doi.acm.org/10.1145/800105.803400 · Zbl 0412.68090
[17] Cid, C., Rechberger, C. (eds.): FSE 2014. LNCS, vol. 8540. Springer, Heidelberg (2015). http://dx.doi.org/10.1007/978-3-662-46706-0 · Zbl 1318.68013
[18] Cogliani, S., Maimuţ, D., Naccache, D., do Canto, R.P., Reyhanitabar, R., Vaudenay, S., Vizár, D.: OMD: a compression function mode of operation for authenticated encryption. In: Joux, A., Youssef, A. (eds.) SAC 2014. LNCS, vol. 8781, pp. 112–128. Springer, Heidelberg (2014). http://dx.doi.org/10.1007/978-3-319-13051-4_7 · Zbl 1382.94083 · doi:10.1007/978-3-319-13051-4_7
[19] Daemen, J., Rijmen, V.: Probability distributions of correlation and differentials in block ciphers. J. Math. Crypt. 1(3), 221–242 (2007). http://dx.doi.org/10.1515/JMC.2007.011 · Zbl 1211.94028
[20] Damgård, I., Funder, J., Nielsen, J.B., Salvail, L.: Superposition attacks on cryptographic protocols. In: Padró, C. (ed.) ICITS 2013. LNCS, vol. 8317, pp. 142–161. Springer, Heidelberg (2014). http://dx.doi.org/10.1007/978-3-319-04268-8_9 · Zbl 1395.94278 · doi:10.1007/978-3-319-04268-8_9
[21] Dworkin, M.: Recommendation for block cipher modes of operation: the CMAC mode for authentication. NIST Special Publication 800–38B, National Institute for Standards and Technology, May 2005
[22] Even, S., Mansour, Y.: A construction of a cipher from a single pseudorandom permutation. J. Crypt. 10(3), 151–162 (1997). http://dx.doi.org/10.1007/s001459900025 · Zbl 1053.94552 · doi:10.1007/s001459900025
[23] Gagliardoni, T., Hülsing, A., Schaffner, C.: Semantic security and indistinguishability in the quantum world. arXiv preprint (2015). arXiv:1504.05255 · Zbl 1406.81021
[24] 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). http://doi.acm.org/10.1145/237814.237866 · Zbl 0922.68044
[25] Hoang, V.T., Krovetz, T., Rogaway, P.: Robust authenticated-encryption AEZ and the problem that it solves. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 15–44. Springer, Heidelberg (2015). http://dx.doi.org/10.1007/978-3-662-46800-5_2 · Zbl 1365.94485 · doi:10.1007/978-3-662-46800-5_2
[26] Iwata, T., Kurosawa, K.: OMAC: one-key CBC MAC. In: Johansson, T. (ed.) FSE 2003. LNCS, vol. 2887, pp. 129–153. Springer, Heidelberg (2003). http://dx.doi.org/10.1007/978-3-540-39887-5_11 · Zbl 1254.94033 · doi:10.1007/978-3-540-39887-5_11
[27] Iwata, T., Minematsu, K., Guo, J., Morioka, S.: CLOC: authenticated encryption for short input. In: Cid and Rechberger [17] , pp. 149–167. http://dx.doi.org/10.1007/978-3-662-46706-0_8 · Zbl 1382.94121 · doi:10.1007/978-3-662-46706-0_8
[28] Kaplan, M.: Quantum attacks against iterated block ciphers. CoRR abs/1410.1434 (2014). http://arxiv.org/abs/1410.1434
[29] Kaplan, M., Leurent, G., Leverrier, A., Naya-Plasencia, M.: Quantum differential and linear cryptanalysis. CoRR abs/1510.05836 (2015). http://arxiv.org/abs/1510.05836 · Zbl 1391.94766
[30] Krovetz, T., Rogaway, P.: The software performance of authenticated-encryption modes. In: Joux, A. (ed.) FSE 2011. LNCS, vol. 6733, pp. 306–327. Springer, Heidelberg (2011). http://dx.doi.org/10.1007/978-3-642-21702-9_18 · Zbl 1307.94119 · doi:10.1007/978-3-642-21702-9_18
[31] Kuwakado, H., Morii, M.: Quantum distinguisher between the 3-round Feistel cipher and the random permutation. In: 2010 IEEE International Symposium on Information Theory Proceedings (ISIT), June 2010, pp. 2682–2685 (2010) · doi:10.1109/ISIT.2010.5513654
[32] Kuwakado, H., Morii, M.: Security on the quantum-type Even-Mansour cipher. In: 2012 International Symposium on Information Theory and Its Applications (ISITA), October 2012, pp. 312–316 (2012)
[33] Liskov, M., Rivest, R.L., Wagner, D.: Tweakable block ciphers. J. Crypt. 24(3), 588–613 (2011). http://dx.doi.org/10.1007/s00145-010-9073-y · Zbl 1258.94040 · doi:10.1007/s00145-010-9073-y
[34] Luby, M., Rackoff, C.: How to construct pseudorandom permutations from pseudorandom functions. SIAM J. Comput. 17(2), 373–386 (1988). http://dx.doi.org/10.1137/0217022 · Zbl 0644.94018 · doi:10.1137/0217022
[35] Lydersen, L., Wiechers, C., Wittmann, C., Elser, D., Skaar, J., Makarov, V.: Hacking commercial quantum cryptography systems by tailored bright illumination. Nat. Photonics 4(10), 686–689 (2010) · doi:10.1038/nphoton.2010.214
[36] McGrew, D.A., Viega, J.: The security and performance of the Galois/Counter Mode (GCM) of operation. In: Canteaut, A., Viswanathan, K. (eds.) INDOCRYPT 2004. LNCS, vol. 3348, pp. 343–355. Springer, Heidelberg (2004). http://dx.doi.org/10.1007/978-3-540-30556-9_27 · Zbl 1113.94315 · doi:10.1007/978-3-540-30556-9_27
[37] Minematsu, K.: Parallelizable Rate-1 authenticated encryption from pseudorandom functions. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 275–292. Springer, Heidelberg (2014). http://dx.doi.org/10.1007/978-3-642-55220-5_16 · Zbl 1332.94091 · doi:10.1007/978-3-642-55220-5_16
[38] Montanaro, A., de Wolf, R.: A survey of quantum property testing. arXiv preprint (2013). arXiv:1310.2035
[39] Rogaway, P.: Efficient instantiations of tweakable blockciphers and refinements to modes OCB and PMAC. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 16–31. Springer, Heidelberg (2004). http://dx.doi.org/10.1007/978-3-540-30539-2_2 · Zbl 1094.94035 · doi:10.1007/978-3-540-30539-2_2
[40] Rogaway, P., Bellare, M., Black, J., Krovetz, T.: OCB: a block-cipher mode of operation for efficient authenticated encryption. In: Reiter, M.K., Samarati, P. (eds.) CCS 2001, Proceedings of the 8th ACM Conference on Computer and Communications Security, Philadelphia, Pennsylvania, USA, 6–8 November 2001, pp. 196–205. ACM (2001). http://doi.acm.org/10.1145/501983.502011
[41] Santoli, T., Schaffner, C.: Using simon’s algorithm to attack symmetric-key cryptographic primitives. arXiv preprint (2016). arXiv:1603.07856
[42] Sasaki, Y., Todo, Y., Aoki, K., Naito, Y., Sugawara, T., Murakami, Y., Matsui, M., Hirose, S.: Minalpher v1.1. CAESAR submission, August 2015
[43] Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997). http://dx.doi.org/10.1137/S0097539795293172 · Zbl 1005.11065 · doi:10.1137/S0097539795293172
[44] Simon, D.R.: On the power of quantum computation. SIAM J. Comput. 26(5), 1474–1483 (1997) · Zbl 0883.03024 · doi:10.1137/S0097539796298637
[45] Unruh, D.: Non-interactive zero-knowledge proofs in the quantum random oracle model. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 755–784. Springer, Heidelberg (2015). Preprint on IACR ePrint 2014/587 · Zbl 1375.94159 · doi:10.1007/978-3-662-46803-6_25
[46] Xu, F., Qi, B., Lo, H.K.: Experimental demonstration of phase-remapping attack in a practical quantum key distribution system. New J. Phys. 12(11), 113026 (2010) · doi:10.1088/1367-2630/12/11/113026
[47] Yuval, G.: Reinventing the travois: Encryption/MAC in 30 ROM bytes. In: Biham, E. (ed.) FSE 1997. LNCS, vol. 1267, pp. 205–209. Springer, Heidelberg (1997). http://dx.doi.org/10.1007/BFb0052347 · Zbl 1385.94079 · doi:10.1007/BFb0052347
[48] Zhandry, M.: How to construct quantum random functions. In: 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, 20–23 October 2012, pp. 679–687. IEEE Computer Society (2012). http://dx.doi.org/10.1109/FOCS.2012.37 · doi:10.1109/FOCS.2012.37
[49] Zhandry, M.: Secure identity-based encryption in the quantum random oracle model. Int. J. Quan. Inf. 13(04), 1550014 (2015) · Zbl 1327.81178 · doi:10.1142/S0219749915500148
[50] Zhao, Y., Fung, C.H.F., Qi, B., Chen, C., Lo, H.K.: Quantum hacking: experimental demonstration of time-shift attack against practical quantum-key-distribution systems. Phys. Rev. A 78(4), 042333 (2008) · doi:10.1103/PhysRevA.78.042333
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.