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

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」也是放著,不知道是卡到什麼東西,可能是專利?

Kaspersky Password Manager 的漏洞

Hacker News Daily 上看到「Kaspersky Password Manager: All your passwords are belong to us」這篇,講 Kaspersky Password Manager (KPM) 嚴重的安全漏洞,另外在 Hacker News 上的討論「Kaspersky Password Manager: All your passwords are belong to us (ledger.com)」也有提到一些有趣的東西。

標題的 All your passwords are belong to us 是出自「All your base are belong to us」這個梗的變形。

這包安全問題主要的原因是因為 KPM 沒有使用 CSPRNG,而且也沒有正確 seed,所以極為容易被猜出密碼本身。

KPM 的 Web 版使用了 Math.random(),在各家瀏覽器主要是用 xorshift128+ 實做 Math.random(),作者沒有針對這塊再花時間研究,但很明顯的 Math.random() 不是個 CSPRNG:

The underlying PRNG used by Chrome, Firefox and Safari for Math.random() is xorshift128+. It is very fast, but not suitable to generate cryptographic material. The security consequences in KPM has not been studied, but we advised Kaspersky to replace it with window.crypto.getRandomValues(), as recommended by the Mozilla documentation page previously mentioned.

Note: Math.random() does not provide cryptographically secure random numbers. Do not use them for anything related to security. Use the Web Crypto API instead, and more precisely the window.crypto.getRandomValues() method.

而桌機版則是用了 MT19937,理論上取得 624 bytes 的輸出後就可以重建整個 PRNG 的內部狀態 (於是就可以預測後續的 output),但這代表你要知道其他網站的密碼,這點其實有點困難。

但作者發現 KPM 在產生 MT19937 的 seed 只跟時間有關,超級容易被預測:

So the seed used to generate every password is the current system time, in seconds. It means every instance of Kaspersky Password Manager in the world will generate the exact same password at a given second.

於是可以直接暴力解出所有的可能性:

The consequences are obviously bad: every password could be bruteforced. For example, there are 315619200 seconds between 2010 and 2021, so KPM could generate at most 315619200 passwords for a given charset. Bruteforcing them takes a few minutes.

Hacker News 上有不少陰謀論的討論,像是:

Getting some DUAL_EC prng vibes.

Insert Kaspersky owned by Russia intelligence conspiracy here...

另外 Kaspersky 跟俄羅斯軍方的關係也是很知名,這些東西大概要到十來年後才會知道...

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。

所以要開始開發 CECPQ2 了...

CECPQ1Google 在研究對抗量子電腦的演算法,作為測試用的演算法,曾經在 Google Chrome 的 54 beta 版 (2016 年) 存活過一段時間,最近又開始在開發新一代的演算法 CECPQ2 了,這次會是基於 TLS 1.3 上測試:「CECPQ2」。

CECPQ2 will be moving slowly: It depends on TLS 1.3 and, as mentioned, 1.3 is taking a while. The larger messages may take some time to deploy if we hit middlebox- or server-compatibility issues. Also the messages are currently too large to include in QUIC. But working though these problems now is a lot of the reason for doing CECPQ2—to ensure that post-quantum TLS remains feasible.

目前對抗量子電腦的演算法好像都跟 Lattice 有關,找時間來補一下基礎理論... @_@

Ethereum Smart Contracts 裡的 PRNG

現代密碼學的安全性有很大一塊是基於亂數產生器 (RNG) 非常難被預測。如果這個前提不成立的話,利用亂數產生器產生出來的各種資訊都會被預測出來 (尤其是 Private Key)。

但真正的 RNG 需要靠硬體支援,而且產生速度很慢,一般都會使用 PRNG (Pseudorandom number generator) 產生。也就是「看起來」很亂的亂數產生器。

PRNG 通常是指在統計學上通過許多測試,像是在多種測試都是 Discrete uniform distribution,不需要防止有惡意人,可以從產生出的 PRNG 的值而推導出後續結果的用途。

在「Predicting Random Numbers in Ethereum Smart Contracts」這篇裡面,作者列出了一堆實做 Ethereum Smart Contracts 卻誤用 PRNG 的行為。

文章裡提到的問題都是因為 PRNG 拿著可被預測的資訊當作 entropy source (e.g. seed),而且提出來的範例都是拿 block 本身或衍生的資訊 (像是 block 的 hash) 來用:

  • PRNGs using block variables as a source of entropy
  • PRNGs based on a blockhash of some past block
  • PRNGs based on a blockhash of a past block combined with a seed deemed private
  • PRNGs prone to front-running

然後列了大量的程式碼當例子,建議有需要接觸的人看過一次,或是有時間的人都值得看這些負面範例... XDDD

不過作者在文章裡面也給了一堆有問題的方法,像是從外部網站取得亂數之類的 XDDD

正確的方法是使用 CSPRNG (Cryptographically secure pseudorandom number generator),這是專門設計給密碼學用的 PRNG。

