SHA1 Partial Collision

Question

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. :)

Answer 1

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).