SHA-1 的 chosen-prefix collision 低於 2^64 了...

算是前陣子的大消息,SHA-1 的 chosen-prefix collision 需要的運算已經低於 2^64 了:「SHA-1 is a Shambles」。

基本的 collision 指的是演算法找出 p1p2 兩個字串,使得 hash(p1) == hash(p2)。但這個方法對於實際的攻擊價值並不大,因為 p1p2 是透過演算法找出來 collision,都是亂數字串。

chosen-prefix collision 指的是先給定 p1p2 (在實際攻擊中,兩組都會是有意義的字串),然後攻擊的演算法可以算出 m1m2,使得 hash(p1 // m1) == hash(p2 // m2),其中的 // 就是字串加法。這樣的是先產生出有意義的字串,於是就可以在真實世界中使用。

舉例來說,我先產生出 blog.gslin.org 的 SSL certificate,然後再產生出一個 github.com 的 SSL certificate,這兩個分別就是 p1p2

接下來演算法算出 m1m2,使得 hash(p1 // m1)hash(p2 // m2) 相同。

接著,我就可以拿 p1 // m1 給 CA 簽名 (因為我有 blog.gslin.org 的擁有權),而拿到的憑證因為 hash 值相同,就可以給 github.com 這組用。

2008 年的時候就用這個方法生出一個 sub-CA:

In 2008, researchers used a chosen-prefix collision attack against MD5 using this scenario, to produce a rogue certificate authority certificate. They created two versions of a TLS public key certificate, one of which appeared legitimate and was submitted for signing by the RapidSSL certificate authority. The second version, which had the same MD5 hash, contained flags which signal web browsers to accept it as a legitimate authority for issuing arbitrary other certificates.[14]

另外,如果跟 2017 年由 GoogleCWI 打出來的 SHAttered 比較,當時的攻擊是 identicial-prefix,實際上的用途沒那麼大,這次是 chosen-prefix,就有很強的實際用途了。

所以這次的攻擊給了幾個重要的事情。

第一個是 SHA-1 的 chosen-prefix collision attack 運算已經降到 2^64 以下了,然後加上:

第二個是 2^64 的運算成本已經低於 USD$100k 了,作者是使用 GPUserversrental 這個租用 GPU 的服務跑出這次的運算,而這也表示攻擊安全層級是 2^64 的密碼系統,成本也是 USD$100k 了。

地球上還是有不少系統使用 SHA-1 (作者在網站上有提到),看起來這陣子會有不少修正...

兩個 gperf...

翻資料的時候覺得怎麼跟印象中的不太一樣,多花些時間翻了一下,發現原來有兩個東西同名...

一個是 GNUgperf,給定字串集合,產生 C 或 C++ 的 perfect hash function (i.e. no collision):

GNU gperf is a perfect hash function generator. For a given list of strings, it produces a hash function and hash table, in form of C or C++ code, for looking up a value depending on the input string. The hash function is perfect, which means that the hash table has no collisions, and the hash table lookup needs a single string comparison only.

另外一個是 Google 弄出來的 gperftoolsmalloc() 的替代品以及效能分析工具:

gperftools is a collection of a high-performance multi-threaded malloc() implementation, plus some pretty nifty performance analysis tools.

V8 對 Hash Flooding 的防禦措施

Hash Flooding 問題是指 Hash 這個資料結構是可以被預測 collision 所造成的問題,在隨機的情況下會是 O(1) 的操作,在特定挑選故意讓他 collision 而變成 O(n),當有 n 個元素時,乘起來就會變成 O(n^2)。這算是一種阻斷攻擊 (DoS attack)。

在「About that hash flooding vulnerability in Node.js...」這邊提到了 V8 之前為了避免 Hash Flooding 的問題,關掉了 Startup snapshot 而造成的效能問題,以及後續的很多故事,最後找了長期的解法。

這個解法已經併入 Node.js 裡,預定下個包括的版本是 8.3.0:

The patch to re-enable startup snapshot has been merged into Node.js. It is part of the recent Node.js v8.3.0 release.

不過這表示現有的 LTS (4.8.4 以及 6.11.2) 還是... XD

PGP 短 ID 的安全問題

PGP 短 ID 的安全問題出來了,不見棺材不掉淚啊:「Fake Linus Torvalds' Key Found in the Wild, No More Short-IDs.」。

重點在這段,已經有人發出攻擊了:

Search Result of 0x00411886: https://pgp.mit.edu/pks/lookup?search=0x00411886&op=index
Fake Linus Torvalds: 0F6A 1465 32D8 69AE E438  F74B 6211 AA3B [0041 1886]
Real Linus Torvalds: ABAF 11C6 5A29 70B1 30AB  E3C4 79BE 3E43 [0041 1886]

Search Result of 0x6092693E: https://pgp.mit.edu/pks/lookup?search=0x6092693E&op=index
Fake Greg Kroah-Hartman: 497C 48CE 16B9 26E9 3F49  6301 2736 5DEA [6092 693E]
Real Greg Kroah-Hartman: 647F 2865 4894 E3BD 4571  99BE 38DB BDC8 [6092 693E]

另外作者給了還蠻重要的觀念:

DO NOT TRUST ANYTHING SHORTER THAN THE FINGERPRINTS.

Google 自動駕駛車保護行人而申請的專利

在「Google patent: Glue would stick pedestrian to self-driving car after collision」這邊看到因為自動駕駛車的發明才有可能做到的專利。

一般的情況下,在汽車撞到行人後,駕駛會急忙停下來,而可能會導致後方車輛的追撞,而且可能會導致行人直接飛出去造成更多的傷害。這個專利規劃在車輛前端使用特殊的黏性膠,再透過減速讓行人黏在上面停下來:

The front region of the vehicle may be coated with a specialized adhesive that adheres to a pedestrian, and thus holds the pedestrian on the vehicle in the unfortunate event that the front of the vehicle comes into contact with the pedestrian,

The adhesion of the pedestrian to the vehicle may prevent the pedestrian from bouncing off.

專利的示意圖:

V8 的 Math.random() 亂度不足的問題

在「TIFU by using Math.random()」這篇看到作者踩到地雷,於是在討論 V8 EngineMath.random() 的亂度不足。

其實這個問提早在 2012 年就有人在 StackOverflow 上詢問:「Why is Google Chrome's Math.random number generator not *that* random?」,而且也回答得很清楚。

而 Mozilla 這邊在 2006 年也被提出了類似的問題:「Bug 322529 - Upgrade Math.random() to a better algorithm, such as Mersenne Twister」。

文章中間花了許多篇幅講 PRNG 的介紹,以及 cycle length 的說明,重點其實在結論的部份。

主要是因為 V8 Engine 的 Math.random() 實作的是 MWC1616 演算法 (Fast random number generation using 128 bit multimedia extension registers on Pentium class machines),而這個演算法用起來也綁手綁腳:

If you’re only using the most significant 16 bits it has a very short effective cycle length (less than 2³⁰).

有兩個方向可以改善 (不衝突的方向),一個是使用 CSPRNG (保證有極長的 cycle length),另外一個請求 V8 Engine 把 Math.random() 的演算法換掉,像是 MT19937 這類 cycle length 超級長的演算法。

不知道後續有沒有機會改善...

對 SHA-1 的攻擊進展

Bruce Schneier 這邊看到對 SHA-1 的攻擊又有新的進展了:「SHA-1 Freestart Collision」。

這次的論文不是真的找出 collision,而是對 internal compression function 攻擊,不過即使如此,這是首次攻擊完整的 80 rounds:

We present in this article a freestart collision example for SHA-1, i.e., a collision for its internal compression function. This is the first practical break of the full SHA-1, reaching all 80 out of 80 steps, while only 10 days of computation on a 64 GPU cluster were necessary to perform the attack.

論文資訊可以在「The SHAppening: freestart collisions for SHA-1」這邊看到。

用 Amazon EC2 的 GPU instance 計算 MD5 collision

在「Create your own MD5 collisions」這篇教你用 Amazon EC2 的 GPU instance 計算 MD5 collision。

由於不是什麼正式的服務,文章裡介紹你用 Spot instance 開機器,會便宜不少。可以看到最後的結果:

在文後也把兩張圖都附上來讓大家確認,抓下來後也可以確認:

gslin@GSLIN-DESKTOP [~/tmp] [13:16/W3] md5sum *.jpg
253dd04e87492e4fc3471de5e776bc3d  plane.jpg
253dd04e87492e4fc3471de5e776bc3d  ship.jpg

屬於 chosen prefix collision 的攻擊。

Btrfs 的 Hash Collision...

Slashdot 上看到「Denial-of-Service Attack Found In Btrfs File-System」覺得很有趣,結果一看,又是 hash collision... XD

一年前的「n.runs-SA-2011.004 - web programming languages and platforms - DoS through hash table (PDF)」打爆所有主流語言,沒想到在 filesystem 上也發生了 XDDD

不知道要怎麼修正... (已經存在的資料要怎麼 migrate?incompatible change?)