Tag: nsa

似乎是這幾天 cryptography 領域裡面頗熱鬧的消息，SIDH 以及 SIKE 確認有嚴重的問題：「SIKE Broken」，論文在「An efficient key recovery attack on SIDH (preliminary version)」這邊可以取得。

這次的成果是 Key recovery attack，算是最暴力的幹法，直接把 key 解出來。

另外 SIKE 剛好也是先前 Cloudflare 在解釋 Hertzbleed 時被拿來打的目標：「Cloudflare 上的 Hertzbleed 解釋」，這樣看起來連 patch 也都不用繼續研究了...

論文裡面的攻擊對象中，第一個是 Microsoft 在 $IKE challenges 內所定義的 $IKEp182 與 $IKEp217，在只用 single core 的情況下，分別在四分鐘與六分鐘就解出來：

Ran on a single core, the appended Magma code breaks the Microsoft SIKE challenges $IKEp182 and $IKEp217 in about 4 minutes and 6 minutes, respectively.

接著是四個參與 NIST 標準選拔的參數，分別是 SIKEp434、SIKEp503、SIKEp610 以及 SIKEp751，也都被極短的時間解出來：

A run on the SIKEp434 parameters, previously believed to meet NIST’s quantum security level 1, took about 62 minutes, again on a single core.

We also ran the code on random instances of SIKEp503 (level 2), SIKEp610 (level 3) and SIKEp751 (level 5), which took about 2h19m, 8h15m and 20h37m, respectively.

在 Ars Technica 的採訪「Post-quantum encryption contender is taken out by single-core PC and 1 hour」裡面，有問到 SIKE 的共同發明人 David Jao 的看法，他主要是認為密碼學界的人對於數學界的「武器」了解程度不夠而導致這次的情況：

It's true that the attack uses mathematics which was published in the 1990s and 2000s. In a sense, the attack doesn't require new mathematics; it could have been noticed at any time. One unexpected facet of the attack is that it uses genus 2 curves to attack elliptic curves (which are genus 1 curves). A connection between the two types of curves is quite unexpected. To give an example illustrating what I mean, for decades people have been trying to attack regular elliptic curve cryptography, including some who have tried using approaches based on genus 2 curves. None of these attempts has succeeded. So for this attempt to succeed in the realm of isogenies is an unexpected development.

In general there is a lot of deep mathematics which has been published in the mathematical literature but which is not well understood by cryptographers. I lump myself into the category of those many researchers who work in cryptography but do not understand as much mathematics as we really should. So sometimes all it takes is someone who recognizes the applicability of existing theoretical math to these new cryptosystems. That is what happened here.

這樣第四輪的選拔只剩下三個了...