Side-Channel Attacks On Post-Quantum Cryptography

By Mike Hamburg and Bart Stevens

Device security requires designers to secure their algorithms, not only against direct attacks on the input and output, but also against side-channel attacks. This requirement is especially notable for cryptographic algorithms, since they have a regular, well-understood structure, and the secrets they process often give access to much more information.

Side-channel attacks (SCA) are a category of attacks that ignore the mathematic properties of a cryptographic system and instead focus on its physical implementation in hardware. Put simply, side-channel attacks monitor power consumption and electromagnetic emissions while a device is performing cryptographic operations. Previous blogs on SCA can be found here and here.

Side-channel attacks have been studied for decades in the context of classical ciphers such as RSA, AES and elliptic-curve cryptography, but its application to post-quantum cryptography is a new and evolving field.

The simplest form of side-channel attack recovers information by observing timing, power or electromagnetic channels while a private key, secret nonce, secret message or secret intermediate value is being processed. In the worst case, this information might be enough to immediately recover either the private key or the message. More often, the attacker needs to observe many operations and combine side-channel information from all of them to recover the secrets. Classical attacks on RSA, ECDSA and EdDSA often combine the information using lattice reduction techniques. Since many post-quantum algorithms are built directly on lattice problems, lattice techniques are also used against those algorithms: see for example here and here.

Side-channel information can also be accumulated, either across a single observation or across many observations, using a technique called belief propagation. Belief propagation is used for soft-decoding algorithms for error-correcting codes, meaning algorithms which receive noisy observations (such as the signals received by a cellular modem) and attempt to reconcile those observations with known constraints (such as an error-correcting code). Belief propagation is also very useful in side-channel attacks on post-quantum cryptography. This is perhaps unsurprising for attacks against systems based on error-correcting codes such as HQC: see here. But observations of the Number Theoretic Transform used in algorithms such as Kyber and Dilithium follow a structure similar to a low-density parity check (LDPC) error-correcting code, and belief propagation is useful there as well: see here, here, here, here, etc.

Defending against side-channel attacks is tricky. Even in the relatively simple case of software timing attacks, post-quantum cryptography presents new challenges because some values, such as the challenge in ML-DSA, are derived from the private key and/or private nonce but are not themselves secret. Software often contains timing vulnerabilities, even when written by experts: see e.g. here. Even when software is written with source-level countermeasures against side-channel attacks, compiler optimizations or microarchitectural effects can remove that protection. So, robust testing and build tooling is required to make sure that a small change doesn’t introduce vulnerabilities.

The Fujisaki-Okamoto-style (FO) transforms used in ML-KEM and HQC are especially vulnerable to chosen-ciphertext side-channel attacks. This transform re-encrypts the decrypted message and checks whether the re-encryption matches the ciphertext, that is, whether the message was encrypted honestly. This prevents a family of chosen-ciphertext attacks which cleverly corrupt ciphertexts, testing the boundaries where decryption begins to fail. The re-encryption step is especially vulnerable to side-channel attack: an attacker needs only to distinguish re-encryption of a fixed value from a random one in this step. While fixed-vs-random tests are often used as a benchmark for countermeasure effectiveness, a real attack usually needs to go far beyond fixed-vs-random, but against the FO transform breaking fixed-vs-random is enough. A further weakness is that the attacker can stimulate re-encryption with messages of their choice, usually without any invasive access to the device. This makes profiled attacks much easier. The FO transform is also vulnerable to fault attacks: see e.g. here and here.

In some applications, devices can use a simple countermeasure to attacks on the FO transform: simply change the key after a set number of decryption failures have occurred. Since most attacks on the FO transform require many decryption failures, this is an effective mitigation. However, it is still possible to mount other chosen-ciphertext side-channel attacks, where only valid ciphertexts are used, such as described here.

Fault attacks are especially powerful against signature schemes. This is especially well-known for deterministic signatures, where a fault can cause two different signatures to be produced for the same message and nonce, or for signatures that share part of a nonce or other intermediate, as in here. Similar attacks apply to a deterministic variant of Falcon: see here. Deterministic Falcon may be especially difficult to secure, with variations in floating-point implementations functioning in the same way as a fault attack, which is why NIST is likely to mandate randomized signing. Correction attacks are also a risk, in which a fault attack causes the device to produce an incorrect signature, and the attack examines the degree to which it is incorrect, or the changes required to correct it: see for example here and here.

In conclusion, implementing robust countermeasures against side-channel attacks in post-quantum (quantum-safe) cryptographic hardware and software is not only as critical as it is for classical public key cryptography, it is arguably even more essential. Post-quantum cryptographic algorithms are inherently more complex and significantly newer, with implementation practices that are still maturing. This combination of novelty and complexity increases their exposure to side-channel vulnerabilities.

At Rambus, we’ve long been at the forefront of delivering high-assurance, side-channel-resistant solutions for classical cryptographic accelerators. Building on that foundation, we continue to apply our expertise to our quantum-safe accelerator cores, ensuring they are hardened against side-channel threats from the ground up. Rambus offers SCA resistant quantum safe algorithm acceleration both as a standalone Quantum Safe Engine as well as embedded on our SCA resistant Root-of-Trust cores.

Links:

• Rambus CryptoManager Root of Trust with Quantum Safe Protections
• Rambus Quantum Safe Engine

Bart Stevens is senior director of product management for cryptography at Rambus.