Hash

SHA-3 中的自由啟動碰撞

  • July 28, 2017

鑑於構成 SHA-3 的五個子功能是可逆的，個人可以產生他們選擇的特定輸出。以下是據我所知的 SHA-3(256) 中自由啟動衝突的範例。兩個初始向量都違反了 FIPS-202 中概述的填充協議。據了解，next_block 值已正確填充，並理解此理論消息的位長度是 1088 的整數倍。我省略了在消息中附加空字元串的步驟，因為這對於本範例來說是不必要的步驟。

選擇的 initial_vectors 是否代表可以傳遞給 SHA-3 內部函式的可能輸入狀態？

initial_vector_0=[
    '0001100010111010010011010010100010111011000100001110101001001100',
    '1111101100111100001110010110111001100001110101101101101000100001',
    '0110010010111111000111101000000100010010111101011110001011010101',
    '0001111000111111111100011001100001110011100010010111100100000110',
    '1101000001010010011100110101010101001111100100001111111111110011',

    '0110101010110100110110010001100111011000100110001101000110011111',
    '0101110001101010100010000100001101001111111000001101011000000101',
    '1101001100001000101001000000111100011100000111011011010110000010',
    '1111001100100111011011110011000101010100111010000001011100100111',
    '0010101111001100000101011000100100100010010111111000111100101000',

    '0100011010101111010000010011011101110010111001100101000000011101',
    '0010001101111100001010110101000101011100110111010110110011110100',
    '1110101011110000111111000001010011001011100101010100011101101100',
    '1100110001100111011001110001001010000011110001110001101101000011',
    '0000010011101111010111001100000111000101010001111001101010101011',

    '1101011111011011011011110011010011001101011011100101101010000111',
    '0011010101110100101011101010100101010001010011100001111010001001',
    '1011100001001010001000001010110000111010001110101001100101011000',
    '0000100000101101111101001000001011011001000101000001000010010101',
    '0111011010010110100111111111110010011011000110111110000001010101',

    '1010000111011001001101011110110000001001100010010110000000011100',
    '1001001110001111000001000110100001100000110100011101000100100110',
    '1011110010000110001111010011110101111101110001110010100010010001',
    '1110101110011000011000000111010011010111101000110010110011011101',
    '0001111011111100001000110001011101001110110001101110010000101001']

next_block_0=[
    '1100111010000010101001100011001000100110110111001011010111101001',
    '0101110001011011111011101001101011001101001001011000111101111100',
    '1001001101001000101111101111011110010101110011111001001100000001',
    '0101000010111111011000000000110001000111011100110001110110000010',
    '0010001100100011010100011011010000110101111100110010110010010010',

    '0010101001101000110000111111000110011000111000011010011101001011',
    '1110110001111001011100011110100100010001100000010101010101001001',
    '1001011000001110010101100001110011111001001000000000010011000010',
    '1011111001011111000001101011000110110000111110011101001011100011',
    '0001100111010001111110011001010011000111011010110010010000101010',

    '0000101000001111101000101001000110001111000100011111010101110001',
    '0000011101010101001110010000000111011100010001101010101100111010',
    '1010101011000011110001111000111011000010110011110111100011110110',
    '0000111100010100111001110001000000000001110111011110001000000000',
    '0101001100100000011100111001111111001000110111111001010100101000',

    '0010000111101100110101101011010100011111110010000001101000001100',
    '1101001010100000111011000111100100000111011111101100101001111010',
    '0000000000000000000000000000000000000000000000000000000000000000',
    '0000000000000000000000000000000000000000000000000000000000000000',
    '0000000000000000000000000000000000000000000000000000000000000000',

    '0000000000000000000000000000000000000000000000000000000000000000',
    '0000000000000000000000000000000000000000000000000000000000000000',
    '0000000000000000000000000000000000000000000000000000000000000000',
    '0000000000000000000000000000000000000000000000000000000000000000',
    '0000000000000000000000000000000000000000000000000000000000000000']

