[Cryptography] SHA-256 challenge

[McDair]

The challenge as presented by Mr. Dillinger is as follows:

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 17 rounds
----------------------

EXAMPLE 1:

Message length: 31 bytes
Message (HEX): 716bb9216a2038dd92e63067398bf9b01389992ea9b039f8dad7d812cfa881
Message (bytes): 113, 107, 185, 33, 106, 32, 56, 221, 146, 230, 48, 103, 57, 139, 249, 176, 19, 137, 153, 46, 169, 176, 57, 248, 218, 215, 216, 18, 207, 168, 129

Resulting block (big-endian words): 1902885153, 1780496605, 2464559207, 965474736, 327784750, 2846898680, 3671578642, 3483926912, 0, 0, 0, 0, 0, 0, 0, 248, 722654979

Whereby (0, 248) represent the message size and 722654979 a derived word.

EXAMPLE 2 whereby the message contains non-random data (custom inserted text) (!):

Message length: 55 bytes
Message (HEX): 3568454cf4467cb73b89951b5b0dde9209e02bc22697d6b51e4c92e50554069a5361746f736869204e616b616d6f746f2072756c657321
Message (bytes): 53, 104, 69, 76, 244, 70, 124, 183, 59, 137, 149, 27, 91, 13, 222, 146, 9, 224, 43, 194, 38, 151, 214, 181, 30, 76, 146, 229, 5, 84, 6, 154, 83, 97, 116, 111, 115, 104, 105, 32, 78, 97, 107, 97, 109, 111, 116, 111, 32, 114, 117, 108, 101, 115, 33

Resulting block: 896025932, 4098260151, 998872347, 1527635602, 165686210, 647485109, 508334821, 89392794, 1398895727, 1936222496, 1315007329, 1836020847, 544372076, 1702044032, 0, 440, 2535353578

The last 23 bytes translate to an important message...

EXAMPLE 3 is a different preimage (or collision if you will) containing the same custom text:

Message length: 55 bytes
Message (HEX): c38e78ed0a66beb5ac22a275fc99b667ae8d95d0766a002540bf8edb8548c0675361746f736869204e616b616d6f746f2072756c657321
Message (bytes): 195, 142, 120, 237, 10, 102, 190, 181, 172, 34, 162, 117, 252, 153, 182, 103, 174, 141, 149, 208, 118, 106, 0, 37, 64, 191, 142, 219, 133, 72, 192, 103, 83, 97, 116, 111, 115, 104, 105, 32, 78, 97, 107, 97, 109, 111, 116, 111, 32, 114, 117, 108, 101, 115, 33

Resulting block: 3280894189, 174505653, 2887950965, 4237932135, 2928514512, 1986658341, 1086295771, 2236137575, 1398895727, 1936222496, 1315007329, 1836020847, 544372076, 1702044032, 0, 440, 4226562623

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

Preimages of 64 rounds
----------------------

- Change the first 56 words of the block input to custom values and deterministically resolve to the desired output hash using the remaining 8 rounds.

- Alternatively and maybe more interesting: manipulate the last 56 words and (deterministically) resolve to the desired hash using the first 8 rounds.

EXAMPLE

For this example I took the first 224 characters of the first paragraph of the bitcoin white paper, translated to 56 (big-endian) words.

Text: "Abstract. A purely peer-to-peer version of electronic cash would allow online payments to be sent directly from one party to another without going through a financial institution. Digital signatures provide part of the solut".

Translated to words:
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

Full block of 64 words containing the custom 56 values AT THE BEGINNING and resolving to the desired hash (deb360ae3c1ff7a29f83731b33dcd4bf354a5e80de2dc50370ebf55a14216b85):
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, 3833417232, 985654276, 1251143496, 1630026482, 1872776035, 2777850990, 3552141516, 4268646800

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

McDair
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20240328/68cfbc23/attachment.htm>