|Main Archive Page > Month Archives > openssh-unix-dev archives|
On Tue, 24 May 2011, Dan Kaminsky wrote:
> > random delays will not help because you can sample to eliminate them. I
> > think you would want something like the following, that rounds signing
> > operations up to the next power of two milliseconds.
> I could see some weird corner case where the private key determines which
> edge a delay falls on, causing a response in 2ms or 4ms. That's actually a
> really clean signal to look for.
I don't think it likely that signing operations would be reliably poised
at the precise microsecond bounday to cause it to flip between 2^n and
2^n+1. In any case, the proposed patch drops the (easily*) observable
resolution to milliseconds, which are well above the threshold for
Actually, we can make the magic increment harder to hit by using
clock_gettime() to give us nanosecond precision.
If someone came up with a credible attack, then we could drop the
resolution further to 5ms increments and it still would not be
perceptible to users.
I guess if you wanted to dither (pun!) then you could do something like:
+ duration = (duration + (arc4random() & 1) ? 999 : 0) / 1000;
to make it random whether you round up or down, but I suspect that would
increase the infomation leaked rather than decrease it.
> The aold standard is constant time. But making every operation constant
> time is hard, and getting harder, due to higher level languages (not our
> problem). In theory, a random delay can be teased out by looking at the
> peak of the distribution of results -- it'll be slightly shifted when the
> original delay is minimal rather than maximal.
> But I tell you, I sure note the people doing timing attacks at the tens of
> nanosecond scale aren't getting their attacks to work versus Internet level
> latencies...that something is possible after billions of packets does not
> mean that something is necessarily practical.
> So I'd definitely do random noise over next-power-of-two-ms.
That these attacks require nanosecond precision is a good argument for
rounding to ms and 2^n too. The rounding approach doesn't have the
statistical leak either.
> Better than both though would be to discover the worst case scenario time
> for a handful of keys, double that, and then sleep until twice the
> difference has elapsed. So, if the worst case scenario for ECDSA was
> calculated as 10ms, execute, see a delay of 5ms, sleep 15ms, and go on with
A handful of keys under what circumstances? An unloaded machine? A
server that just started with cold caches? A machine running hundreds
of concurrent signing operations? A machine that is deep in swap? There
is no good guide except the time it took to complete the last signing
* sleeping to foil timing oracles might be susceptible to attacks that
observe CPU load on the target. These might be possible for an
openssh-unix-dev mailing list