在給定所有消息塊的情況下查找 SHA-256 的 IV 值
給定所有消息塊 $ w[i],i \in 0:63 $ 並假設 $ n<128 $ （任意）位 $ x_1,x_2,…,x_n $ 的 IV 值未知（例如， $ h_7 $ 位未知），而其他 IV 值與 SHA-256 算法中的值一致。讓 $ h_{i}^{j} $ 表示 $ i $ -th 的雜湊 $ j $ - 即是$$ (h_{0}^{0},h_{1}^{0},…,h_{7}^{0})\overbrace{\mapsto}^{SHA256}(h_{0}^{1},h_{1}^{1},…,h_{7}^{1})\overbrace{\mapsto}^{SHA256} …\overbrace{\mapsto}^{SHA256}(h_{0}^{64},h_{1}^{64},…,h_{7}^{64}), $$和 $ (h_{0}^{64},h_{1}^{64},…,h_{7}^{64}) $ 取決於 $ n $ 未知的 IV 位。現在讓我們採取 $ n $ （任意）位 $ y_1,y_2,…,y_n $ 的 $ (h_{0}^{64},h_{1}^{64},…,h_{7}^{64}) $ 並為它們賦值。
**問：**有沒有可能找到 $ x_1,x_2,…,x_n $ 給出分配的值 $ y_1,y_2,…,y_n $ 比窮舉搜尋更快？
備註。可以注意到，對於固定 $ w $ 功能
$ \operatorname{SHA256}{w}^{-64}(h{0}^{64},h_{1}^{64},…,h_{7}^{64}) = (h_{0}^{0},h_{1}^{0},…,h_{7}^{0}) $ 可以解析構造，所以如果 $ (h_{0}^{64},h_{1}^{64},…,h_{7}^{64}) $ 已知，很容易獲得IV值。然而，如果只是 $ n<128 $ 位被分配它需要找到 $ 2^{256-n} $ 最壞情況下的原像。
根據所問的問題，不，不可能恢復失去的部分 $ h_0^0,h_1^0,\ldots,h_7^0 $ 比蠻力搜尋更快。
問題指出：
$ \operatorname{SHA256}_{w}^{-64}(h_0^{64},h_1^{64},\ldots,h_7^{64})=(h_0^0,h_1^0,\ldots,h_7^0) $ 可以解析構造
很可能，這甚至不是一個函式，因為真正的 SHA-256 壓縮函式 $ \operatorname{SHA256}_{w} $ , 以後 $ F $ , 很可能不是雙射，因此 $ F^{-1} $ 不是一個功能，由於構造 $ F $ 作為 $$ \begin{align}F: {0,1}^{256}&\longmapsto{0,1}^{256}\ h’\quad&\longrightarrow;F(h);\underset{\text{def}}=;G(h)\boxplus h\end{align} $$ 在哪裡
- $ h $ 表示向量 $ h_0,h_1,\ldots h_7 $ 同化為一個 256 位比特環 $ {0,1}^{256} $
- $ G $ 是一個雙射，完全由 512 位填充消息塊確定（取自 $ w $ ) 在這個壓縮步驟，以及 SHA-256 的規範。 $ G $ 本質上是具有已知子密鑰的 64 輪分組密碼。一個有用的心智模型 $ G $ 是集合的任意雙射 $ {0,1}^{256} $ .
- $ \boxplus $ 是加法模 $ 2^{32} $ 32 位字，集合的正常組操作 $ {0,1}^{256} $ .
會心 $ h’=G(x)\boxplus h $ ，我們不知道找到未知的方法 $ h $ 比蠻力搜尋更好，並且在簡單的模型下顯然沒有更好的搜尋 $ G $ 作為實現任意雙射的預言機。
如果我們還知道一部分 $ h $ [例如 $ h_7 $ 就像第一個壓縮步驟的問題一樣，甚至 $ h_1,h_2\ldots,h_{7} $ ]，它所做的最好的事情是稍微簡化了我們面臨的組合問題，但最有名的解決它的方法本質上是蠻力，在隨機預言模型下顯然如此。
因此，即使問題是針對單個壓縮步驟並且已知完整輸出，也沒有已知的方法可以比搜尋未知輸入位更有效地解決它，但代價是 $ \mathcal O(2^n) $ . 更多的壓縮步驟使情況更加絕望。
這個後期的評論引入了一個激進的變體，壓縮函式簡化為 $ F=G $ . 現在 $ F^{−1} $ 是一個函式，可以通過將 64 輪中的每一輪取反來輕鬆計算 $ G $ 以相反的順序。
維基百科的壓縮主循環虛擬碼：
for i from 0 to 63 S1 := (e rightrotate 6) xor (e rightrotate 11) xor (e rightrotate 25) ch := (e and f) xor ((not e) and g) temp1 := h + S1 + ch + k[i] + w[i] S0 := (a rightrotate 2) xor (a rightrotate 13) xor (a rightrotate 22) maj := (a and b) xor (a and c) xor (b and c) temp2 := S0 + maj h := g g := f f := e e := d + temp1 d := c c := b b := a a := temp1 + temp2可以倒置為：
for i from 63 downto 0 S1 := (f rightrotate 6) xor (f rightrotate 11) xor (f rightrotate 25) ch := (f and g) xor ((not f) and h) S0 := (b rightrotate 2) xor (b rightrotate 13) xor (b rightrotate 22) maj := (b and c) xor (b and d) xor (c and d) temp2 := S0 + maj temp1 := a - temp2 a := b b := c c := d d := e - temp1 e := f f := g g := h h := temp1 - S1 - ch - k[i] - w[i]注意：當倒退時
S1，ch、S0、maj和temp2是從不同的變數中計算出來的，否則使用與前進相同的公式；和temp1(resp.dandh) 是通過使用基本代數反轉用於正向計算a(resp.eandtemp1) 的公式來計算的。如果我們知道整個輸出 $ h^{64} $ ，我們可以有效地從它走回 $ h^0 $ 有 64 個評價 $ F^{−1} $ 由 64 個已知片段確定的功能 $ w $ ，與向前散列一樣有效。IV的部分知識將無濟於事。
但在這個問題中我們只知道 $ n $ 出 256 位 $ h^{64} $ . 最好的攻擊是問題中建議的受過教育的蠻力，代價是 $ \mathcal O(2^{\min(n,256-n)}) $ . 這是通過在未知輸入位中搜尋小的 $ n $ , 和未知的輸出位大 $ n $ . 論據：（修改後的）壓縮函式的整個鏈形成雙射，並且在隨機預言模型中，最好的攻擊就是這種蠻力。