Cryptology ePrint Archive: Report 2021/858

Full key recovery side-channel attack against ephemeral SIKE on the Cortex-M4

Aymeric GenÍt and Natacha Linard de Guertechin and Novak Kaluđerović

Abstract: This paper describes the first practical single-trace side-channel power analysis of SIKE. While SIKE is a post-quantum key exchange, the scheme still relies on a secret elliptic curve scalar multiplication which involves a loop of a double-and-add procedure, of which each iteration depends on a single bit of the private key. The attack therefore exploits the nature of elliptic curve point addition formulas which require the same function to be executed multiple times. We show how a single trace of a loop iteration can be segmented into several power traces on which 32-bit words can be hypothesised based on the value of a single private key bit. This segmentation enables a classical correlation power analysis in an extend-and-prune approach. Further error-correction techniques based on depth-search are suggested. The attack is explicitly geared towards and experimentally verified on an STM32F3 featuring a Cortex-M4 microcontroller which runs the SIKEp434 implementation adapted to 32-bit ARM that is part of the official implementations of SIKE. We obtained a resounding 100% success rate recovering the full private key in each experiment. We argue that our attack defeats many countermeasures which were suggested in a previous power analysis of SIKE, and finally show that the well-known countermeasure of projective coordinate randomisation stops the attack with a negligible overhead.

Category / Keywords: implementation / sike, side-channel analysis, correlation power analysis, single-trace attack, post-quantum key exchange, isogeny-based cryptography

Original Publication (in the same form): COSADE 2021

Date: received 23 Jun 2021

Contact author: aymeric genet at alumni epfl ch

Available format(s): PDF | BibTeX Citation

Version: 20210624:145316 (All versions of this report)

Short URL: ia.cr/2021/858


[ Cryptology ePrint archive ]