Recent Updates in PQC and Why We Should Learn to Love Cryptanalysis

Since the NIST PQC standardization effort began in 2017, there have been numerous attacks on the potential cryptography standards. Amongst the 82 initial submissions, 69 were accepted by NIST for being ‘complete and proper’. Of the schemes that were not accepted to Round 1, some were withdrawn by the authors, and some were attacked quite devastatingly; for example, the ciphertext in one encryption scheme candidate could be decoded without knowing the secret key! NIST’s iterative reduction (visit our blog post for details about NIST’s latest selection of algorithms) of remaining schemes, as the rounds progressed, has allowed cryptographers to focus their cryptanalysis on a more concentrated group of algorithms.

This year, some of the most notable and groundbreaking attacks were made public. One attack was against Rainbow– a Round 3 finalist candidate, one against SIKE– a Round 4 alternate candidate, and one against SPHINCS+ – a signature scheme selected for standardization. In this post we delve a bit more into the main takeaways of these cryptanalysis results.

Over (for) The Rainbow

Rainbow is a digital signature scheme which was selected by NIST as a finalist in the Third Round. This means the signature scheme was a favored candidate by NIST; indeed the other two finalists –CRYSTALS-Dilithium and FALCON– were both selected as standards in July 2022. In an elegant and amazingly fast attack, Ward Beullens – a researcher at IBM Research Zurich - was able to break the NIST Level 1 (128-bit secure) parameters of Rainbow in a weekend (53 hours) on a laptop. The impact on real-world implementations is fortunately fairly minimal, with the few use cases to date being an implementation of PQ-WireGuard and a cryptocurrency.

The attack is an improvement on earlier work by Beullens and exploits the mathematical relationships of a certain structure that had been added in Rainbow for efficiency reasons, compared to the simpler Oil and Vinegar (OV) signature scheme that Rainbow is based on. In a nutshell, Rainbow is a 2-layer OV scheme and the attack removes one of the layers, transforming it into an insecure instance of the OV scheme. Given the attack, it might be more efficient to directly use (a secure instance of) the OV scheme (given that it is unaffected by the attack). Therefore, we may see a version of this submitted to NIST’s new standardization effort for further digital signature schemes in 2023. As a result of these attacks, NIST did not select Rainbow to proceed in their standardization effort in July 2022.

Unlike most cryptographic schemes submitted to NIST’s PQC standardization, Rainbow did not have a formal security proof. These are important components to any primitive as it helps the community understand its security strengths and weaknesses, and make it more likely to identify potential attacks.

No Longer SIKEed Up

SIKE is a key encapsulation mechanism which was selected by NIST as an alternate candidate in the Third Round. SIKE remained a potential standard, i.e., it had been selected as a 4th Round candidate, due to its small key and ciphertext sizes, but it suffers from significantly slow runtime performances. The attack by Castryck and Decru (KU Leuven) targets the hardness problem underlying SIKE, namely the Supersingular Isogeny Diffie-Hellman (SIDH) problem. The attack recovers SIKE’s NIST Level 1 parameters (SIKEp434 for 128 bits) in one hour or less using a single CPU core. The remaining parameters for Level 2 (SIKEp503), Level 3 (SIKEp610), and Level 5 (SIKEp751) took 2h19m, 8h15m, and 20h37m, respectively. The attack seems to be sufficient to claim an award launched by Microsoft called the SIKE Cryptographic Challenge which rewards the recipient(s) with $50,000 USD! The implementation of the attack was later improved by Giacomo Pope (NCC Group), who reduced the runtimes of the attack against Level 1 and Level 5 parameters to 22 seconds and 1 hour, respectively.

The hardness of SIDH is based on pseudo-random walks in a (supersingular isogeny) graph, as shown in the diagram below. Alice and Bob start off at the same place (the same curve, $E_0$), but then they randomly walk away, creating two points (curves $E_A$ and $E_B$). Alice and Bob then share this information, so they can both arrive at the same place, i.e., a shared secret key.

