NIST P-curve 的 Seed Bounty Program

Filippo Valsorda 發起了 seed bounty program,針對 NIST P-curve 裡 seed 的部分尋找 SHA-1 的 pre-image:「Announcing the $12k NIST Elliptic Curves Seeds Bounty」。

先講一下這次的 bounty program,希望找出下面這些 SHA-1 的 pre-image input (也就是找出 input,使得 SHA1(input) 會等於下面的東西):

3045AE6FC8422F64ED579528D38120EAE12196D5
BD71344799D5C7FCDC45B59FA3B9AB8F6A948BC5
C49D360886E704936A6678E1139D26B7819F7E90
A335926AA319A27A1D00896A6773A4827ACDAC73
D09E8800291CB85396CC6717393284AAA0DA64BA

金額是 US$12288,但是要五個都找到。

話說在寫這篇時,查資料發現 P-384 有獨立條目,但 P-256P-521 都是重導指到 Elliptic-curve cryptography 這個條目,但 P-384 看起來也沒什麼特別的,不知道當初編輯的人是怎麼想的...

回來原來的問題,要從一些背景開始講,橢圓曲線的表示法有多種,像是:

y^2 = x^3 + ax + b (Weierstrass form) y^2 = x^3 + ax^2 + bx (Montgomery form)

而這些常數 ab 的選擇會影響到計算速度,所以通常會挑過,但畢竟是密碼學用的東西,挑的過程如果都不解釋的話,會讓人懷疑是不是挑一個有後門的數字,尤其 NIST (NSA) 後來被證實在 Dual_EC_DRBG 裡面埋後門的醜聞,大家對於 NIST 選擇或是設計的密碼系統都有很多疑慮。

舉個例子來說,2005 年時 djb 發明了 Curve25519 (論文「Curve25519: new Diffie-Hellman speed records」則是記錄 2006),選擇的橢圓曲線是:

y^2 = x^3 + 486662x^2 + x

他就有提到這邊的 486662 是怎麼來的:他先在前一個段落說明,這邊數字如果挑的不好的話,會有哪些攻擊可以用,接下來把最小的三個值列出來,然後說明原因:

To protect against various attacks discussed in Section 3, I rejected choices of A whose curve and twist orders were not {4 · prime, 8 · prime}; here 4, 8 are minimal since p ∈ 1+4Z. The smallest positive choices for A are 358990, 464586, and 486662. I rejected A = 358990 because one of its primes is slightly smaller than 2^252, raising the question of how standards and implementations should handle the theoretical possibility of a user’s secret key matching the prime; discussing this question is more difficult than switching to another A. I rejected 464586 for the same reason. So I ended up with A = 486662.

而 P-192、P-224、P-256、P-384 與 P-521 的值都很怪,這是十六進位的值,在正式的文件或是正式的說明上都沒有解釋,屬於「magic number」:

3045AE6FC8422F64ED579528D38120EAE12196D5 # NIST P-192, ANSI prime192v1
BD71344799D5C7FCDC45B59FA3B9AB8F6A948BC5 # NIST P-224
C49D360886E704936A6678E1139D26B7819F7E90 # NIST P-256, ANSI prime256v1
A335926AA319A27A1D00896A6773A4827ACDAC73 # NIST P-384
D09E8800291CB85396CC6717393284AAA0DA64BA # NIST P-521

依照 Steve Weis 說,這些值當初是 Jerry Solinas 是隨便抓個字串,再用 SHA-1 生出來的:

Apparently, they were provided by the NSA, and generated by Jerry Solinas in 1997. He allegedly generated them by hashing, presumably with SHA-1, some English sentences that he later forgot.

這是 Steve Weis 的敘述,出自「How were the NIST ECDSA curve parameters generated?」:

[Jerry] told me that he used a seed that was something like:
SEED = SHA1("Jerry deserves a raise.")
After he did the work, his machine was replaced or upgraded, and the actual phrase that he used was lost. When the controversy first came up, Jerry tried every phrase that he could think of that was similar to this, but none matched.

如果可以證實當初的字串,那麼 NIST 在裡面埋後門的疑慮會再降低一些,這就是這次發起 bounty program 的原因。

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 年聽起來還是有點慢...

