Hidden shift quantum cryptanalysis and implications. (English) Zbl 1446.94106
Peyrin, Thomas (ed.) et al., Advances in cryptology – ASIACRYPT 2018. 24th international conference on the theory and application of cryptology and information security, Brisbane, QLD, Australia, December 2–6, 2018. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 11272, 560-592 (2018).
Summary: At Eurocrypt 2017 [G. Alagic and A. Russell, Lect. Notes Comput. Sci. 10212, 65–93 (2017; Zbl 1394.94924)] a tweak to counter Simon’s quantum attack was proposed: replace the common bitwise addition with other operations, as a modular addition. The starting point of our paper is a follow up of these previous results:{
}First, we have developed new algorithms that improves and generalizes Kuperberg’s algorithm for the hidden shift problem, which is the algorithm that applies instead of Simon when considering modular additions. Thanks to our improved algorithm, we have been able to build a quantum attack in the superposition model on Poly1305, proposed at FSE 2005 [D. J. Bernstein, Lect. Notes Comput. Sci. 3557, 32–49 (2005; Zbl 1140.68382)], widely used and claimed to be quantumly secure. We also answer an open problem by analyzing the effect of the tweak to the FX construction.{
}We have also generalized the algorithm. We propose for the first time a quantum algorithm for solving the hidden problem with parallel modular additions, with a complexity that matches both Simon and Kuperberg in its extremes.{
}In order to verify our theoretical analysis, and to get concrete estimates of the cost of the algorithms, we have simulated them, and were able to validate our estimated complexities.{
}Finally, we analyze the security of some classical symmetric constructions with concrete parameters, to evaluate the impact and practicality of the proposed tweak. We concluded that the tweak does not seem to be efficient.
For the entire collection see [Zbl 1402.94008].
For the entire collection see [Zbl 1402.94008].
Keywords:
quantum cryptanalysis; hidden shift problem; Simon-meets-Kuperberg; Poly1305; symmetric cryptography; modular additionsReferences:
| [1] | Abadi, M.; Rogaway, P., Reconciling two views of cryptography (the computational soundness of formal encryption), J. Cryptol., 20, 3, 395 (2007) · doi:10.1007/s00145-007-0203-0 |
| [2] | Albrecht, M.R., Degabriele, J.P., Hansen, T.B., Paterson, K.G.: A surfeit of SSH cipher suites. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM CCS 2016, pp. 1480-1491. ACM Press, October 2016 |
| [3] | Albrecht, M.R., Paterson, K.G., Watson, G.J.: Plaintext recovery attacks against SSH. In: 2009 IEEE Symposium on Security and Privacy, pp. 16-26. IEEE Computer Society Press, May 2009 |
| [4] | AlFardan, N.J., Paterson, K.G.: Lucky thirteen: breaking the TLS and DTLS record protocols. In: 2013 IEEE Symposium on Security and Privacy, pp. 526-540. IEEE Computer Society Press, May 2013 |
| [5] | Andreeva, E.; Bogdanov, A.; Luykx, A.; Mennink, B.; Mouha, N.; Yasuda, K.; Sarkar, P.; Iwata, T., How to securely release unverified plaintext in authenticated encryption, Advances in Cryptology - ASIACRYPT 2014, 105-125 (2014), Heidelberg: Springer, Heidelberg · Zbl 1306.94021 · doi:10.1007/978-3-662-45611-8_6 |
| [6] | Barwell, G.; Page, D.; Stam, M.; Groth, J., Rogue decryption failures: reconciling AE robustness notions, Cryptography and Coding, 94-111 (2015), Cham: Springer, Cham · Zbl 1376.94026 · doi:10.1007/978-3-319-27239-9_6 |
| [7] | Bellare, M.; Boldyreva, A.; Desai, A.; Pointcheval, D.; Boyd, C., Key-privacy in public-key encryption, Advances in Cryptology — ASIACRYPT 2001, 566-582 (2001), Heidelberg: Springer, Heidelberg · Zbl 1064.94553 · doi:10.1007/3-540-45682-1_33 |
| [8] | Bellare, M., Desai, A., Jokipii, E., Rogaway, P.: A concrete security treatment of symmetric encryption. In: 38th FOCS, pp. 394-403. IEEE Computer Society Press, October 1997 |
| [9] | Bellare, M., Kohno, T., Namprempre, C.: Authenticated encryption in SSH: provably fixing the SSH binary packet protocol. In: Atluri, V. (ed.) ACM CCS 2002, pp. 1-11. ACM Press, November 2002 |
| [10] | Bellare, M.; Namprempre, C.; Okamoto, T., Authenticated encryption: relations among notions and analysis of the generic composition paradigm, Advances in Cryptology — ASIACRYPT 2000, 531-545 (2000), Heidelberg: Springer, Heidelberg · Zbl 0973.68059 · doi:10.1007/3-540-44448-3_41 |
| [11] | Boldyreva, A.; Degabriele, JP; Paterson, KG; Stam, M.; Pointcheval, D.; Johansson, T., Security of symmetric encryption in the presence of ciphertext fragmentation, Advances in Cryptology - EUROCRYPT 2012, 682-699 (2012), Heidelberg: Springer, Heidelberg · Zbl 1297.94053 · doi:10.1007/978-3-642-29011-4_40 |
| [12] | Boldyreva, A.; Degabriele, JP; Paterson, KG; Stam, M.; Moriai, S., On symmetric encryption with distinguishable decryption failures, Fast Software Encryption, 367-390 (2014), Heidelberg: Springer, Heidelberg · Zbl 1321.94044 · doi:10.1007/978-3-662-43933-3_19 |
| [13] | Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: 42nd FOCS, pp. 136-145. IEEE Computer Society Press, October 2001 |
| [14] | Canetti, R.; Krawczyk, H.; Pfitzmann, B., Analysis of key-exchange protocols and their use for building secure channels, Advances in Cryptology — EUROCRYPT 2001, 453-474 (2001), Heidelberg: Springer, Heidelberg · Zbl 0981.94032 · doi:10.1007/3-540-44987-6_28 |
| [15] | Canetti, R.; Krawczyk, H.; Knudsen, LR, Universally composable notions of key exchange and secure channels, Advances in Cryptology — EUROCRYPT 2002, 337-351 (2002), Heidelberg: Springer, Heidelberg · Zbl 1056.94511 · doi:10.1007/3-540-46035-7_22 |
| [16] | Canvel, B.; Hiltgen, AP; Vaudenay, S.; Vuagnoux, M.; Boneh, D., Password interception in a SSL/TLS channel, Advances in Cryptology - CRYPTO 2003, 583-599 (2003), Heidelberg: Springer, Heidelberg · Zbl 1122.94362 · doi:10.1007/978-3-540-45146-4_34 |
| [17] | Degabriele, J.P., Paterson, K.G.: On the (in)security of IPsec in MAC-then-encrypt configurations. In: Al-Shaer, E., Keromytis, A.D., Shmatikov, V. (eds.) ACM CCS 2010, pp. 493-504. ACM Press, October 2010 |
| [18] | Desai, A.; Bellare, M., New paradigms for constructing symmetric encryption schemes secure against chosen-ciphertext attack, Advances in Cryptology — CRYPTO 2000, 394-412 (2000), Heidelberg: Springer, Heidelberg · Zbl 0989.68054 · doi:10.1007/3-540-44598-6_25 |
| [19] | Fischlin, M.; Stern, J., Pseudorandom function tribe ensembles based on one-way permutations: improvements and applications, Advances in Cryptology — EUROCRYPT 99, 432-445 (1999), Heidelberg: Springer, Heidelberg · Zbl 0931.94044 · doi:10.1007/3-540-48910-X_30 |
| [20] | Fischlin, M.; Günther, F.; Marson, GA; Paterson, KG; Gennaro, R.; Robshaw, MJB, Data is a stream: security of stream-based channels, Advances in Cryptology - CRYPTO 2015, 545-564 (2015), Heidelberg: Springer, Heidelberg · Zbl 1369.94535 · doi:10.1007/978-3-662-48000-7_27 |
| [21] | Hoang, VT; Krovetz, T.; Rogaway, P.; Oswald, E.; Fischlin, M., Robust authenticated-encryption AEZ and the problem that it solves, Advances in Cryptology - EUROCRYPT 2015, 15-44 (2015), Heidelberg: Springer, Heidelberg · Zbl 1365.94485 · doi:10.1007/978-3-662-46800-5_2 |
| [22] | Hoang, VT; Reyhanitabar, R.; Rogaway, P.; Vizár, D.; Gennaro, R.; Robshaw, MJB, Online authenticated-encryption and its nonce-reuse misuse-resistance, Advances in Cryptology - CRYPTO 2015, 493-517 (2015), Heidelberg: Springer, Heidelberg · Zbl 1375.94167 · doi:10.1007/978-3-662-47989-6_24 |
| [23] | Küsters, R., Tuengerthal, M.: Universally composable symmetric encryption. In: Proceedings of the 22nd IEEE Computer Security Foundations Symposium, CSF 2009, Port Jefferson, New York, USA, 8-10 July 2009, pp. 293-307. IEEE Computer Society (2009). doi:10.1109/CSF.2009.18 |
| [24] | Maurer, U.; Rüedlinger, A.; Tackmann, B.; Cramer, R., Confidentiality and integrity: a constructive perspective, Theory of Cryptography, 209-229 (2012), Heidelberg: Springer, Heidelberg · Zbl 1303.94092 · doi:10.1007/978-3-642-28914-9_12 |
| [25] | Maurer, U., Tackmann, B.: On the soundness of authenticate-then-encrypt: formalizing the malleability of symmetric encryption. In: Al-Shaer, E., Keromytis, A.D., Shmatikov, V. (eds.) ACM CCS 2010, pp. 505-515. ACM Press, October 2010 |
| [26] | Paterson, KG; Watson, GJ; Gilbert, H., Plaintext-dependent decryption: a formal security treatment of SSH-CTR, Advances in Cryptology - EUROCRYPT 2010, 345-361 (2010), Heidelberg: Springer, Heidelberg · Zbl 1280.94090 · doi:10.1007/978-3-642-13190-5_18 |
| [27] | Rogaway, P.; Roy, BK; Meier, W., Nonce-based symmetric encryption, Fast Software Encryption, 348-358 (2004), Heidelberg: Springer, Heidelberg · Zbl 1079.68559 · doi:10.1007/978-3-540-25937-4_22 |
| [28] | Rogaway, P., Bellare, M., Black, J., Krovetz, T.: OCB: a block-cipher mode of operation for efficient authenticated encryption. In: ACM CCS 2001, pp. 196-205. ACM Press, November 2001 |
| [29] | Rogaway, P.; Shrimpton, T.; Vaudenay, S., A provable-security treatment of the key-wrap problem, Advances in Cryptology - EUROCRYPT 2006, 373-390 (2006), Heidelberg: Springer, Heidelberg · Zbl 1140.94369 · doi:10.1007/11761679_23 |
| [30] | Kaplan, M.; Leurent, G.; Leverrier, A.; Naya-Plasencia, M., Quantum differential and linear cryptanalysis, IACR Trans. Symmetric Cryptol., 2016, 1, 71-94 (2016) · Zbl 1391.94766 |
| [31] | Kilian, J.; Rogaway, P.; Koblitz, N., How to protect DES against exhaustive key search, Advances in Cryptology — CRYPTO ’96, 252-267 (1996), Heidelberg: Springer, Heidelberg · Zbl 1329.94067 · doi:10.1007/3-540-68697-5_20 |
| [32] | Kuperberg, G., A subexponential-time quantum algorithm for the dihedral hidden subgroup problem, SIAM J. Comput., 35, 1, 170-188 (2005) · Zbl 1084.81019 · doi:10.1137/S0097539703436345 |
| [33] | Kuperberg, G.: Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem. In: Severini, S., Brandão, F.G.S.L. (eds.) 8th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2013, 21-23 May 2013, Guelph, Canada. LIPIcs, vol. 22, pp. 20-34. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2013) · Zbl 1356.68076 |
| [34] | 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), pp. 2682-2685, June 2010 |
| [35] | Kuwakado, H., Morii, M.: Security on the quantum-type Even-Mansour cipher. In: 2012 International Symposium on Information Theory and its Applications (ISITA), pp. 312-316, October 2012 |
| [36] | Langley, A., Chang, W., Mavrogiannopoulos, N., Strombergson, J., Josefsson, S.: chacha20-poly1305 cipher suites for transport layer security (TLs). In: RFC 7905, June 2016. doi:10.17487/RFC7905 |
| [37] | Leander, Gregor; May, Alexander, Grover Meets Simon - Quantumly Attacking the FX-construction, Advances in Cryptology - ASIACRYPT 2017, 161-178 (2017), Cham: Springer International Publishing, Cham · Zbl 1380.94109 · doi:10.1007/978-3-319-70697-9_6 |
| [38] | 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 |
| [39] | Regev, O.: A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space. CoRR (2004) |
| [40] | Rivest, R.L., Robshaw, M.J.B., Yin, Y.L.: RC6 as the AES. In: AES Candidate Conference, pp. 337-342 (2000) |
| [41] | Roetteler, M.; Steinwandt, R., A note on quantum related-key attacks, Inf. Process. Lett., 115, 1, 40-44 (2015) · Zbl 1358.94076 · doi:10.1016/j.ipl.2014.08.009 |
| [42] | Santoli, T., Schaffner, C.: Using Simon’s Algorithm to Attack Symmetric-Key Cryptographic Primitives. arXiv preprint arXiv:1603.07856 (2016) |
| [43] | Simon, D.R.: On the power of quantum cryptography. In: 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994, pp. 116-123. IEEE Computer Society (1994) |
| [44] | Song, F.; Yun, A.; Katz, J.; Shacham, H., Quantum security of NMAC and related constructions, Advances in Cryptology - CRYPTO 2017, 283-309 (2017), Cham: Springer, Cham · Zbl 1410.94107 · doi:10.1007/978-3-319-63715-0_10 |
| [45] | Suzaki, T.; Minematsu, K.; Morioka, S.; Kobayashi, E.; Knudsen, LR; Wu, H., \( \mathit{TWINE} \): a lightweight block cipher for multiple platforms, Selected Areas in Cryptography, 339-354 (2013), Heidelberg: Springer, Heidelberg · Zbl 1327.94075 · doi:10.1007/978-3-642-35999-6_22 |
| [46] | Takagi, T.; Peyrin, T., Advances in Cryptology - ASIACRYPT 2017 (2017), Cham: Springer, Cham · Zbl 1380.94008 · doi:10.1007/978-3-319-70697-9 |
| [47] | Unruh, D.; Oswald, E.; Fischlin, M., Non-interactive zero-knowledge proofs in the quantum random oracle model, Advances in Cryptology - EUROCRYPT 2015, 755-784 (2015), Heidelberg: Springer, Heidelberg · Zbl 1375.94159 · doi:10.1007/978-3-662-46803-6_25 |
| [48] | Xu, F.; Qi, B.; Lo, HK, 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 |
| [49] | Yuval, G.; Biham, E., Reinventing the travois: encryption/MAC in 30 ROM bytes, Fast Software Encryption, 205-209 (1997), Heidelberg: Springer, Heidelberg · Zbl 1385.94079 · doi:10.1007/BFb0052347 |
| [50] | 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 (2012) |
| [51] | Zhandry, M., Secure identity-based encryption in the quantum random oracle model, Int. J. Quantum Inf., 13, 4, 1550014 (2015) · Zbl 1327.81178 · doi:10.1142/S0219749915500148 |
| [52] | Zhao, Y.; Fung, CHF; Qi, B.; Chen, C.; Lo, HK, 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
