Paper 2019/292

Timing attacks on Error Correcting Codes in Post-Quantum Secure Schemes

Jan-Pieter D'Anvers and Marcel Tiepelt and Frederik Vercauteren and Ingrid Verbauwhede

Abstract

While error correcting codes (ECC) have the potential to significantly reduce the failure probability of post-quantum schemes, they add an extra ECC decoding step to the algorithm. As this additional computation handles secret information, it is susceptible to side-channel attacks. We show that if no precaution is taken, it is possible to use timing information to distinguish between ciphertexts that result in an error before decoding and ciphertexts that do not contain errors, due to the variable execution time of the ECC decoding algorithm. We demonstrate that this information can be used to break the IND-CCA security of post-quantum secure schemes by presenting an attack on both the Ring-LWE scheme LAC and the Mersenne prime scheme Ramstake. This attack recovers the full secret key using a limited number of timed decryption queries. The attack is implemented on the reference and the optimized implementations of both submissions. It is able to retrieve LAC's secret for all security levels in under 2 hours using less than $2^{21}$ decryption queries and Ramstake's secret in under 2 minutes using approximately $2400$ decryption queries. The attack generalizes to other schemes with ECC's in which side-channel information about the presence of errors is leaked during decoding.