5 ms·
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 d
by norswap 12y ago
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.
- stouset 12y agoAdding random delays does not remove signal; it only adds noise. Noise can be removed by simply performing more trials.
- Narishma 12y agoThe 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.
- dllthomas 12y ago'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.
- tedunangst 12y ago> 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.
- eps 12y agoIt 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.
- PeterisP 12y agoThe 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.
- deleted 12y ago[deleted]
- norswap 12y agoI 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.