News for hackers. Stuff that matters.
Re:There are no good constant-time data structures by thaumaturgy on Tuesday December 02, 2014 @05:56PM (#8690623)
I don't understand: why not write the function to take a predetermined (or even slightly random) amount of time to run, and have it just sleep at the end of execution until the timer's up?
Re:There are no good constant-time data structures by norswap on Tuesday December 02, 2014 @07:06PM (#8691000)
Came here to say this. If that's deemed too heavyweight, you can just add "delay" as a random amount of computation overhead (say a loop that does nothing but does not get optimized away). The trick is to make the delay large enough that if you run X times a password with wrong first characters and a password with wrong last character, you aren't able to tell the difference (or you need like a zillion tries -- at which point you may as well do bruteforce).

If you did not have the requirement that password could be arbitrarily long (which seems like a bad idea anyway), you could just pad the password, then compare char by char, never stopping until the end, updating a boolean variable that says if the string is different at each step (character).

Also, this might not be a concern on the web where there's already quite a bit of variability in the response time.

Re:There are no good constant-time data structures by stouset on Tuesday December 02, 2014 @07:33PM (#8691126)
Adding random delays does not remove signal; it only adds noise. Noise can be removed by simply performing more trials.
Re:There are no good constant-time data structures by PeterisP on Tuesday December 02, 2014 @08:36PM (#8691348)
The point is to pad the time to a random amount, not by a random amount.

If a particular function by design needs to have a throughput of at least 100 requests/sec, then you ensure that it has a throughput of exactly 100 rq/sec by calculating the response and then busywaiting until 10ms has elapsed - no matter if the actually neccessary things took 1 or 9 ms based on the input, caching and whatever else.

Alternatively, you use a secure random to state that this request will respond in exactly x ms - not when some calculations are finished. Again, you need to be sure that your calculations are guaranteed to finish before x, so you need to know the worst case time of your algorithm, but you don't need it to be constant time.

Re:There are no good constant-time data structures by Narishma on Tuesday December 02, 2014 @07:54PM (#8691198)
The delays aren't random. They last just enough so that the function always takes the same amount of time, presumably the worst-case amount of time.
Re:There are no good constant-time data structures by tedunangst on Tuesday December 02, 2014 @09:27PM (#8691540)
> presumably the worst-case amount of time.

Determining the the worst case amount of time is far from trivial. What's the slowest amount of time it takes lookup table based AES to decrypt a block?

The only answer to that question is to measure it a bunch, then pick some percentile and hope your margin of safety is sufficient. Or you could use a constant time algorithm to start and rely less on hope.

Re:There are no good constant-time data structures by eps on Wednesday December 03, 2014 @05:22AM (#8692881)
It is actually quite trivial.

You simply align function running time to the worst case _so far_. Start with 0, put it through a warm-up cycle and use it to set a reasonable default. Cache the value between app's sessions, re-initialize when changing the setup.

Re:There are no good constant-time data structures by dllthomas on Tuesday December 02, 2014 @08:50PM (#8691405)
'If that's deemed too heavyweight, you can just add "delay" as a random amount of computation overhead (say a loop that does nothing but does not get optimized away).'

If the delay here is not meant to be random, what is the "that" being contrasted against? I understood "that" to be what you say, which would imply this is something different.

Re:There are no good constant-time data structures by norswap on Thursday December 04, 2014 @05:17AM (#8698603)
I know, that was my point about making the random delay large enough that recovering the signal would be less efficient than a brute-force attack.

And I also suggest a scheme that is about rounding to a fixed delay.