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?)