Security of OpenSSL ECDSA signatures

[Damien Miller]

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
timing attacks.

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
> life.

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
operation itself.

-d

* sleeping to foil timing oracles might be susceptible to attacks that
  observe CPU load on the target. These might be possible for an
  authenticated user.