Home » Posts tagged "pseudo"

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

在 Ubuntu 16.04 上面隨機改變無線網卡的 MAC address

在「Randomize your WiFi MAC address on Ubuntu 16.04」這邊看到作者在介紹如何在 Ubuntu 上藉由改變無線網卡的 MAC address 保護自己的隱私:

Your device’s MAC address can be used to track you across the WiFi networks you connect to. That data can be shared and sold, and often identifies you as an individual. It’s possible to limit this tracking by using pseudo-random MAC addresses.

成果像是這樣:

主要應該是給 Ubuntu 的筆電使用者用...

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 超級長的演算法。

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

NSA 付錢給 RSA 放後門的事件...

Edward Snowden 再次丟出 NSA 內部文件,表示 NSA 付錢給 RSA 在演算法裡面放後門:「Exclusive: Secret contract tied NSA and security industry pioneer」。

RSA 的回應則是完全不想提到這筆錢是做什麼用的:「RSA Response to Media Claims Regarding NSA Relationship」。

現在一般在猜測,這個後門應該就是 RSA BSAFE 的預設偽隨機數產生器 Dual_EC_DRBG

對於 Dual_EC_DRBG 的攻擊,2006 年的「Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator」就這樣寫:

Our experimental results and also empirical argument show that the DEC PRG is insecure. The attack does not imply solving the ECDLP for the corresponding elliptic curve. The attack is very efficient.

在 2007 年,Bruce Schneier 寫了一篇「Did NSA Put a Secret Backdoor in New Encryption Standard?」,提到這個弱點並沒有大到使得這個演算法不堪用,但看了總是不爽:

Problems with Dual_EC_DRBG were first described in early 2006. The math is complicated, but the general point is that the random numbers it produces have a small bias. The problem isn't large enough to make the algorithm unusable -- and Appendix E of the NIST standard describes an optional work-around to avoid the issue -- but it's cause for concern. Cryptographers are a conservative bunch: We don't like to use algorithms that have even a whiff of a problem.

並且建議不要用 Dual_EC_DRBG:

My recommendation, if you're in need of a random-number generator, is not to use Dual_EC_DRBG under any circumstances. If you have to use something in SP 800-90, use CTR_DRBG or Hash_DRBG.

現在回頭看這件事情... hmmm...

Archives