LLL lattice basis reduction algorithm

短短幾天內看到兩個不同的地方用到了 1982 年發現的「Lenstra–Lenstra–Lovász lattice basis reduction algorithm」。

第一個是「Randar: A Minecraft exploit that uses LLL lattice reduction to crack server RNG (github.com/spawnmason)」這篇,作者群利用 LLL 去分析 java.util.Random 的內部狀態,進而得到其他玩家的地點資訊:

Every time a block is broken in Minecraft versions Beta 1.8 through 1.12.2, the precise coordinates of the dropped item can reveal another player's location.

"Randar" is an exploit for Minecraft which uses LLL lattice reduction to crack the internal state of an incorrectly reused java.util.Random in the Minecraft server, then works backwards from that to locate other players currently loaded into the world.

另外一個是在 Hacker News 上面的 id=40080651 提到,前幾天 PuTTY 的 p521 問題在底層也用到了 LLL:

LLL lattice reduction is the same algorithm that can be used for cracking PuTTY keys from biased nonces from the CVE a few days ago. 'tptacek explained a bit about the attack (and links to a cryptopals problem for it, which I can almost pretend to understand if I squint) https://news.ycombinator.com/item?id=40045377

從維基百科的內容也可以看出來 application 非常多,不光是密碼學的領域用到,看起來值得花點力氣來了解...

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

SHA-256 的 Length extension attack

Hacker News 上看到「Breaking SHA256: length extension attacks in practice (kerkour.com)」,在講不當使用 SHA-256 會導致 Length extension attack 類的安全漏洞,主要是因為 MD5SHA-1 以及 SHA-2 類的 hash function 最後生出 hash 值時會暴露出 hash function 的內部狀態而導致的問題。

這邊講的不當使用是指你沒有使用標準的 MAC,而是自己用字串組合實作造成的問題,通常是 S = H(secret || message) 這樣的形式,這邊的 || 是指字串相接。

拿 MD5 為例子,在維基百科上面可以看到 MD5 演算法對應的 pseudo code,最後輸出的部分可以看到是把 a0a1a2a3 這四個 32-bit variable 接起來,也就是把內部的狀態丟出來了:

// Process the message in successive 512-bit chunks:
for each 512-bit chunk of padded message do
    // ...

    // Add this chunk's hash to result so far:
    a0 := a0 + A
    b0 := b0 + B
    c0 := c0 + C
    d0 := d0 + D
end for

var char digest[16] := a0 append b0 append c0 append d0 // (Output is in little-endian)

於是你在可以反推 padding 的結構之後 (會需要知道 secret 的長度),就可以往後接東西繼續算下去,這就是被稱作 length extension attack。

本來只有 S = H(secret || message),你在不知道 secret 的情況下就可以疊字串到後面而且算出對應的 hash 值,變成 S' = H(secret || message || evildata)

維基百科給的例子也示範了怎麼「用」,這是原始的資料以及 server 端簽出來的 hash 值:

Original Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo
Original Signature: 6d5f807e23db210bc254a28be2d6759a0f5f5d99

於是我們想要蓋 waffle 參數,就變成:

Desired New Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo&waffle=liege

攻擊者則可以不斷的嘗試,去猜測 padding 的結構,把計算出來對應的 hash 值丟到 server 看反應,直到看到 200 OK 的回應:

New Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x02\x28&waffle=liege
New Signature: 0e41270260895979317fff3898ab85668953aaa2

如同前面提到的,這是 hash function 在最後把內部狀態直接暴露出來造成的問題,在 MD5、SHA-1、SHA-2 (SHA-256、SHA-384、SHA-512) 都有類似的問題,而比較新的 hash function 在設計時就已經有考慮到了,不會出現這個問題,像是 SHA-3

另外一方面,不要自己發明演算法,使用標準的 MAC 演算法通常是比較好的選擇。這邊用的比較廣泛的應該就是 HMAC,超過 25 年了。

結論是 SHA-256 還是堪用,儘量拿現成的演算法套,不要自己搞。

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.

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

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

Linux 打算合併 /dev/random 與 /dev/urandom 遇到的問題

