Home » Posts tagged "crypto"

對 SHA-3 的攻擊

隔壁棚剛順利打趴 SHA-1 (Google 與 CWI Amsterdam 合作,找到 SHA-1 第一個 collision),還是有人在針對比較新的演算法在攻擊:「SymSum: Symmetric-Sum Distinguishers Against Round Reduced SHA3」。

完整的 SHA-3 是 24 rounds,這次打的是 9 rounds 版本,雖然有段距離,但這等於是大進展:

Based on this we propose a new distinguisher called SymSum for the SHA3 family which penetrates up to 9 rounds and outperforms the ZeroSum distinguisher by a factor of four.

不過 SHA-3 用的人不算多,該不會在還沒成為主流就被打趴...

Google 與 CWI Amsterdam 合作,找到 SHA-1 第一個 collision

GoogleCWI Amsterdam 正式攻陷 SHA-1:「Announcing the first SHA1 collision」,然後也沒什麼意外的,現在大家都喜歡針對各種安全問題註冊一個 domain 來介紹:「SHAttered」。

shattered-1.pdfshattered-2.pdf 下載下來確認,可以看出來兩個不一樣的檔案有同樣的 SHA-1 value:

gslin@home [/tmp] [21:33/W4] sha1sum *.pdf
38762cf7f55934b34d179ae6a4c80cadccbb7f0a  shattered-1.pdf
38762cf7f55934b34d179ae6a4c80cadccbb7f0a  shattered-2.pdf

gslin@home [/tmp] [21:33/W4] sha256sum *.pdf
2bb787a73e37352f92383abe7e2902936d1059ad9f1ba6daaa9c1e58ee6970d0  shattered-1.pdf
d4488775d29bdef7993367d541064dbdda50d383f89f0aa13a6ff2e0894ba5ff  shattered-2.pdf

直接拿 pdf 來打,表達的是「一次到位」以及「既然可以攻擊 pdf,那麼其他東西當然也有可能」...

攻擊計算量的部份,這次攻擊使用的資源其實不算少,但對於大公司與大單位已經不是問題了,猜這次 Google 應該是贊助不少雲端設施:

  • 6,500 years of CPU computation to complete the attack first phase
  • 110 years of GPU computation to complete the second phase

這衍生出另外一個頭比較大的問題是 Git 目前使用的 SHA1:

GIT strongly relies on SHA-1 for the identification and integrity checking of all file objects and commits. It is essentially possible to create two GIT repositories with the same head commit hash and different contents, say a benign source code and a backdoored one. An attacker could potentially selectively serve either repository to targeted users. This will require attackers to compute their own collision.

這下得來看 Git 核心團隊要怎麼從 SHA-1 migrate 到其他 hash function 了...

NIST 開始徵求 Post-Quantum Cryptography 演算法

現有常見的幾個加密基礎在量子電腦上都有相當快速的解 (像是整數質因數分解、離散對數),只是現在建不出對應夠大台的量子電腦... 但畢竟只是時間的問題了,所以 NIST 照著慣例對外尋求能夠抵抗量子電腦的演算法:「NIST Asks Public to Help Future-Proof Electronic Information」、「Announcing Request for Nominations for Public-Key Post-Quantum Cryptographic Algorithms」。

類似於 Google 先前在 Google Chrome 上實做的 CECPQ1,對 key exchange 的部份加上保護 (Google Chrome 引入 CECPQ1,開始測試 Post-Quantum Cryptography),這次 NIST 是針對 public key crytpsystem 的部份而發的...

投稿時間在 2017 的十一月底,大約一年後就可以看到有哪些演算法要參加競賽了... 不過因為 NSA 的惡名,不知道會不會有其他單位在同個時段啟動類似的活動...

OpenSSL 1.1.0

看到「OpenSSL 1.1.0 released」這篇得知大家期待已久的 OpenSSL 1.1.0 出了,在 1.1.0 的重要新功能中,對 ChaCha20 + Poly1305 的支援算是大家等很久的:

  • Support for ChaCha20 and Poly1305 added to libcrypto and libssl

由於 RC4 已經被證明不安全,OpenSSL 內變成沒有堪用的 stream cipher,這邊總算要補上來了...

另外兩個也頗有趣的:

  • Support for scrypt algorithm
  • Support for X25519

多了些東西...

Libgcrypt 與 GnuPG 的安全性問題

在「Security fixes for Libgcrypt and GnuPG 1.4 [CVE-2016-6316]」這邊看到這個歷史悠久的 bug:

Felix Dörre and Vladimir Klebanov from the Karlsruhe Institute of Technology found a bug in the mixing functions of Libgcrypt's random number generator: An attacker who obtains 4640 bits from the RNG can trivially predict the next 160 bits of output. This bug exists since 1998 in all GnuPG and Libgcrypt versions.

就這樣的行為,對於自己用的機器應該是還好... 不過得到 4640 bits 後就可以預測接下來的 160 bits,這個 RNG 有點囧 @_@

官方目前是認為應該還好:

A first analysis on the impact of this bug in GnuPG shows that existing RSA keys are not weakened. For DSA and Elgamal keys it is also unlikely that the private key can be predicted from other public information. This needs more research and I would suggest _not to_ overhasty revoke keys.

不過如果你有絕對的安全需求的話還是可以考慮 revoke 再重新生一把...

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

Love your country, but never trust its government

Hacker News Daily 上看到的,在 Sun-2 的 bootloader 裡可以看到「Love your country, but never trust its government」這樣的字串:「Why the Sun 2 has the message "Love your country, but never trust its government"」。

這段字串是由 John Gilmore 當時在 Sun 開發時所放入的,John Gilmore 同時也是後來 EFF 創辦人之一,不過當初放入這段字串的目的是為了抓到盜版:

Yes. Vinod Khosla, first President of Sun, came to me at one point and said to put something hidden, triggered in an unexpected way, into the ROM Monitor, so that if somebody cloned the Sun Workstation (violating our software’s copyright), we could do that unexpected thing to the competitor’s demo workstation at a trade show and thereby prove that they had cloned it.

過了三十年後 John Gilmore 被挖出來問的回應也是蠻有趣的... (可以參考原文附上的信件)

而這句話現在回頭看也很經典,尤其是最近各國政府想要在 crypto system 裡面放後門的各種反應。

在攻擊時總是挑最弱的一環: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。

對 SHA-1 的攻擊進展

Bruce Schneier 這邊看到對 SHA-1 的攻擊又有新的進展了:「SHA-1 Freestart Collision」。

這次的論文不是真的找出 collision,而是對 internal compression function 攻擊,不過即使如此,這是首次攻擊完整的 80 rounds:

We present in this article a freestart collision example for SHA-1, i.e., a collision for its internal compression function. This is the first practical break of the full SHA-1, reaching all 80 out of 80 steps, while only 10 days of computation on a 64 GPU cluster were necessary to perform the attack.

論文資訊可以在「The SHAppening: freestart collisions for SHA-1」這邊看到。

Archives