An implementation of a meet-in-the-middle attack on the jenkins-one-at-a-time hashing algorithm, capable of checking at peta-hash speeds (more than 1015 hashes per second).
On a 8-core/16-thread CPU (Ryzen 7 5800H):
- Finding all collisions for
0x1F9F1matching[a-z0-9_]{0,11}produced 42569552 unique results in 10.82 seconds. - Finding all collisions for
0x1F9F1matching[a-z0-9_]{0,12}produced 1575231307 unique results in 401.78 seconds.
To achieve this speed, a number of algorithms and optimisations are used, including:
- Using a meet-in-the-middle attack.
- Using multi-threading for parallel matching and sorting.
- Using SIMD for hashing.
- Using the position of the pre-computed hashes to derive their string values (avoiding the need to store the string representation of every candidate hash).
- Compressing the pre-computed hashes into buckets (to reduce memory usage).
- Discarding invalid hashes using a 232-bit bitset (this could have used a bloom filter, but as the number of hashes increases, the target size of a bloom filter becomes larger than 232 bits).
Furthermore, due to the vast number of matches, the code for storing and de-duplicating the resulting strings also had to be highly optimised for both speed and memory usage.
Results are streamed to a temporary file during matching, then read back and de-duplicated at the end.
For some more information, see my blog post.