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

· · Web · 1 · 0 · 1

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

Sign in to participate in the conversation
unidentified instance

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!