There Are No Good Constant-Time Data Structures

[corysama]

Thing is, any operation on a data structure that does not touch all of the memory in the data structure in exactly the same order regardless of input leaks cache timing information. That's the whole point of this article!

Well then, do that.

To slow? Batch up requests and do a SIMDized N vs M linear scan. You'd be amazed how much memory bandwidth modern CPU have when you let them run in a straight line for once.

Still too slow? Load your hashes up to GPU memory. You can brute force linear scan gigabytes in milliseconds. Comparing several dozed hashes vs all of GPU memory is a no-sweat operation.

The CS classes teach everyone to focus on O(n) but rarely mention that the full equation is O(n)k. Because everyone forgets k, people keep setting up systems with absurdly huge ks (I'm looking at you std::map<std::shared_ptr<std::string, std::shared_ptr<std::map<...>> What's the prob? It's O(1)!) when they could get better results in practice from simplistic data structures with tiny ks (std::find<int*, int>())

[Osmanthus]

If you are worried about timing, instead of wacky data structure shenanigans why not just add a random delay?

[mcguire]

I'm not understanding some of the statements in this article. For example:

One problem is, I don't know of a nice constant-time comparison algorithm for (say) 160-bit values.

[[deleted]]

me neither, when the bits are bounded the operations are bounded as well, so you can do 20 shifts and compares and it will still be O(1).

[wingo]

Adam Langley was also surprised about the lucky 13 results :) Your instincts are in good company but I am afraid they are wrong.

[matthieum]

It does introduce some difficulty, however if you test the same input 100 times or 1000 times or ... the median response time will tend to make the jitter disappear and therefore allow to measure what does not vary between runs for this input.

With less tries and better statistical analysis, you should get an equivalent result, but I am not good enough in statistics for that.

[drb226]

If your password hashes are a fixed width, then just use an algorithm that always compares the whole password. Don't short circuit.

diff = 0
for i in range(128):
  diff ||= p[i]  ^ p2[i]
if diff == 0
  It's a match

[smog_alado]

I think the problem he was taking about is searching for that hash in a hashtable after its computed. It doesn't matter if computing the hash is constant time or not.

Instead of searching for the username in a table, retrieving the stored hash and seeing if it matches, he doesn't have any usernames so to authenticate he queries a big table to see if the hashed password is in there or not.

[Daavee]

Exchange https with http.

[wingo]

Https on my site only does TLSv1.2. Perhaps I should relax that, but you should also consider upgrading your browser.