Statistical-Test

當映射到特定範圍的值時,如何衡量 RC4 的安全性降低(如果有)?

  • November 3, 2011

對於使用 RC4 的項目,輸出將映射到 0 到 35 的值。因此,只有 36 個唯一的輸出值代表字母 A 到 Z 和 0 到 9。

為了避免偏差,如果值大於 251,則丟棄 RC4 字節輸出(範圍為 0 到 255)。輸出然後是 mod 36,然後將輸出映射到 0 到 35 的範圍內。

這是否通過採取此映射步驟有效地降低了 RC4 的強度,還是安全性保持不變?如何衡量證券的減少量?它是否與值 252、253、254 和 255 的失去有關?或者,由於將可能的輸出值減少到原始值的 1/7,它是否也是執行 mod 36 步驟的一個因素。

謝謝!

通過丟棄 252 到 255 的值,您可以有效地避免引入任何新的偏差;通用方法在很多地方都有表達,例如這篇文章(第 3 頁)。在之間生成隨機值 $ 0 $ 和 $ d-1 $ (包括)從產生位的 PRNG,您執行以下操作:

  1. 選擇一個整數 $ r $ 這樣 $ 2^r \geq d $ .
  2. 獲得一個 $ r $ 位字 $ x $ 來自 PRNG。
  3. 計算 $ t = \lfloor \frac{x}{d} \rfloor $ .
  4. 如果 $ d+td \gt 2^r $ , 回到第 2 步。
  5. 輸出 $ x - td $ .

您的建議等同於上面的算法 $ d = 36 $ 和 $ r = 8 $ (您使用 8 位字,俗稱“字節”)。

關於選擇有權衡取捨 $ r $ ,這取決於硬體和軟體可以做什麼。在功率很小的 8 位 CPU 上,使用字節肯定是有效的,但需要進行除法(這在 CPU 時間上會很昂貴)或使用具有 256 個條目的查找表(因此 256 字節的 ROM——可能是可以容忍的) ,因為 RC4 本身需要 256 字節的 RAM,而且 RAM 比 ROM 貴很多)。說到這一點,RC4 不一定是最好的選擇,性能方面:還有其他值得考慮的流密碼。

請注意,即使您的方法沒有引入任何偏差,您仍然有 RC4 的缺點,即原始輸出中存在一些可檢測的偏差(在實踐中沒有致命性,但足以讓學術密碼學家膽戰心驚),並且沒有任何IV,這意味著您需要為每個生成的流創建一個新密鑰(如果您的消息是連續且序列化的,您可以將它們全部視為單個大流的一部分,但每個新會話/重新啟動都必須暗示一個新密鑰;否則就是臭名昭著的“兩次墊”)。

36 代表字母和數字;對於一般消息,您可能需要為空格和基本標點符號添加一些符號(至少是單詞分隔符)。

乍一看,這個基本的 36 個密鑰流看起來至少和RC4本身一樣安全——你只是丟棄了一些輸出,而不是引入任何偏差。

請注意,RC4 的輸出開頭有一些普遍的弱點,這意味著通常建議在初始化後丟棄前 1000 個左右的字節(我必須查看詳細資訊,但是我在相當慢的電腦)。當然,永遠不要為多個消息流重複使用一個密鑰。

此外,如果您的微控制器生活在惡劣的環境中,則丟棄的字節可能可以通過側通道攻擊(定時和/或電源跟踪)進行跟踪。

引用自:https://crypto.stackexchange.com/questions/1121