ZMap: Internet scanner maps all of IPv4 in 45 minutes
I thought the approach they took to permuting the address space was particularly clever, but was quickly schooled on Twitter by how bog-standard the approach apparently is (I very much concede the point!). In the interest of honesty about how easily impressed I am, and because I still think it's a neat little trick:<p>You want to generate a permutation of the entire IPv4 address space, but you don't simply want to shuffle every possible IP address because that would require you to keep an insane amount of state. So instead, work in the multiplicative group modulo <i>p</i> for prime <i>p</i> > 2^32, find an appropriate generator, and iterate by multiplying with the generator mod <i>p</i>. Remember the prime, the generator, the starting address, and your current address and you can detect a complete traversal of the space when the starting address recurs.<p>There are a number of simpler ways to do this (after sheepishly conceding that this is pretty fundamental stuff, I played with using PRFs and card shuffling to do it; DrHoney suggested Gray codes), but I liked how immediately obvious the multiplicative group solution was, and that I could code it from a simple description.