Hash Pile Ups: Using Collisions to Identify Unknown Hash Functions

Hash functions are often used to consistently assign objects to particular resources, for example to load balancing in networks. These functions can be randomly selected from a family, to prevent attackers generating many colliding objects, which usually results in poor performance.We describe a number of attacks allowing us to identify which hash function from a family is being used by observing a relatively small number of collisions. This knowledge can then be used to generate a large number of colliding inputs. In particular we detail attacks against small families of hashes, Pearson-like hash functions and linear hashes, such as the Toeplitz hash used in Microsoft’s Receive Side Scaling