News for hackers. Stuff that matters.
Re:There are no good constant-time data structures by kazinator on Tuesday December 02, 2014 @09:06PM (#8691464)
You can gate the completion of each hash lookup with an absolute-sleep, e.g. using the POSIX function clock_nanosleep with a flags value of TIMER_ABSTIME.

Before the hash lookup, calculate a set time into the future, say 300 ms. Then do the hash lookup. Then wait until the predetermined time and return the result.

Waking up a thread at a specific time is just real-time programming 101.

Another idea: if you have some context information that lets you identify that queries are coming from the same entity (same IP address, same tty, same operating system user, whatever), you can impose a shadow ban after 10 unsuccessful tries: fail even if there is a hash "hit", and randomize the times to feed the attacker junk timing data.

Re:There are no good constant-time data structures by kabdib on Tuesday December 02, 2014 @09:59PM (#8691653)
You have to ensure the attacker can't measure temperature-induced clock drift, because you can still measure the amount of work the CPU is doing to surprising accuracy. You can probably introduce extra busy-work, or farm the work out to satellite servers whose timing jitter can't be observed at the microsecond level.

You can also run your lookup against uncacheable memory, so that the attacker can't detect hot keys. There's still some memory timing analysis available because of DRAM banking, though.

Security is a process :-)

Re:There are no good constant-time data structures by kazinator on Wednesday December 03, 2014 @12:19AM (#8692027)
Or you could put a heater with temperature control on the CPU. Oh look, just take that one out of the soldering iron ... :) No wait, sync the clock to a remote external source.