Home » Posts tagged "mwc1616"

V8 Engine 的 Math.random() 在新版被重寫了...

先前在「V8 的 Math.random() 亂度不足的問題」提到 Math.random() 因為使用 MWC1616 (Fast random number generation using 128 bit multimedia extension registers on Pentium class machines) 而不夠亂的問題。

這個問題在新版 V8 Engine 提出改善了:「There's Math.random(), and then there's Math.random()」。

Untitled drawing

新實作的方法是 xorshift128+,擁有極長的 period length:

This has been pointed out to us, and having understood the problem and after some research, we decided to reimplement Math.random based on an algorithm called xorshift128+. It uses 128 bits of internal state, has a period length of 2128 - 1, and passes all tests from the TestU01 suite.

將會在 Google Chrome 49 (目前是 47) 引入:

The new implementation landed in V8 4.9.41.0 within a few days of us becoming aware of the issue. It will become available with Chrome 49. Both Firefox and Safari switched to xorshift128+ as well.

同時還是再次提醒,這不是 CSPRNG,要用在密碼學相關應用還是要用專門的 library 來產生 pseudo random number:

Make no mistake however: even though xorshift128+ is a huge improvement over MWC1616, it still is not cryptographically secure.

V8 的 Math.random() 亂度不足的問題

在「TIFU by using Math.random()」這篇看到作者踩到地雷,於是在討論 V8 EngineMath.random() 的亂度不足。

其實這個問提早在 2012 年就有人在 StackOverflow 上詢問:「Why is Google Chrome's Math.random number generator not *that* random?」,而且也回答得很清楚。

而 Mozilla 這邊在 2006 年也被提出了類似的問題:「Bug 322529 - Upgrade Math.random() to a better algorithm, such as Mersenne Twister」。

文章中間花了許多篇幅講 PRNG 的介紹,以及 cycle length 的說明,重點其實在結論的部份。

主要是因為 V8 Engine 的 Math.random() 實作的是 MWC1616 演算法 (Fast random number generation using 128 bit multimedia extension registers on Pentium class machines),而這個演算法用起來也綁手綁腳:

If you’re only using the most significant 16 bits it has a very short effective cycle length (less than 2³⁰).

有兩個方向可以改善 (不衝突的方向),一個是使用 CSPRNG (保證有極長的 cycle length),另外一個請求 V8 Engine 把 Math.random() 的演算法換掉,像是 MT19937 這類 cycle length 超級長的演算法。

不知道後續有沒有機會改善...

Archives