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

Amazon SES 總算支援 2048 bits RSA key 了

Amazon SES 總算是支援 2048 bits RSA key 了:「Amazon SES now supports 2048-bit DKIM keys」。

然後講一些幹話... 隔壁微軟早在 2019 年就支援 2048 bits RSA key 了:

Until now, Amazon SES supported a DKIM key length of 1024-bit, which is the current industry standard.

另外用 ECC 演算法的一直都沒進 standard,像是已經先 book 了 RFC 8463 位置的 Ed25519,在 draft 狀態放好久了:「A New Cryptographic Signature Method for DomainKeys Identified Mail (DKIM)」,還有用 ECDSA 的「Defining Elliptic Curve Cryptography Algorithms for use with DKIM」也是放著,不知道是卡到什麼東西,可能是專利?

CloudFront 宣佈支援 ECDSA 的 Certificate

Amazon CloudFront 宣佈支援 ECDSA 的 certificate:「Amazon CloudFront now supports ECDSA certificates for HTTPS connections to viewers」。

用主要是讓 certificate 更小,讓 HTTPS 建立時的過程更快 (包括了傳輸的速度與計算的速度):

As a result, conducting TLS handshakes with ECDSA certificates requires less networking and computing resources making them a good option for IoT devices that have limited storage and processing capabilities.

很久以前好像有看到資料說 256 bits 的 EC 運算量跟 768~1024 bits 的 RSA 差不多,但一時間找不到資料...

目前 CloudFront 只支援 NIST P-256 (secp256r1,或稱作 prime256v1):

Starting today, you can use Elliptic Curve Digital Signature Algorithm (ECDSA) P256 certificates to negotiate HTTPS connections between your viewers and Amazon CloudFront.

但 NIST P-256 一直為人詬病,在「SafeCurves: choosing safe curves for elliptic-curve cryptography」這邊可以看到 NIST 宣稱的效率設計實際上都不是真的:

Subsequent research (and to some extent previous research) showed that essentially all of these efficiency-related decisions were suboptimal, that many of them actively damaged efficiency, and that some of them were bad for security.

但目前標準是往 NIST P-256、NIST P-384 與 NIST P-521 靠攏 (主要是受到 CA/Browser Forum 的限制),要其他 curve 的 certificate 也沒辦法生,目前可能還是繼續觀望...

Amazon Aurora (MySQL) 推出相容於 MySQL 5.7 的版本

Amazon Aurora (MySQL) 推出相容於 MySQL 5.7 的版本了:「Amazon Aurora is Compatible with MySQL 5.7」。

不過網站上的介紹還沒更新:

Amazon Aurora is a relational database service that combines the speed and availability of high-end commercial databases with the simplicity and cost-effectiveness of open source databases. The MySQL-compatible edition of Aurora delivers up to 5X the throughput of standard MySQL running on the same hardware, and is designed to be compatible with MySQL 5.6, enabling existing MySQL applications and tools to run without requiring modification.

5.7 其中一個賣點在於支援 Spatial index (透過 R-tree),不過 AWS 的版本看起來是自己用 B-tree 加上 Z-order curve 實做:「Amazon Aurora under the hood: indexing geospatial data using Z-order curves」。

我覺得看看就好啦,拿 244GB RAM 的 r3.8xlarge 跑 1GB 的 data set,當大家是傻逼嗎...

密碼系統的 Monoculture

這篇文章講到最近密碼系統的現象:「On the Impending Crypto Monoculture」。

目前常在用的密碼系統包括了 RSA、DH、ECDH、ECDSA、SHA-2、AES 這些演算法,而最近這幾年大家在推廣使用的演算法都出自於同一個人手裡,Dan Bernstein,也就是 djb:

A major feature of these changes includes the dropping of traditional encryption algorithms and mechanisms like RSA, DH, ECDH/ECDSA, SHA-2, and AES, for a completely different set of mechanisms, including Curve25519 (designed by Dan Bernstein et al), EdDSA (Bernstein and colleagues), Poly1305 (Bernstein again) and ChaCha20 (by, you guessed it, Bernstein).

這些演算法或是定義,包括了 Curve25519、EdDSA、Poly1305、ChaCha20。而這篇文章試著說明造成這樣情況的背景以及原因,以及這樣會導致什麼問題。

當實際分析時會發現,檯面上沒幾個能用的演算法,而看起來能用的那幾個又有專利 (像是 OCB),不然就是看起來被 NSA 放了一些說明不了的參數 (像是 P-256 Curve)。

