8
$\begingroup$

Given that the five sub-functions that comprise SHA-3 are reversible an individual can produce specific outputs of their choosing. The following is to my knowledge an example of a free start collision in SHA-3(256). Both initial vectors violate the padding protocol outlined in FIPS-202. It’s understood that the next_block values are padded correctly, with the understanding that this theoretical message has a bit length that is an integer multiple of 1088. I omitted the step of appending an empty string to the message as it’s an unnecessary step for this example.

Do the selected initial_vectors represent possible input states that can be passed to SHA-3’s internal functions?

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']

Using pseudo code below to test outputs. Now in an actual implementation the next_block wouldn't actually be passed through the internal functions. Its been added here to show reversibility. 

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']

Edit:

Link to data, that when passed through 24 rounds of keccak, will produce an output of all zeros. Not partially useful, but kind of interesting.

|improve this question
$\endgroup$
  • $\begingroup$ If you want to share code, use gist. Please. $\endgroup$ – Biv Jun 14 '17 at 6:50
  • $\begingroup$ Also your code does not execute as we don't have your definitions of chi etc... $\endgroup$ – Biv Jun 14 '17 at 7:43
  • $\begingroup$ Also worth nothing that you can represent your state with hexa notation as defined in FIPS 202, it makes it shorter. $\endgroup$ – Biv Jun 14 '17 at 7:44
  • $\begingroup$ here is a WORKING code of the question... $\endgroup$ – Biv Jun 14 '17 at 10:37
  • 3
    $\begingroup$ A free start collision is significant with a Merkle-Damgard hash, because it assumes that the hash compression function is itself collision resistant (and a demonstration of a free start collision disproves that). A sponge hash function makes other assumptions about its permutation; a free start collision does not violate those assumptions $\endgroup$ – poncho Jun 14 '17 at 14:10
13
$\begingroup$

NO, you can't !

I will only consider initial_vector_0 and next_block_0.

What you have found is this:

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

Can we build a collision from that ?

Somewhat Yes...

From these two you can build the following messages:

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

and

e9b5dc2632a682ce7c8f25cd9aee5b5c0193cf95f7be4893821d73470c60bf50922cf335b45123234ba7e198f1c3682a49558111e97179ecc20420f91c560e96e3d2f9b0b1065fbe2a246bc794f9d11971f5118f91a20f0a3aab46dc01395507f678cfc28ec7c3aa00e2dd0110e7140f2895dfc89f7320530c1ac81fb5d6ec217aca7e0779eca0d2ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

If the first message has for IV : initial_vector_0 and the second one as for IV the empty state (as stipulated in FIPS 202) then $\texttt{SHA-3-256}$ will lead to the following result in both cases:

561e54b2906f81048b46c8c8c9049b9ccbc0b64cfda0cf482668268b301b2170

First reaction expected: yaaaaay we have a collision !

Second reaction: How do I get to have this IV into the state (or see the quote below) :

Do the selected initial_vectors represent possible input states that can be passed to SHA-3’s internal functions?

That is where the fun actually begins!

To get this state, you need to get a capacity of value :

58993a3aac204ab8951014d982f42d0855e01b9bfc9f96761c608909ec35d9a126d1d16068048f939128c77d3d3d86bcdd2ca3d7746098eb29e4c64e1723fc1e

From this you will have the following discussion:

- Wait you said that the capacity needs to have a certain value right?
- Yes
- But isn't the complexity of finding such exact value in the capacity $\mathcal{O}(2^{512})$ (pre-image resistance) ?
- Yes that is correct
- But isn't the complexity of finding a collision with a birthday paradox over $\texttt{SHA-3-256}$ just $\mathcal{O}(2^{256})$?
- So all this hype for a pseudo-collision is for nothing ?
- That is entirely correct.
- In other word, a Free start collision is useless because of the sponge construction ?
- YES !

TL;DR

Because of to the sponge construction, having a Free-start-collision is completely useless (especially because Keccak-f is invertible).

The code of the collision etc. is available here.

|improve this answer
$\endgroup$
  • 1
    $\begingroup$ I REALLY appreciate the effort you put into confirming, and was hoping/expecting this answer. So you're saying that given some specified capacity there is no conventional way to invert keccak while ensuring that the input you derive has the correct padding? Provided the output rate that you start with is undefined, and assuming there is no way to guess the correct rate values when inverting. All at the same time maintaining the correct output capacity! Ugh... $\endgroup$ – Q-Club Jun 14 '17 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.