Breaking supersingular isogeny Diffie-Hellman (SIDH)

When a browser talks to a server over HTTPS, it needs to have a shared secret key with the server to encrypt its streams. Diffie-Hellman is a protocol that achieves that through a back-and-forth communication with no preexisting secret, but its security relies on the complexity of solving the discrete logarithm problem, which is hard on a classical computer, and thus safe; but is much more tractable on a quantum computer, and thus unsafe. Quantum computers that are big or reliable enough don’t exist, but nefarious people can store HTTPS streams on disk until they do, and decrypt them then, which will be a tremendous loss of confidentiality worldwide.

As a result, there is some urgency in getting browsers to use a new algorithm that survives quantum computers. NIST set up a competition: PQC. Various entries adopted different mathematical approaches. One of the entries, SIKE, which is an instance of SIDH, survived cryptanalysis and was a 4th round finalist.

However, this week, a paper was published, describing an algorithm that can recover the shared key from seeing the SIKE Diffie-Hellman exchange. It is not just theoretical: it was implemented and could break keys in less than a day. It is particularly shocking because we came near a situation where it could have been standardized or even implemented in browsers with devastating consequences once the attack was found. Furthermore, it puts into question the use of the whole mathematical approach used for SIKE.