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



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

· · Web · 0 · 0 · 0
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!