Secure Implementation Of Post-Quantum Crypto In The Spotlight

The US-based NIST body takes a leading role in the migration to Post-Quantum Crypto (PQC). After a multi-year selection process, in 2022 they preliminarily identified a number of Post Quantum algorithms, which were recommended to replace the current public key algorithms (RSA, ECC). While the process of scrutiny is still ongoing, they now took another important step by putting emphasis on implementation security. Although the design of new algorithms comes first, this only makes sense if they can be securely implemented.

With implementation security we focus on two classes of Sensitive Security Parameters: Public Security Parameters, data that needs integrity (can’t be modified), and Critical Security Parameters, which is data that also needs confidentiality (secrecy). In the protection of Sensitive Security Parameters we focus on the prevention of leakage of the Critical Security Parameters through Side Channel Analysis, and the robustness of all Sensitive Security Parameters against Fault Injection.

NIST hosted the first session about Side Channel Analysis (SCA) of PQC implementations on April 4. The second session on Fault Injection is planned for May 5. The SCA session was given by Professor Saarinen, who is also cryptography architect at PQShield, a pioneer in PQC implementation. Here’s our review of the session focused on Side Channel Analysis.

The speaker recognized that protection against SCA is more challenging for PQC than for legacy crypto. Secure implementation requires the design of dozens of new ‘gadgets,’ which are implementations of cryptographic functionality that have built-in SCA protection. But, even before that, developers should consider time-constant program code. This is needed to prevent breaches when secret information can be derived by looking at the execution time of a process. However, it is a common misunderstanding that all crypto code needs to be time-constant. This requirement only applies to the handling of Critical Security Parameters. For instance, several PQC algorithms include a mechanism that is called ‘Rejection Sampling,’ which repeats an algorithm step until its results satisfy specific criteria. As long as these results cannot be traced back to key material, it is argued that this is not a problem.

Although leakage can ultimately lead to key retrieval, it is commonly acknowledged that security testing does not necessarily have to prove that keys can be extracted. One can even argue that by focusing on leakage it may only be possible to prevent future attacks that would exploit such leakage. The ISO 17825 standard provides a test procedure that evaluates leakage and includes a threshold for acceptable leakage levels.

It is very helpful that NIST stresses the importance of security implementation testing. As one of the few security labs that understand implementation security for PQC, Riscure is keen to help developers who seek assurance for their products. We look forward to the next presentation on the topic of Fault Injection.