算是前陣子的大消息，SHA-1 的 chosen-prefix collision 需要的運算已經低於 2^64 了：「SHA-1 is a Shambles」。
基本的 collision 指的是演算法找出 p1 與 p2 兩個字串，使得 hash(p1) == hash(p2)。但這個方法對於實際的攻擊價值並不大，因為 p1 與 p2 是透過演算法找出來 collision，都是亂數字串。
chosen-prefix collision 指的是先給定 p1 與 p2 (在實際攻擊中，兩組都會是有意義的字串)，然後攻擊的演算法可以算出 m1 與 m2，使得 hash(p1 // m1) == hash(p2 // m2)，其中的 // 就是字串加法。這樣的是先產生出有意義的字串，於是就可以在真實世界中使用。
舉例來說，我先產生出 blog.gslin.org 的 SSL certificate，然後再產生出一個 github.com 的 SSL certificate，這兩個分別就是 p1 與 p2。
接下來演算法算出 m1 與 m2，使得 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 年由 Google 與 CWI 打出來的 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 (作者在網站上有提到)，看起來這陣子會有不少修正...
Mentions