Secure and Efficient Post-Quantum Cryptography in Hardware and Software

We will soon be witnessing wide-scale adoption of lattice-based schemes on embedded devices, and these devices have to be evaluated based on different security certification standards such as FIPS 140-3 [2], Common Criteria [3]. In order to perform side-channel leakage evaluation of PQC schemes, we are not aware of the concrete set of tests that need to be done to certify a given PQC hardware or software against side-channel analysis. Thus, it can be an interesting research direction from the point of view of security certification of PQC HW and SW implementations.

Some of the specific open-problems that we considered during our discussions are as follows:

1. 1.

   What are the exhaustive set of tests required to test side-channel leakage from all the operations within the decapsulation procedure of IND-CCA secure Key Encapsulation Mechanisms (KEMs). The first challenge towards devising an exhaustive set is the fact that the decapsulation procedure contains three different operations (i.e.) decryption, re-encryption and ciphertext comparison. Thus, it is necessary to device separate tests to test for leakage from each of these three operations separately. While it does not appear to be extremely difficult to arrive at such exhaustive tests for individual post-quantum KEMs, it needs to be analyzed whether they make up the exhaustive set of tests that are sufficient to prove existence of leakage or otherwise.

2. 2.

   While leakage evaluation tests can help us detect or test for leakage of sensitive variables, it does not necessarily indicate the possibility to perform key recovery. Thus, it is also interesting to ponder upon development of novel techniques that can map available leakage to the most efficient key recovery attack. We are probably not looking at automatic discovery of new attacks based on existing vulnerabilities, but probably estimate the effort required to mount known attacks provided the calculated leakage. This could be particularly interesting for the case of single trace attacks [4, 5], where we can ask the question what is the minimum amount of leakage required to mount a given single trace attack, without explicitly performing the attack itself.

3. 3.

   Can we develop techniques that can ascertain if certain types of PQC schemes are more difficult to attack through SCA/FIA compared to others? This is for instance, a pertinent question that came up during the NIST PQC process, where NIST was particularly interested in factors that differentiated the different lattice-based schemes in the context of side-channel analysis, given that there were several lattice-based schemes in the NIST PQC standardization process. Development of such analysis techniques can potentially enable us to build leakage resilient schemes that are inherently resistant to SCA [6, 8, 7].

1. 1.

   Masking countermeasures for PQC schemes typically involve a large amount of randomness, especially because they involve computation over large polynomials, matrices or vectors spanning dimensions of the order of a few hundred to few thousand. Obtaining access to a large amount of high quality randomness typically required for masking schemes is particularly challenging, especially when considering constrained embedded devices, which are especially required to be protected against side-channel attacks. These challenges for masking countermeasures gives rise to the following questions.

   1. (a)

      What is the effect of reusing randomness in masking schemes, tailor made for specific PQC schemes to reduce the true performance overhead of masking countermeasures? This will reduce the randomness requirement, thereby reducing the true performance overhead of masking countermeasures.

   2. (b)

      What is the impact of using randomness of bad quality in masked implementations of PQC schemes?

2. 2.

   Masking countermeasures are usually considered to be very expensive, as they have shown to incur a significant overhead in runtime in several prior works [9, 10, 11]. We also observe that PQC schemes involve computation over large polynomials, matrices or vectors spanning dimensions of the order of a few hundred to few thousand. Thus, it is interesting to contemplate use of shuffling countermeasures, exploiting the large dimensions of elements used in PQC based schemes. This is particularly relevant in scenarios where that an attacker is in a restricted setting, limiting him/her with access to “N” traces for a given secret key. In such scenarios, whether shuffling alone is sufficient to provide provable security?

3. 3.

   Code-based schemes are currently in the spotlight as we expect a code-based scheme to be standardized in the fourth round. Interestingly, there are no systematic measures for SCA protection of these schemes. The decoding algorithms are notoriously difficult to even do in constant time, and the question is whether we can use masking techniques in the decoding algorithms – for instance Reed Muller, Reed Solomon Decoder in HQC, Berlekamp-Massey in Classic McEliece.

1. 1.

   Existing side-channel attacks on lattice-based cryptographic schemes either require the knowledge of inputs/outputs, or require to control the inputs to the DUT [12]. However, it is possible in certain scenarios that the attacker does not directly obtain access to the I/O of the DUT. In such a setting, the attacker only has access to the side-channel traces, and it begets the question if an attacker can still perform key recovery without knowledge of the DUT’s inputs/outputs. It is also interesting to explore for which post-quantum schemes this scenario leads to meaningful, exploitable leakage.

2. 2.

   Several prior works have shown that an attacker can craft malicious inputs to the decapsulation procedure of KEMs to amplify the side-channel leakage of the secret key for efficient key recovery attacks. One of the main downsides of these attacks is that the malformed ciphertexts used for the attack, can be detected with a very high probability. Such chosen-ciphertext attacks using malformed ciphertexts have also been used to target other PQC schemes as well [1]. This makes it natural for a designer to implement a simple protection: refresh the secret key every time he/she observes a decapsulation failure, since decapsulation failures for valid ciphertexts occur with negligible probability. This raises a natural question on whether "it is possible to perform chosen-ciphertext attacks on lattice-based schemes with valid ciphertexts?". This represents a more stealthy approach towards chosen-ciphertext attacks, as valid ciphertexts cannot be detected as malicious by the decapsulation procedure, as they do not trigger decapsulation failures.