Security of OpenSSL ECDSA signatures

[Dan Kaminsky]

On Tue, May 24, 2011 at 1:08 AM, Damien Miller <djm at mindrot.org> wrote:

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

Eh, the thing is that you're creating a _really_ strong signal (a multi
millisecond delay) thats dependent on microsecond timings.  The whole game
is in making it so the attacker can't differentiate the slight microsecond
differences derived from noise, from the slight differences derived from the
underlying crypto functions.

According to Nate Lawson, he got all sorts of interesting data watching the
quantized distribution of network traffic off EC2 nodes.  He was totally
doing stuff involving a packet sent at 1.9999ms vs. 2.0000ms.  I do think
that's viable.


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

It does, it's just at the edge finding layer.  Think of it like you have
certain inputs that suddenly get super high jitter.


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

So scale the delay to 2x-10x the longest signature of the last 6 hours, with
some maximum, and some minimum too.

I think we agree roughly that there's an intermediate mitigation between
O(1) and nothing, heretical as that statement may be.


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

Lets deal with the network case for now.