6 ms·

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

2 points by KaoruAK 9mo ago

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.ipynb/blob/main/Base_Version/SHA_256_COLISION_FINDER_RECORD3.ipynb https://github.com/POlLLOGAMER/SHA-256-Colision-Finder-NEW.i... https://github.com/POlLLOGAMER/SHA-256-Colision-Finder-NEW.ipynb/blob/main/verify_quasi_collision_184_bits_of_256.ipynb https://github.com/POlLLOGAMER/SHA-256-Colision-Finder-NEW.i... OSF project: https://doi.org/10.17605/OSF.IO/EA739 https://doi.org/10.17605/OSF.IO/EA739 Not a full collision. Open to feedback.

slooonz 9mo 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.

2 points by KaoruAK 9mo ago

slooonz 9mo 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.