SHA-1 在 2022 的破解速度已經降到 ~5.4 GPU years

前幾天在 Hacker News 上看到目前撞 SHA-1 collision 的難度:「How easy is it in 2022 to find a SHA1 collision? (stackexchange.com)」,原文在「How easy is it in 2022 to find a SHA1 collision?」。

在答案裡面有提到,即使在不考慮 ASIC 的情況下,光是用 GPU 算就可以可以降到 ~5.4 GPU years 了:

Remarkably, we can see that in only 5 years, we're down from an attack costing ~110 GPU years to an attack costing ~8 GPU-years in 2020 (thanks to theoretical improvements & newer GPUs) to just ~5.4 GPU years nowadays (thanks to newer, faster GPUs).

除了演算法本身的進步以外,GPU 的效能進展也帶動不少,而如果考慮到 ASIC 的話會快更多,對美國政府來說,如果搬出超級電腦來算的話,就是一天可以撞一個出來:

In a more realistic way, it would take less than a day to do it on a super-computer such as the one owned by the US Department of Energy's Oak Ridge National Laboratory (ORNL) named "Summit".

沒有在追進度,發現進展蠻快的,現在的攻擊速度比想像中快不少...

OpenSSH 8.4 預設停用 ssh-rsa

前幾天 OpenSSH 8.4 釋出了:「Announce: OpenSSH 8.4 released」。

比較重要的改變是 ssh-rsa 預設變成停用,因為是使用 SHA-1 演算法的關係:

It is now possible[1] to perform chosen-prefix attacks against the SHA-1 algorithm for less than USD$50K. For this reason, we will be disabling the "ssh-rsa" public key signature algorithm by default in a near-future release.

官方給了三個方案:

  • The RFC8332 RSA SHA-2 signature algorithms rsa-sha2-256/512. These algorithms have the advantage of using the same key type as "ssh-rsa" but use the safe SHA-2 hash algorithms. These have been supported since OpenSSH 7.2 and are already used by default if the client and server support them.
  • The ssh-ed25519 signature algorithm. It has been supported in OpenSSH since release 6.5.
  • The RFC5656 ECDSA algorithms: ecdsa-sha2-nistp256/384/521. These have been supported by OpenSSH since release 5.7.

掃了一下 ~/.ssh/known_hosts,看起來目前大多都是 ssh-ed25519 了,還有少數還是 ssh-rsa

翻了一下 Ubuntu 這邊的版本,16.04 是 7.2p2,看起來目前有支援的版本都可以用這三個。

官方有提到可以在 command 上強制關閉 ssh-rsa 測試的方法:

ssh -oHostKeyAlgorithms=-ssh-rsa user@host

現在看起來比較麻煩的是 Dropbear 的部份,我自己之前是有包 PPA 來用 (2019.78),但看起來還是不夠新支援 ssh-ed25519 (要今年六月的 2020.79 才支援),所以也許要找時間來把 PPA 更新到 2020.80...

另外一種方法是走 ecdsa-sha2-nistp{256,384,521} 這些演算法,不過從名字就可以知道裡面演算法的由來,卡個 NIST 在那邊看起來就不太舒服,但還是寫一下方法好了:

先用 dropbearkey 產生對應的 ecdsa host key:

sudo dropbearkey -t ecdsa -f /etc/dropbear/dropbear_ecdsa_host_key -s 256

再來在 /etc/default/dropbear 裡面把 DROPBEAR_EXTRA_ARGS 加上對應的 ecdsa host key 資訊,這邊直接用 -r 是因為他可以重複指定,不會影響到其他的 host key 設定:

# any additional arguments for Dropbear
DROPBEAR_EXTRA_ARGS="-r /etc/dropbear/dropbear_ecdsa_host_key"

然後重跑 dropbear 就可以了。

另外有興趣的人可以用 ssh -Q key 看 openssh client 支援的演算法。

Django 3.1

看到「Django 3.1 Released」這邊的公告,比較完整的改變可以在「Django 3.1 release notes」這邊翻到。

這應該是第一次要把手上的專案跳 minor version 升級,看起來應該是還好,但天曉得會有什麼狀況... 看起來主要會是 sha1 要被換成 sha256 會有影響到。

