SHA-256 壓縮函式的不動點

SHA256自由啟動自碰撞（全64輪）

IVec：

72BF9EF1 27B82DFB F298F3B7 22B6C32C 18A54860 4C032D91 ADD7B85B 7ED1A4AC

堵塞：

0000004D 0000006F 00000075 00000073 00000065 00000054 00000072 00000061
00000070 00000000 00000000 00000000 00000000 00000080 00000000 000001B8

輸出：

72BF9EF1 27B82DFB F298F3B7 22B6C32C 18A54860 4C032D91 ADD7B85B 7ED1A4AC

http://modalisengineering.com/crypt/sha256mt.c

這是一個問題嗎？

SHA-256 基於 Davies-Meyer 壓縮函式。容易找到不動點是這種結構的一個已知特性。

Davies-Meyer 構造的一個顯著特性是，即使底層的分組密碼是完全安全的，也可以計算構造的不動點：對於任何 $ m $ , 可以找到一個值 $ h $ 這樣 $ E_m(h) \oplus h = h $ ：一個只需要設置 $ h = E_m^{-1}(0) $ . 這是隨機函式當然不具備的屬性。到目前為止，還沒有基於此屬性的實際攻擊，但應該注意這個“特性”。

定點可用於第二次原像攻擊（給定一條消息 m1，攻擊者找到另一條消息 m2 以滿足 Kelsey 和 Schneier 的 hash(m1) = hash(m2) ） $ 2^k $ -message-block 消息及時 $ 3 \cdot 2^{n/2+1}+2^{n-k+1} $ . 如果構造不允許輕鬆創建固定點（如 Matyas-Meyer-Oseas 或 Miyaguchi-Preneel），則可以在 $ k \cdot 2^{n/2+1}+2^{n-k+1} $ 時間。請注意，在這兩種情況下，複雜度都高於 $ 2^{n/2} $ 但在下面 $ 2^n $ 當消息很長並且當消息變短時，攻擊方法的複雜性 $ 2^n $ .

（來自單向壓縮功能 - 維基百科）

感謝Samuel Neves指出這一點。

在 reddit 上看到類似的文章後，我發現了這個文章。似乎作者正在從這裡到黑客新聞再到 cryptography.reddit。

我很好奇這些固定點是否可以通過 SAT 找到，結果答案是“是”而且非常快。我對 reddit 的評論在這裡重新生成。感興趣的部分在底部，我展示了這些固定點在 SAT 中很容易找到。

我採用了SHA256 的 Cryptol 實現並添加了呈現的常量：

hAttack : [8][32]
hAttack =
 [0xad3381f1, 0x8f9dae20, 0x5419ec4e, 0xc0a9c019, 0x839a030f,
  0xe8bfad5a, 0xd308ae65, 0x3a456ff1]

mAttack : [16][32]
mAttack =
 [0x5b4adf0b, 0xb6373803, 0xdae2f3a9, 0xa951f172, 0xea5ca7b5,
  0x9ce5d74a, 0xce7a52a5, 0xb222cc78, 0xb69c9ed2, 0x60685995,
  0xc5bb23de, 0x1ffe6463, 0xa2c707da, 0xf76ac1c1, 0x71858d71,
  0xc94b58ad]

那麼計算是

hPostAttack : [8][32]
hPostAttack = SHA256Compress hAttack (SHA256MessageSchedule mAttack)

我們留下了一個問題：

SHA256> hPostAttack == hAttack
True

為了便於展示，​​我們可以定義一個助手：

attackedFunction : [8][32] -> [16][32] -> [8][32]
attackedFunction h m = SHA256Compress h (SHA256MessageSchedule m)

這是一個不錯的點，您可以詢問現代 SAT 求解器：

:sat \h m -> attackedFunction h m == h

Boolector 可以快速解決這個問題（而其他人的終止速度不足以滿足我的口味）：

(\h m -> attackedFunction h m == h)
 [0x85bc5e5e, 0x3f915388, 0xbdf7d66e, 0x391de59f, 0xf274a8a7,
  0x2cda9e8a, 0x84a49266, 0xaafb7f03]
 [0x914a03b5, 0x43a0873d, 0xbf4839a4, 0x8ee2573a, 0x83b9c634,
  0xce68bdf3, 0x28e46e7d, 0x12121529, 0x3f8cfbb2, 0x1ba42c39,
  0xe9f045cf, 0x6f591416, 0x5219af1d, 0x9f4f98a5, 0x459adb3d,
  0xec7b71c0] = True

和

(\h m -> attackedFunction h m == h && h != [0x85bc5e5e, 0x3f915388,
                                           0xbdf7d66e, 0x391de59f, 0xf274a8a7, 0x2cda9e8a,
                                           0x84a49266, 0xaafb7f03])
 [0xfbfce142, 0xf1bd9a26, 0x0d57d527, 0xb8ddd0ae, 0xd1393f0a,
  0x53a1c4b4, 0x167dcc03, 0x67ca2e21]
 [0x7ecce350, 0x47b67412, 0x06b2ba9b, 0x13ed7363, 0x6fecd8eb,
  0x03ea043d, 0xf315c864, 0xf9616041, 0x66a269ad, 0x001e71ff,
  0x2ad7cd97, 0x52125bbc, 0x253bc0d6, 0xdb1b6fa6, 0x0e8d5430,
  0x45a9f029] = True

引用自：https://crypto.stackexchange.com/questions/48580