SHA-256 的 Length extension attack

Hacker News 上看到「Breaking SHA256: length extension attacks in practice (kerkour.com)」,在講不當使用 SHA-256 會導致 Length extension attack 類的安全漏洞,主要是因為 MD5SHA-1 以及 SHA-2 類的 hash function 最後生出 hash 值時會暴露出 hash function 的內部狀態而導致的問題。

這邊講的不當使用是指你沒有使用標準的 MAC,而是自己用字串組合實作造成的問題,通常是 S = H(secret || message) 這樣的形式,這邊的 || 是指字串相接。

拿 MD5 為例子,在維基百科上面可以看到 MD5 演算法對應的 pseudo code,最後輸出的部分可以看到是把 a0a1a2a3 這四個 32-bit variable 接起來,也就是把內部的狀態丟出來了:

// Process the message in successive 512-bit chunks:
for each 512-bit chunk of padded message do
    // ...

    // Add this chunk's hash to result so far:
    a0 := a0 + A
    b0 := b0 + B
    c0 := c0 + C
    d0 := d0 + D
end for

var char digest[16] := a0 append b0 append c0 append d0 // (Output is in little-endian)

於是你在可以反推 padding 的結構之後 (會需要知道 secret 的長度),就可以往後接東西繼續算下去,這就是被稱作 length extension attack。

本來只有 S = H(secret || message),你在不知道 secret 的情況下就可以疊字串到後面而且算出對應的 hash 值,變成 S' = H(secret || message || evildata)

維基百科給的例子也示範了怎麼「用」,這是原始的資料以及 server 端簽出來的 hash 值:

Original Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo
Original Signature: 6d5f807e23db210bc254a28be2d6759a0f5f5d99

於是我們想要蓋 waffle 參數,就變成:

Desired New Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo&waffle=liege

攻擊者則可以不斷的嘗試,去猜測 padding 的結構,把計算出來對應的 hash 值丟到 server 看反應,直到看到 200 OK 的回應:

New Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x02\x28&waffle=liege
New Signature: 0e41270260895979317fff3898ab85668953aaa2

如同前面提到的,這是 hash function 在最後把內部狀態直接暴露出來造成的問題,在 MD5、SHA-1、SHA-2 (SHA-256、SHA-384、SHA-512) 都有類似的問題,而比較新的 hash function 在設計時就已經有考慮到了,不會出現這個問題,像是 SHA-3

另外一方面,不要自己發明演算法,使用標準的 MAC 演算法通常是比較好的選擇。這邊用的比較廣泛的應該就是 HMAC,超過 25 年了。

結論是 SHA-256 還是堪用,儘量拿現成的演算法套,不要自己搞。

GPT 的進程 (或是 LLM 的進程)

前幾天不知道在哪邊看到「Five years of GPT progress」這篇,裡面整理了這五年 GPT/LLM 的進程,算是回顧性質的文章,裡面當然有提到技術改善的地方 (像是參數大小,類神經網路層的架構差異),另外裡面都有原始論文或是資料的連結,然後作者也有描述一些當時的背景,對於要釐清歷史脈絡也蠻有幫助的。

GPTGPT-2GPT-3 這三個 OpenAI 的作品開始講,然後提到 GPT-3 帶出來的新紀元。

接著提到的是各家都開始進來參與的年代,Jurassic-1 (AI21 Labs)、Megatron-Turing NLG (Nvidia)、Gopher (DeepMind)、Chinchilla (DeepMind)、PaLM (Google AI)。

然後是 LLaMa (Facebook),第一個有參數夠大,而且效能夠好的 model,被放出來讓大家玩的 LLM。

最後又回到 OpenAI 的 GPT-4

這樣整理讀起來清晰不少,但要注意裡面的發展不是線性關係,彼此之間互相影響交錯在跑 (因為中間還是有很多其他的論文互相影響)。

Vector clock 的發明時間軸

一樣是在 Hacker News 上看到「Who invented vector clocks? (decomposition.al)」這篇文章,在找出誰發明了 vector clock,原文在「Who invented vector clocks?」。

主要有兩個不同的時間點,一個是 vector clock 概念的提出,另外一個是第一次用到 vector 這個詞。

這篇讓我覺得有趣的地方是,vector clock 本來就是在處理分散式系統裡面事件順序的問題,而這篇文章則是在找出真實世界裡面這些發明的先後順序,而且也牽扯到了各種 citation (類比到分散式系統裡事件的 dependency)。

