4 ms·
Cuckoo's insert is, in fact, hard to implement correctly. Every implementation I looked at was vulnerable to "chosen key" attack which made it either O(n) or wo
by beagle3 11y ago
Cuckoo's insert is, in fact, hard to implement correctly. Every implementation I looked at was vulnerable to "chosen key" attack which made it either O(n) or worse -- run into an infinite loop or fail to insert.
- FullyFunctional 11y agoGood point. Isn't this a problem with the hash functions exclusively? Can't you avoid this by picking the two hashing functions at random every time you rehash? (I acknowledge that my original comment was misplaced given the off-/on-line difference).
- beagle3 11y agoYou can if you're just avoiding bad luck; You often cannot if you're avoiding an active opponent - in which case, your random would need to be cryptographically secure AND not leak any data through timing or other ways. Here's an observation: Quicksort is similarly vulnerable to an active attacker[0], and can similarly be "protected" with random pivot selection. How many quicksort implementations have you seen in production quality libraries that actually have a random pivot selection? I have seen none. As a result, I avoid quicksort (and cuckoo, and any other basic algorithm which depends on good crypto to perform well). [0] I'm not referring to McIlroy's "antiquicksort" here, which makes quicksort O(n^2) even in the presence of completely unpredictable pivot selection -- I'm assuming the data to be sorted is laid out before the sorting starts.