另外看到這個:

SimpleTestCase now implements the debug() method to allow running a test without collecting the result and catching exceptions. This can be used to support running tests under a debugger.

看起來應該也蠻有用的,可以玩看看...

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 (作者在網站上有提到),看起來這陣子會有不少修正...

實際比較 Linode 的 Dedicated 主機與 AWS 的 c5.*

先前有提到 Linode 出了 Dedicated 主機:「Linode 推出 Dedicated CPU Instances」,現在找機會測試看看,拿了 Linode 的 Dedicated (4GB) 與 AWSc5.large 比較,同樣都是 2 vCPU 與 4GB RAM。

這邊用了 n-st/nenchOpenSSL 的 speed (包括了 aes、md5、rsa、sha1 與 sha256) 測試,我把結果都貼到這邊:「Linode (Dedicated 4GB) v.s. AWS (c5.large)」。

可以看到在 CPU 方面主要的差異是 Linode 用的是 AMD,而 AWS 用的是 Intel,所以就會有蠻多不同的數字表現...

如果仔細看 OpenSSL 的測試數據,可以看到不同演算法的差異還蠻大的,馬上可以想到的應該是硬體加速方式與 cache 架構差異造成的:

  • 在 cipher 類的測試我只測了 AES (目前的主流),小的 block (16/64/256 bytes) 時 AMD 會輸一些,但大的 block (1024/8192/16384 bytes) 反而會贏不少。
  • 在 hash 類的測試中,跑 MD5 時 Linode 則是輸一些,但 SHA1 反而是贏一些,然後 SHA256 時效能好到爆炸贏了一倍 XDDD
  • 在 public key 類的測試我測了 RSA,則是 Linode 輸的蠻慘的...

如果考慮到價位大約只有 AWS 的一半,應該是還不錯...

GitHub 移除 HTTPS 中的 TLSv1/TLSv1.1,以及 SSH 中 SHA1 相關的協定

GitHub 完全移除掉 TLSv1/TLSv1.1 以及 SSH 中 SHA1 相關的協定了:「Weak cryptographic standards removed」。其中 TLSv1 與 TLSv1.1 的部份也可以從 SSL Report: github.com 這邊看到:

這是之前就預告的關閉,可以參考先前提到的文章:「GitHub 停用過時加密演算法的計畫」。

GitHub 停用過時加密演算法的計畫

先前有提到 GitHub 廢除 SSH 中的弱演算法 (參考「GitHub 明年關閉 SSH 上 SHA1 相關的 Kx (Key Exchange) 演算法」),現在宣佈詳細作法了:「Weak cryptographic standards removal notice」。

包括 HTTPS 的 TLSv1/TLSv1.1 以及 SSH 的 diffie-hellman-group1-sha1/diffie-hellman-group14-sha1 都會被廢止。而作法跟其他家不太一樣:

  • February 8, 2018 19:00 UTC (11:00 am PST): Disable deprecated algorithms for one hour
  • February 22, 2018 19:00 UTC (11:00 am PST): Permanently disable deprecated algorithms

先關閉一個小時讓沒看公告但是有注意到的人可以發現,然後過兩個禮拜後才完全關閉。跟其他家不太一樣的作法...

GitHub 明年關閉 SSH 上 SHA1 相關的 Kx (Key Exchange) 演算法

GitHub 定下落日條款了:「Weak cryptographic standards deprecation update」。

這次目標是 diffie-hellman-group1-sha1diffie-hellman-group14-sha1,同時啟用了 diffie-hellman-group-exchange-sha256

Since the announcement, we have been focusing on the impact of disabling the diffie-hellman-group1-sha1 and diffie-hellman-group14-sha1 key exchanges for SSH. As of last week, we have enabled diffie-hellman-group-exchange-sha256. This key exchange method is widely supported and will allow most legacy clients to seamlessly transition away from diffie-hellman-group1-sha1 and diffie-hellman-group14-sha1.

明年二月拔掉 diffie-hellman-group1-sha1diffie-hellman-group14-sha1

This is a very small percentage of traffic, but we would like to see if we can reduce the incompatible traffic percentage even further before disabling support for the older key exchange algorithms on February 1, 2018.