Hacker News 上看到「Problems emerge for a unified /dev/*random (lwn.net)」的,原文是「Problems emerge for a unified /dev/*random」(付費內容,但是可以透過 Hacker News 上的連結直接看)。

標題提到的兩個 device 的性質會需要一些背景知識,可以參考維基百科上面「/dev/random」這篇的說明,兩個都是 CSPRNG,主要的分別在於 /dev/urandom 通常不會 block:

The /dev/urandom device typically was never a blocking device, even if the pseudorandom number generator seed was not fully initialized with entropy since boot.

/dev/random 不保證不會 block,有可能會因為 entropy 不夠而卡住:

/dev/random typically blocked if there was less entropy available than requested; more recently (see below, different OS's differ) it usually blocks at startup until sufficient entropy has been gathered, then unblocks permanently.

然後順便講一下,因為這是 crypto 相關的設計修改,加上是 kernel level 的界面,安全性以及相容性都會是很在意的點,而 Hacker News 上的討論裡面很多是不太在意這些的,你會看到很多「很有趣」的想法在上面討論 XDDD

回到原來的文章,Jason A. Donenfeld (Linux kernel 裡 RNG maintainer 之一,不過近期比較知名的事情還是 WireGuard 的發明人) 最近不斷的在改善 Linux kernel 裡面這塊架構,這次打算直接拿 /dev/random 換掉 /dev/urandom:「Uniting the Linux random-number devices」。

不過換完後 Google 的 Guenter Roeck 就在抱怨在 QEMU 環境裡面炸掉了:

This patch (or a later version of it) made it into mainline and causes a large number of qemu boot test failures for various architectures (arm, m68k, microblaze, sparc32, xtensa are the ones I observed). Common denominator is that boot hangs at "Saving random seed:". A sample bisect log is attached. Reverting this patch fixes the problem.

他透過 git bisect 找到發生問題的 commit,另外從卡住的訊息也可以大概猜到在虛擬機下 entropy 不太夠。

另外從他們三個 (加上 Linus) 在 mailing list 上面討論的訊息可以看到不少交流:「Re: [PATCH v1] random: block in /dev/urandom」,包括嘗試「餵」entropy 進 /dev/urandom 的 code...

後續看起來還會有一些嘗試,但短期內看起來應該還是會先分開...

挖 Ethereum 加熱房間...

大家都好像有過類似的想法,只是實際去做的不多 XDDD

有人把整個作法寫出來,挖 Ethereum 加熱房間:「How I heat my home by mining crypto currencies」。

從網站上的「About me」這邊看起來應該是住在奧地利?

I am a tech geek from Austin TX (USA), living on the country side in Austria and devote most of my time to my girlfriend, my company, my students and different projects.

不確定是哪個城市,先抓了首都維也納的溫度來看,看起來一到三月的平均氣溫都在個位數 (攝氏),可以理解暖氣應該是常備物品:

作者之前就先搞過一個可以一路接到 Grafana 的電錶,然後也有裝太陽能電板,但因為暖氣用電的關係而不夠用:

After building my own smart meter using 4$ in parts I started checking my electricity usage every day, which made me realize how expensive it is to heat your home. Especially since all heat and warm water in my low-energy house is made with electricity. I do have 4.8 kwp solar panels on my roof but in winter they don't cover too much for obvious reasons.

順便查了一下電價,在「Austria electricity prices」這頁可以看到奧地利的每一度要 USD$0.248:

而同一份資料上,台灣是 USD$0.101:

回到他的暖氣機,他是屬於中央空調大台機器的類型:

這種機器會恆溫輸出,所以是進風溫度愈低,就需要使用愈高的電能加熱。所以他想到的解法就是針對進風口預先用顯卡挖礦加熱 (四張 AMD 的 R9 390),這樣就可以降低暖氣機的電力消耗 (不過整體的消耗會提昇):

I had 4 older AMD R9 390 GPUs laying around (for the nVidia crowd that's basically on a level with a GTX 970) and I thought it could work.

後面就是改裝過程了,最後的結果雖然整體的電力使用量上升,但因為暖氣機的電力消耗降低,加上礦機挖到的 ETH 直接 cover 暖氣機的費用,反而讓暖氣機變免費了:

Success! I was able to lower my heat pump's electricity needs by ~50% and half of the costs are also paid for by the mining earnings

台灣的氣溫應該是用不太到 XDDD

NIST 對密碼學演算法建議的長度 (2020 版)

在「Comparing SSH Encryption Algorithms - RSA, DSA, ECDSA, or EdDSA?」這邊一路翻到「Keylength - NIST Report on Cryptographic Key Length and Cryptoperiod (2020)」這篇,裡面引用的是 NIST 的「NIST Special Publication 800-57 Part 1 Revision 5」。

在 NIST 的文件裡面,不同的演算法散落在不同地方,Keylength 整理起來後比較方便看。

想要特別拉出來講是因為看到 RSA 2048 bits 被放到 112 這個等級 (Security Strength),我一直以為是 128,不過查了一下發現好像以前是就 112 了...

Intel 的 RDRAND 爆炸...

在正妹 wens 的 Facebook 上看到的,IntelRDRAND 因為有安全漏洞 (CrossTalk/SRBDS),新推出的修正使得 RDRAND 只有原來的 3% 效能:

從危機百科上看,大概是因為這個指令集有 compliance 的要求,所以這個安全性漏洞必須在安全性上修到乾淨,所以使用了暴力鎖硬解,造成效能掉這麼多:

The random number generator is compliant with security and cryptographic standards such as NIST SP 800-90A, FIPS 140-2, and ANSI X9.82.

不過畢竟這個指令不是常常被使用,一般使用者的影響應該是還好:

As explained in the earlier article, mitigating CrossTalk involves locking the entire memory bus before updating the staging buffer and unlocking it after the contents have been cleared. This locking and serialization now involved for those instructions is very brutal on the performance, but thankfully most real-world workloads shouldn't be making too much use of these instructions.

另外這個漏洞早在 2018 九月的時候就通報 Intel 提了,但最後花了超過一年半時間才更新,這算是當初在提 Bug Bounty 制度時可能的缺點,在這次算是比較明顯:

We disclosed an initial PoC (Proof-Of-Concept) showing the leakage of staging buffer content in September 2018, followed by a PoC implementing cross-core RDRAND/RDSEED leakage in July 2019. Following our reports, Intel acknowledged the vulnerabilities, rewarded CrossTalk with the Intel Bug Bounty (Side Channel) Program, and attributed the disclosure to our team with no other independent finders. Intel also requested an embargo until May 2020 (later extended), due to the difficulty of implementing a fix for the cross-core vulnerabilities identified in this paper.

回到原來的 bug,主要還是 Intel 架構上的問題造成大家打得很愉快,現在 Intel 這邊的架構對於資安研究員仍然是個大家熱愛的地方... (因為用的使用者太多)

原來 Fully Homomorphic Encryption 已經被解啦...

Hacker News Daily 上看到「IBM Releases Fully Homomorphic Encryption Toolkit for MacOS and iOS; Linux and Android Coming Soon」這個消息,主要是 IBM Research 要放出一些跟 Fully Homomorphic Encryption (FHE) 的 library。

Homomorphic encryption 講的是直接對密文操作:(這邊的 \cdot 是操作,可能是加法,也可能是乘法,或是其他類型)

C_1 = enc(P_1)
C_2 = enc(P_2)

enc(P_1 \cdot P_2) = enc(P_1) \cdot enc(P_2) = C_1 \cdot C_2

也就是說,不需要把 Ciphertext 解成 Plaintext 處理完後再加密回去 (這有安全性與隱私的問題),而是直接對兩個 Ciphertext 計算就可以了。

之前還在學校學密碼學的時候 (大概 2005 與 2006),有翻到 Homomorphic encryption 中的 Fully Homomorphic Encryption (FHE) 是尚未被解決的問題,當時的解法都是特殊解。

剛剛因為看到上面那篇文章,查了一下發現原來在 2009 的時候 Craig Gentry 提出了一套方法,用 Lattice-based cryptogtaphy 建構出加法與乘法的操作,也就達成了 FHE 的低標。

查資料的時候發現 1) 他論文只用了十頁 2) 這是他的博班論文,解掉這個 open problem,不過看到他的博班指導教授是 Dan Boneh 好像不意外... XD

(雖然只用了十頁主要還是因為 STOC 篇幅的關係,但扣掉 circuit privacy 的部份,前面在說明建構與證明的過程只用了九頁也是很驚人)

然後接下來的幾年他又跟其他幾位學者改進了不少效能上的問題,在英文版維基百科上可以翻到有好幾個不同世代的 FHE。