initial_vector_1=[
    '1110011111100100011110011010011110110000000110011011111001110011',
    '1010000001101101010101010111001011101100011100110000111111000100',
    '1000101101000110110110010011110001011010111110111011100001010100',
    '1010011000010011111000001100101100111010100001011110101110110100',
    '1111011001010101000101111000011101010110111001001111111110001000',

    '1011011001110101110101000110100011000001010111010111000101101100',
    '1101111010011010011100110101111010000100110101010011001011001011',
    '1001001011000101101100101010010001011011101110111000001000111011',
    '1010001101011110001001000000010001101010011011010100010001110110',
    '0111101000011011111011101011111101001111100101011110110001011011',

    '0111110110101100011101110111010011100001001000011100110000010100',
    '1111001011000111111101111000010100010001101110111110110010001000',
    '1011011111111011111101110101011001101101100100101001010010100110',
    '1000000001100110010001000111111011011101001000011010001000100110',
    '1011000000000110001011100000110110001100001101100000111111110111',

    '1110110000101110101111101111110001110111111100001001111100100110',
    '1011011001100110100101101100101101110101101100000001111101010000',
    '0111001000111111011010010101110101010111100011110010100101001011',
    '0101010001000011110111000110000101101110100111010010110101000000',
    '1001000101010001001000010100101010111101001010101110010001001101',

    '0000110100100101011000101010010110011101100011110010011101001110',
    '1011011000101011110111001001100101111001110000011011001100111010',
    '1000010100110010110001000101011011101110111001000110110110111011',
    '0110001100101111000101111001101001011000011101000100001110100011',
    '0110001011001101101011101000101000010001001101011010111010110111']


next_block_1=[
    '1011010000000001011100101111000000011010001101001010110101111010',
    '1001011111101110111010010101101000100000101010111111010110101100',
    '1001010011111101101001101110010010000110000010101010101101111101',
    '1011100101001110000100000110100000101001110000110110000011101010',
    '1100101100111100000000011100111100111010000110000001101100011010',

    '0001011000111110010000001011010000111110101111010110101010000000',
    '1011010000110110101100100111100100010001011101001110001010111000',
    '1001100111100100111100110110000101001001010101100001000001101110',
    '0101011111100111100111111011110010010110000111110001101000101110',
    '0011010111011001010110001010010101111111111111101010001001100000',

    '0110001101011101101010010101000001001111111011110100011111111011',
    '0111000101101011101101010001001011101101101011100000110101010010',
    '1101110110001011111100011010100000010001100100110100101100100101',
    '0110000000010011110000000110100000100100100001111000111000010000',
    '0000110000101001011010100001111010101111011110101110101010110110',

    '0100000101110101001110110011000110001110111000011000010100001101',
    '0111001101100010010011100000101111100010100010000011001001101001',
    '0000000000000000000000000000000000000000000000000000000000000000',
    '0000000000000000000000000000000000000000000000000000000000000000',
    '0000000000000000000000000000000000000000000000000000000000000000',

    '0000000000000000000000000000000000000000000000000000000000000000',
    '0000000000000000000000000000000000000000000000000000000000000000',
    '0000000000000000000000000000000000000000000000000000000000000000',
    '0000000000000000000000000000000000000000000000000000000000000000',
    '0000000000000000000000000000000000000000000000000000000000000000']

使用下面的虛擬碼來測試輸出。現在在實際實現中，next_block 實際上不會通過內部函式傳遞。它被添加在這里以顯示可逆性。

def FREE_START_TEST(initial_vector,next_block):
   for i in range(24):
       initial_vector=_iota(_chi(pi(rho(____THETA(initial_vector)))),i)
   for i in range(24):
       next_block=_iota(_chi(pi(rho(____THETA(next_block)))),i)
   return(XOR_set(initial_vector,next_block))


FREE_START_TEST(initial_vector_0,next_block_0)=[
'1111111111111111111111111111111111111111111111111111111111111111',
'1111111111111111111111111111111111111111111111111111111111111111',
'1111111111111111111111111111111111111111111111111111111111111111',
'1111111111111111111111111111111111111111111111111111111111111111',
'1111111111111111111111111111111111111111111111111111111111111111',

'1111111111111111111111111111111111111111111111111111111111111111',
'1111111111111111111111111111111111111111111111111111111111111111',
'1111111111111111111111111111111111111111111111111111111111111111',
'1111111111111111111111111111111111111111111111111111111111111111',
'1111111111111111111111111111111111111111111111111111111111111111',

'1111111111111111111111111111111111111111111111111111111111111111',
'1111111111111111111111111111111111111111111111111111111111111111',
'1111111111111111111111111111111111111111111111111111111111111111',
'1111111111111111111111111111111111111111111111111111111111111111',
'1111111111111111111111111111111111111111111111111111111111111111',

'1111111111111111111111111111111111111111111111111111111111111111',
'1111111111111111111111111111111111111111111111111111111111111111',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',

'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000'] 



