Show HN: SHA-256 quasi-collision with 184/256 matching bits(github.com)
github.com
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
1 comments
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.
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.
Code and verification script:
https://github.com/POlLLOGAMER/SHA-256-Colision-Finder-NEW.i...
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.