隨機性 • 嚴謹密碼學：現代加密實務入門

隨機性在密碼學中無所不在：秘密金鑰的產生、加密方案本身，甚至是對密碼系統的攻擊。

沒有隨機性，密碼學就不可能存在——因為所有操作都會變得可預測，因而不安全。

本章脈絡#

隨機或不隨機——「看起來隨機」與「真的隨機」的差別，以及人們常犯的兩種判斷錯誤。
隨機性作為機率分布——用機率分布刻畫隨機過程，均勻與非均勻。
熵：不確定性的度量——如何計算熵，以及偏差如何降低熵。
RNG 與 PRNG——熵源與擴張演算法、Fortuna、密碼學與非密碼學 PRNG 之別。
真實世界的 PRNG——Unix 的 /dev/urandom、Windows 的 CryptGenRandom()、Intel 的 RDRAND。

常見錯誤#

以下四個隨機性失效的案例，各自展示了不同類型的問題。

熵源太差#

1996 年，Netscape 瀏覽器的 SSL 實作以下列虛擬碼計算 128 位元的 PRNG 種子：

global variable seed;

RNG_CreateContext()
    (seconds, microseconds) = time of day;   /* Time elapsed since 1970 */
    pid = process ID; ppid = parent process ID;
    a = mklcpr(microseconds);
    b = mklcpr(pid + seconds + (ppid << 12));
    seed = MD5(a, b);   /* Derivation of a 128-bit value using the hash MD5 */

mklcpr(x)   /* not cryptographically significant; shown for completeness */
    return ((0xDEECE66D * x + 0x2BBB62DC) >> 1);

問題在於 PID 與微秒都是可猜測的值。
假設你猜得到 seconds 的值，microseconds 只有 10^6 種可能，熵約為 log(10^6) ≈ 20 位元。
PID 與 PPID 都是 15 位元的值，本來預期會多出 15 + 15 = 30 位元的熵。但看看 b 的計算方式：三個位元的重疊使得熵只有約 15 + 12 = 27 位元。
總熵因此只有約 47 位元——而一個 128 位元的種子，本應具有 128 位元的熵。

開機時熵不足#

2012 年，研究人員掃描整個網際網路，收割 TLS 憑證與 SSH 主機的公鑰。他們發現有一小撮系統擁有完全相同的公鑰，某些情況下則是極為相似的金鑰——具體來說是共用質因數的 RSA 金鑰：兩個數 n = pq 與 n′ = p′q′ 而 p = p′，然而正常情況下不同模數的所有 p 與 q 都該相異。

進一步調查後發現：許多裝置在首次開機時就過早產生公鑰，當時尚未蒐集到足夠的熵——儘管它們用的 PRNG 本身還算不錯（通常是 /dev/urandom）。不同系統中的 PRNG 因為同一個基礎熵源（例如硬編碼的種子）而產出了相同的隨機位元。

相同金鑰源自這樣的金鑰產生流程：

prng.seed(seed)
p = prng.generate_random_prime()
q = prng.generate_random_prime()
n = p*q

若兩個系統以相同的種子執行這段程式，就會產出相同的 p、相同的 q，因而得到相同的 n。

共用質數則源自過程中額外注入熵的流程：

prng.seed(seed)
p = prng.generate_random_prime()
prng.add_entropy()
q = prng.generate_random_prime()
n = p*q

若兩個系統以相同種子執行這段程式，會產出相同的 p，但 prng.add_entropy() 注入的熵確保了 q 相異。

共用質因數的問題在於：給定 n = pq 與 n′ = pq′，只要計算 n 與 n′ 的最大公因數（GCD），就能輕易還原出共用的 p。
細節見 Heninger、Durumeric、Wustrow 與 Halderman 的論文〈Mining Your Ps and Qs〉，可於 https://factorable.net/ ^↗ 取得。

使用非密碼學 PRNG#

前面談過密碼學與非密碼學 PRNG 的差別，以及為何後者絕不該用於密碼應用。可惜許多系統忽略了這個細節。

熱門的 MediaWiki 應用（維基百科與許多其他 wiki 都在跑它）使用隨機性來產生安全令牌與臨時密碼，這些當然應該是不可預測的。不幸的是，一個現已淘汰的 MediaWiki 版本用了非密碼學的 Mersenne Twister 來產生這些令牌與密碼：

/**
 * Generate a hex-y looking random token for various uses.
 * Could be made more cryptographically sure if someone cares.
 * @return string
 */
function generateToken( $salt = '' ) {
    $token = dechex(mt_rand()).dechex(mt_rand());
    return md5( $token . $salt );
}

注意到 mt_rand() 了嗎？這裡的 mt 就是 Mersenne Twister。

2012 年研究人員展示了如何利用 Mersenne Twister 的可預測性：只要拿到少數幾個安全令牌，就能預測未來的令牌與臨時密碼。MediaWiki 隨後被修補為使用密碼學 PRNG。

強隨機性下的取樣錯誤#

最後這個 bug 顯示：即使是熵充足的強密碼學 PRNG，也可能產出有偏差的分布。

聊天程式 Cryptocat 的設計目標是提供安全通訊。它用一個函式試圖產生均勻分布的十進位數字字串（0 到 9 的數字）。

問題在於：直接把隨機位元組對 10 取模並不會得到均勻分布——因為把 0 到 255 之間所有的數字對 10 取模，0 到 9 各值出現的次數並不相等。

Cryptocat 這樣處理：

Cryptocat.random = function () {
  var x,
    o = "";
  while (o.length < 16) {
    x = state.getBytes(1);
    if (x[0] <= 250) {
      o += x[0] % 10;
    }
  }
  return parseFloat("0." + o);
};

這幾乎是完美的：只取到 10 的倍數為止的數字、其餘捨棄，本來就會得到 0 到 9 的均勻分布。

不幸的是，if 條件裡有一個差一錯誤（off-by-one error）。
產生的值的熵是 45 位元，而非應有的約 53 位元。（提示：<= 應該是 <。）