然後 djb 弄出來的演算法不只看起來乾淨許多,也直接用數學模型證明安全性。而且他的實作也很理論派,像是還蠻堅持要做到 constant time implementation 以避開各種 side channel attack。

就... 理論很強,又很實戰派的一個人啊,檯面上真的沒幾隻可以打的贏啊 XD

OpenSSL 的 ECDH 中,224 bits 速度比 160/192 bits 快的原因

openssl speed ecdh 的時候發現很特別的現象:

Doing 160 bit  ecdh's for 10s: 40865 160-bit ECDH ops in 9.99s
Doing 192 bit  ecdh's for 10s: 34169 192-bit ECDH ops in 9.99s
Doing 224 bit  ecdh's for 10s: 60980 224-bit ECDH ops in 9.99s
Doing 256 bit  ecdh's for 10s: 34298 256-bit ECDH ops in 10.00s
Doing 384 bit  ecdh's for 10s: 9602 384-bit ECDH ops in 10.00s
Doing 521 bit  ecdh's for 10s: 9127 521-bit ECDH ops in 9.99s

原因是 Google 這篇論文的貢獻:「Fast Elliptic Curve Cryptography in OpenSSL」,開頭就提到:

We present a 64-bit optimized implementation of the NIST and SECG-standardized elliptic curve P-224.

而實際成果:

full TLS handshakes using a 1024-bit RSA certificate and ephemeral Elliptic Curve Diffie-Hellman key exchange over P-224 now run at twice the speed of standard OpenSSL, while atomic elliptic curve operations are up to 4 times faster.

OpenSSLCHANGES 也可以看到對應的修改,不只是 NIST-P224 有被改善,其他的 NIST-P256 與 NIST-P521 也都有被改善:

Add optional 64-bit optimized implementations of elliptic curves NIST-P224, NIST-P256, NIST-P521, with constant-time single point multiplication on typical inputs.

頗特別的...

AWS ELB 加強安全性...

AWS ELB 加強對 SSL 安全性的功能:「Elastic Load Balancing – Perfect Forward Secrecy and Other Security Enhancements」。

第一個是支援 PFS (Perfect Forward Secrecy),愈大多數的實做相同,是使用 ECDH

第二個是 Server Order Preference,由 server 這邊決定最終的 cipher。

最重要的是第三個,也就是「懶人包」。推出新的 security policy ELBSecurityPolicy-2014-01,把上面兩個都設進去了。

這次的升級是對安全性的提昇...

NSA 付錢給 RSA 放後門的事件...

Edward Snowden 再次丟出 NSA 內部文件,表示 NSA 付錢給 RSA 在演算法裡面放後門:「Exclusive: Secret contract tied NSA and security industry pioneer」。

RSA 的回應則是完全不想提到這筆錢是做什麼用的:「RSA Response to Media Claims Regarding NSA Relationship」。

現在一般在猜測,這個後門應該就是 RSA BSAFE 的預設偽隨機數產生器 Dual_EC_DRBG

對於 Dual_EC_DRBG 的攻擊,2006 年的「Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator」就這樣寫:

Our experimental results and also empirical argument show that the DEC PRG is insecure. The attack does not imply solving the ECDLP for the corresponding elliptic curve. The attack is very efficient.

在 2007 年,Bruce Schneier 寫了一篇「Did NSA Put a Secret Backdoor in New Encryption Standard?」,提到這個弱點並沒有大到使得這個演算法不堪用,但看了總是不爽:

Problems with Dual_EC_DRBG were first described in early 2006. The math is complicated, but the general point is that the random numbers it produces have a small bias. The problem isn't large enough to make the algorithm unusable -- and Appendix E of the NIST standard describes an optional work-around to avoid the issue -- but it's cause for concern. Cryptographers are a conservative bunch: We don't like to use algorithms that have even a whiff of a problem.

並且建議不要用 Dual_EC_DRBG:

My recommendation, if you're in need of a random-number generator, is not to use Dual_EC_DRBG under any circumstances. If you have to use something in SP 800-90, use CTR_DRBG or Hash_DRBG.

現在回頭看這件事情... hmmm...

橢圓曲線密碼學...

Bruce Schneier 的 blog 上看到這篇推薦文章,介紹橢圓曲線密碼學的基礎:「Elliptic Curve Crypto Primer」。被推薦的文章是「A (relatively easy to understand) primer on elliptic curve cryptography」這篇。

當初在學校的時候學這個是靠著數學系代數的背景硬吃,看了一下這篇介紹,講得超級淺啊...

建議要再研究的人還是看看 1985 年的「Elliptic curve cryptosystems」,只有七頁,這篇就是 ECC 的起源。