NIST 開始徵求 Post-Quantum Cryptography 演算法

現有常見的幾個加密基礎在量子電腦上都有相當快速的解 (像是整數質因數分解、離散對數),只是現在建不出對應夠大台的量子電腦... 但畢竟只是時間的問題了,所以 NIST 照著慣例對外尋求能夠抵抗量子電腦的演算法:「NIST Asks Public to Help Future-Proof Electronic Information」、「Announcing Request for Nominations for Public-Key Post-Quantum Cryptographic Algorithms」。

類似於 Google 先前在 Google Chrome 上實做的 CECPQ1,對 key exchange 的部份加上保護 (Google Chrome 引入 CECPQ1,開始測試 Post-Quantum Cryptography),這次 NIST 是針對 public key crytpsystem 的部份而發的...

投稿時間在 2017 的十一月底,大約一年後就可以看到有哪些演算法要參加競賽了... 不過因為 NSA 的惡名,不知道會不會有其他單位在同個時段啟動類似的活動...

Google 測試 CECPQ1 的一些資料...

七月的時候提到「Google Chrome 引入 CECPQ1,開始測試 Post-Quantum Cryptography」,剛剛看到 Adam Langley 寫了一些數據出來:「CECPQ1 results」。

目前看起來對於網路速度不快的使用者會影響比較大,最慢的 5% 使用者大約慢了 20ms,最慢的 1% 使用者會慢 150ms:

Although the median connection latency only increased by a millisecond, the latency for the slowest 5% increased by 20ms and, for the slowest 1%, by 150ms. Since NewHope is computationally inexpensive, we're assuming that this is caused entirely by the increased message sizes. Since connection latencies compound on the web (because subresource discovery is delayed), the data requirement of NewHope is moderately expensive for people on slower connections.

由於實驗算是完成了,加上 TLS 已經有規劃了,所以 Google Chrome 打算拔掉這個功能等標準出來:

At this point the experiment is concluded. We do not want to promote CECPQ1 as a de-facto standard and so a future Chrome update will disable CECPQ1 support. It's likely that TLS will want a post-quantum key-agreement in the future but a more multilateral approach is preferable for something intended to be more than an experiment.

Libgcrypt 與 GnuPG 的安全性問題

在「Security fixes for Libgcrypt and GnuPG 1.4 [CVE-2016-6316]」這邊看到這個歷史悠久的 bug:

Felix Dörre and Vladimir Klebanov from the Karlsruhe Institute of Technology found a bug in the mixing functions of Libgcrypt's random number generator: An attacker who obtains 4640 bits from the RNG can trivially predict the next 160 bits of output. This bug exists since 1998 in all GnuPG and Libgcrypt versions.

就這樣的行為,對於自己用的機器應該是還好... 不過得到 4640 bits 後就可以預測接下來的 160 bits,這個 RNG 有點囧 @_@

官方目前是認為應該還好:

A first analysis on the impact of this bug in GnuPG shows that existing RSA keys are not weakened. For DSA and Elgamal keys it is also unlikely that the private key can be predicted from other public information. This needs more research and I would suggest _not to_ overhasty revoke keys.

不過如果你有絕對的安全需求的話還是可以考慮 revoke 再重新生一把...

Google Chrome 引入 CECPQ1,開始測試 Post-Quantum Cryptography

Quantum Computer 對現有密碼學的衝擊很大,像是 RSA 演算法是基於「質因數分解」的難題而架構出來的系統,在 Quantum Computer 上存在有效率的演算法,也就是 Shor's algorithm

雖然 Quantum Computer 在技術上還沒辦法對現有演算法造成有效的攻擊,但已經有人提出新的演算法來對抗,而 Google 打算在 Google Chrome 裡面引入測試:「Experimenting with Post-Quantum Cryptography」。

Google 也特別說明了,他們不希望這個實驗最後變成 de-facto standard (借測轉出貨的概念),而是希望當作一個開頭,希望之後可以用更好的標準換掉:

We explicitly do not wish to make our selected post-quantum algorithm a de-facto standard. To this end we plan to discontinue this experiment within two years, hopefully by replacing it with something better.

