Sha256: Any significance in being able to find message schedules that lead from different initial hash values but produce the same hash?

Question

Is there any significance in being able to find message schedules that result in the same hash but require different initial hash values? Can generate every 5-10~ minutes for any hash.

Confirmed message schedule regenerates from first 16 W values, and hash produced is the same when using the new initial hash values when reconstructing. But again, I’m not sure if this is significant in any way.

Sample code of what I used to verify it’s a valid message schedule below, this matches the values I generated— all 64 values match.

for i in range(16, 64):
    w_val = (sigma1(W[i-2]) + W[i-7] + sigma0(W[i-15]) + W[i-16]) & 0xFFFFFFFF
    W.append(w_val)

Edit: This might be called a free start collision? I haven’t tried adjusting to try to match the default initial hash values for sha256.

Edit 2: Got runtime per free start collision to 10-20 seconds

Edit 3: Clarifying that the message schedules from the original message and the new message are not the same

Here are some examples:

Original Message: c6b933ebc3fc6c20efca... (Last 20 Characters Redacted)
SHA-256 Hash w/ Free Start IV: dd962f2b94954efd9bf7123d604f77964cbba3c33ebce23f5427e2bd68746b90
SHA-256 Hash w/ Default IV:    dd962f2b94954efd9bf7123d604f77964cbba3c33ebce23f5427e2bd68746b90
Free-Start IV: ['a0c713d2', 'f72d07f2', 'cae8d227', '7517016b', 'fbe4026f', 0, 0, 0] ...(Last Three Values Redacted)
Default IV:    ['6a09e667', 'bb67ae85', '3c6ef372', 'a54ff53a', '510e527f', '9b05688c', '1f83d9ab', '5be0cd19']
===========================================================================================
Processing Time: 15.410990953445435 seconds...


Original Message: c7bd47c2b2ac163413bf... (Last 20 Characters Redacted)
SHA-256 Hash w/ Free Start IV: 28fae8901514959ba91483edf61c6b68f048ba70c9c5a4f363902d203d9a5267
SHA-256 Hash w/ Default IV:    28fae8901514959ba91483edf61c6b68f048ba70c9c5a4f363902d203d9a5267
Free-Start IV: ['d04e04a6', 'a491e269', 'c9a91311', '3a6e8a91', '4ff36d8e', 0, 0, 0] ...(Last Three Values Redacted)
Default IV:    ['6a09e667', 'bb67ae85', '3c6ef372', 'a54ff53a', '510e527f', '9b05688c', '1f83d9ab', '5be0cd19']
===========================================================================================
Processing Time: 10.901056051254272 seconds...


Original Message: 6c581fe6ec7eea7cfe67... (Last 20 Characters Redacted)
SHA-256 Hash w/ Free Start IV: a3eb9a1ae2e36a2ca916641056c282ccd3591a6ccabc130da4d18f76d7b18bd9
SHA-256 Hash w/ Default IV:    a3eb9a1ae2e36a2ca916641056c282ccd3591a6ccabc130da4d18f76d7b18bd9
Free-Start IV: ['6151dac5', 'ae19c43d', '6d0ba457', '33b5ed7f', '81e3520', 0, 0, 0] ...(Last Three Values Redacted)
Default IV:    ['6a09e667', 'bb67ae85', '3c6ef372', 'a54ff53a', '510e527f', '9b05688c', '1f83d9ab', '5be0cd19']
===========================================================================================
Processing Time: 6.203358173370361 seconds...


Original Message: db6bd2b96d000a5d4727... (Last 20 Characters Redacted)
SHA-256 Hash w/ Free Start IV: ad1aad4b2a5ba77759ef3b636a0c79a5c9eb8c5b1ca34553412c3163d6abee52
SHA-256 Hash w/ Default IV:    ad1aad4b2a5ba77759ef3b636a0c79a5c9eb8c5b1ca34553412c3163d6abee52
Free-Start IV: ['dd0bdfbd', 'b509a2e5', 'd2bec68c', '89edbd89', '4f19c561', 0, 0, 0] ...(Last Three Values Redacted)
Default IV:    ['6a09e667', 'bb67ae85', '3c6ef372', 'a54ff53a', '510e527f', '9b05688c', '1f83d9ab', '5be0cd19']
===========================================================================================
Processing Time: 19.402303457260132 seconds...

Answer 1

First thing to do is to make sure that what you computed is really what you think it is, and to be able to state it clearly.

Here is a perfunctory implementation of the SHA-256 hash function, that I just wrote (in Python, following the standard): https://gist.github.com/pornin/46a1701d2c2e377cf4ffe9ecb6c94b32

This implementation defines SHA256.ProcessBlock() which expects two parameters, both of type bytes (the Python type for a binary string): an initial value (32 bytes) and a message block (64 bytes). It computes and returns the 32-byte output, again with type bytes. At the end of the file there is an example of how it should be invoked.

From what you describe in your questions and comments, you claim to have something that is not, actually, a "free-start collision", but could still be interesting. First some notations: let $H$ be a hash function (here, SHA-256) which works by processing successive fixed-size blocks; processing of each block is done with the block processing function $B$ that takes two inputs (a state $s$ and a message block $m$) and produces an output (the new state value). For an input message, $H$ works as follows:

