[Cryptography] SHA-256 challenge

[McDair]

> On 28 Mar 2024 10:42 +0000, from cryptography at metzdowd.com (McDair via cryptography):
> 
> > Find a full-fledged preimage that matches output hash:
> > 
> > deb360ae3c1ff7a29f83731b33dcd4bf354a5e80de2dc50370ebf55a14216b85
> > 
> > Tip: the original message size is 32 bytes.
> > 
> > Here are the results I can share at the moment:
> > 
> > - With respect to the overall hash function (including additional 'one' bit, zero padding, message length and derived words):
> 
> > Preimages of 64 rounds
> > ----------------------
> 
> > Full block of 64 words containing the custom 56 values AT THE END and resolving to the desired hash:
> > 1137559525, 3265777086, 3513913394, 2594848941, 129008566, 107100536, 378474686, 8040043, 1096971124, 1918985076, 773865760, 1886745189, 1819877488, 1701147181, 1953443184, 1701147168, 1986359923, 1768910368, 1868963941, 1818583924, 1919905385, 1663066977, 1936203895, 1869966436, 543255660, 1870078063, 1852598638, 1696624737, 2037212526, 1953702004, 1864393317, 544433518, 1948279913, 1919247220, 1819877478, 1919905056, 1869505824, 1885434484, 2032170095, 543256175, 1952998770, 544696692, 1752135028, 543649641, 1852252276, 1752330101, 1734877281, 543582574, 1634624361, 1634476137, 1853060201, 1953854569, 1869491744, 1147758441, 1952541728, 1936287598, 1635022194, 1702043760, 1919907433, 1684349040, 1634890784, 1868963956, 1751457907, 1869378932
> 
> 
> At least treating these numbers as base 10 representations of 32-bit
> integers representing a preimage, having tried several times, I cannot
> get a hash matching the specified SHA-256 hash.
> 
> The closest I can get is to recover the text you reference, by:
> 
> $ printf '%s\n' 1137559525, 3265777086, 3513913394, 2594848941, 129008566, 107100536, 378474686, 8040043, 1096971124, 1918985076, 773865760, 1886745189, 1819877488, 1701147181, 1953443184, 1701147168, 1986359923, 1768910368, 1868963941, 1818583924, 1919905385, 1663066977, 1936203895, 1869966436, 543255660, 1870078063, 1852598638, 1696624737, 2037212526, 1953702004, 1864393317, 544433518, 1948279913, 1919247220, 1819877478, 1919905056, 1869505824, 1885434484, 2032170095, 543256175, 1952998770, 544696692, 1752135028, 543649641, 1852252276, 1752330101, 1734877281, 543582574, 1634624361, 1634476137, 1853060201, 1953854569, 1869491744, 1147758441, 1952541728, 1936287598, 1635022194, 1702043760, 1919907433, 1684349040, 1634890784, 1868963956, 1751457907, 1869378932 | tr -d , | perl -e '$n = 0; while(<>) { $v = $_; $v1 = ($v & 0xff000000) >> 24; $v2 = ($v & 0x00ff0000) >> 16; $v3 = ($v & 0x0000ff00) >> 8; $v4 = ($v & 0x000000ff); printf "%08x: %02x %02x %02x %02x\n", $n, $v1, $v2, $v3, $v4; $n+=4; }' | xxd -r
> 
> 
> but using the output of the above as a preimage, it SHA-256 hashes to
> d084a44d89a2ce255743f551c92e018f5ddcc5b98a3adfddd2edd4b109b6b379, not
> deb360ae3c1ff7a29f83731b33dcd4bf354a5e80de2dc50370ebf55a14216b85.
> 
> (Note to anyone executing this: keep in mind that the first several
> bytes of the output are non-ASCII. You probably don't want to send the
> output directly to a terminal.)
> 
> So either I am making a mistake when converting your string of
> numbers to something which actually can be hashed in a meaningful way
> (which seems relatively unlikely given that it does correctly include
> the text you reference and the number of bytes appears to be correct),
> or it doesn't actually as a preimage hash to the specified hash.
> 
> To fully rule out the former, please rather post a plain binary file
> containing exactly your proposed preimage with no gratuitous encoding.
> 
> You are the one making a claim here. If your claim is accurate, I do
> believe it would be in your interest to make it easy for people to
> verify the correctness of your claim.
> 
> --
> Michael Kjörling 🔗 https://michael.kjorling.se
> “Remember when, on the Internet, nobody cared that you were a dog?”
> 
> _______________________________________________
> The cryptography mailing list
> cryptography at metzdowd.com
> https://www.metzdowd.com/mailman/listinfo/cryptography


Thank you for trying to validate this.

I divided my findings in two categories in this thread:

Quotes:

"
- With respect to the overall hash function (including additional 'one' bit, zero padding, message length and derived words)
"

...

"
- With respect to the main compression function (excluding Merkle–Damgård padding scheme and derived words validation)
"



The first one contain all the security properties of SHA-256, while the second one does not.

I provided a couple of 17-round preimage examples in the first category. They are preimages to the full extend for hash deb360ae3c1ff7a29f83731b33dcd4bf354a5e80de2dc50370ebf55a14216b85, however limited to 17 rounds.


I have also provided 64-round examples for the second category, they will *not* yield to the challenge provided using the complete hash function. I provided these examples to show progress wrt being able to move around the 64 block words, which is essential to efficiently finding preimages, and for the people who were genuinely interested in this from the start (yes, there are).


You seem to have redirected the 64-round example under the wrong category?

With respect to the full hash function (17 rounds), you should try and validate the examples in the first category (for which I provided the hex value/bytes of the input message).


McDair