Fingerprinting systems with TCP source-port selection

Posted Oct 7, 2022 10:50 UTC (Fri) by scientes (guest, #83068)
In reply to: Fingerprinting systems with TCP source-port selection by scientes
Parent article: Fingerprinting systems with TCP source-port selection

Nobody less than Donald E Knuth says that balanced trees and not hash tables must be used for security considerations in many places.

Fingerprinting systems with TCP source-port selection

Posted Oct 7, 2022 13:20 UTC (Fri) by wittenberg (subscriber, #4473) [Link] (3 responses)

Could you give a reference please? I'd like to see his reasoning.

Fingerprinting systems with TCP source-port selection

Posted Oct 7, 2022 13:59 UTC (Fri) by Wol (subscriber, #4433) [Link]

My immediate reaction is that a hash tree relies on *pseudo*randomness. As such, it is always vulnerable to being cracked.

If you use a drunken walk to walk a balanced tree, then you both avoid re-using values you've already used, and you end up in a genuinely random new place every time. And as the tree grows, the number of random numbers used to get a new value grows - after 1000 values a tree with 2 nodes per branch will require a ten-step drunken walk ... if your RNG truly is random then no way is an attacker going to predict where you'll end up.

Cheers,
Wol

Fingerprinting systems with TCP source-port selection

Posted Oct 7, 2022 15:23 UTC (Fri) by epa (subscriber, #39769) [Link] (1 responses)

I don't know what Knuth wrote, but it's undeniable that hashing depends to some extent on "luck". If you are very "unlucky" then you will get lots of hash collisions, and performance degrades. In other words, while the average case performance is fine, the worst case is poor. If your input data may be chosen by an attacker, you have to worry about the worst case performance, even though in a benign environment it is so unlikely you can dismiss it. Or you have to be certain your hash function is secure enough that an attacker won't find a way to make it degrade.

Fingerprinting systems with TCP source-port selection

Posted Oct 8, 2022 23:00 UTC (Sat) by NYKevin (subscriber, #129325) [Link]

IMHO there are a few exceptions here:

1. The hashing algorithm is salted with a CSPRNG value generated at startup. But this requires you to know what you are doing, because there are a variety of side-channel attacks that might leak this value or allow an attacker to make educated guesses about it. For example, if a collision happens, a request might take slightly longer to process, and if an attacker can observe collisions, they may be able to try different keys and figure out the possible salt values. Or maybe not, as this is probably infeasible for very large keyspaces and salts.
2. A "perfect" hashing algorithm (i.e. an algorithm that never collides - only possible if there are at least as many hash buckets as valid keys, or if you can somehow prove that no two valid keys that collide will ever be used simultaneously, so you can't do this in the general case).
3. You have hard-realtime requirements, you absolutely need O(1) performance, and it is acceptable to drop requests that cause collisions. I'm not sure why you would want that, but it is theoretically a valid combination of requirements.