Systems such as masscan, yarrp and diamond-miner send in the order of a million packets/s in order to discover open ports and packet paths on the Internet. To avoid overloading the network and trigger rate-limiting or intrusion detection systems, the probes must be distributed evenly across the network. Standard methods for generating random permutations, such as the Fisher-Yates shuffle, usually require to store the whole permutation in memory, which is prohibitive when the number of probes to send is large (>1B typically). In this talk we will discuss methods to generate random permutations, and in particular the Generalized-Feistel Cipher [1] which can generate permutations on arbitrary domains, on-the-fly and in constant memory.
[1] Black, John, and Phillip Rogaway. “Ciphers with arbitrary finite domains.” /Cryptographers’ track at the RSA conference/. Springer, Berlin, Heidelberg, 2002.