FREE_START_TEST(initial_vector_1,next_block_1)=[
'1111111111111111111111111111111111111111111111111111111111111111',
'1111111111111111111111111111111111111111111111111111111111111111',
'1111111111111111111111111111111111111111111111111111111111111111',
'1111111111111111111111111111111111111111111111111111111111111111',
'1111111111111111111111111111111111111111111111111111111111111111',

'1111111111111111111111111111111111111111111111111111111111111111',
'1111111111111111111111111111111111111111111111111111111111111111',
'1111111111111111111111111111111111111111111111111111111111111111',
'1111111111111111111111111111111111111111111111111111111111111111',
'1111111111111111111111111111111111111111111111111111111111111111',

'1111111111111111111111111111111111111111111111111111111111111111',
'1111111111111111111111111111111111111111111111111111111111111111',
'1111111111111111111111111111111111111111111111111111111111111111',
'1111111111111111111111111111111111111111111111111111111111111111',
'1111111111111111111111111111111111111111111111111111111111111111',

'1111111111111111111111111111111111111111111111111111111111111111',
'1111111111111111111111111111111111111111111111111111111111111111',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',

'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000000']

編輯：

連結到數據，當通過 24 輪 keccak 時，將產生全為零的輸出。不是部分有用，但有點有趣。

不，你不能！

我只會考慮initial_vector_0和next_block_0。

你發現的是這樣的：

        +---+
        |   |
        |   |
IV0 ---->+ f +---->   state
        |   |
        |   |         |
        +---+         |  xor
                      +--------->  1111111111...1 0000000000
        +---+         |
        |   |         |                           <-------->
        |   |
NB0 ---->+ f +---->   state'        Collision on the capacity
        |   |
        |   |
        +---+

我們可以從中建立碰撞嗎？

有點是的…

從這兩個中，您可以建構以下消息：

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

和

e9b5dc2632a682ce7c8f25cd9aee5b5c0193cf95f7be4893821d73470c60bf50922cf335b45123234ba7e198f1c3682a49558111e97179ecc20420f91c560e96e3d2f9b0b1065fbe2a246bc794f9d11971f5118f91a20f0a3aab46dc01395507f678cfc28ec7c3aa00e2dd0110e7140f2895dfc89f7320530c1ac81fb5d6ec217aca7e0779eca0d2ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

如果第一條消息針對 IV :initial_vector_0而第二條消息針對 IV 為空狀態（如 FIPS 202 中規定），則 $ \texttt{SHA-3-256} $ 在這兩種情況下都會導致以下結果：

561e54b2906f81048b46c8c8c9049b9ccbc0b64cfda0cf482668268b301b2170

預期的第一反應：yaaaaaay我們發生了碰撞！

第二反應：我如何讓這個 IV 進入狀態（或參見下面的引用）：

選擇的 initial_vectors 是否代表可以傳遞給 SHA-3 內部函式的可能輸入狀態？

這就是樂趣真正開始的地方！

要獲得這種狀態，您需要獲得 value 的容量：

58993a3aac204ab8951014d982f42d0855e01b9bfc9f96761c608909ec35d9a126d1d16068048f939128c77d3d3d86bcdd2ca3d7746098eb29e4c64e1723fc1e

由此您將進行以下討論：

- 等等你說容量需要有一定的價值對吧？

- 是

的 - 但是在容量中找到如此精確的值不是很複雜嗎 $ \mathcal{O}(2^{512}) $ （前像電阻） ?

- 是的，那是正確

的 - 但是找到與生日悖論的碰撞的複雜性不是 $ \texttt{SHA-3-256} $ 只是 $ \mathcal{O}(2^{256}) $ ?

- 所以所有這些關於偽碰撞的炒作都是徒勞的？

- 這是完全正確的。

- 換句話說，由於海綿結構，自由啟動碰撞是無用的？

-是的！

TL;博士

由於海綿結構，Free-start-collision 完全沒用（特別是因為 Keccak-f 是可逆的）。

碰撞程式碼等可在此處獲得。

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

相關問答

Encryption

為什麼是Hash(x⊕y)Hash⁡(x⊕y)operatorname{Hash}(x oplus y)不是安全的工作量證明算法？

  • October 31, 2022
檢視問答
Encryption

為什麼雜湊（data1 xor data2）不安全的工作量證明算法

  • October 29, 2022
檢視問答
Hash

使用數據雜湊作為完整性證明並防止衝突

  • September 23, 2021
檢視問答
Hash

SHA 的安全漏洞有哪些？

  • June 23, 2021
檢視問答
Hash

SHA3 -255，少一點

  • September 29, 2019
檢視問答
Hash

具有雜湊函式的二進制韌體文件的完整性檢查

  • February 10, 2019
檢視問答