看到「PuTTY vulnerability vuln-p521-bias (greenend.org.uk)」這個消息，官網的說明在「PuTTY vulnerability vuln-p521-bias」這邊。

DSA 類的簽名演算法有個得很小心的地方，是 nonce 選擇不當會造成 key recovery，這在原文有提到：

All DSA signature schemes require a random value to be invented during signing, known as the 'nonce' (cryptography jargon for a value used only once), or sometimes by the letter k. It's well known that if an attacker can guess the value of k you used, or find any two signatures you generated with the same k, then they can immediately recover your private key.

維基百科的業面上也有提到這點：

With DSA, the entropy, secrecy, and uniqueness of the random signature value {\displaystyle k} are critical. It is so critical that violating any one of those three requirements can reveal the entire private key to an attacker. Using the same value twice (even while keeping {\displaystyle k} secret), using a predictable value, or leaking even a few bits of {\displaystyle k} in each of several signatures, is enough to reveal the private key {\displaystyle x}.

這次爆炸的起因是 PuTTY 用了 SHA-512 產生 nonce，這邊只會有 512 bits 的輸出，而這對 P-521 需要 521 bits 是不夠的 (於是前 9 個 bit 會是 0)：

PuTTY's technique worked by making a SHA-512 hash, and then reducing it mod q, where q is the order of the group used in the DSA system. For integer DSA (for which PuTTY's technique was originally developed), q is about 160 bits; for elliptic-curve DSA (which came later) it has about the same number of bits as the curve modulus, so 256 or 384 or 521 bits for the NIST curves.

In all of those cases except P521, the bias introduced by reducing a 512-bit number mod q is negligible. But in the case of P521, where q has 521 bits (i.e. more than 512), reducing a 512-bit number mod q has no effect at all – you get a value of k whose top 9 bits are always zero.

而更糟的是，這不僅僅是將降了 29 的安全性，而是因為 nonce 有 bias，這在 DSA 上已經足以從 60 次的簽出的 signature 中還原出 private key (也就是文章裡提到的 key recovery attack)：

This bias is sufficient to allow a key recovery attack. It's less immediate than if an attacker knows all of k, but it turns out that if k has a biased distribution in this way, it's possible to aggregate information from multiple signatures and recover the private key eventually. Apparently the number of signatures required is around 60.

新版會改用 RFC 6979 (Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA)) 實作：

To fix this vulnerability, we've completely abandoned PuTTY's old system for generating k, and switched to the RFC 6979 technique, for all DSA and ECDSA key types. (EdDSA keys such as Ed25519 already used a different system, which has not changed.) However, this doesn't affect the fact that information about existing P521 private keys has already been leaked whenever a signature was generated using the old k generator.

所以這次的 fix 得更新 PuTTY 版本，然後重新產生 private key (會假設已經 leak 了)，然後看看系統有什麼要處理的...

To respond on your own website, enter the URL of your response which should contain a link to this post's permalink URL. Your response will then appear (possibly after moderation) on this page. Want to update or remove your response? Update or delete your post and re-enter your post's URL again. (Learn More)