Cache-Timing Vulnerabilities of NIST PQC Competitors

This post describes our researches on Cache-Timing security evaluation of NIST Post-Quantum competition submissions.The NIST Post-Quantum competition aims at evaluating new cryptographic implementations not only on their correctness and safety, but also on their security. On this aspect, Side-Channels are considered some of the most efficient ways of breaking even strong cryptographic standards. These attacks exploit unintentional non-functional albeit observable effects of the execution of a program, in order to gain knowledge about its internal state and recover sensitive information (e.g., the secret key) it processes. For software implementations such as the NIST competitors, Cache attacks are among the most threatening as they don’t require any specific sidechannel setup, can succeed key extraction with one measure only and target easily modern, high-frequency CPUs. We have developed dedicated vulnerability research tools to assess the robustness of competitors to Cache-Timing attacks and identify the weaknesses to correct in the code.

A. Cache-Timing Attacks

Cache-Timing vulnerabilities exploit the access time difference between the slow main memory, or RAM, and the much faster processor cache. Monitoring these cache access patterns during the execution of cryptographic code allows an attacker to efficiently recover the values of internal variables. If the code is not correctely protected, the secret key can potentially be recovered. Several techniques exploiting this same source of leakage have been discovered, such as PRIME+PROBE [1], or more recently, the more efficient FLUSH+RELOAD [2] attack. They allow the attacker to gain information about the value of variables used to index an array or to determine the truth value of conditional jumps. These techniques have been used to break popular implementations of RSA, AES, ECDSA (see https://eprint.iacr.org/2014/140.pdf) and more recently, the post-quantum signature scheme BLISS (see https://eprint.iacr.org/2016/300.pdf). A definitive way of making sure that no cache-timing attack can be applied to a given implementation is to make sure that there is no array access or conditional jump that depends on the algorithm’s sensitive data. Sensitive data might be the secret key of the cryptographic algorithm, but in many cases also the randomness used during encryption, decryption or signature.

B. Our Contribution

Our contribution to the physical security evaluation process is on three aspects:

  1. A static analysis of the competition implementations via an automatic source code analysis tool;
  2. A study of the most frequent leakage sources among competitors;
  3. Generic mitigation proposals.

C. Static Analysis Tool

We have built an analysis tool in order to automate the assessment of C source code implementations. The tool realizes a dependency analysis, followed by an in-depth study of all the code portions manipulating sensitive variables. After sensitive variables are tagged as such, the tool tracks them (and the variables depending on them) through the whole source code tree. When a variable depending on sensitive values is involved in a potential leakage pattern, a warning is emitted. We are thus able to determine which functions contain leaks, what sensitive variables are leaked, the dependency chain between variables, etc. This provides an efficient and automatic way of reporting potential vulnerabilities in the code and correct them.

Leakages types: As described, our tool is targeting potential leakage patterns which can lead to recovering information about sensitive variable values. We distinguish three types of leakage:

  • Secret dependent conditional instruction: This includes conditional branching as well as loops with variable iteration number. In both cases, some instructions will be executed (or not) depending on the sensitive variable value, allowing attacks based on timing and instruction counting;
  • Secret used as index in an array: this includes accesses to memory addresses depending on the sensitive variable value. This allows attacks based on tracking the addresses values;
  • Secret used by third-part libraries: this includes the call to unknown, potentially vulnerable libraries.

D. Methodology

The submissions to the NIST contest have mostly similar structures. In particular, they all need to implement a main function which creates and verifies Known Answer Tests (KATs). This function thus performs either a signature and verification, or an encryption and decryption, with randomly generated key pairs. Executing this function therefore provides a relatively good code coverage. For the tagged variables, we simply chose to taint the randomness sources (which are also required to respect some specific format), as these sources are used to generate the secret keys as well as the randomness used during signature or encryption, which is probably sensitive in most cases. An issue is that the public key would also be considered sensitive. We somewhat mitigate this issue by automatically declaring safe any variable called pk. Of course, a more individual analysis would be necessary if one wants to guarantee the constant time property of a given implementation or, on the contrary, build a side-channel attack. However, this first analysis allows us to gain first insights about the existing and probable future difficulties of implementing constant time post-quantum schemes.

ANALYSIS RESULTS – TEASER

We have realized the static analysis of all the submissions to the competition. For the sake of readibility, we present on the figure below the results for 39 representative submissions. Out of these 39 candidates, potential vulnerabilities were found in 35 of them. 9 candidates have more than 100 potential vulnerabilities reported and 3 have more than 1000 potential vulnerabilities reported. The vast majority of these submissions are not correctly protected against Cache attacks, due to recurrent programming mistakes in the portions of code handling sensitive data.

Fig_summary_17042018

 

The detailed reports provided by the tool allowed us to classify the vulnerabilities into several categories, which seem to occur frequently among the submissions:

  • Gaussian sampling leaks: similar to the issues reported with BLISS [3], implementing a side-channel leakage free Gaussian sampler is not trivial to achieve. Some proposals, such as Frodo, manage to avoid this issue by slightly modifying the distribution being sampled and implementing this sampling in a constant-time fashion.
  • Other sampling leaks: in general, when specific distributions need to be sampled, one has to take care to avoid conditional branches and array accesses that depend on the randomness source being used.
  • GMP library use: some submissions use GMP. This library does not implement operations in constant time (at least, according to the C code implementing the library, excluding potential assembly level optimizations), and thus functions defined by this library should not be used on sensitive data without further inspection of their assembly level implementation.
  • Operations in finite fields: several implementations need to handle operations in finite fields, notably multiplications. For small groups, this is often done via log/antilog tables, which might open these implementations to cache-attacks. Other ways to implement these operations must be considered.
  • Other: there were some potential leaks that we were not able to fit into one of the other categories. For instance, some submissions provide their own implementation of AES that use table accesses, or perform data-dependent branching for matrix operations such as Gaussian elimination.

A detailed study of these vulnerabilities, along with generic mitigation proposals, has been realized and is pending publication.

Authors: Sébastien CARRE, Adrien FACON, Sylvain GUILLEY, Matthieu LEC’HVIEN, Alexander SCHAUB.

REFERENCES

[1] Fangfei Liu, Yuval Yarom, Qian Ge, Gernot Heiser, and Ruby B Lee. Last-level cache side-channel attacks are practical. In 2015 IEEE Symposium on Security and Privacy , pages 605–622. IEEE, 2015.

[2] Yuval Yarom and Katrina Falkner. Flush+ reload: A high resolution, low noise, l3 cache side-channel attack. In USENIX Security Symposium, pages 719–732, 2014.

[3] Leon Groot Bruinderink, Andreas Hülsing, Tanja Lange, and Yuval Yarom. Flush, Gauss, and Reload — A Cache Attack on the BLISS Lattice-Based Signature Scheme. In Benedikt Gierlichs and Axel Y. Poschmann, editors, Cryptographic Hardware and Embedded Systems – CHES 2016 – 18th International Conference, Santa Barbara, CA, USA, August 17-19, 2016, Proceedings, volume 9813 of Lecture Notes in Computer Science, pages 323–345. Springer, 2016.