(Some) Algorithms for generating random permutations
Speaker: Maxime Mouchet (LIP6).
Webpage: https://www.lincs.fr/events/algorithm....
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 (more than 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.