CSPRNG 有幾種方法可以取得:

  • 在大多數的程式語言內都有對應的 library 可以用,另外在比較近代的瀏覽器內 (如果問 IE 的話,是 11+),可以透過 RandomSource.getRandomValues() 得到。
  • 如果打算自己搞底層而需要直接取得 CSPRNG 的產出,在 Unix-like 的環境下可以透過 /dev/urandom 取得,在 Microsoft Windows 下則可以透過 CryptGenRandom 取得。

別學作者那邊奇怪方法啊 XDDD

IBM 的 50 qubit quantum computer

IBM 在展示他們做到了什麼:「IBM makes 20 qubit quantum computing machine available as a cloud service」。

不過重點應該在目前已經拉出 50 qubit prototype 了:

The company also announced that IBM researchers had successfully built a 50 qubit prototype, which is the next milestone for quantum computing, but it’s unclear when we will see this commercially available.

18 個月從 5 qubit 到 20 qubit:

IBM has been offering quantum computing as a cloud service since last year when it came out with a 5 qubit version of the advanced computers. Today, the company announced that it’s releasing 20-qubit quantum computers, quite a leap in just 18 months. A qubit is a single unit of quantum information.

如果是以這樣的速度成長 (每 18 個月變成原來四倍),五年後就有機會殺 RSA 2048 bits 了?(大約需要 4000 個 qubit)

這比想像中快好多,難怪現在密碼學都在討論抵抗 quantum computer 的演算法...

下一代的 Tor Hidden Service

Tor 公佈了下一代的 Hidden Service (Onion Service):「Tor's Fall Harvest: the Next Generation of Onion Services」。

三年前 Facebook 自己暴力算出 facebookcorewwwi.onion 這個很特別的名字 (參考「Facebook 證明 Tor 的 Hidden Service 不安全」),這陣子連紐約時報也能暴力算出 nytimes3xbfgragh.onion 這個好名字 (參考「紐約時報網站上 Tor 的 Hidden Service (i.e. Tor Onion Service)」,這讓只有 16 chars 的 hostname 的 hashed-space 不夠大的問題愈來愈明顯 (只有 80 bits 的空間)。

如果你也想要找出一個有趣的 hostname 的話,可以用 lachesis/scallion 這樣的工具,這程式用 CPU 產生出 RSA key 後,再用 GPU 算 SHA-1

The inital RSA key generation is done the CPU. An ivybridge i7 can generate 51 keys per second using a single core. Each key can provide 1 gigahash worth of exponents to mine and a decent CPU can keep up with several GPUs as it is currently implemented.

也因為如此,Facebook 與紐約時報在上線時並不是直接在 Hidden Service 上裸奔,而是上了 HTTPS 作為 workaround,以避免資料外洩。

但這畢竟是 workaround,Tor 的人還是希望協定本身就可以提供一個夠安全的架構,而花了四年多發展出下一代的 Hidden Service,也就是這次提到的成果了。

最大的改變就是 hostname 變長很多了,從本來的 16 chars 變成 56 chars:

And finally from the casuals user's PoV, the only thing that changes is that new onions are bigger, tastier and they now look like this: 7fa6xlti5joarlmkuhjaifa47ukgcwz6tfndgax45ocyn4rixm632jid.onion.

hostname 變長主要是因為把整個 256 bits public key 放進去,可以從 spec 看到:

6. Encoding onion addresses [ONIONADDRESS]

   The onion address of a hidden service includes its identity public key, a
   version field and a basic checksum. All this information is then base32
   encoded as shown below:

     onion_address = base32(PUBKEY | CHECKSUM | VERSION) + ".onion"
     CHECKSUM = H(".onion checksum" | PUBKEY | VERSION)[:2]

     where:
       - PUBKEY is the 32 bytes ed25519 master pubkey of the hidden service.
       - VERSION is an one byte version field (default value '\x03')
       - ".onion checksum" is a constant string
       - CHECKSUM is truncated to two bytes before inserting it in onion_address

  Here are a few example addresses:

       pg6mmjiyjmcrsslvykfwnntlaru7p5svn6y2ymmju6nubxndf4pscryd.onion
       sp3k262uwy4r2k3ycr5awluarykdpag6a7y33jxop4cs2lu5uz5sseqd.onion
       xa4r2iadxm55fbnqgwwi5mymqdcofiu3w6rpbtqn7b2dyn7mgwj64jyd.onion

   For more information about this encoding, please see our discussion thread
   at [ONIONADDRESS-REFS].

這是因為在 ECC 的安全性被廣泛認可後,ECC 的優點就被拿出來用在這次設計上了:

  • 256 bits 的 ECC key 強度大約是 3072 bits RSA key (以現在最好的攻擊演算法來估算)。
  • 直接放 public key 不需要經過 hash function 計算,可以避免掉 hash function 被找到 collision 時的風險。

於是因為 hostname 放的下,就硬塞進去了 XDDD

不過如果要玩的人需要裝 alpha 版本,目前的 stable 版本還沒有這個功能:

Tor as of version 0.3.2.1-alpha supports the next-gen onion services protocol for clients and services! As part of this release, ​the core of proposal 224 has been implemented and is available for experimentation and testing by our users.