Put together an example implementation of Wagner's attack in Python.

The TLDR is to make a tree structure where you match on incrementally more bits at each height of the tree, meaning you can solve the generalized birthday problem ("sum" k hashes to get a target) as opposed to the vanilla birthday problem ("sum" 2 hashes to a target, e.g. zero) in way less time than the latter problem. Instead of O(2^(n/2)) samples you only need O(2^(n/(lg k + 1)).

waxwing@waxwing@x0f.org(sidenote, while Python is obviously stupidly slow for such things, I think there should be an easy way to make it work quite a bit faster when matching byte strings bitwise, my method is too slow and the comparisons are of course the bottleneck).