On Thu, May 29, 2003 at 03:33:06PM -0500, Scott A Crosby wrote: > They exploit the difference between 'typical case' behavior versus > worst-case behavior. For instance, in a hash table, the performance is > usually O(1) for all operations. However in an adversarial > environment, the attacker constructs carefully chosen input such that > large number of 'hash collisions' occur. This is precisely one of the attacks which have been considered, avoided(*), and documented in my Phrack #53 article entitled "Designing and Attacking Port Scan Detection Tools" - "Data Structures and Algorithm Choice" back in 1998. Now you report another port scan detector (Bro) still vulnerable to this attack. I'm not surprised. (*) http://www.openwall.com/scanlogd/ As for solutions, while using a keyed hash function offers the best performance with a large enough number of entries (but not with a small one!), it is rather complicated when done right, too easy to do wrong, and may be imperfect anyway because of timing leaks (see below). It requires that a cryptographically random secret is used (and really kept secret!), that it is large enough to not be successfully brute-forced, and a cryptographic hash function is used (or it might be possible to infer the secret). This is why a hashing library like yours is needed. But for many applications it could make more sense to use another data structure and algorithm (such as binary search). Now the promised attack on using a keyed hash function with the above requirements met. Let's assume that all input to the hash function, except for the secret, is under control of an attacker. Further, let's assume that she is able to infer if a hash collision occurs by measuring the time it takes to process a request (possibly repeating each request multiple times). After a bit of trying, she will know that inputs A and B produce a collision. She will then keep A and B fixed and search for an input C which will collide with A and B. And so on. Changing the secret once in a while reduces this attack and may well make it impractical with many particular applications. Note that one doesn't have to use any additional true randomness (and possibly exhaust the randomness pool) for each new secret to be used with the keyed hash. If the secret itself is not leaked in the attack (and it shouldn't be), something as simple as secret++ could suffice. However, this does have its difficulty: maintaining existing entries. -- Alexander Peslyak <solar@openwall.com> GPG key ID: B35D3598 fp: 6429 0D7E F130 C13E C929 6447 73C3 A290 B35D 3598 http://www.openwall.com - bringing security into open computing environments
