Top

Designs, Codes and Cryptography

Published in:

29-04-2023

Exploiting ROLLO’s constant-time implementations with a single-trace analysis

Authors: Agathe Cheriere, Lina Mortajine, Tania Richmond, Nadia El Mrabet

Published in: Designs, Codes and Cryptography | Issue 3/2024

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

ROLLO, for Rank-Ouroboros, LAKE and LOCKER, was a candidate to the second round of the National Institute of Standards and Technology (NIST) Post-Quantum Cryptography (PQC) standardization process. In the lastest update in April 2020, there was a key-encapsulation mechanism (ROLLO-I) and a public-key encryption scheme (ROLLO-II). In this paper, we propose a side-channel attack to recover the syndrome during the decapsulation process of ROLLO-I. From this syndrome, we explain how to recover the private key. We target two constant-time implementations: the C reference implementation and a C implementation available on GitHub. By capturing power measurements during the execution of the Gaussian elimination function, we are able to extract from a single trace each element of the syndrome. This attack can also be applied to the decryption process of ROLLO-II. Finally, we give countermeasures based on masking and randomization to protect future implementations. We also provide their impact regarding the execution time.

previous article Interpolation-based decoding of folded variants of linearized and skew Reed–Solomon codes

next article Densities of codes of various linearity degrees in translation-invariant metric spaces

Available only for authorised users

Aguilar-Melchor C., Aragon N., Bardet M., et al.: ROLLO-Rank-Ouroboros, LAKE & LOCKER. https://pqc-rollo.org/ (2019).

Aguilar-Melchor C., Aragon N., Bellini E., et al.: Constant time algorithms for ROLLO-I-128. https://eprint.iacr.org/2020/1066.pdf, source code available at https://github.com/peacker/constant_time_rollo.git (2020).

Aragon N., Bidoux L.: rbc_library. https://rbc-lib.org/ (2020).

Aragon N., Gaborit P.: A key recovery attack against LRPC using decryption failures. In: International Workshop on Coding and Cryptography (WCC), Saint-Jacut-de-la-Mer, France (2019).

Bardet M., Briaud P., Bros M., et al.: An algebraic attack on rank metric code-based cryptosystems. In: Canteaut A., Ishai Y. (eds.) Advances in Cryptology - EUROCRYPT 2020, pp. 64–93. Springer, Cham (2020).CrossRef

Bardet M., Bros M., Cabarcas D., et al.: Improvements of algebraic attacks for solving the rank decoding and minrank problems. In: Moriai S., Wang H. (eds.) Advances in Cryptology - ASIACRYPT 2020, pp. 507–536. Springer, Cham (2020).CrossRef

Bernstein D.J., Chou T., Schwabe P.: McBits: Fast constant-time code-based cryptography. In: Bertoni G., Coron J.S. (eds.) Cryptographic Hardware and Embedded Systems (CHES), pp. 250–272. Springer, Berlin (2013).

Cayrel PL., Colombier B., Drgoi VF., et al.: Message-recovery laser fault injection attack on the classic mceliece cryptosystem. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer, pp 438–467 (2021).

Gaborit P., Murat G., Ruatta O., et al.: Low Rank Parity Check codes and their application to cryptography. In: Budaghyan L, Helleseth T, Parker MG (eds.) International Workshop on Coding and Cryptography (WCC), Bergen, Norway, https://hal.archives-ouvertes.fr/hal-00913719, iSBN 978-82-308-2269-2 (2013).

10.

Hoffstein J., Pipher J., Silverman J.H.: NTRU: A ring-based public key cryptosystem. In: Proceedings of the Third International Symposium on Algorithmic Number Theory, pp. 267–288 (1998).

11.

Johnson D., Menezes A., Vanstone S.: The Elliptic Curve Digital Signature Algorithm (ECDSA). Int. J. Inf. Secur. 1(1), 36–63 (2001). https://doi.org/10.1007/s102070100002.CrossRef

12.

Kocher P.C.: Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In: Koblitz N. (ed.) Advances in Cryptology - CRYPTO, pp. 104–113. Springer, Berlin (1996).CrossRef

13.

Lahr N., Niederhagen R., Petri R., et al.: Side channel information set decoding using iterative chunking. In: Moriai S., Wang H. (eds.) Advances in Cryptology - ASIACRYPT 2020, pp. 881–910. Springer, Cham (2020).CrossRef

14.

McEliece R.J.: A public-key cryptosystem based on algebraic coding theory. Tech. Rep. 44, California Inst. Technol., Pasadena, CA (1978).

15.

Melchor C.A., Aragon N., Bettaieb S., et al.: Rank Quasi-Cyclic (RQC). https://pqc-rqc.org/ (2020).

16.

Moody D., Alagic G., Apon D.C., et al.: Status report on the second round of the NIST post-quantum cryptography standardization process. Tech. rep. (2020). https://doi.org/10.6028/nist.ir.8309.CrossRef

17.

Rivest R.L., Shamir A., Adleman L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978).MathSciNetCrossRef

18.

Samardjiska S., Santini P., Persichetti E., et al.: A reaction attack against cryptosystems based on LRPC codes. In: Progress in Cryptology – LATINCRYPT. Springer, pp. 197–216, https://doi.org/10.1007/978-3-030-30530-7_10 (2019).

19.

Shor P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997).MathSciNetCrossRef

20.

Strenzke F., Tews E., Molter HG., et al.: Side channels in the McEliece PKC. In: International Workshop on Post-Quantum Cryptography, Springer, pp. 216–229 (2008).

Title: Exploiting ROLLO’s constant-time implementations with a single-trace analysis
Authors: Agathe Cheriere
Lina Mortajine
Tania Richmond
Nadia El Mrabet
Publication date: 29-04-2023
Publisher: Springer US
Published in: Designs, Codes and Cryptography / Issue 3/2024
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-023-01227-3

Springer Professional

Exploiting ROLLO’s constant-time implementations with a single-trace analysis

Abstract

Premium Partner

Springer Professional

Abstract

Please log in to get access to your license.

Other articles of this Issue 3/2024

Classification of extremal type II -codes of length 24

Constructing irreducible polynomials recursively with a reverse composition method

On subfield subcodes obtained from restricted evaluation codes

Interpolation-based decoding of folded variants of linearized and skew Reed–Solomon codes

Densities of codes of various linearity degrees in translation-invariant metric spaces

On the (in)security of optimized Stern-like signature schemes

Premium Partner