Post-Quantum 的 KEM,SIDH/SIKE 確認死亡

似乎是這幾天 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.


AWS KMS 與 AWS ACM 支援 post-quantum TLS ciphers

AWS 宣佈 AWS KMSAWS ACM 支援 post-quantum TLS ciphers:「AWS KMS and ACM now support the latest hybrid post-quantum TLS ciphers」。

全區支援 Kyber、BIKE 與 SIKE 這三個演算法:

The three PQC key encapsulation mechanisms (KEMs) offered are Kyber, BIKE, and SIKE. Hybrid post-quantum TLS combines a classical key agreement, such as ECDHE, with one of these KEMs. The result is that your TLS connections inherit the security properties of both the classical and post-quantum key exchanges.

Hybrid post-quantum TLS for AWS KMS and ACM is available in all public AWS Regions.

不過這是 NIST Post-Quantum Cryptography Standardization 裡 Round 3 裡面其中幾個演算法而已:

AWS Key Management Service (KMS) and AWS Certificate Manager (ACM) now support hybrid post-quantum key establishment for transport layer security (SSL/TLS) connections using the latest post-quantum ciphers from Round 3 of the NIST Post-Quantum Cryptography (PQC) selection process.

順便補一下隔壁棚 Cloudflare 的研究:「Making protocols post-quantum」。

Google 與 Cloudflare 測試 Post-Quantum 演算法的成果


其中 Google Chrome 的團隊與 Cloudflare 的團隊手上都有夠大的產品,兩個團隊合作測試的結果在學界與業界都還蠻重視的:「Real-world measurements of structured-lattices and supersingular isogenies in TLS」、「The TLS Post-Quantum Experiment」。

Google Chrome 這邊是使用了 Canary 與 Dev 兩個 channel,有控制組與兩個新的演算法:

Google Chrome installs, on Dev and Canary channels, and on all platforms except iOS, were randomly assigned to one of three groups: control (30%), CECPQ2 (30%), or CECPQ2b (30%). (A random ten percent of installs did not take part in the experiment so the numbers only add up to 90.)

這兩個演算法有優點也有缺點。一個是 key 比較小,但運算起來比較慢 (SIKE,CECPQ2b);另外一個是 key 比較大,但是運算比較快 (HRSS,CECPQ2):

For our experiment, we chose two algorithms: isogeny-based SIKE and lattice-based HRSS. The former has short key sizes (~330 bytes) but has a high computational cost; the latter has larger key sizes (~1100 bytes), but is a few orders of magnitude faster.

We enabled both CECPQ2 (HRSS + X25519) and CECPQ2b (SIKE/p434 + X25519) key-agreement algorithms on all TLS-terminating edge servers.