為什麼 Math.floor(Math.random()*9000) 在 JavaScript 中不安全？

我聽說有人可以預測Math.Random()JavaScript 的輸出，但有一天我有一個想法可以結合起來Math.random()讓它Math.floor()更難預測，但一周前我看到一個使用者聲稱即使我使用了他也可以預測Math.floor()，而且只需要14 個樣本值來做到這一點。

數學上怎麼可能？

---

有問題的混凝土結構是Math.floor(Math.random()*9000)+1000。

各種API規範隨處可見。根據這個答案，大多數瀏覽器都使用 Xorshift128+，可能源自此C 原始碼。

在此評論中，OP 建議問題是關於*“Chrome 的 V8 實現”*和指向Chromium 送出的連結。

ECMA-262 /JavaScriptMath.random()中的應該返回

一個帶正號的數值，大於或等於 0 但小於 1，隨機或偽隨機選擇，在該範圍內具有近似均勻分佈，使用依賴於實現的算法或策略。

沒有什麼可以說它在密碼學上是安全的，因此唯一謹慎的做法是假設它不是。

但這不是具體的攻擊，更不用說針對*“Chrome 的 V8 實現”*的要求了。首先需要檢查如何Math.random()使用。在這裡，我們得到應用程序使用Math.floor(Math.random()*9000)+1000.

ECMA-262 指定IEEE 754 -2008 雙精度 64 位二進制格式（尾數的 52 顯式位 + 1 隱式），採用*“四捨五入，與偶數”*舍入（最多導致 2 -54的相對誤差）。由此可見，Math.random() 在 [0 … 1 - 2 -53 ] 中輸出一個值，並Math.floor(Math.random()*9000)+1000在集合 { 1000, 1001, …, 9999 } 中輸出一個大約均勻隨機的整數，因此最多約 ⌊log 2 (9000)⌋ ≈ 每個輸出的熵為 13.136 位。其餘部分未由 ECMA-262 指定，我們需要深入研究實現的功能。

---

我對那裡的 Chromium 原始碼（第 62/63 行及其連結的內容）以及Firefox 47.0和Safari 的 Webkit（最清晰）的初步分析得出的結論是，Math.random()這些的下一個值好像是由以下內容生成的：

uint64_t state0, state1;    // the 128-bit state

// update state and produce a double
double MathRandom(void) {
 uint64_t s0 = state1;  // notice the swap
 uint64_t s1 = state0;
 s1 = s1 ^ (s1 << 23);
 s1 = s1 ^ (s1 >> 17) ^ (s0 >> 26) ^ s0;
 state0 = s0;
 state1 = s1;
 if (Firefox || Webkit) // Firefox v47.0, Webkit 2019-07 thru 2020-02
   return (double)( (s0+s1) & (((uint64_t)1<<53)-1) ) / ((uint64_t)1<<53);
 else                   // ChromX V8, 2019-01 thru 2020-02
   return (double)(  s0     >> 12                   ) / ((uint64_t)1<<52);
}

這與問題中連結的Xorshift128+ 原始碼有很大不同：移位常數不同，對於 ChromX V8，64 位加法消失了。

---

在所有版本中，因為 9000 ≥ 2 13Math.floor(Math.random()*9000)+1000 ，我們可以確定每個輸出最多 13 位（ s0ChromX V8 的 63…51 位s0+s1，Firefox/Webkit 的 52…10 位）。確定該段的前 j 位的機率大於 1-2 j-13。

ChromX V8 版本是完全線性的：狀態的 128 位中的每一個都是前一個狀態位的異或組合，因此（通過歸納）任何早期狀態¹。狀態的 52 位直接輸出到 的輸出Math.random，因此我們在每一步直接得到的上述 j ≲ 13 位是狀態位。來自同一執行緒的超過 10 個（計算為 ⌈128/13⌉ ）連續輸出²，可以通過高斯消元法找到生成器的狀態，並預測其餘的（之前/之後）。這只是技術性。我將嘗試連結到程式碼片段。

Firefox/Webkit 版本更難，因為它具有原始 Xorshift128+ 的模 2 64的加法。儘管如此，雖然輸出是非線性的，但狀態是線性演變的，通過在可滿足性問題的框架中表達已知的內容並送出給最先進的 SAT 求解器，有效的攻擊是可行的，只需更多的連續輸出²。這基本上就是這次攻擊中所做的，但在每一步都有更多的狀態洩漏，使其更容易。

在這 三個 評論中，Poncho 描述了針對 Firefox/Webkit 版本的顯式攻擊策略。這些都不在了：

• 我們假設從中獲得的值Math.floor(Math.random()*9000)+1000足以始終如一地為我們提供s0+s1我們可以觀察到的位 52…40 的部分中的 9 位 52…44；如果不是，我們猜測幾位，將我們以後的工作乘以一個小因素（下面不再考慮）。
• 我們猜測初始 52…40 的 9 個對應位，以及我們可以觀察到的第一個輸出state1的加法中從位 39 到 40 出現的進位位。s0+s1在s0+s1中，操作數s0是我們猜測的，因此我們可以計算相應的新的s1。
• 該新的 9 位中的每一個都是s1初始狀態位的已知線性組合，這為我們提供了 9 個用於高斯消元的方程，旨在找到完整的初始狀態。
• 移動到下一個輸出，我們只需要猜測加法s0+s1中從第 39 位到第 40 位出現的進位位，以保持對應新的執行知識s1，並獲得 9 個附加的高斯消元方程。
• 大約 ⌈(128-9)/9⌉ = 14 個 RNG 輸出，我們有足夠的方程來求解系統，從而驗證我們的猜測。
• 我們必須按照 2 個9+14系統的順序來求解，這非常易於管理。

---

筆記：

¹ 這是 Xorshift128+ 的設計功能，可以輕鬆計算輸出序列的任意部分。

² 我們還可以利用輸出中已知位置的輸出，例如，在涉及已知數量 N 的玩家的遊戲中，特定玩家獲得的集合 { 1000, 1001, …, 9999 } 中的 N 個值中的一個。

引用自：https://crypto.stackexchange.com/questions/78417