No induced collision avoidance?

Posted Jul 15, 2024 21:42 UTC (Mon) by Cyberax (✭ supporter ✭, #52523)
Parent article: A hash table by any other name

I'm super worried that they are not doing anything to avoid induced collisions. This can become a vector for DoS attacks.

Perhaps a per-map random seed to rejiggle the buckets on array growth?

No induced collision avoidance?

Posted Jul 15, 2024 22:30 UTC (Mon) by Paf (subscriber, #91811) [Link] (6 responses)

Is there such a thing in the current rhashtable?

No induced collision avoidance?

Posted Jul 15, 2024 22:40 UTC (Mon) by Cyberax (✭ supporter ✭, #52523) [Link] (3 responses)

Nope. But it looks like rhashtable is not widely used, it's mostly present in Ethernet drivers and in the network stack. For things that are somewhat harder to manipulate by an attacker.

The only other significant user, that is a good attack vector, seems to be bcachefs.

No induced collision avoidance?

Posted Jul 16, 2024 23:43 UTC (Tue) by neilbrown (subscriber, #359) [Link] (2 responses)

> Nope.

Wrong answer :-)

rhashtable generates a random seed each time the table is resized, and if a chain ever reaches 16, the table is "resized" though the size doesn't change.
So as long as the hash function is effective at using the seed to modify the distribution, any induced collision will be quickly disabled by the seed being changed.
Of course if client code requests a poor hash function, all bets are off.

No induced collision avoidance?

Posted Jul 16, 2024 23:45 UTC (Tue) by Cyberax (✭ supporter ✭, #52523) [Link] (1 responses)

Ah, great! Is rosebush similar?

No induced collision avoidance?

Posted Jul 16, 2024 23:58 UTC (Tue) by neilbrown (subscriber, #359) [Link]

> Ah, great! Is rosebush similar?

I cannot find the word "seed" in the patch, and the documentation suggests that hashing is left entirely up to the caller.
So I don't think rosebush attempts to address this issue.

No induced collision avoidance?

Posted Jul 16, 2024 7:35 UTC (Tue) by Wol (subscriber, #4433) [Link]

Dunno about rhashtable in particular, but I think anything with a seed has it generated at the same time as the hashtable.

So while it remains constant as long as the hash table "just grows", as soon as anything triggers the hash table into rebuilding (this could be as simple as it getting too big and being rebuilt with a new size), a new seed is generated.

So any attack that needs to know the seed is aiming at a moving target ...

Cheers,
Wol

No induced collision avoidance?

Posted Jul 16, 2024 10:46 UTC (Tue) by npws (subscriber, #168248) [Link]

Its up to the caller to add a "salt" to the key, like net_random().

No induced collision avoidance?

Posted Jul 16, 2024 8:48 UTC (Tue) by vegard (subscriber, #52330) [Link] (1 responses)

The kernel currently uses the parent directory pointer as a salt for the dentry hash function. It does so in such a way that if two directory entries of the same parent directory were to collide, they would almost certainly not collide under a different parent directory (in other words, creating a collision in one directory does not imply the same names would collide in a different directory). Kernel pointers are not entirely random, but they are also not knowable to an attacker, so this is deemed good enough. Looking at the Rosebush patches for the dentry cache, they don't change the hashing mechanism at all, so it would still be using the same mechanism. Other Rosebush users would presumably have to supply their own hashing function with its own salting mechanism.

No induced collision avoidance?

Posted Jul 16, 2024 22:33 UTC (Tue) by Cyberax (✭ supporter ✭, #52523) [Link]

> Kernel pointers are not entirely random, but they are also not knowable to an attacker

Hah, I wonder if this can be used in reverse, to obtain the kernel pointers by carefully timing the insertions...?