Show HN: SHA-256 quasi-collision with 184/256 matching bits

https://github.com/POlLLOGAMER/SHA-256-Colision-Finder-NEW.ipynb/blob/main/Base_Version/SHA_256_COLISION_FINDER_RECORD3.ipynb

by KaoruAK • 7 months ago

2 1 7 months ago

github.com

I obtained a SHA-256 quasi-collision with 184 out of 256 matching bits (71.88%) using a geometric search. Found in ~25 minutes on a Google Colab v5e-1 TPU.

Code and verification script:

https://github.com/POlLLOGAMER/SHA-256-Colision-Finder-NEW.i...

OSF project:

https://doi.org/10.17605/OSF.IO/EA739

Not a full collision. Open to feedback.

slooonz• 7 months ago

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.

Show HN: SHA-256 quasi-collision with 184/256 matching bits

Related Stories