Implementing the Castryck-Decru SIDH Key Recovery Attack in SageMath

Introduction

Last weekend (July 30th) a truly incredible piece of mathematical/cryptanalysis research was put onto eprint. Wouter Castryck and Thomas Decru of KU Leuven published a paper “An efficient key recovery attack on SIDH (preliminary version)” describing a new attack on the Supersingular Isogeny Diffie-Hellman (SIDH) protocol together with a corresponding proof-of-concept implementation.

SIDH is at the core of the Post-Quantum key encapsulation mechanism SIKE, which was expected to continue to round four of the NIST Post-Quantum Project for consideration of standardisation. The paper says that their proof of concept code can break the proposed NIST level 1 parameters (supposedly approximating security on-par with AES-128) in an hour of single core computation, and the strongest parameter set in less than 24 hours.

However, the proof of concept code published has been written using the computer algebra software system Magma. Magma is a very efficient and powerful piece of software, but it is difficult for people to obtain access to. This meant that despite being able to run the attack over a lunch break, most of the community was unable to verify the result at all.

Motivated by a beautiful attack and a love of open-source software, a plan was made to read the attack and implementation and then reimplement it in SageMath; a free, open-source mathematics software system. This was not only a great opportunity to learn exactly how the attack came together, but the effort should also then open up the research to the cryptographic community, who could verify

Read more

Explore the site

More from the blog

Latest News