分散式系統的 clock

前幾天在 Hacker News 上看到「Clocks and Causality – Ordering Events in Distributed Systems (2022) (exhypothesi.com)」這篇,講分散式系統上 clock 的設計,作者也有跑出來在 Hacker News 上面跟大家聊一下 (帳號是 thoughtlede),原文在「Clocks and Causality - Ordering Events in Distributed Systems」這邊。

文章裡面主要講空間是 O(1)Lamport timestamp 與空間是 O(n)Vector clock (這邊的 n 相對於節點數量),以及這兩個對應的擴充版本:

作者會整理這些資料的原因是因為在研究 CRDT 的時候看到演算法中常常會需要處理分散式系統裡面事件的順序,所以花了一些時間整理常見的方式:

Author here. Pleasantly surprised to see the article here.

Some context behind the article. I studied CRDTs for a few months, and noticed that different CRDT designs use logical clocks in different and clever ways. And I haven't seen anyone narrate all those ways of use in one article. My attempt with this article was to dredge up those flavors of logical clocks into one article and give them names for future reference.

(To respond to a couple of other comments, I ignored atomic (and gps-based) clocks in this discussion, as indicated in my footnote 3).

我記得還有一個 Interval Tree Clocks 可以參考 (在「Interval Tree Clocks」這邊講的比較清楚),是針對節點的動態增刪而改善的演算法,但不確定有什麼比較有名的系統有用。

大多數應該都是用 Vector clock,畢竟是在 2007 年的「Dynamo: Amazon’s Highly Available Key-value Store」被發揚光大,而且也算是還不錯的演算法?

OpenSSH 與 Dropbear 對 Ed25519 的支援

查了一下這兩個 server 端的軟體支援 Ed25519 的時間點。

OpenSSH 是在 2014/01/30 的 6.5 就支援了:

* ssh(1), sshd(8): Add support for Ed25519 as a public key type. Ed25519 is a elliptic curve signature scheme that offers better security than ECDSA and DSA and good performance. It may be used for both user and host keys.

算是相當久以前就支援了。對應到第一個支援的 Debian 版本是 Jessie 使用的 OpenSSH 6.7:「sshd(8) — openssh-server — Debian jessie — Debian Manpages」;第一個支援的 Ubuntu (LTS) 版本是 Trusty (14.04) 用的 OpenSSH 6.6:「openssh source package in Trusty」。

Dropbear 這邊就晚不少,在 2020/06/15 的 2020.79 版本才支援:

- Support ed25519 hostkeys and authorized_keys, many thanks to Vladislav Grishenko. This also replaces curve25519 with a TweetNaCl implementation that reduces code size.

所以對應到第一個支援的 Debian 版本是 Bullseye 的 2020.81:「Debian -- Details of package dropbear in bullseye」;第一個支援 Ubuntu (LTS) 的版本是 Jammy (22.04) 的 2020.81:「Ubuntu – Details of package dropbear in jammy」。

這樣看起來如果就是想要用 Ed25519 的話,變成 server 端的軟體得配合:預設裝的 sshd 應該都是 OpenSSH,如果想要換 Dropbear 的話要看 distribution 內給的版本夠不夠新,或是透過 PPA 之類的方法裝新版。

但大多數採用 BusyBox 的機器應該沒有採用新版 Dropbear (像是 AP 刷機),這邊還是得使用其他 key format,如果要避開 NIST 有介入的格式,就還是得用 ssh-rsa 了。

Intel 用 AVX-512 加速 NumPy 的排序演算法被整合進主線了

IntelAVX-512 加速 NumPy 排序的實做被整合進主線了:「「Intel Publishes Blazing Fast AVX-512 Sorting Library, Numpy Switching To It For 10~17x Faster Sorts」」。

GitHub 的 PR 在「ENH: Vectorize quicksort for 16-bit and 64-bit dtype using AVX512 #22315」這邊,可以看到相關的留言:

This patch adds AVX512 based 64-bit on AVX512-SKX and 16-bit sorting on AVX512-ICL. All the AVX512 sorting code has been reformatted as a separate header files and put in a separate folder. The AVX512 64-bit sorting is nearly 10x faster and AVX512 16-bit sorting is nearly 16x faster when compared to std::sort. Still working on running NumPy benchmarks to get exact benchmark numbers

