Algorithm-Design

無袖數字標準

  • March 21, 2021

前提

幾個密碼原語採用隨機數字常數。為了避免懷疑設計者選擇了這樣的常量來植入後門,使用了“nothing-up-my-sleeve numbers”。這些是由一些重要常數的第一個數字構成的數字,例如 $ \pi $ , $ e $ , $ \sqrt{2} $ , … 這樣它們看起來就不會被精心設計來隱藏後門。

問題

然而,不同系統的設計者使用不同的常數。下面是從維基百科頁面複製的一些範例:

  • 小整數的小根 (SHA-1, SHA-2)
  • $ \sin 1, \sin 2, \dots $ (MD5)
  • $ e $ (DFC)
  • $ \pi $ (河豚和許多其他)
  • $ 1/\pi $ (空氣)
  • 0x123456789ABCDEFFEDCBA9876543210(霞)
  • ASCII 字元串“擴展 32 字節 k”(Salsa20)

但是如果有足夠的自由度,很明顯,無所事事的數字失去了它們的目的。例如,誰保證句子“expand 32-byte k”沒有在數千個同樣無辜的句子中被選中(“expanding 32-byte k”、“expansion of 32-byte k”、“32-byte expand k” , …) 為了隱藏後門?對於數值常數也是如此。

問題

鑑於之前的考慮,是否曾經提出過“無袖數字標準”?如果不是,為什麼不呢?

一個非常簡單的標準可能是:“使用隨機常數的密碼原語 $ C $ (如果有更多隨機常數, $ C $ 是它們的二進制連接)必須修復 $ C $ 成為二進製表示的第一個數字 $ \pi $ 。”

不使用標準的一個(可能是弱的)理由是,一些毫無意義的數字可能用於某種目的。例如,您不能將 Salsa20 的常量更改為任何值,它必須足夠不對稱。假設另一個密碼可能有不同的要求是可行的

根據這個答案

Salsa20 具有很強的旋轉對稱性。這些常數的要點是它們在旋轉下不是不變的,從而引入了不對稱性。精確值不是很重要,只要它足夠不對稱即可。

答案更詳細,引用了 DJB 本人的話。

這個答案還詳細說明了幾個加密常量,並且 HMAC 的填充常量同樣設計為不對稱的:

HMAC 的填充常量、ipad 的 0x36 和 opad 的 0x5C 被重複(對於散列函式的塊大小)並與密鑰進行異或以生成兩個散列步驟的前綴。0x36 = 0b00110110 和 0x5C = 0b01011100 - 這兩個值大約是“盡可能不同”,以避免任何依賴於內部和外部雜湊的關鍵塊之後的類似雜湊狀態的攻擊。據我了解,這主要是一種啟發式方法。

可以任意選擇的密碼學常數通常不太可能成為後門的良好候選者。可以後門的密碼學常量通常有一些要求,首先隨機生成它們是不切實際的。

但是如果有足夠的自由度,很明顯,無所事事的數字失去了它們的目的。

足夠的自由度絕對會減少使用無袖數字的好處。一篇題為“如何操作曲線標準:黑帽白皮書”的論文解釋了 ECC 曲線中使用的常數風險背後的數學原理。還提供了一個簡單的 32 位偽 NUMS 生成器的實際概念驗證程式碼。雖然如果每個人都使用相同的常數可能會更好,但風險也不會嚴重到可以說他們完全失去了目的。

誰保證句子“expand 32-byte k”沒有在數千個同樣無辜的句子中被選中(“expanding 32-byte k”,“expansion of 32-byte k”,“32-byte expand k”,.. .) 為了隱藏後門?

該特定實例是一個常量,由於它的用途,它實際上並不可疑。它只需要具有不對稱性並且是非空的。它與隨機數、計數器和密鑰一起被輸入到 ChaCha 中的隨機函式中。如果有一個特殊常量可以降低 ChaCha 核心的安全性,那麼攻擊者可以通過選擇惡意隨機數或計數器來自行利用它。

鑑於之前的考慮,是否曾經提出過“無袖數字標準”?

我不知道有任何建議的標準可以在任何地方用於所有目的。這是因為通常要求常量具有某些屬性並且不能簡單地是隨機的。不過,有一些解決方案,例如著名的 Oakley 小組採用的解決方案,它們是使用確定性生成的 $ \pi $ 作為RFC 3526中的常量。由 Richard Schroeppel 設計的特定技術可以縮放以生成任何大的偽隨機素數,用作常數而不會引起懷疑。它是專門為 Diffie-Hellman 設計的。算法是這樣的:

$ p = 2^n - 2^{n - 64} - 1 + 2^{64} (\lfloor 2^{n - 130} \pi \rfloor + c) $

這裡, $ n $ 是素數的所需大小,以位為單位,並且 $ c $ 是滿足的最小非負整數 $ p,(p-1)/2 \in \mathbb{P} $ (即確保 $ p $ 是一個安全的素數,是 DH 中素數的性質所必需的)和 $ p \equiv 7 \pmod 8 $ . 這個等式證明您可以從非結構化 NUMS 常量生成結構化 NUMS 常量(在這種情況下,從無理數生成素數)。如果我們想要 $ n = 2048 $ ,我們得到 $ c = 124476 $ (DH 組 14)。請注意,這只適用於生成素數。

如果不是,為什麼不呢?

在 S-box 中用於分組密碼的一個常見的地方是我的袖珍號碼很難使用。S-box 最好是專為良好的差分屬性而設計,而對一種密碼有益的 S-box 可能對另一種密碼不利。儘管您可以使用完全隨機生成的 S-box,但安全屬性並不理想。沒有任何理由生成的 S-box 很可能會引起密碼學家的懷疑。這發生在俄羅斯 Streebog 散列函式 (GOST R 34.11-2012) 和 Kuznyechik 分組密碼 (GOST R 34.12-2015) 中,通常認為其 S-box是非隨機設計的,因此很可能引入了一個弱點成為後門。

後門的無袖數字的想法雖然不是新的,但並不是許多密碼學家考慮過的。這主要是因為大多數後門常量需要具有極其罕見的特殊屬性。以 NIST ECC 曲線為例。這些曲線的參數有些人認為是可疑的。它們是通過將表面上的隨機輸入通過 SHA-1 並使用生成的摘要作為常數來生成的。這個想法是,弱曲線參數非常罕見,實際上不可能通過運氣找到它們,並且生成特定的後門參數需要針對 SHA-1 的原像攻擊,這被認為是不可行的(閱讀:不會發生)。

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