Home » Posts tagged "dh"

密碼系統的 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

在攻擊時總是挑最弱的一環:NSA 對 DH 的攻擊

在「How is NSA breaking so much crypto?」這邊提到了 2012 年有文章說明 NSA 有能力解開部份的加密通訊,而後來 Snowden 所提供的資料也證實了這點:

In 2012, James Bamford published an article quoting anonymous former NSA officials stating that the agency had achieved a “computing breakthrough” that gave them “the ability to crack current public encryption.” The Snowden documents also hint at some extraordinary capabilities: they show that NSA has built extensive infrastructure to intercept and decrypt VPN traffic and suggest that the agency can decrypt at least some HTTPS and SSH connections on demand.

但在這之前一直都不清楚是怎麼解出來的,直到最近才猜測應該是 Diffie-Hellman 的強度以及實作問題:「Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice」。


We go on to consider Diffie-Hellman with 768- and 1024-bit groups. We estimate that even in the 1024-bit case, the computations are plausible given nation-state resources. A small number of fixed or standardized groups are used by millions of servers; performing precomputation for a single 1024-bit group would allow passive eavesdropping on 18% of popular HTTPS sites, and a second group would allow decryption of traffic to 66% of IPsec VPNs and 26% of SSH servers. A close reading of published NSA leaks shows that the agency’s attacks on VPNs are consistent with having achieved such a break. We conclude that moving to stronger key exchange methods should be a priority for the Internet community.

作者群給的建議有三個方向,一個是把長度加長到 2048 bits,另外一個是改用 ECDH,而最差的情況 (如果還是需要使用 1024 bits DH) 則是避免使用固定的 prime number。

CloudFlare 的 Keyless SSL 服務

CloudFlare 有兩篇公告出來:「Announcing Keyless SSL™: All the Benefits of CloudFlare Without Having to Turn Over Your Private SSL Keys」、「Keyless SSL: The Nitty Gritty Technical Details」。前面的一篇偏向公告文 (以及公關稿),而後面的一篇提到了實際運作的方式。

用兩張 Keyless SSL 的 flow 就可以知道差異了,一張是 RSA-based,一張是 DH-based:

把與 private key 相關的運算拆出來,由後方計算完成後再計算出 session key 與 client 溝通。如此一來,雖然速度比較慢,但 private key 管理在客戶自己手上...

1024bits 的 RSA 與 DH...

看到「Majority of Tor crypto keys could be broken by NSA, researcher says」,說明 NSA 曾經跟 IBM 訂作特殊晶片:

"Everyone seems to agree that if anything, the NSA can break 1024 RSA/DH keys," Graham wrote in a blog post published Friday. "Assuming no 'breakthroughs,' the NSA can spend $1 billion on custom chips that can break such a key in a few hours. We know the NSA builds custom chips, they've got fairly public deals with IBM foundries to build chips."

而目前大多數的 Tor 節點都是用 2.3.x 的版本 (使用 1024bits DHE),官方網站目前也是提供 2.3.x 下載,只有少數使用 2.4.x (使用 ECDHE),不過一時間找不到 ECDHE 用多長的 EC key,所以也不清楚抵抗能力到底到麼程度...