3 ms·
Yes it does seem like a problem, by my reading this will just endlessly try to "split" the bucket of 20 items, hoping that eventually one of the items goes into
by tialaramex 2y ago
Yes it does seem like a problem, by my reading this will just endlessly try to "split" the bucket of 20 items, hoping that eventually one of the items goes into a new bucket leaving space, but if they have the same hash that never happens, disaster.
If I'm wrong I don't think this code does a good enough job of explaining what's going on, and if I'm correct it's defective and should not ship.
Even if this situation "shouldn't" happen, it clearly can happen, you just have to get unlucky, and it's difficult to compute how unlikely that is for real systems, so better to ensure that "We got unlucky" isn't a disaster for the kernel.
- rurban 2y agoNo desaster. On an actual attack (eg if the seed leaked) you count the collisions and return empty on some low threshold. Like 100 on 32bit
- tialaramex 2y agoWhere in the code is this "no disaster" routine you describe?
- rurban 2y agoThe code is not security hardened yet. seed attacks are not yet accustomed for. But it's no disaster, as it's trivial to prevent. They say seeds are secure, so no chance to attack it. Which is a bit childish. It would just be a disaster if they follow Miller's networking code, which uses slower hashes to prevent seed attacks. But every other popular language/library does the very same wrong thing.