32
$\begingroup$

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?

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ 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. $\endgroup$
    – Nathan.Mariels
    Commented Jun 24, 2017 at 12:15
  • 4
    $\begingroup$ Actually this is more of a fixed point ($f(x)=x$) rather than a collision. $\endgroup$
    – SEJPM
    Commented Jun 24, 2017 at 12:25
  • 2
    $\begingroup$ 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? $\endgroup$
    – Dmitry Kaigorodov
    Commented Jun 24, 2017 at 12:35
  • 6
    $\begingroup$ I verified that compressing this (IV, block) pair with SHA256 does indeed reproduce the input IV. How did you find this? $\endgroup$
    – CodesInChaos
    Commented Jun 24, 2017 at 12:37
  • 2
    $\begingroup$ Give me a 64 byte block, and I'll give you the IVEC of the zero point $\endgroup$
    – Nathan.Mariels
    Commented Jun 24, 2017 at 14:10

2 Answers 2

Reset to default
34
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I don't understand why is this not a full collision? Can't this be made to a practical length extention attack? $\endgroup$
    – Meir Maor
    Commented Jun 24, 2017 at 14:17
  • 8
    $\begingroup$ @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. $\endgroup$
    – CodesInChaos
    Commented Jun 24, 2017 at 14:48
  • $\begingroup$ Relevant crypto.stackexchange.com/questions/44642/… $\endgroup$
    – Q-Club
    Commented Jun 28, 2017 at 19:48
  • $\begingroup$ @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. $\endgroup$
    – Q-Club
    Commented Jun 29, 2017 at 2:05
  • 1
    $\begingroup$ @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. $\endgroup$
    – CodesInChaos
    Commented Jun 29, 2017 at 14:03
6
$\begingroup$

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
Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Actually, you don't need a SAT solver; the SHA-256 hash compression function is $hc(state, message) = state \oplus E_{message}(state)$, for an easily invertible (if you know the message) $E$. All you need to do is take your arbitrary message block and find the state for which $0 = E_{message}(state)$ $\endgroup$
    – poncho
    Commented May 27, 2019 at 21:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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