• The message is padded in an unambiguous way, so that the total length of the padded message is a multiple of that of the block. In the case of SHA-256, blocks have size 64 bytes, and padding adds between 1 and 64 bytes. The padded message is then split into blocks $m_1$, $m_2$,... $m_n$.

• A state value $s$ is initialized to a conventional fixed value (the IV). Then message blocks are processed one by one; for each message block, the block processing function is applied on the current state, to get the new state value, i.e. for message $i$, $s$ is replaced with $B(s, m_i)$.

• The hash output is the final value of $s$.

This being given, if you can find two state values $s$ and $s'$, and two block values $m$ and $m'$, such that $B(s, m) = B(s', m')$:

• If $s = s'$ and $m = m'$ then that's trivial.
• If $s = s'$ and $m \neq m'$ then this is a free-start collision. It is a full collision if furthermore $s$ is the standard conventional IV.
• If $s \neq s'$ then this is not what is called a free-start collision (regardless of whether $m = m'$ or $m \neq m'$); it is still interesting because intuitively this should not be easy to compute.

Take care of the following notes:

• In all of the above I am talking about message blocks which are sequences of bytes (64 bytes for SHA-256). I am not talking about the expanded message, which is something internal to how SHA-256 is defined; looking at the expanded message is not relevant to knowing whether you found something that matches the description above.

• What I called $B$ above is the complete block processing function. Internally, SHA-256 defines that $B$ is the combination of a complicated structure which is actually a block cipher (which uses the message block as key), and a word-wise addition (lines 89-96 in my code). The addition is important! If you forget to apply it, then it is pretty trivial to find colliding outputs, but without the addition, it's not SHA-256.

• In any case, the interest here is purely "academic". This has no practical application (for attack nor for defence of anything), but it may yield some insights on how an actual attack (e.g. full collision) on SHA-256 might work. To give an historical example, on the MD5 hash function, free-start collisions were found by Dobbertin in 1996 (and he could generate them in a few minutes on a desktop computer from 1996...) while actual full collisions were found by Wang only in 2004: thus, there is no obvious and immediate path from free-start collisions to full collisions. In particular, there is no real way to monetize such finds, except in the academic way: publish the method, and possibly leverage that to get an academic job. By sending an example on ePrint (as @fgrieu suggests) you'll get attribution (i.e. nobody could "steal" your result) and that's about as much as you could hope for.

An unfortunate characteristic of the modern world is that claims by "people on the Internet" of novel properties found in standard cryptographic functions are not exactly a rarity. There are myriads of such claims and the very overwhelming majority is just a huge time-waster. This is why in practice you do not get credibility nor even attention if you do not provide something that can be independently verified -- not necessarily the method by which you get the values, but at least an example that can be fed into, for instance, a SHA-256 implementation such as mine.

Answer 2

In SHA-256, the compression function has two inputs:

• a 8×32-bit hash input $H$ (designated "initial hash value" or IV in the question, because that input is set to the SHA-256 Initialisation Value in the first compression function of a full SHA-256 hash)
• a 16×32-bit block input $M$ (set to 512-bit of the padded message to hash)

The block $M$ is noted $W_0\ldots W_{15}$, with each of the 16 $W_i$ a 32-bit word. As part of the compression function, it is expanded into the 64×32-bit message schedule $W_0\ldots W_{63}$ with $W_0\ldots W_{15}$ unchanged, as shown in the question.

Is there any significance in being able to find message schedules that result in the same hash but require different initial hash values?

Only for message schedules that could occur in SHA-256, that is such that their $W_{16}\ldots W_{63}$ are as computed from their $W_0\ldots W_{15}$ by the standard method. This seems to be the meaning of the question's "it’s a valid message schedule", but the question does not contain enough to check the assertion made.

Assuming that, it's better to state the result not in term of message schedule, but in term of message blocks: the questions asserts producing distinct pairs $(H_0,M_0)$ and $(H_1,M_1)$ that yield the same output for the SHA-256 compression function. That is, a collision for the SHA-256 compression function (but not a free-start collision, which additionally requires $H_0=H_1$).

I think this would be a publishable result. At least, the first published collision for the compression function of MD5 was not a free-start collision, yet was a major milestone in attacking that hash. It is highly cited: Bert den Boer & Antoon Bosselaers, Collisions for the compression function of MD5, in proceedings of Crypto 1993.

Ideally, the OP would post here an example of $(H_0,M_0)$ and $(H_1,M_1)$. That's a mere 384 hexadecimal characters (plus formatting). Or at least send that to a trusted person able to independently confirm the result.

Then if the result is confirmed, possible next steps are pre-publication of the method at ePrint, and/or submission to an IACR conference (Update: but see below !)

---

A comment suggests the SHA-256 compression function might have been modified to use two different values for the hash input: one used to initialize the 32-byte state, the other at the end to obtain the result with eight 32-bit additions. Because the SHA-256 round function uses the Davies-Meyer structure, it's easy to modify the value of either one of these now two 32-byte inputs to obtain any desired output value. That, and direct consequences, are void of interest.

Update: I was privately given test values and verification code in Python. Just as Marc Stevens first reported, I found that the standard SHA-256 IV remains used at the end of the code for the SHA-256 function. This confirms the above beyond doubt.