16-bit int sped up by 17x and float64 by nearly 10x for random arrays. Benchmarked on a 11th Gen Tigerlake i7-1165G7.

有點「有趣」的情況是,AVX-512 在新的 Intel 消費級 CPU 被拔掉了,只有伺服器工作站的 CPU 有保留。而 AMDZen 4 則是跳下去支援 AVX-512...

另外在「Intel Publishes Fast AVX-512 Sorting Library, 10~17x Faster Sorts in NumPy (phoronix.com)」這邊當然也有人提到,如果用更廣泛的 AVX2 (寬度是 256bits) 加速的話應該也會有很大的進步才對?幾乎這十年的 CPU 都有 AVX2 了... 不過看起來沒有什麼深入的討論?

NIST 更新了 SHA-1 的淘汰計畫

NISTSHA-1 的新的淘汰計畫出來了:「NIST Retires SHA-1 Cryptographic Algorithm」。

先前 NIST 在 2004 年時是計畫在 2010 年淘汰掉 SHA-1,在「NIST Brief Comments on Recent Cryptanalytic Attacks on Secure Hashing Functions and the Continued Security Provided by SHA-1」這邊可以看到當時的宣佈:

The results presented so far on SHA-1 do not call its security into question. However, due to advances in technology, NIST plans to phase out of SHA-1 in favor of the larger and stronger hash functions (SHA-224, SHA-256, SHA-384 and SHA-512) by 2010.

但看起來當時沒有強制性,所以事情就是一直拖一直延期,中間經過了 2017 年 GoogleCWI Amsterdam 展示的 SHA-1 collision:「Google 與 CWI Amsterdam 合作,找到 SHA-1 第一個 collision」。

以及 2020 年時的進展與分析,發現 chosen-prefix collision 已經是可行等級了:「SHA-1 的 chosen-prefix collision 低於 2^64 了...」。

然後 NIST 總算是想起來要更新 phase out 的計畫,現在最新的計畫是在 2030 年年底淘汰掉 SHA-1:

As today’s increasingly powerful computers are able to attack the algorithm, NIST is announcing that SHA-1 should be phased out by Dec. 31, 2030, in favor of the more secure SHA-2 and SHA-3 groups of algorithms.

這次就有一些強制的規範了,包括採購的部份:

“Modules that still use SHA-1 after 2030 will not be permitted for purchase by the federal government,” Celi said.

但 2030 年聽起來還是有點慢...

網頁大小 14KB 與 15KB 的速度差異

Hacker News 上看到「Why your website should be under 14kB in size」這篇,對應的討論在「A 14kb page can load much faster than a 15kb page (endtimes.dev)」,在講網頁大小 14KB/15KB 的速度差異比 15KB/16KB 大很多的問題:

What is surprising is that a 14kB page can load much faster than a 15kB page — maybe 612ms faster — while the difference between a 15kB and a 16kB page is trivial.

原因是 TCP slow start 造成的:

This is because of the TCP slow start algorithm.

而網頁這邊 TCP slow start 目前大多數的實做都是 10 packets 後發動:

Most web servers TCP slow start algorithm starts by sending 10 TCP packets.

然後再組合 1500 bytes/packet 以及 overhead,就差不多是 14KB 了:

The maximum size of a TCP packet is 1500 bytes.

This this maximum is not set by the TCP specification, it comes from the ethernet standard

Each TCP packet uses 40 bytes in its header — 16 bytes for IP and an additional 24 bytes for TCP

That leaves 1460 bytes per TCP packet. 10 x 1460 = 14600 bytes or roughly 14kB!

然後 HTTP/3 也可以看到類似的設計 (出自「QUIC Loss Detection and Congestion Control」:

Sending multiple packets into the network without any delay between them creates a packet burst that might cause short-term congestion and losses. Implementations MUST either use pacing or limit such bursts to the initial congestion window, which is recommended to be the minimum of 10 * max_datagram_size and max(2* max_datagram_size, 14720)), where max_datagram_size is the current maximum size of a datagram for the connection, not including UDP or IP overhead.

算是一個小知識... 但對於現在肥滋滋的網頁效果來說就沒辦法了,而且考慮到大一點的網站會在一個 TCP 連線裡面可能會傳很多 request,其實早就超過 TCP slow start 的門檻了。

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