一些關(guān)于隨機數(shù)的理解
Posted on 2008-08-28 23:46 Fingki.li 閱讀(886) 評論(0) 編輯 收藏 所屬分類: About development以往有聽說過“Microsoft Windows、FreeBSD不安全隨機數(shù)生成器信息泄露漏洞”之類的文章,大都是因為隨機函數(shù)存在漏洞生成不安全的隨機,導(dǎo)致可預(yù)測的加密密鑰。
About Random
隨機數(shù)是密碼學(xué)的一個重要部分,它通常作為初始化向量用于密鑰生成中。有許多測試根據(jù)數(shù)字計算給定數(shù)字序列的隨機性,它們考慮給定數(shù)定在序列中出現(xiàn)的周期,做更細(xì)致的測量,包括相同數(shù)字或其他重復(fù)形式出現(xiàn)的周期。
但統(tǒng)計隨機性的要求與加密隨機性不同。
一個數(shù)字序列在統(tǒng)計上是隨機的,但如果攻擊者可以推算出數(shù)字的序列(通過了解使用的算法和隨機種子值),那么加密是變得不安全了。
About Pseudo Random 偽隨機數(shù)
對于一串隨機的數(shù)字,最常見的描述就是沒有從前一個數(shù)字推算出后一個數(shù)字的數(shù)學(xué)方法。最好的隨機數(shù)是從物理過程中獲得的,因為實際物理程才是真正隨機的。事實上,一些隨機數(shù)生成器就是使用硬件設(shè)置來實現(xiàn),如音頻輸入或二極管。
從設(shè)計上來說,計算機是很確定的,因此不是生成隨機數(shù)的就好選擇。它們通常求助于一個生成統(tǒng)計上隨機的數(shù)字串的算法。為了確定在該算法中使用的輸入值,它們要求用戶提供一個種子值,這通常來自于系統(tǒng)時鐘、網(wǎng)卡MAC地址以及其他不同的系統(tǒng)參數(shù)。
這些隨機數(shù)字很適合于計算機游戲中的示例數(shù)據(jù)或建模物理過程。不過,它們不適合于加密。它的弱點包括以下幾點:
● 偽隨機數(shù)是周期性的。最終將重復(fù)數(shù)字序列。
● 如果使用相同的種子值,將接收到序列完全一樣的“隨機”數(shù)。因此,隨機序列與種子值一樣多。
● 隨機數(shù)可使用逆向工程。運用算法知識,強力攻擊會立即猜測到種子值。如果種子值和時間之間有相關(guān)性,攻擊者將會推算出所有后面的“隨機”數(shù)。
偽隨機數(shù)是出現(xiàn)許多臭名昭著的攻擊的主要原因。破解56 位DES從1997年1月的96 天到1999 年1月的22 小時15 分鐘,由于DES使用的偽隨機數(shù)生成算法導(dǎo)致了這個結(jié)果,有一種攻擊就是針對賭博應(yīng)用程序,這種應(yīng)用程序使用一個隨機數(shù)種子值來對紙牌進(jìn)行排序,而洗牌的可能性是有限的。在看完開始的幾張牌后,用戶可以將當(dāng)前發(fā)的牌與某種可能的洗牌序列匹配,來確定剩下牌的順序。
另一個著名的例子就是Netscape Navigator 早期版本中的取決于時間的隨機數(shù)字生成器,它泄露了動態(tài)生成的用于加密運用SSL的會話中數(shù)據(jù)的密鑰。
About Random encrypted 加密的隨機數(shù)
隨機數(shù)生成是許多加密操作不可分割的組成部分。例如,加密密鑰需要盡可能地隨機,以便使它們很難被復(fù)制。加密隨機數(shù)生成器必須生成在計算上無法進(jìn)行推算(低于 p < .05 的概率)的輸出;即,任何推算下一個輸出位的方法不得具有比隨機猜測更高的成功幾率。
為了說明一連串的隨機數(shù)字是加密安全的,必須使得用戶不可能通過計算重新生成同樣序列的隨機數(shù)。遺憾的是,運用偽隨機數(shù)字,可以很容易地重新生成同樣的序列。用戶需要知道的知識就是偽隨機數(shù)生成器算法和種子值。
通過加密保護(hù)數(shù)據(jù)基于加密算法和更為隨機的種子值就是本文要提出的方法,一個帶加密功能的隨機數(shù)產(chǎn)生器,可以應(yīng)用于需要加密隨機數(shù)的場合.為了構(gòu)成種子值,需要用不同的值組合成一個系統(tǒng)范圍內(nèi)的種子值。這些值包括調(diào)用的應(yīng)用程序可以提供的位,例如鼠標(biāo)或鍵盤動作之間的用戶反應(yīng)時間、象進(jìn)程ID和線程ID這樣的系統(tǒng)和用戶數(shù)據(jù)、系統(tǒng)時鐘、系統(tǒng)計數(shù)器、自由磁盤集群屬和散列的用戶環(huán)境塊。接著使用SHA-1散列這個值,輸出用于創(chuàng)建一個隨機數(shù)據(jù)流(用于更新系統(tǒng)種子值)。這可以起作用,是因為散列值生成了看似隨機的數(shù)據(jù),只改變源文檔(種子值)中的一個位,任何兩個輸出的散列共享它們50%的位,盡管兩個輸出只有一位之差。當(dāng)然,從理論上講,有些過程還是周期性的。例如磁盤搜索時間看似隨機的,實際取決于易于確定的因素,可以被推測出來。為了獲取更好的隨機數(shù)生成,可以采用硬件生成器,例如Intel的隨機數(shù)生成器。
說明:
創(chuàng)建加密安全的隨機數(shù)需要更多的時間,這意味著如果需要快速地在一個短時間內(nèi)生成大量隨機數(shù)(例如百萬級的數(shù)據(jù))是不適合的。在一個簡單測試中,用本文提到的RNG生成一百萬個隨機數(shù)的時間花費差不多是偽隨機數(shù)生成器所用時間的八倍之多。
相關(guān)資源:http://www.xfocus.net/articles/200209/451.html