向更廣泛的受眾解釋 Dual EC DRBG 的弱點？
我有一群高級（非技術）高管和高級技術人員，他們在 Dual_EC_DRBG 中採取了後門，並將其視為一般橢圓曲線的弱點。在我的展示文稿中，我最多可以花大約 10 分鐘來解決這個問題 - 不多了。
- 我如何通過數學直覺（而不是核心數學證明）向這樣的聽眾解釋 EC_DUAL_DRBG 的弱點？
- 我如何區分 Dual EC DRBG 中的弱點與 EC 中的任何弱點（尤其是 NSA 的 Suite B EC 曲線 - 具有諷刺意味，嗯？）。對我來說，Dual EC DRBG 的弱點很明顯（事實上，在事實之後）選擇了恆定曲線點。但是 NIST EC 曲線也有常數，儘管性質大不相同（大素數模數）。控制偏執狂……並不容易。
請注意，非技術人員非常聰明——只是不是安全專家。所以我想尊重這一點，而不是把它弄得太笨拙。
我不會試圖解釋後門的數學原理。只需解釋一下 NSA 在其中隱藏了一個秘密後門。
相反，我建議關注歷史和背景。例如，您可以解釋 Crypto.AG，他們如何使用 RNG 來幫助 NSA 監視他們的客戶。您可以解釋隨機數生成器如何成為密碼學中的一個經典弱點，因為 RNG 已被安裝後門，任何知道後門的人都可以恢復您的所有密鑰。您還可以解釋這很難檢測到：因為 RNG 應該輸出看起來隨機的位，如果它實際上是 NSA 可以預測但其他人無法預測的偽隨機位（如果這些位實際上來自 PRNG，那麼NSA 知道種子，但沒有其他人知道），這很難通過黑盒測試或通過檢查所謂的隨機位來檢測。
如果你願意，你可以解釋一下，早在 2006 年，密碼學家就發現了允許後門的數學結構，但迴避提出任何指控，因為，嘿，國家安全域肯定不會這樣做——那太令人震驚了似乎很難想像它實際上包含一個後門。而現在情況發生了變化：看起來難以想像的東西，實際上是現實。因此，您可以解釋這如何讓加密社區大開眼界，以及它將如何改變我們對未來政府標準和系統設計的看法。
然後你可以解釋影響。您可以解釋為什麼認為影響相對較小，因為大多數人從 2007 年開始注意到 Bruce Schneier 的警告並且沒有使用 Dual_EC_DRBG。但是，您可以解釋至少一個主要的加密庫（RSA 的 BSAFE）確實使用它，原因尚不清楚，因此這可能會對未知數量的已部署產品產生未知影響。你可以解釋這個後門如何可能只允許 NSA 解密流量，而不是其他任何人。最後，你可以解釋最大的影響是什麼：對加密標準和美國公司失去信任的可能性。我不確定我們是否已經看到公眾失去信任——我認為人們仍然相信Google、蘋果和亞馬遜會支持他們——但如果發生這種情況，
我看到你想解釋數學。好的，這裡有一個解釋。我將攻擊 Dual_EC_DRBG 的簡化版本，但簡化不會改變攻擊的任何本質。
算法規範指定了一條橢圓曲線，它基本上只是一個有限循環（因此是阿貝爾）群 $ G $ . 該算法還指定了兩個組元素 $ P,Q $ . 它沒有說明他們是如何被選中的。我們所知道的是，他們是由 NSA 的一名僱員選擇的。在簡化算法中，PRNG 在時間的狀態 $ t $ 是某個整數 $ s $ . 要向前執行 PRNG 一步，我們執行以下操作：
- 我們計算 $ sP $ （回想一下，我們使用加法組表示法；這與 $ P^s $ ，如果你更喜歡乘法符號），將其轉換為整數，然後呼叫它 $ r $ .
- 我們計算 $ rP $ ，將其轉換為整數，然後呼叫它 $ s’ $ （這將成為下一步的新狀態）。
- 我們計算 $ rQ $ 並將其作為此步驟的 PRNG 輸出輸出。（好的，從技術上講，我們以特定方式將其轉換為位串，但您可以忽略它。）
現在這是觀察結果：我們幾乎可以保證 $ P=eQ $ 對於某個整數 $ e $ . 我們不知道什麼 $ e $ 是，我們很難找到它（這需要解決橢圓曲線上的離散對數問題，所以這可能很難）。然而，由於 NSA 選擇了這些值 $ P,Q $ ，它可以通過挑選來選擇它們 $ Q $ 隨機，採摘 $ e $ 隨機，並設置 $ P=eQ $ . 特別是，國家安全域本可以選擇他們，以便他們知道 $ e $ .
這裡的數字 $ e $ 是一個後門，可讓您破解 PRNG。假設 NSA 可以觀察到 PRNG 的一個輸出，即 $ rQ $ . 他們可以乘以 $ e $ ， 要得到 $ erQ $ . 現在註意到 $ erQ = r(eQ) = rP = s’ $ . 因此，他們可以推斷 PRNG 的下一個狀態是什麼。這意味著他們了解您的 PRNG 的狀態！這真的很糟糕——在只觀察了 PRNG 的一個輸出之後，他們幾乎不需要任何工作就可以預測 PRNG 的所有未來輸出。這幾乎是 PRNG 可能發生的最糟糕的突破。
當然，只有知道的人 $ e $ 可以打破PRNG。所以這是一種特殊的後門：NSA 大概知道如何破解 Dual_EC_DRBG，但其他人不太可能知道如何破解它。即使我們現在知道後門存在，但很難恢復秘密後門 $ e $ ，因為這需要解決離散對數問題。
唔。也許這仍然太複雜了，因為它需要了解加法組和一些關於橢圓曲線的知識……呃。好的。所以，讓我和你分享一個類似的東西：一個類似於 Dual_EC_PRNG 的 PRNG，不同之處在於它使用整數，而不是橢圓曲線。特別是，一切在概念上基本相同——後門將相同，PRNG 將相同——這將更容易理解，無需任何橢圓曲線密碼學背景。希望這會給直覺帶來更好的感覺。
- **PRNG。**該算法指定一個素數 $ p $ , 和兩個整數 $ g,h $ 都小於 $ p $ . 該算法告訴您 PRNG 在每個時間點的狀態是某個數字 $ s $ 滿足 $ 1\le s < p $ . 要將 PRNG 向前推進一次迭代，您設置 $ r = g^s \bmod p $ , $ s’ = g^r \bmod p $ , 將狀態更新為 $ s’ $ , 和輸出 $ t = h^r \bmod p $ .
- **後門。**後門是一個秘密號碼 $ e $ 這樣 $ g=h^e \bmod p $ . 創建算法規範的 NSA 選擇了 $ g,h $ 通過採摘 $ h $ 隨機，採摘 $ e $ 隨機，設置 $ g=h^e \bmod p $ ，然後發布 $ g,h,p $ （但保持 $ e $ 秘密，因為 $ e $ 是後門）。
- **打破 PRNG。**以下是 NSA 如何破解此 PRNG。假設他們觀察到一個輸出 $ t $ 來自 PRNG。他們計算 $ t^e \bmod p $ . 請注意
$$ t^e = (h^r)^e = h^{re} = (h^e)^r = g^r = s’ \pmod p. $$ 這意味著他們能夠計算 $ s’ $ ，PRNG 的下一個狀態。因此，在僅觀察 PRNG 的一個輸出之後，他們可以推斷 PRNG 的下一個狀態，從而預測 PRNG 的所有未來輸出將是什麼。
例如，假設您使用此生成器生成一個隨機 IV（並以明文形式發送），然後使用此生成器生成一個會話密鑰，然後在該會話密鑰下加密內容。NSA（竊聽您的通信並因此可以看到 IV）知道 IV 是此 PRNG 的輸出，並且可以使用他們的後門來推斷 PRNG 的狀態並預測其未來的輸出 - 因此他們可以預測您的會話密鑰並解密所有後續流量。你已經被擁有了！
我希望這能給出直覺。Dual_EC_DRBG 的問題與我剛才描述的這個假設的 PRNG 的問題完全相同。希望這很容易理解：如果您了解 Diffie-Hellman 的工作原理，您就可以理解為什麼它會被破壞。