2015 年的 Turing Award 由 Whitfield Diffie 與 Martin E. Hellman 獲得

紐約時報看到今年的 Turing AwardWhitfield DiffieMartin E. Hellman 獲得:「Cryptography Pioneers Win Turing Award」。在 Turing Award 官網上也可以看到對應的說明。

Diffie–Hellman key exchange 是全世界第一個 (1976 年) 在公開頻道上建立 shared secret 的演算法,直到現在都還廣泛的被使用,可以防禦被動式的監聽攻擊:

The Diffie–Hellman key exchange method allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure channel.

現在這個演算法用在 PFS (Perfect forward secrecy),或稱為 FS (Forward secrecy),確保 public key 被破解前的連線記錄不會輕易被破解,於是更確保了資料的安全性:

a secure communication protocol is said to have forward secrecy if compromise of long-term keys does not compromise past session keys.

後來這個演算法也被延用到 Elliptic curve 上,也就是 ECDH,因為不使用 Z_{2^p}Z_p (field) 而是使用 Elliptic curve (group),而大幅降低了可被拿來攻擊的特性,而使得 key 的長度可以比 RSA 小很多。

上一個因密碼學拿到 Turing Award 的是 2012 年得獎的 Silvio MicaliShafi Goldwasser,他們所音發展出來的用以對密碼系統驗證的數學方法而得獎。

而更有名的應該是 2002 年 Ronald L. RivestAdi ShamirLeonard M. Adleman 因為 RSA 演算法而得獎的事情。

在愈來愈多新聞揭露安全與隱私問題後 (尤其是政府對人民的監控),密碼學愈來愈被重視。之前在密碼學領域做出重大貢獻的人也陸陸續續得獎...

荷蘭政府捐贈五十萬歐元給 OpenSSL

在一堆政府想要立法放後門進系統的情況下,荷蘭政府則反對這樣的想法,並且決定捐贈五十萬歐元 (目前約五十四萬美金) 給 OpenSSL:「Dutch govt says no to backdoors, slides $540k into OpenSSL without breaking eye contact」:

The Dutch government has formally opposed the introduction of backdoors in encryption products.

A government position paper, published by the Ministry of Security and Justice on Monday and signed by the security and business ministers, concludes that "the government believes that it is currently not appropriate to adopt restrictive legal measures against the development, availability and use of encryption within the Netherlands."

以及:

The formal position comes just months after the Dutch government approved a €500,000 ($540,000) grant to OpenSSL, the project developing the widely used open-source encryption software library.

OpenSSL 的 ECDH 中,224 bits 速度比 160/192 bits 快的原因

openssl speed ecdh 的時候發現很特別的現象:

Doing 160 bit  ecdh's for 10s: 40865 160-bit ECDH ops in 9.99s
Doing 192 bit  ecdh's for 10s: 34169 192-bit ECDH ops in 9.99s
Doing 224 bit  ecdh's for 10s: 60980 224-bit ECDH ops in 9.99s
Doing 256 bit  ecdh's for 10s: 34298 256-bit ECDH ops in 10.00s
Doing 384 bit  ecdh's for 10s: 9602 384-bit ECDH ops in 10.00s
Doing 521 bit  ecdh's for 10s: 9127 521-bit ECDH ops in 9.99s

原因是 Google 這篇論文的貢獻:「Fast Elliptic Curve Cryptography in OpenSSL」,開頭就提到:

We present a 64-bit optimized implementation of the NIST and SECG-standardized elliptic curve P-224.

而實際成果:

full TLS handshakes using a 1024-bit RSA certificate and ephemeral Elliptic Curve Diffie-Hellman key exchange over P-224 now run at twice the speed of standard OpenSSL, while atomic elliptic curve operations are up to 4 times faster.

OpenSSLCHANGES 也可以看到對應的修改,不只是 NIST-P224 有被改善,其他的 NIST-P256 與 NIST-P521 也都有被改善:

Add optional 64-bit optimized implementations of elliptic curves NIST-P224, NIST-P256, NIST-P521, with constant-time single point multiplication on typical inputs.

頗特別的...