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.

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

Small Characteristic DLP (Discrete Log Problem) 被解決

最近幾天在密碼學領域還蠻紅的話題 (雖然預印本在去年就發了),EUROCRYPT 2014 上發表對 DLP (Discrete Log Problem) 的重大進展。

論文在 arXiv 上可以取得:「A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic」。

針對使用小特徵值的有限域 (finite field) 的 DLP 問題 (也就是 Zqk 上) 直接從 sub-exponential 降到 nO(logn) (quasi-polynomial)。最常見到的應該是 Z2n

雖然現有被廣泛使用的密碼系統在使用 DLP 建構時都是用 Zp,但這次的成果絕對寫下了 DLP cryptoanalysis 上的里程碑...

對稱式加密系統的爆炸歷史 (Authenticated encryption 的問題)

在「Disasters」這邊列了不少對稱式加密系統 (secret-key cryptography) 爆炸的歷史,其中提到了很多 Encrypt 與 MAC 結合時的問題 (Authenticated encryption)。另外 Colin Percival 在 2009 年的時候有寫了一篇為什麼要用 Encrypt-then-MAC 的文章:「Encrypt-then-MAC」,當時 Colin Percival 寫的時候大家還是不能理解,但現在回頭看上面的爆炸歷史應該就清楚很多了 XDDD

SSH 協定是使用 Encrypt-and-MAC (傳輸「密文」與「明文的 MAC 值」)。在 2008 年時 SSH 使用 CBC 模式時會有安全問題:對 128bits CBC mode system (像是 aes128-cbc),任意位置的 32bits 有 2-18 的機會可以解出原文。(CVE-2008-5161,論文是「Plaintext Recovery Attacks Against SSH」)

TLS 1.0 (SSLv3) 使用 MAC-then-Encrypt (傳輸「明文與明文的 MAC 值」加密後的結果)。1999 年就知道這個方法不可靠,不過到了 2011 年時才被拿出來示範,也就是 BEAST attack。(CVE-2011-3389,在 ekoparty Security Conference 上的「表演」:「BEAST: Surprising crypto attack against HTTPS」,連結1連結2)

OpenSSLGnuTLS 所實作的 DTLS 在 2011 年也被炸到,其中 OpenSSL 是 100% plaintext recovery,GnuTLS 是 4%。(CVE-2012-0390,論文是「Plaintext-Recovery Attacks Against Datagram TLS」)

而 Encrypt-then-MAC (傳輸「密文」與「密文的 MAC」) 是三者裡面最不容易出包的作法,而且被證明 Provable security:Encrypt 與 MAC 所用的 crypto system 的安全強度不會因為 Encrypt-then-MAC 而減少。而這也是 IPSec 的作法。

附帶一提,其中 Provable security 這個詞,並非表示「可被證明是安全的」,在「In defense of Provable Security」這篇文章裡有比較完整的說明。通常是指安全強度不會因為這個系統而降低:以 Encrypt-then-MAC 的例子來說,如果 Encrypt 的部份用 DES,或是 MAC 用 CRC32,那麼 Encrypt-then-MAC 並不會提供更強的安全性...

總而言之,MAC-then-Encrypt 與 Encrypt-and-MAC 的方式要小心才能避免各種攻擊 (像是不能用 CBC mode),而 Encrypt-then-MAC 可以讓設計協定的人放鬆到「只要 Encrypt 與 MAC 都夠強」系統就沒問題。在 Authenticated encryption 裡提到的 ISO/IEC 19772:2009 支援六個模式,有些有專利問題,有些演算法看起來就很複雜 (於是就容易出包),其中 Encrypt-then-MAC 看起來是個還不錯的方案...

虛擬機內的 Side-channel attack...

前陣子在其他地方看到,不過剛剛在「Stealing VM Keys from the Hardware Cache」看到利用 Side-channel attack 的攻擊:「Cross-VM Side Channels and Their Use to Extract Private Keys」。

實際攻擊的項目是 libgcrypt 實做的 ElGamal 演算法,長度是 4096bits。環境是 Xen,限制是在同一台實體機器上。

對抗 side-channel attack 的幾個方法:實體隔離 (效果最好) 或是改善演算法 (通常是犧牲一些演算法效率,換取難以被外部預測的保護)。前者也就是 AWS 為了符合美國政府要求所建立 AWS GovCloud (US) 的原因之一。