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 的原因。

Cavium (被 Marvell 併購) 在 Snowden leak 中被列為 SIGINT "enabled" vendor

標題可能會有點難懂,比較簡單的意思就是在 Snowden 當年 (2013) 洩漏的資料裡面發現了不太妙的東西,發現 Cavium (現在的 Marvell) 的 CPU 有可能被埋入後門,而他們家的產品被一堆廠商提供的「資安產品」使用。

出自 X (Twitter) 上面提到的:

這段出可以從 2022 年的「Communication in a world of pervasive surveillance」這份文件裡面找到,就在他寫的 page 71 (PDF 的 page 90) 的 note 21:

While working on documents in the Snowden archive the thesis author learned that an American fabless semiconductor CPU vendor named Cavium is listed as a successful SIGINT "enabled" CPU vendor. By chance this was the same CPU present in the thesis author’s Internet router (UniFi USG3). The entire Snowden archive should be open for academic researchers to better understand more of the history of such behavior.

Ubiquiti 直接中槍...

而另一方面,在 Hacker News 上的討論「Snowden leak: Cavium networking hardware may contain NSA backdoor (twitter.com/matthew_d_green)」就讓人頭更痛了,像是當初 Cavium 就有發過新聞稿提到他們是 AWS CloudHSM 的供應商:「Cavium's LiquidSecurity® HSM Enables Hybrid Cloud Users to Synchronize Keys Between AWS CloudHSM and Private Clouds」。

而使用者也確認有從 log 裡面看到看到 Cavium 的記錄:

Ayup. We use AWS CloudHSM to hold our private signing keys for deploying field upgrades to our hardware. And when we break the CI scripts I see Cavium in the AWS logs.

Now I gotta take this to our security team and figure out what to do.

居然是 CloudHSM 這種在架構上幾乎是放在 root of trust 上的東西...

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

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.

這樣第四輪的選拔只剩下三個了...

Decompile to C 的工具

昨天在 Hacker News 上看到「Decompiler Explorer (dogbolt.org)」這篇,裡面列出了很多 Decompile to C 的工具 (就不用直接硬看 assembly),包括了 open source 與商用軟體:

網站本身則是提供界面可以交叉比較,不過各家的結果看起來還是有侷限...

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

GCP 推出 Cloud HSM (beta)

這算是 Google Cloud Platform 在補產品線,讓那些有強制使用 HSM 的需求的應用 (通常是遇到一定要 FIPS 140-2 的規範) 可以搬上雲端:「Introducing Cloud HSM beta for hardware crypto key security」。

從圖片上可以看到 LiquidSecurity,應該是「LiquidSecurity® General Purpose HSM Adapters and Appliances」這個產品:

如同 AWSCloudHSM 服務,GCP 的 Cloud HSM 也是提供 FIPS 140-2 Level 3:

Cloud HSM allows you to host encryption keys and perform cryptographic operations in FIPS 140-2 Level 3 certified HSMs (shown below).

演算法上,支援 AESRSAECC (NIST 的 P-256 與 P-384):

In addition to symmetric key encryption using AES-256 keys, you can now create various types of asymmetric keys for decryption or signing operations, which means that you can now store your keys used for PKI or code signing in a Google Cloud managed keystore. Specifically, RSA 2048, RSA 3072, RSA 4096, EC P256, and EC P384 keys will be available for signing operations, while RSA 2048, RSA 3072, and RSA 4096 keys will also have the ability to decrypt blocks of data.

目前只支援 us-east1us-west1,另外價錢也比軟體服務版本的 Cloud KMS 貴不少:

Billable item For keys with protection level SOFTWARE For keys with protection level HSM
Active AES-256 and RSA 2048 key versions $0.06 per month $1.00 per month
Active RSA 3072, RSA 4096 or Elliptic Curve key versions $0.06 per month $2.50 per month for the first 2,000
$1.00 per month thereafter
Destroyed key versions Free Free
Key operations: Cryptographic $0.03 per 10,000 operations $0.03 per 10,000 operations for AES-256 and RSA 2048 keys
$0.15 per 10,000 operations for RSA 3072, RSA 4096, and Elliptic Curve keys
Key operations: Admin Free Free

不過一般情況應該不會得用 CloudHSM,先有個印象就好...

CA/Browser Forum 上的會議記錄:關於密碼與 2FA 的強制要求

CA/Browser Forum 會定時將會議記錄與最後的結論公開放在網站上,有時候有些資訊還蠻有趣的。像是前幾天在「Ballot 221 - Two-Factor Authentication and Password Improvements - CAB Forum」這邊看到 CA/Browser Forum 的成員對密碼與 2FA 提出了修正提案,其中瀏覽器端只有 Microsoft 參與投票,但是被否決了...

不知道否決的原因,但是大概可以猜到幾個點。

第一個是提案提到了 NSANIST 800-63B Appendix A,這個單位不太受歡迎啊...

第二個則是「For accounts that are accessible only within Secure Zones or High Security Zones, require that passwords have at least twelve (12) characters;」這段強迫使用密碼,而現在有比密碼更安全的方案存在 (以 public key cryptography 為認證基礎的方案),像是早期的 U2F 以及今年定案的 WebAuthn

應該是這些原因吧...

TLS 1.3 進入 Proposed Standard

最近蠻熱的一個新聞,TLS 1.3 的 draft-ietf-tls-tls13-28.txt 進入 Proposed Standard 了 (在「draft-ietf-tls-tls13-28 - The Transport Layer Security (TLS) Protocol Version 1.3」這邊可以看到歷史記錄):「Protocol Action: 'The Transport Layer Security (TLS) Protocol Version 1.3' to Proposed Standard (draft-ietf-tls-tls13-28.txt)」。

沒意外的話這就會是最終版本了。如果要看 TLS 1.2 與 TLS 1.3 的差異,看維基百科上的 Transport Layer Security - TLS 1.3 會比較清楚。

大家等很久了... 像是 OpenSSL 1.1.1 其實一部分也是在等 TLS 1.3 正式推出:(出自「Using TLS1.3 With OpenSSL」)

OpenSSL 1.1.1 will not be released until (at least) TLSv1.3 is finalised. In the meantime the OpenSSL git master branch contains our development TLSv1.3 code which can be used for testing purposes (i.e. it is not for production use).

主要還是期待非 NSA 派系的 cipher (其實幾乎都是 djb 的戰果) 與 1-RTT handshake,後續等 TLS 1.3 變成 Standard Track 應該就會被各家瀏覽器開預設值了...

以色列黑了 Kaspersky 的系統,然後通報美國機密資料外洩...

前幾天在「俄羅斯政府透過卡巴斯基的漏洞,偷取美國國安局的文件」這邊提到了俄羅斯是透過 Kaspersky 的漏洞取得,後續又有些消息揭露出來了...

這件事情會被抓包,是因為以色列黑進去 Kaspersky 的系統 (???),然後發現美國的機密資料外洩 (??????),於是通報盟友美國後追查出來的 (?????????):「Israel hacked Kaspersky, then tipped the NSA that its tools had been breached」。

這過程是殺小 XDDD