Timing Analysis of Algorithm Substitution Attacks in a Post-Quantum TLS Protocol

• Dúnia Marchiori UFSC http://orcid.org/0000-0003-0501-8990
• Alexandre A. Giron UFSC / UTFPR https://orcid.org/0000-0001-7668-7505
• João Pedro A. do Nascimento UFSC
• Ricardo Custódio UFSC

DOI: https://doi.org/10.5753/sbseg.2021.17311

Resumo

Snowden's revelations about mass surveillance brought to public attention devastating attacks on cryptographic algorithm implementations. One of the most prominent subsets of these attacks is called Algorithm Substitution Attacks (ASA), where a subverted implementation leaks sensitive information. Recently, it has been proposed to modify TLS implementations to use Post-Quantum Cryptography (PQC). In this paper, we propose and analyze ASA in two PQC schemes that can be used in TLS. We attacked the Kyber Key Encapsulation Mechanism (KEM) and Falcon Signature and successfully deployed them in a TLS implementation. Results show that timing analysis can distinguish our Falcon subversion, but it is not enough to detect our attacks deployed in TLS.

Palavras-chave: algorithm substitution attacks, post-quantum cryptography, TLS

Referências

Avanzi, R., Bos, J., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J. M., Schwabe, P., Seiler, G., and Stehlé, D. (2020). CRYSTALS-Kyber: Algorithm specications and supporting documentation (version 3.0). Submission to the NIST’s postquantum cryptography standardization process.

Baek, J., Susilo, W., Kim, J., and Chow, Y.-W. (2019). Subversion in practice: How to efciently undermine signatures. IEEE Access, 7:68799–68811.

Bellare, M., Jaeger, J., and Kane, D. (2015). Mass-surveillance without the state: Strongly undetectable algorithm-substitution attacks. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, CCS ’15, page 1431–1440, New York, NY, USA. Association for Computing Machinery.

Berndt, S., Wichelmann, J., Pott, C., Traving, T.-H., and Eisenbarth, T. (2020). ASAP: Algorithm Substitution Attacks on Cryptographic Protocols. Cryptology ePrint Archive, Report 2020/1452. Available at: https://eprint.iacr.org/2020/1452. Accessed on 2021-05-02.

Braithwaite, M. (2016). Experimenting with post-quantum cryptography. https://security.googleblog.com/2016/07/ at: Available experimenting-with-post-quantum.html. Accessed on 2021-02-25.

Checkoway, S., Maskiewicz, J., Garman, C., Fried, J., Cohney, S., Green, M., Heninger, N., Weinmann, R.-P., Rescorla, E., and Shacham, H. (2016). A systematic analysis of the juniper dual EC incident. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS ’16, page 468–479, New York, NY, USA. Association for Computing Machinery.

Fouque, P.-A., Hoffstein, J., Kirchner, P., Lyubashevsky, V., Pornin, T., Prest, T., Ricosset, T., Seiler, G., Whyte, W., and Zhang, Z. (2020). Falcon: Fast-Fourier Latticebased Compact Signatures over NTRU documentation (version 1.2). Submission to the NIST’s post-quantum cryptography standardization process.

Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212–219, Philadelphia Pennsylvania USA. ACM.

Janovsky, A., Krhovjak, J., and Matyas, V. (2019). Bringing kleptography to real-world TLS. In Blazy, O. and Yeun, C. Y., editors, Information Security Theory and Practice, pages 15–27, Cham. Springer International Publishing.

Kwant, R., Lange, T., and Thissen, K. (2018). Lattice klepto. In Adams, C. and Camenisch, J., editors, Selected Areas in Cryptography – SAC 2017, pages 336–354, Cham. Springer International Publishing.

Kwiatkowski, K., Langley, A., Sullivan, N., Levin, D., Mislove, A., and Valenta, L. (2019). Measuring TLS key exchange with post-quantum KEM. In Workshop Record of the Second PQC Standardization Conference.

Lantz, B. and O’Connor, B. (2015). A mininet-based virtual testbed for distributed sdn development. ACM SIGCOMM Computer Communication Review, 45(4):365–366.

Martínez, V. G., Encinas, L. H., and Dios, A. Q. (2015). Security and practical considerations when implementing the elliptic curve integrated encryption scheme. Cryptologia, 39(3):244–269.

Mironov, I. and Stephens-Davidowitz, N. (2015). Cryptographic reverse rewalls. In Oswald, E. and Fischlin, M., editors, Advances in Cryptology EUROCRYPT 2015, pages 657–686, Berlin, Heidelberg. Springer Berlin Heidelberg.

Mosca, M. (2018). Cybersecurity in an era with quantum computers: Will we be ready? IEEE Security Privacy, 16(5):38–41.

Nemec, M., Sys, M., Svenda, P., Klinec, D., and Matyas, V. (2017). The return of coppersmith’s attack: Practical factorization of widely used rsa moduli. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS ’17, page 1631–1648, New York, NY, USA. Association for Computing Machinery.

NIST (2016). Post-quantum cryptography. Available at: https://csrc.nist.gov/Projects/Post-Quantum-Cryptography. Accessed on 2020-06-26.

Paquin, C., Stebila, D., and Tamvada, G. (2020). Benchmarking post-quantum cryptography in TLS. In Ding, J. and Tillich, J.-P., editors, Post-Quantum Cryptography, pages 72–91, Cham. Springer International Publishing.

Perlroth, N., Larson, J., and Shane, S. (2021). N.S.A. able to foil basic safeguards of privacy on web. Available at: https://www.nytimes.com/2013/09/06/us/nsa-foils-much-internet-encryption.html. Accessed on 2021-04-21.

Rescorla, E. (2018). The transport layer security (TLS) protocol version 1.3. RFC 8446, RFC Editor. Available at: http://www.rfc-editor.org/rfc/rfc8446.txt. Accessed on 2021-05-02.

Shor, P. W. (1994). Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science, pages 124–134, Santa Fe, NM, USA. IEEE, IEEE.

Stebila, D. and Mosca, M. (2016). Post-quantum key exchange for the internet and the open quantum safe project. In International Conference on Selected Areas in Cryptography, pages 14–37. Springer.

Teseleanu, G. (2019). Threshold kleptographic attacks on discrete logarithm based signatures. In Lange, T. and Dunkelman, O., editors, Progress in Cryptology – LATINCRYPT 2017, pages 401–414, Cham. Springer International Publishing.

Yang, Z., Chen, R., Li, C., Qu, L., and Yang, G. (2020a). On the security of LWE cryptosystem against subversion attacks. The Computer Journal, 63(4):495–507.

Yang, Z., Xie, T., and Pan, Y. (2020b). Lattice klepto revisited. In Proceedings of the 15th ACM Asia Conference on Computer and Communications Security, ASIA CCS ’20, page 867–873, New York, NY, USA. Association for Computing Machinery.

Young, A. and Yung, M. (1996). The dark side of “black-box” cryptography or: Should we trust capstone? In Koblitz, N., editor, Advances in Cryptology - CRYPTO ’96, pages 89–103, Berlin, Heidelberg. Springer Berlin Heidelberg.