Comment by slooonz

You’re just doing brute force, but with extra steps. It turns out that partial collisions are more common than you think, and it’s not particularly hard to find some.

Here, a 186-bits partial collision, found in less than two minutes on my CPU, by brute force :

sha256(cbfad45814d54d1d56d30de387d957ed3b50e06270ad6e4b897f4a0000000000) = 692207e28eb8dd3eb4f8fab938ea5103faa1060c3bbed204f564e10c65d06b33 sha256(cbfad45814d54d1d56d30de387d957ed3b50e06270ad6e4be8c33e0000000000) = 006347a21f7c9b3eb4fa52b75d0e5a03dbe556b579d6d2867d44c38c06546f6f

(in Python :

>>> hashlib.sha256(bytes.fromhex("cbfad45814d54d1d56d30de387d957ed3b50e06270ad6e4b897f4a0000000000")).hexdigest()

'692207e28eb8dd3eb4f8fab938ea5103faa1060c3bbed204f564e10c65d06b33'

>>> hashlib.sha256(bytes.fromhex("cbfad45814d54d1d56d30de387d957ed3b50e06270ad6e4be8c33e0000000000")).hexdigest()

'006347a21f7c9b3eb4fa52b75d0e5a03dbe556b579d6d2867d44c38c06546f6f'

>>> a = hashlib.sha256(bytes.fromhex("cbfad45814d54d1d56d30de387d957ed3b50e06270ad6e4b897f4a0000000000")).digest()

>>> b = hashlib.sha256(bytes.fromhex("cbfad45814d54d1d56d30de387d957ed3b50e06270ad6e4be8c33e0000000000")).digest()

>>> sum((x^y^0xff).bit_count() for (x, y) in zip(a, b))

186

)

Intuition pump : the expected number of equal bits for two random inputs is 128.