The core idea of the attack is to apply the “Reducibility Criterion” theorem (or so-called Glue-and-Split Theorem) developed by Ernst Kani in 1997. The SIDH graph shown in the diagram is similar to what Kani refers to as a “isogeny diamond configuration”.

The attack targets the (auxiliary) points given in SIDH and relies on ‘gluing together’ multiple elliptic curves which emerge in the SIDH construction (giving an abelian surface) and computing a specially crafted random walk (an isogeny) defined by these aforementioned (auxiliary) points on that higher-dimensional object.

Besides having been considered in some benchmarking evaluations by AWS, Google, and Cloudflare, SIKE fortunately has only been used in hybrid mode. Hybrid mode means combining two (or more) schemes of the same kind (e.g., signatures of a signature scheme or the shared keys of KEMs) such that an attacker needs to break all ingredient schemes in order to break the hybrid scheme. As examples, Microsoft’s implementation of OpenVPN as well as AWS’ Key Management Service and Certificate Manager offer to use SIKE in hybrid mode alongside elliptic-curve cryptography (ECC) equivalents. As such, the above-mentioned implementations are not vulnerable as of today, showing the benefit of hybrid modes as also discussed below.

The Broken Nose of SPHINCS+

SPHINCS+ is a digital signature scheme, first selected by NIST as an alternate candidate in Round 3 and, finally, in July 2022, selected as one of four PQC standards, alongside signature schemes CRYSTALS-Dilithium and Falcon, and key encapsulation mechanism scheme CRYSTALS-Kyber.

While the first two attacks we’ve already discussed are so devastating that they effectively rule out Rainbow and SIKE ever becoming standardized, the recent attack on SPHINCS+ has nowhere near this impact. Three researchers at NIST, namely, Perlner, Kelsey, and Cooper (based on an observation of Sydney Antonov), were able to reduce the security of some SPHINCS+ instantiations which used the hash function SHA-256 in its constructions. The forgery attack exploits that SHA-256 does not achieve collision resistance for many different target values at the same time. This property, however, is required for the security of SPHINCS+. As such, the attack does not exploit a weakness in the signature scheme but uncovers an insecure instantiation which uses SHA-256. As a result, the SPHINCS+ team removed the use of SHA-256, switching to SHA-512 instead, which comes with the needed property.

Takeaways

The four candidates selected by NIST as PQC standards will not be available until 2023-2024. This is because NIST will need to formally write these four schemes as standards, which implementations will need to conform to, as well as deciding on parameters for each scheme. Moreover, we may (and are quite likely to) see more attacks on PQC schemes, which could have impacts ranging from small-to-moderate changes in parameters (like the attack against SPHINCS+) to a complete break in the scheme (like the attacks against Rainbow and SIKE).

As a result, the current safest way to experiment or integrate PQC is using the hybrid approach. For example, in the case of Microsoft’s above-mentioned OpenVPN implementation, to break the security of the hybrid implementation, an attacker needs to break both SIKE and ECC. Thus, any major cryptanalytic results will not hinder the overall security since we also rely on ECC. We should not be surprised or frightened by these attacks, either; these works are an essential part of the global effort to standardize PQC, and cryptographic schemes in general, and we will still require much more cryptanalytic efforts on all PQC schemes in the future.

These results show that the NIST PQC standardization process is working well; we are finding new significant advancements in the cryptanalysis of PQC faster and more often due to NIST’s effort. Clearly, we do not recommend using Rainbow. Likewise, we also do not currently recommend using SIKE or SIDH-based cryptography, as there it is unknown whether sound mitigations against the attack are possible. SPHINCS+ was selected by NIST as a standard and with the correct configuration and parameters, it will be fine to use for PQC-secure signatures. Finally, these results show that it’s key to embrace cryptographic agility as a core pillar for any solution requiring security and privacy guarantees, with the aim of being able to swap algorithms as seamlessly as possible as new cryptanalytics results are made public.