# SHA1 Partial Collision

I'm working on a little python script that reads in two fairly similar English sentences (they're in text files - reading them in) and I'm trying to force a SHA1 partial collision (e.g. first 32 bits of each hash are equivalent).

Currently, my logic of thinking is as follows:

1. Concatenate empty space to the end of string 1.
2. Hash string 1.
3. Concatenate empty space to the end of string 2.
4. Hash string 2.
5. Check if hash_of_string_01[:32] exists in the dict, if not, move on - else exit program.
6. Check if hash_of_string_02[:32] exists in the dict, if not, move on - else exit program.
7. Add both new hashes to the dict.
8. Loop...

However, this isn't anywhere near efficient, nor entirely correct. I'm trying to wrap my head around how I can approach this solution...

Any guidance you can provide me would be valuable! Thank you. :)

• It is necessary for you that the collisions must be constructed from the initial sentences? – cygnusv Feb 3 '15 at 11:29
• Or you just need a pair of random strings that produce a partial collision? – cygnusv Feb 3 '15 at 11:40
• In the latter case, then you can use some cycle detection algorithm and find a partial collision in a matter of seconds. – cygnusv Feb 3 '15 at 11:52
• I have to use the initial sentences... I'll look into the cycle detection algo though tooo! Thanks :) – mrsmithson Feb 3 '15 at 22:40
• Maybe you loose a lot of time on concatenating spaces to strings - you can use sha1().update to increment a hash state. Also [:32] in python will give you first 32 bytes, not bits (and you shouldn't convert hashes to bits of course). – Fractalice Feb 5 '15 at 23:03

It is wanted a partial collision (over $b=32$ bits) between hashes of strings starting in distinct strings 1 and 2. I won't directly answer homework, but my hints outgrew a comment.

The solution presented should work, though details allowing to output the colliding strings are left out, and there are inefficiencies. Towards guiding optimization, I suggest estimating (perhaps, in big-$\mathcal O$ notation)

1. the expected number of steps in the algorithm,
2. the expected cumulated size of the hashed strings;
3. the expected number of insertions (and searches);
4. required memory size (which depends on the aforementioned details).

If 4 becomes outrageous, be smarter: minimize what's in the dictionarie(s), and make a second hash pass to detect the other colliding string; or store a value allowing to reconstruct that string, rather than the string itself.

You'll find that 2 suggests that (at least when $b$ grows), the naive method of obtaining the hash of a string by hashing it from the start dominates the cost of the calculation. That can be fixed in at least two ways: hashing shorter strings (hint: as suffix, combine space and some other character with similar rendering, such as non-breaking space); or if that's not allowed, being smarter at computing the hash of long strings with the same start (hint: keep appropriate hash states).

After these tweaks, if insertions and searches in the dictionaries become a serious bottleneck, or if one is tight on memory, or otherwise want to get rid of dictionaries, one can use Floyd's cycle finding algorithm with an appropriately defined function (hint: craft a function $f$ over $\{0,1\}^b$ such that finding a collision for $f$ solves the problem with odds about 50%). This is a great way to solve the problem, although it requires somewhat more hashes than techniques using a dictionary.

If $b$ grows to the point that the hashing needs to be distributed, see Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, January 1999, Volume 12, Issue 1; free slightly earlier version available from the first author's website).

• Thank you very much for your guidance. I def. was not looking for a concrete answer, just guidance! Thanks. – mrsmithson Feb 3 '15 at 22:42
• If this helped you find a solution you can still accept the answer to show that the guidance was correct. – Maarten Bodewes Nov 4 '18 at 16:25