SHA256 Free Start Self Collision (Full 64 rounds)

IVec:

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

Block:

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

Output:

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

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

Is this an issue?

  • 1
    The IVEC is not part of the data block. The link above shows an example C program that allows for the IVEC to be entered on the command line. Alternatively, edit any publicly available source code and use the above IVEC. With this example, the input block can be repeated any number of times and the hash value does not change. – Nathan.Mariels Jun 24 '17 at 12:15
  • 4
    Actually this is more of a fixed point ($f(x)=x$) rather than a collision. – SEJPM Jun 24 '17 at 12:25
  • 2
    Actually this is more of a fixed point (f(x)=x). Right. I'm thinking if a number of such known fixed points will give dangerous insights on SHA256? – Dmitry Kaigorodov Jun 24 '17 at 12:35
  • 6
    I verified that compressing this (IV, block) pair with SHA256 does indeed reproduce the input IV. How did you find this? – CodesInChaos Jun 24 '17 at 12:37
  • 2
    Give me a 64 byte block, and I'll give you the IVEC of the zero point – Nathan.Mariels Jun 24 '17 at 14:10

SHA-256 is based on a Davies–Meyer compression function. Easy to find fixed-points are a known property of this construction.

A notable property of the Davies–Meyer construction is that even if the underlying block cipher is totally secure, it is possible to compute fixed points for the construction : for any $m$, one can find a value of $h$ such that $E_m(h) \oplus h = h$ : one just has to set $h = E_m^{-1}(0)$. This is a property that random functions certainly do not have. So far, no practical attack has been based on this property, but one should be aware of this "feature".

The fixed-points can be used in a second preimage attack (given a message m1, attacker finds another message m2 to satisfy hash(m1) = hash(m2) ) of Kelsey and Schneier for a $2^k$-message-block message in time $3 \cdot 2^{n/2+1}+2^{n-k+1}$. If the construction does not allow easy creation of fixed points (like Matyas–Meyer–Oseas or Miyaguchi–Preneel) then this attack can be done in $k \cdot 2^{n/2+1}+2^{n-k+1}$ time. Note that in both cases the complexity is above $2^{n/2}$ but below $2^n$ when messages are long and that when messages get shorter the complexity of the attack approaches $2^n$.

(from One-way compression function - wikipedia)

Thanks to Samuel Neves for pointing this out.

  • I don't understand why is this not a full collision? Can't this be made to a practical length extention attack? – Meir Maor Jun 24 '17 at 14:17
  • 8
    @MeirMaor To abuse this property you need to get the state of the hash to match a state you get when running the decryption of the blockcipher underlying the compression function. Finding such a match requires a meet-in-the-middle attack with cost $2^{n/2}$ and thus isn't cheaper than finding a collision. – CodesInChaos Jun 24 '17 at 14:48
  • Relevant crypto.stackexchange.com/questions/44642/… – Q-Club Jun 28 '17 at 19:48
  • @CodesInChaos In the description you posted, the function Em() can be inverted. In the context of the question would Em() be SHA-256? I haven't tried to invert SHA-256 with both IV's and W_t undefined (I will have more degrees of freedom). Inverting the one equation one unknown mod 2^32 addition isn't completely intuitive. – Q-Club Jun 29 '17 at 2:05
  • 1
    @back_seat_driver $E_m$ is SHACAL-2, the block-cipher underlying SHA-2. Practically all blockciphers support efficient decryption. Note that $m$ is the message-block of SHA-2 is used as key in the blockcipher while the IV is used as message. – CodesInChaos Jun 29 '17 at 14:03

I found this thread after seeing a similar post on reddit. It seems the author(s) are making the rounds from here to hacker news to cryptography.reddit.

I was curious if these fixed points could be found with SAT and it turns out the answer is "yes" and extremely quickly. My comment on reddit is re-produced here. The portion of interest is at the bottom where I show these fixed points are cheap to find with SAT.

I took a Cryptol implementation for SHA256 and added the presented constants:

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]

Then the computation is

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

And we're left with the question:

SHA256> hPostAttack == hAttack
True

For ease of presentation we can define a helper:

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

And this is a decent point to call out that you can ask a modern SAT solver:

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

Boolector can solve this quickly (while others didn't terminate fast enough for my tastes):

(\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

and

(\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

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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