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

International audienceROLLO, 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