Attacking B-SIDH Using Castryck-Decru's Key Recovery Attack on SIDH

Abstract

Fundamentet i nesten alle offentlige nøkkelkryptografier ligger i vanskeligheten til spesifikke matematiske problemer. Selv om det ikke eksisterer effektive løsninger for disse problemene på klassiske datamaskiner, presenterer kommende kvantemaskiner en betydelig trussel. Kvantemaskiner har potensiale til å løse disse vanskelige problemene, og truer sikkerheten til nåværende offentlige nøkkelkryptografi systemer. Som en konsekvens utforsker det kryptografiske miljøet aktivt etter alternative kryptografiske protokoller, som er avhengige av andre vanskelige matematiske problemer som er robuste mot både klassiske- og kvanteangrep. To slike systemer er isegoni baserte nøkkelutvekslinger, Supersingulær Isogeni Diffie-Hellman (SIDH) og den nært relaterte B-SIDH. Disse to er basert på vanskelige problemer fra teorien om elliptiske kurver og isogenier, som er rasjonelle avbildninger mellom elliptiske kurver.

Sommeren 2022 presenterte Castryck og Decru et nytt ødeleggende nøkkelgjenopprettingsangrep på SIDH, og brøt det på sekunder. Angrepet gjenoppretter Bob sin hemmelige nøkkel ved å beregne isogenier i en høyere dimensjon. I denne oppgaven undersøker vi i hvilken grad Castryck og Decru sitt angrep holder i tilfellet med B-SIDH og utforsker anvendelsen av angrepet. I tillegg endrer vi den praktiske implementasjonen av angrepet for å ta hensyn til Bob sin varierende torsjon og skaper en ny representasjon av Bob sin hemmelige nøkkel ved å bruke det kinesiske restteorem.

Våre funn indikerer at angrepet effektivt kan brukes på B-SIDH under visse omstendigheter. Spesielt når p + 1 eller p - 1 kan bli faktorisert til bare primpotenser av to. Når Alice sin grad ikke er en toerpotens, krever angrepet beregningen av (ℓ, ℓ)-isogenier for ℓ > 2, som forårsaker praktiske utfordringer. Angrepet sin effektivitet på B-SIDH er naturlig tregere på grunn av nødvendigheten av å beregne isogenier av høyere grad.

The foundation of our public-key cryptography schemes lies in the hardness of specific mathematical problems. Although no efficient solution for these problems exists for classical computers, the advent of quantum computing presents a significant threat. Quantum computers have the potential to solve these mathematical problems, threatening the security of our current public-key cryptography systems. As a consequence, the cryptographic community is actively exploring alternative cryptographic protocols, which rely on other hard mathematical problems robust against both classical and quantum attacks. Two such schemes are the isogeny-based key exchanges called Supersingular Isogeny Diffie-Hellman (SIDH) and the closely related B-SIDH. These two are based on hard problems from the theory of elliptic curves and isogenies, which are rational maps between elliptic curves.

In the summer of 2022 Castryck and Decru presented a new devastating key-recovery attack on SIDH, breaking it in seconds. The attack recovers Bob’s secret key by computing isogenies in a higher dimension. In this thesis, we examine to what extent Castryck and Decru’s attack holds in the case of B-SIDH and explore the applicability of the attack. Additionally, we modify the practical implementation of the attack to take into account Bob’s varying torsion and create a new representation of Bob’s secret key using the Chinese Remainder Theorem (CRT).

Our findings indicate that the attack can be effectively applied to B-SIDH under certain conditions, especially when p + 1 or p - 1 can be factored into only prime powers of two. When Alice’s degree is not a prime power of two, the attack requires computing (ℓ, ℓ)-isogenies for ℓ > 2, which poses practical challenges. The attack’s efficiency on B-SIDH is innately slower due to the necessity of computing isogenies higher degree.