如何證明在密碼散列函式中找到一個循環是困難的？
我想表明在加密雜湊函式中找到循環是困難的。
**我的想法：**假設有一個黑匣子，給定一個加密雜湊函式 $ h $ , 找到一些 $ x $ 和 $ r $ 在多項式時間內，這樣應用 $ h() $ , $ r $ 時代給 $ x $ : $$ h(h(h\ldots(h(x))) = x $$
這可以用來證明該功能不抗碰撞或抗原像嗎？
如何證明在密碼散列函式中找到一個循環是困難的？
在空間上的均勻隨機函式中 $ n $ 元素，長度上的分佈 $ s $ 從任何開始的鏈 $ x $ 在它重複之前，即最小的 $ s $ 這樣 $ h^s(x) = h^{s - q}(x) $ 對於一些 $ q < s $ 或者等價於不同元素的數量 $ {x, h(x), h(h(x)), \dots, h^{n - 1}(x)} $ ， 是$$ p(s) = \frac{(n - 1)! , s}{(n - s)! , n^s}, $$誰的期望隨著 $ \frac 1 2 \sqrt{2 \pi n} $ （Harris 1960，Eqs. 3.2, 3.4, 3.11；免付費牆）。*
標準碰撞搜尋算法通過使用龜兔算法跟隨這樣的鏈來找到非循環初始鏈與循環重合的點。但是您的黑匣子以某種方式找到了沒有任何初始鏈的循環。儘管週期大小的分佈更傾向於較小而不是較大的周期，但具有預期 $ \frac 1 4 \sqrt{2\pi n} $ (Harris, Eq. 3.11), 數 $ q $ 本身在循環上的元素的分佈與 $ s $ （哈里斯，方程 3.12）。
例如，對於標準 128 位抗碰撞性所需的 256 位散列函式，偶然在一個循環中偶然發現一個元素的預期機率約為 $ 2^{-128} $ . 即使對於像 MD5 這樣的 128 位散列函式，儘管偶然在一個循環中偶然發現一個元素的預期機率約為 $ 2^{-64} $ ，確認它在一個週期上的預期成本是 $ 2^{64} $ 步驟，對於通用算法，雖然也許有一種聰明的方法可以批量或併行加速，比如van Oorschot-Wiener 碰撞搜尋機。
如果，對於某些特定的 $ b $ -bit 雜湊函式針對隨機預言機應用程序，如 SHA3-256，您找到了一種在循環中找到元素的方法，其機率大大高於 $ 2^{-b/2} $ ，或者一種確認元素是否處於循環中的方法，其成本大大低於 $ 2^{b/2} $ ，它可能值得發表，並對雜湊函式的安全性產生嚴重懷疑。
**我的想法：**假設有一個黑匣子，給定一個加密雜湊函式 $ h $ , 找到一些 $ x $ 和 $ r $ 在多項式時間內，這樣應用 $ h() $ , $ r $ 時代給 $ x $ : $$ h(h(h\ldots(h(x))) = x $$ 這可以用來證明該功能不抗碰撞或抗原像嗎？
這個黑匣子是否有助於尋找碰撞或原像並不是先驗的：顯然它本身並沒有找到碰撞，並且它沒有被可以找到原像的圖像參數化。
當然，通用碰撞搜尋領域是一門黑魔法，隱藏在一系列令人驚訝的密碼分析攻擊中，包括通常的雜湊函式碰撞搜尋，Pollard 的 $ \rho $ 對於因式分解，Pollard 的 $ \rho $ 對於離散對數、雜湊函式原像搜尋，包括 AES 密鑰恢復等。
因此，如果具有此功能的黑匣子可以有效地用於加速通用碰撞搜尋，或者如果它可以被證明沒有幫助，我不會感到驚訝，但無論哪種方式，這都是一個有趣的定理！
- Harris 1960是各種重要類型隨機映射中各種數量的機率分佈的優秀綱要。閱讀！
**我的想法：**假設有一個黑匣子，給定一個加密雜湊函式 $ h $ , 找到一些 $ x $ 和 $ r $ 在多項式時間內，這樣應用 $ h() $ , $ r $ 時代給 $ x $ :$$ h(h(h\ldots(h(x))) = x $$
我想了想，發現答案是肯定的。預言機可用於在任意函式中查找原像和碰撞$$ h : {0,1}^n \longrightarrow {0,1}^k. $$
發現碰撞
尋找碰撞 $ h $ , 定義函式 $ h’ $ 從 $ h $ 作為
$$ h’(x) = \begin{cases} x+1 \bmod 2^k& \quad \text{if } h(x) = x,\ x & \quad \text{else if } h(h(x)) = h(x),\ x+1 \bmod 2^k& \quad \text{otherwise}. \end{cases} $$
查詢預言機 $ h’ $ ，它將返回一個長度為的循環 $ 1 $ 如果 $ h $ 有一個碰撞並且它有一個固定點。如果 $ h $ 沒有固定點，那麼預言機將返回一個包含所有長度元素的循環 $ 2^k $ . 如果是這樣，循環結構可以通過（有效計算的）隨機排列重新隨機化 $ \pi $ 作為 $ \pi \circ h $ . 最終，它將有一個固定點。
預言機將（最終）返回一個 $ 1 $ -循環進入 $ h’ $ . 從施工中我們知道 $ h(y) \neq y $ （如果是這樣，這將不是一個固定點 $ h’ $ ）。但我們也知道 $ h(h(y)) = h(y) $ . 這會產生碰撞 $ (h(y), y) $ .
稍微複雜一點，但不需要固定點 $ h $ : $$ f(x|y) = \begin{cases} x|y+1 \bmod 2^k & \quad \text{if } x = y,\ x|y & \quad \text{else if } h(x) = h(y),\ x|y+1 \bmod 2^k& \quad \text{otherwise}. \end{cases} $$
這會立即產生碰撞 $ (x,y) $ , 因為不動點必須有性質 $ x\neq y $ 和 $ h(x) = h(y) $ .
尋找原像
為了找到原像 $ h^{-1}(A) $ ，我們以與之前相同的方式進行，並創建一個輔助函式如下
$$ g_A(x) = \begin{cases} x & \quad \text{if } h(x) = A,\ x+1 \bmod 2^k& \quad \text{otherwise}. \end{cases} $$ 所以，當用 $ g_A $ ，它將返回兩個可能的結果
- 一個長度循環 $ 1 $ ， IE， $ g_A(x) = x \iff h(x) = A $ ,
- 一個長度循環 $ 2^k $ ， 如果 $ h(x) \neq A $ 對所有人 $ x $ .
第一個意味著存在一個非空原像 $ A $ ，而第二個意味著它沒有。
決定版
如果我們有一個預言機，我們可以詢問是否存在長度循環 $ r $ ，然後我們可以將其轉換為搜尋版本。定義
$$ u_{A,B}(x) = \begin{cases} h(x) & \quad \text{if } A \leq x \leq B,\ x+1 \bmod 2^k& \quad \text{otherwise}. \end{cases} $$
假設我們想找到一個長度為 1 的循環。我們稱 $ \textsf{Oracle}(u_{A,B}, 1) $ ， 和 $ A = 0, B = 2^k-1 $ . 如果它返回no，那麼就沒有這樣的循環。否則，我們可以對 $ A $ 和 $ B $ 找到固定點。
總而言之，這個預言機非常強大，能夠解決 NP 中的任何問題。例如，任何 3SAT 都可以編碼為 $ h $ 它返回一個 $ 1 $ -只要滿足公式就循環。例如，任何 3SAT 都可以編碼為函式 $ h $ 它返回一個 $ 1 $ - 每當一個公式循環 $ \varphi $ （在 $ k $ 變數）滿足：
$$ v_{\varphi}(x) = \begin{cases} x & \quad \text{if } \varphi(x_0,x_1,…,x_k) = 1\ x+1 \bmod 2^k& \quad \text{otherwise}. \end{cases} $$ 如果一個 $ 1 $ -cycle 返回，然後 $ x $ 編碼這個（可能是許多中的一個）解決方案，而如果 $ 2^k $ -cycle 然後返回 $ \varphi $ 沒有令人滿意的解決方案。因此，在任意散列函式中找到一個循環 $ h $ 至少和3SAT一樣難。