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.

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

NIST 選出了四個 Post-Quantum Cryptography 演算法

NIST (NSA) 選出了四個 Post-quantum cryptography 演算法 (可以抵抗量子電腦的演算法):「NIST Announces First Four Quantum-Resistant Cryptographic Algorithms」。

四個演算法分別是:

  • CRYSTALS-Kyber:非對稱加密。
  • CRYSTALS-Dilithium:數位簽名。
  • FALCON:數位簽名。
  • SPHINCS+:數位簽名。

這次沒看到非對稱加解密的演算法...

然後翻了 Hacker News 上的討論,果然一堆人在討論 NIST 能不能信任的問題:「NIST Announces First Four Quantum-Resistant Cryptographic Algorithms (nist.gov)」。

然後據說 Kyber 這個名字出自 Star Wars,Dilithium 這個名字則是出自 Star Trek,這還真公平 XDDD

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」。

GET 與 POST 的差異

看到這篇在講 HTTP (& HTTPS) 裡面 GET 與 POST 的差異,剛好把一些標準的定義拿出來翻一翻,算是複習基本概念:「Get safe」。

第一個基本概念主要是 idempotence (& idempotent),重複被呼叫不會造成狀態的再次改變:

Idempotence ([...]) is the property of certain operations in mathematics and computer science whereby they can be applied multiple times without changing the result beyond the initial application.

數學定義是這樣跑:

An element x of a magma (M, •) is said to be idempotent if:

x • x = x.

If all elements are idempotent with respect to •, then • is called idempotent. The formula ∀x, x • x = x is called the idempotency law for •.

這點在 HTTP 標準 (RFC 7231) 裡面的定義也類似:

A request method is considered "idempotent" if the intended effect on the server of multiple identical requests with that method is the same as the effect for a single such request. Of the request methods defined by this specification, PUT, DELETE, and safe request methods are idempotent.

第二個基本概念是 Safe method (也是在同樣的 RFC 裡被提到),主要的思想是 read-only,這也是文章作者的標題要講的事情:

Request methods are considered "safe" if their defined semantics are essentially read-only; i.e., the client does not request, and does not expect, any state change on the origin server as a result of applying a safe method to a target resource. Likewise, reasonable use of a safe method is not expected to cause any harm, loss of property, or unusual burden on the origin server.

然後標準的 HTTP method 是有定義的:

   +---------+------+------------+---------------+
   | Method  | Safe | Idempotent | Reference     |
   +---------+------+------------+---------------+
   | CONNECT | no   | no         | Section 4.3.6 |
   | DELETE  | no   | yes        | Section 4.3.5 |
   | GET     | yes  | yes        | Section 4.3.1 |
   | HEAD    | yes  | yes        | Section 4.3.2 |
   | OPTIONS | yes  | yes        | Section 4.3.7 |
   | POST    | no   | no         | Section 4.3.3 |
   | PUT     | no   | yes        | Section 4.3.4 |
   | TRACE   | yes  | yes        | Section 4.3.8 |
   +---------+------+------------+---------------+

不過文章裡面提到的第一個例子並沒有很好,POST 不保證 safe 沒錯,但不代表 safe operation 就不能用 POST。

這邊用 URI resource 的概念 (以及 SEO?) 或是用 Post/Redirect/Get 的概念來說明會比較好:

<form method="get" action="/search">
<input type="search" name="term">

不過文章後續提到的問題的確就是我自己都會犯錯的問題:

“Log out” links that should be forms with a “log out” button—you can always style it to look like a link if you want.

“Unsubscribe” links in emails that immediately trigger the action of unsubscribing instead of going to a form where the POST method does the unsubscribing. I realise that this turns unsubscribing into a two-step process, which is a bit annoying from a usability point of view, but a destructive action should never be baked into a GET request.

這兩個動作都會造成 server 端的狀態改變,不應該用 GET,而我自己常常忘記第一個... 這邊其實可以用 form 產生 POST 需求,並且用 css 效果包起來,達到看起來跟一般的連結一樣。

寫起來讓自己多一點印象,之後避免再犯一樣的錯誤...

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.

感覺還是會繼續嘗試,因為這兩個演算法的缺點都還是有點致命...

Adobe Security Team 直接把 Private Key 貼到網誌上面...

Security Team 出這種包...:「In spectacular fail, Adobe security team posts private PGP key on blog」。

Adobe 這次的事情要怎麼說呢,hmmm...

Facebook 與 Google Chrome 以及 Firefox 的人合作降低 Reload 使用的資源

Facebook 花了不少時間對付 reload 這件事情:「This browser tweak saved 60% of requests to Facebook」。

Facebook 的人發現有大量對靜態資源的 request 都是 304 (not modified) 回應:

In 2014 we found that 60% of requests for static resources resulted in a 304. Since content addressed URLs never change, this means there was an opportunity to optimize away 60% of static resource requests.

Google Chrome 很明顯偏高:

於是他們找出原因後,發現 Google Chrome 只要 POST 後的頁面都會 revalidate:

A piece of code in Chrome hinted at the answer to our question. This line of code listed a few reasons, including reload, for why Chrome might ask to revalidate resources on a page. For example, we found that Chrome would revalidate all resources on pages that were loaded from making a POST request.

然後在討論後認為這個行為不必要,就修掉了,可以看到降了非常多:

We worked with Chrome product managers and engineers and determined that this behavior was unique to Chrome and unnecessary. After fixing this, Chrome went from having 63% of its requests being conditional to 24% of them being conditional.

但還是很明顯比起其他瀏覽器偏高不少,在追問題後發現當輸入同樣的 url 時 (像是 Ctrl-L 或是 Cmd-L 然後直接按 enter),Google Chrome 會當作 reload:

The fact that the percentage of conditional requests from Chrome was still higher than other browsers seemed to indicate that we still had some opportunity here. We started looking into reloads and discovered that Chrome was treating same URL navigations as reloads while other browsers weren't.

不過這次推出修正後發現沒有大改變:(拿 production 測試 XDDD)

Chrome fixed the same URL behavior, but we didn't see a huge metric change. We began to discuss changing the behavior of the reload button with the Chrome team.

後來是針對 reload button 的行為修改,max-age 很長的就不 reload,比較短的就 reload。算是一種 workaround:

There was some debate about what to do, and we proposed a compromise where resources with a long max-age would never get revalidated, but that for resources with a shorter max-age the old behavior would apply. The Chrome team thought about this and decided to apply the change for all cached resources, not just the long-lived ones.

Google 也發了一篇說明這個新功能:「Reload, reloaded: faster and leaner page reloads」。

當 Facebook 的人找 Firefox 的人時,Firefox 決定另外定義哪些東西在 reload 時不需要 revalidate,而不像 Google Chrome 的 workaround:

Firefox chose to implement this directive in the form of a cache-control: immutable header.

Firefox 的人也寫了一篇「Using Immutable Caching To Speed Up The Web」解釋這個新功能。

所以之後規劃前後端的架構時又有東西要考慮進去...

利用隱藏的 form input 加上自動完成功能取得敏感資料

anttiviljami/browser-autofill-phishing 這邊示範了怎麼用隱藏的 form input 與自動完成功能取得敏感資料。在這邊可以看到示範 (把 POST 丟到 httpbin 上看 response)。

想法不算困難,但好像也不是很好防... 關掉 autofill 是比較簡單的解法 (我是裝好瀏覽器就會關掉,不過好像很多人都喜歡用這個功能),所以這個問題就丟回給這些 browser vendor 想了 :o

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.