Side-Channel Attack on Post-Quantum Key-Encapsulation Mechanism SABER using Belief Propagation

Description

Rising capabilities of quantum computers threaten today’s cryptographic landscape. Therefore, many new cryptosystems have been

proposed to be used in the future. From those, lattice-based schemes appear to be the most promising class of candidates.

In this thesis we discuss mathematical properties and security guarantees of lattice- based cryptosystems in general and SABER in

specific. SABER internally uses the Toom-Cook and Karatsuba algorithms within its multiplication routine. One of the multiplications

directly involves the long-term secret key and is thus the target of our single-trace side-channel attack.

We apply belief propagation, an inference algorithm for graphs, in order to exploit complex relations of intermediate variables within

a single measurement. As the resulting graph of the multiplication procedure would become impractically complex, we propose various

improvements to this method, too.

Nevertheless, we are not able to significantly reduce the security level of SABER, if the reference implementation was used. This is, because

compiler optimizations limit the possible leakage points of the secret key. However, we are able to reliably extract the long-term secret key,

if the order of the inputs to the multiplication (secret key and ciphertext) would have been changed.

Therefore, it is important to consider these results for all implementations of SABER, or other cryptosystems that use the Toom-Cook and

Karatsuba multiplication algorithms.