The breaking state of the week

Let’s talk briefly about some attacks to post-quantum cryptography that were just announced:

Breaking FrodoKEM

The paper “When Frodo Flips: End-to-End Key Recovery on FrodoKEM via Rowhammer” by Michael Fahr Jr. et al. uses the Row hammer security exploit to recover the private key material of the FrodoKEM scheme (it also uses decryption failure attacks). Row hammer allows flipping bits in DRAM by “hammering” rows of memory adjacent to some targeted memory location by repeated memory accesses. They use it in the attack by producing a “poisoned” key.

While the paper uses FrodoKEM as an example, the attack can be theoretically executed in other lattice-based KEMs (with more likelihood to Kyber or Saber, and with more difficulty to NTRU).

Breaking Supersingular Isogeny Diffie–Hellman (SIDH) protocol

The paper by Wouter Castryck and Thomas Decru presents a powerful key recovery attack on SIDH, and its instantiation SIKE. It is based on the “glue-and-split” theorem (Thm 2.6) from 1997 from Ernst Kani and very much outperforms previous attack strategies. It can be used to both recover Bob’s or Alice’s private key.

The attack allows for the recovery of a secret cyclic \(3^{b}\)-isogeny \(\phi : E_0 \rightarrow E\). Note that it assumes an initial input of \(\beta = 0\) and \(E_0 = E_{start}\), where the \(3^{\beta}\)-isogeny \(\tau : E_0 \rightarrow E_{start}\) for some \(\beta \geq 0\). \(E_{start} : y^{2} = x^{3} + x\) or \(E_{start} : y^{2} = x^{3} + 6x^{2} + x\), is one of the two commonly chosen base curves in SIDH/SIKE, with respective j-invariants 1728 and 287496.

Following the work by Kohel–Lauter–Petit–Tignol and the work of Love–Boneh, all known ways to generate a supersingular base curve \(E_0/F_{p^{2}}\) in a trustless manner reveal an isogeny of the previous form (the \(3^{\beta}\) isogeny). In this case, the attack is very powerful as the secret isogeny will be revealed. But even when this is not the case (when using, for example, a trusted set-up or a base curve generated by Alice), the glue-and-split method still lowers security.

In order to make the attack, an “auxiliary” cyclic \(c\)-isogeny \(\gamma: E_0 \rightarrow C\) to some codomain curve \(C\) (assuming \(c = 2a − 3b\)) is needed, with the idea of (efficiently) computing the image points \(P_c\) and \(Q_c\) under it. This is not trivial and for it is needed a factorization of an integer of size \(O(2^{a})\). Here is also needed the “special” nature of \(E_{start}\) which comes with an endomorphism \(2i\) satisfying \((2i)^{2} = −4\) (the previous stated options come with this). What essentially eventually is done is that the intermediate curves are found and with it the private key digit by digit: elliptic curves are “glued” into a Jacobian followed by \(a − \alpha1 − 2\) Richelot isogenies between Jacobians of genus-2 curves (where we also check if the last step “splits”).

What I truly love about the paper is that this works even for base curves without a known path to \(E_{start}\). If \(c = 2a − 3b\) is smooth, then it remains possible to construct the auxiliary isogeny \(\gamma\). Note that the likeliness of finding a smooth c is very small, so this doesn’t seem to lead to a practical attack, but it might lower the security level of some parameter sets.

But, does this mean that all is lost in isogeny-land? Not really. It does not affect CSIDH or SQISign. There could also be ways to counter the attack but I’ll defer until the authors publish the full paper.

For a nicer explanation, read the blog post of Galbraith or the thread of Péter Kutas.

Why are these attacks important?

Attacking cryptographic protocols is important in order to properly assess their security as, when deployed in real-world situations, they lower or enhance the security of users. What these two attacks have shown us is that the post-quantum field is still young: there are still classical and quantum attack avenues to explore, and still lots of implementation attacks that could be found. Migrating to post-quantum cryptography should not be treated lightly. We still don’t have complete data if the post-quantum schemes will work for every situation that the Internet is used for, and lots of time still needs to pass until we can call the field mature.

Congratulations to the authors of these attacks! Finding attacks to schemes makes different fields more mature.