Attacking and defending post-quantum cryptography candidates

• Thales Paiva USP
• Routo Terada USP

DOI: https://doi.org/10.5753/sbseg_estendido.2024.242006

Resumo

This dissertation, which is written as a collection of papers, presents original contributions to the security and implementation of three post-quantum cryptography candidates: HQC, PKP and BIKE. Both HQC and BIKE are code-based key encapsulation mechanisms that were selected as alternate candidates in NIST’s post-quantum standardization process. The Permuted Kernel Problem (PKP) is an NP-hard combinatorial problem that can be used to instantiate post-quantum digital signature schemes. The first contribution is a timing attack against HQC that allows an attacker to recover the secret key after recording the decryption time of around 400 million ciphertexts, for 128 bits of security. The second contribution consists of the first attack targeting a generalization of PKP for small fields. For 80-bit security parameters, the attack is able to recover a fraction 2−40 of the keys using only 248 operations, and about 7.2% of the keys using 262 operations. The third and last contribution consists of a new decryption algorithm for BIKE. Our constant-time implementation of this algorithm achieves speedups of 1.18, 1.29 and 1.47, with respect to state-of-the-art decryption algorithms, for security levels 128, 192 and 256, respectively.

Referências

Albrecht, M., Cid, C., Paterson, K. G., Tjhai, C. J., and Tomlinson, M. (2018). NTS-KEM.

Aragon, N., Barreto, P. S. L. M., Bettaieb, S., Bidoux, L., Blazy, O., Deneuville, J.-C., Gaborit, P., Ghosh, S., Gueron, S., Güneysu, T., Aguilar-Melchor, C., Misoczki, R., Persichetti, E., Richter-Brockmann, J., Sendrier, N., Tillich, J.-P., Vasseur, V., and Zémor, G. (2021). BIKE: Bit flipping key encapsulation. [link].

Aragon, N., Barreto, P. S. L. M., Bettaieb, S., Bidoux, L., Blazy, O., Deneuville, J.-C., Gaborit, P., Gueron, S., Guneysu, T., Melchor, C. A., Misoczki, R., Persichetti, E., Sendrier, N., Tillich, J.-P., and Zémor, G. (2017). BIKE: Bit flipping key encapsulation. [link].

Baldi, M. (2014). QC-LDPC Code-Based Cryptosystems, pages 91–117. Springer International Publishing, Cham.

Bernstein, D. J., Chou, T., Lange, T., Misoczki, R., Niederhagen, R., Persichetti, E., Schwabe, P., Szefer, J., and Wang, W. (2019). Classic McEliece: conservative code-based cryptography.

Beullens, W., Faugère, J.-C., Koussa, E., Macario-Rat, G., Patarin, J., and Perret, L. (2019). PKP-based signature scheme. In International Conference on Cryptology in India, pages 3–22. Springer.

Drucker, N., Gueron, S., and Kostic, D. (2019). On constant-time QC-MDPC decoding with negligible failure rate. IACR Cryptol. ePrint Arch., 2019:1289.

Drucker, N., Gueron, S., and Kostic, D. (2020). QC-MDPC decoders with several shades of gray. In International Conference on Post-Quantum Cryptography, pages 35–50. Springer.

Fabšič, T., Hromada, V., Stankovski, P., Zajac, P., Guo, Q., and Johansson, T. (2017). A reaction attack on the QC-LDPC McEliece cryptosystem. In International Workshop on Post-Quantum Cryptography, pages 51–68. Springer.

Fiat, A. and Shamir, A. (1986). How to prove yourself: Practical solutions to identification and signature problems. In Conference on the Theory and Application of Cryptographic Techniques, pages 186–194. Springer.

Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York.

Guo, Q., Johansson, T., and Stankovski, P. (2016). A key recovery attack on MDPC with CCA security using decoding errors. In 22nd Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT).

Hofheinz, D., Hövelmanns, K., and Kiltz, E. (2017). A modular analysis of the Fujisaki-Okamoto transformation. In Theory of Cryptography Conference, pages 341–371. Springer.

Joiner, L. L. and Komo, J. J. (1995). Decoding binary BCH codes. In Proceedings IEEE Southeastcon’95. Visualize the Future, pages 67–73. IEEE.

Koussa, E., Macario-Rat, G., and Patarin, J. (2019). On the complexity of the Permuted Kernel Problem. IACR Cryptology ePrint Archive, 2019:412.

Lampe, R. and Patarin, J. (2011). Analysis of some natural variants of the PKP algorithm. IACR Cryptology ePrint Archive, 2011:686.

McEliece, R. J. (1978). A public-key cryptosystem based on algebraic coding theory. Deep Space Network Progress Report, 44:114–116.

Melchor, C. A., Aragon, N., Bettaieb, S., Bidoux, L., Blazy, O., Deneuville, J.-C., Gaborit, P., Persichetti, E., Zémor, G., and Bourges, I.-C. (2018). Hamming quasi-cyclic (HQC). Technical report, Technical report, National Institute of Standards and Technology.

Misoczki, R., Tillich, J.-P., Sendrier, N., and Barreto, P. S. L. M. (2013). MDPC-McEliece: New McEliece variants from moderate density parity-check codes. In Information Theory Proceedings (ISIT), 2013 IEEE International Symposium on, pages 2069–2073. IEEE.

Niederreiter, H. (1986). Knapsack-type cryptosystems and algebraic coding theory. Problems of Control and Information Theory, 15(2):159–166.

Rossi, M., Hamburg, M., Hutter, M., and Marson, M. E. (2017). A side-channel assisted cryptanalytic attack against QcBits. In International Conference on Cryptographic Hardware and Embedded Systems, pages 3–23. Springer.

Samardjiska, S., Santini, P., Persichetti, E., and Banegas, G. (2019). A reaction attack against cryptosystems based on LRPC codes. In International Conference on Cryptology and Information Security in Latin America, pages 197–216. Springer.

Sendrier, N. and Vasseur, V. (2020). About low DFR for QC-MDPC decoding. In PQCrypto 2020-Post-Quantum Cryptography 11th International Conference, volume 12100, pages 20–34. Springer.

Shamir, A. (1989). An efficient identification scheme based on permuted kernels. In Conference on the Theory and Application of Cryptology, pages 606–609. Springer.

Tillich, J.-P. (2018). The decoding failure probability of MDPC codes. In 2018 IEEE International Symposium on Information Theory (ISIT), pages 941–945. IEEE.

Vasseur, V. (2021). QC-MDPC codes DFR and the IND-CCA security of BIKE. Cryptology ePrint Archive, Report 2021/1458. [link].