Login | Register For Free | Help
Search for: (Advanced)

Mailing List Archive: OpenSSH: Dev

Security of OpenSSL ECDSA signatures

 

 

OpenSSH dev RSS feed   Index | Next | Previous | View Threaded


aris at 0xbadc0de

May 23, 2011, 1:00 AM

Post #1 of 14 (2488 views)
Permalink
Security of OpenSSL ECDSA signatures

Dear OpenSSH devs,

I came accross this paper yesterday. http://eprint.iacr.org/2011/232
It states that they were able to recover ECDSA keys from TLS servers by
using timing attacks agains OpenSSL's ECDSA implementation.
Is that known to be exploitable by OpenSSH ? (In my understanding, it's
easy to get a payload signed by ECDSA during the key exchange so my
opinion is that it is). There's a patch for openssl in the paper, that
remove the detectable optimization away. Would you consider blacklisting
openssl versions that do not implement that workaround ?

Abstract follows.

Kr,

Aris

Abstract: For over two decades, timing attacks have been an active area
of research within applied cryptography. These attacks exploit
cryptosystem or protocol implementations that do not run in constant
time. When implementing an elliptic curve cryptosystem that provides
side-channel resistance, the scalar multiplication routine is a critical
component. In such instances, one attractive method often suggested in
the literature is Montgomery's ladder that performs a fixed sequence of
curve and field operations. This paper describes a timing attack
vulnerability in OpenSSL's ladder implementation for curves over binary
fields. We use this vulnerability to steal the private key of a TLS
server where the server authenticates with ECDSA signatures. Using the
timing of the exchanged messages, the messages themselves, and the
signatures, we mount a lattice attack that recovers the private key.
Finally, we describe and implement an effective countermeasure.
_______________________________________________
openssh-unix-dev mailing list
openssh-unix-dev [at] mindrot
https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev


djm at mindrot

May 23, 2011, 5:31 AM

Post #2 of 14 (2372 views)
Permalink
Re: Security of OpenSSL ECDSA signatures [In reply to]

On Mon, 23 May 2011, Aris Adamantiadis wrote:

> Dear OpenSSH devs,
>
> I came accross this paper yesterday. http://eprint.iacr.org/2011/232
> It states that they were able to recover ECDSA keys from TLS servers by
> using timing attacks agains OpenSSL's ECDSA implementation.
> Is that known to be exploitable by OpenSSH ? (In my understanding, it's
> easy to get a payload signed by ECDSA during the key exchange so my
> opinion is that it is). There's a patch for openssl in the paper, that
> remove the detectable optimization away. Would you consider blacklisting
> openssl versions that do not implement that workaround

This result concerns binary/GF(2m) fields only and not the prime fields
that OpenSSH uses in recent versions.

Unless a similar timing oracle is found for GF(p) fields then no
OpenSSH-side workaround is required.

-d
_______________________________________________
openssh-unix-dev mailing list
openssh-unix-dev [at] mindrot
https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev


aris at 0xbadc0de

May 23, 2011, 5:34 AM

Post #3 of 14 (2366 views)
Permalink
Re: Security of OpenSSL ECDSA signatures [In reply to]

Le 23/05/11 14:31, Damien Miller a écrit :
> This result concerns binary/GF(2m) fields only and not the prime fields
> that OpenSSH uses in recent versions.
>
> Unless a similar timing oracle is found for GF(p) fields then no
> OpenSSH-side workaround is required.

Thanks for your explanation, I'm not familiar enough with ECC.

Regards,

Aris
_______________________________________________
openssh-unix-dev mailing list
openssh-unix-dev [at] mindrot
https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev


dan at doxpara

May 23, 2011, 6:13 AM

Post #4 of 14 (2367 views)
Permalink
Re: Security of OpenSSL ECDSA signatures [In reply to]

>
> This result concerns binary/GF(2m) fields only and not the prime fields
> that OpenSSH uses in recent versions.
>
> Unless a similar timing oracle is found for GF(p) fields then no
> OpenSSH-side workaround is required.
>
>
OpenSSL has had timing attacks against most of their production ciphers
(RSA, AES, etc). Has the author of the paper weighed in on whether he
thinks his attack will affect GF(p)?

--Dan
_______________________________________________
openssh-unix-dev mailing list
openssh-unix-dev [at] mindrot
https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev


djm at mindrot

May 23, 2011, 2:36 PM

Post #5 of 14 (2359 views)
Permalink
Re: Security of OpenSSL ECDSA signatures [In reply to]

On Mon, 23 May 2011, Dan Kaminsky wrote:

> > Unless a similar timing oracle is found for GF(p) fields then no
> > OpenSSH-side workaround is required.
> >
> >
> OpenSSL has had timing attacks against most of their production ciphers
> (RSA, AES, etc). Has the author of the paper weighed in on whether he
> thinks his attack will affect GF(p)?

The Brumley and Tuveri attack is against a scalar multiplication
algorithm that is specific to GF(2m) fields (see section 3.2 of the
paper). An attack on prime fields would be a new one altogether.

-d
_______________________________________________
openssh-unix-dev mailing list
openssh-unix-dev [at] mindrot
https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev


dan at doxpara

May 23, 2011, 8:43 PM

Post #6 of 14 (2354 views)
Permalink
Re: Security of OpenSSL ECDSA signatures [In reply to]

On Mon, May 23, 2011 at 2:36 PM, Damien Miller <djm [at] mindrot> wrote:

> On Mon, 23 May 2011, Dan Kaminsky wrote:
>
> > > Unless a similar timing oracle is found for GF(p) fields then no
> > > OpenSSH-side workaround is required.
> > >
> > >
> > OpenSSL has had timing attacks against most of their production ciphers
> > (RSA, AES, etc). Has the author of the paper weighed in on whether he
> > thinks his attack will affect GF(p)?
>
> The Brumley and Tuveri attack is against a scalar multiplication
> algorithm that is specific to GF(2m) fields (see section 3.2 of the
> paper). An attack on prime fields would be a new one altogether.
>
> -d
>

I asked one of the timing attack guys if they were able to run their
nanosecond scale attacks against a device having a network interface
enforced jitter several orders of magnitude higher than what they were
looking for. Command looked something like:

tc qdisc change dev eth0 root netem delay 2ms 1ms

No reply.

I know in theory this shouldn't help, but if OpenSSH's ECDSA implementation
is in fact variable time, why not add a random usleep at 10-100x the worst
case scenario for at least average hardware?
_______________________________________________
openssh-unix-dev mailing list
openssh-unix-dev [at] mindrot
https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev


djm at mindrot

May 23, 2011, 11:29 PM

Post #7 of 14 (2365 views)
Permalink
Re: Security of OpenSSL ECDSA signatures [In reply to]

On Mon, 23 May 2011, Dan Kaminsky wrote:

> The Brumley and Tuveri attack is against a scalar multiplication
> algorithm that is specific to GF(2m) fields (see section 3.2 of the
> paper). An attack on prime fields would be a new one altogether.
>
> -d
>
>
> I asked one of the timing attack guys if they were able to run their
> nanosecond scale attacks against a device having a network interface
> enforced jitter several orders of magnitude higher than what they were
> looking for. Command looked something like:
>
> tc qdisc change dev eth0 root netem delay 2ms 1ms
>
> No reply.
>
> I know in theory this shouldn't help, but if OpenSSH's ECDSA implementation
> is in fact variable time, why not add a random usleep at 10-100x the worst
> case scenario for at least average hardware?

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.

Index: key.c
===================================================================
RCS file: /cvs/src/usr.bin/ssh/key.c,v
retrieving revision 1.97
diff -u -p -r1.97 key.c
--- key.c 17 May 2011 07:13:31 -0000 1.97
+++ key.c 24 May 2011 06:28:21 -0000
@@ -36,11 +36,13 @@

#include <sys/param.h>
#include <sys/types.h>
+#include <sys/time.h>

#include <openssl/evp.h>

#include <stdio.h>
#include <string.h>
+#include <unistd.h>

#include "xmalloc.h"
#include "key.h"
@@ -1588,28 +1590,68 @@ key_to_blob(const Key *key, u_char **blo
return len;
}

+/*
+ * Round up to nearest power of two. Bit-twiddle algorithm from
+ * http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
+ */
+static u_int64_t
+ceil2_u64(u_int64_t n)
+{
+ n--;
+ n |= n >> 1;
+ n |= n >> 2;
+ n |= n >> 4;
+ n |= n >> 8;
+ n |= n >> 16;
+ n |= n >> 32;
+ n++;
+ return n;
+}
+
int
key_sign(
const Key *key,
u_char **sigp, u_int *lenp,
const u_char *data, u_int datalen)
{
+ int result = -1;
+ struct timeval start, finish, diff;
+ u_int64_t duration, desired;
+
+ gettimeofday(&start, NULL);
switch (key->type) {
case KEY_DSA_CERT_V00:
case KEY_DSA_CERT:
case KEY_DSA:
- return ssh_dss_sign(key, sigp, lenp, data, datalen);
+ result = ssh_dss_sign(key, sigp, lenp, data, datalen);
+ break;
case KEY_ECDSA_CERT:
case KEY_ECDSA:
- return ssh_ecdsa_sign(key, sigp, lenp, data, datalen);
+ result = ssh_ecdsa_sign(key, sigp, lenp, data, datalen);
+ break;
case KEY_RSA_CERT_V00:
case KEY_RSA_CERT:
case KEY_RSA:
- return ssh_rsa_sign(key, sigp, lenp, data, datalen);
+ result = ssh_rsa_sign(key, sigp, lenp, data, datalen);
+ break;
default:
error("key_sign: invalid key type %d", key->type);
- return -1;
+ result = -1;
+ break;
}
+
+ /*
+ * Round up perceived duration of signing operation to the nearest
+ * power of two milliseconds by sleeping the difference.
+ */
+ gettimeofday(&finish, NULL);
+ timersub(&finish, &start, &diff);
+ duration = diff.tv_sec * 1000000 + diff.tv_usec;
+ duration = (duration + 999) / 1000; /* round up to milliseconds */
+ desired = ceil2_u64(duration); /* round up to 2^n */
+ if (desired > duration)
+ usleep((desired - duration) * 1000);
+ return result;
}

/*
_______________________________________________
openssh-unix-dev mailing list
openssh-unix-dev [at] mindrot
https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev


djm at mindrot

May 23, 2011, 11:57 PM

Post #8 of 14 (2353 views)
Permalink
Re: Security of OpenSSL ECDSA signatures [In reply to]

On Tue, 24 May 2011, Damien Miller 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.

FYI this sleeps for around 30ms on my old IBM x40 laptop* using ECDSA
in a 256 bit curve field.

-d

* cpu0: Intel(R) Pentium(R) M processor 1200MHz ("GenuineIntel" 686-class) 1.20 GHz

_______________________________________________
openssh-unix-dev mailing list
openssh-unix-dev [at] mindrot
https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev


dan at doxpara

May 24, 2011, 12:12 AM

Post #9 of 14 (2356 views)
Permalink
Re: Security of OpenSSL ECDSA signatures [In reply to]

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

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

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.

This keeps burning people, might as well fix it now.
_______________________________________________
openssh-unix-dev mailing list
openssh-unix-dev [at] mindrot
https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev


djm at mindrot

May 24, 2011, 1:08 AM

Post #10 of 14 (2345 views)
Permalink
Re: Security of OpenSSL ECDSA signatures [In reply to]

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.
_______________________________________________
openssh-unix-dev mailing list
openssh-unix-dev [at] mindrot
https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev


aris at 0xbadc0de

May 24, 2011, 1:15 AM

Post #11 of 14 (2342 views)
Permalink
Re: Security of OpenSSL ECDSA signatures [In reply to]

Le 24/05/11 10:08, Damien Miller a écrit :
>
> 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.
>

I think that shooting in the dark in order to block unknown timing
attacks is likely to worsen the problem rather to mitigate it. Wouldn't
be better to "simply" analyze the upstream algorithm and try to make it
O(1), whatever the situation ?
As said in the thread, putting timer loops will not stop side infoleaks
like cpu load, cache misses etc.

Aris
_______________________________________________
openssh-unix-dev mailing list
openssh-unix-dev [at] mindrot
https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev


dan at doxpara

May 24, 2011, 1:21 AM

Post #12 of 14 (2355 views)
Permalink
Re: Security of OpenSSL ECDSA signatures [In reply to]

On Tue, May 24, 2011 at 1:15 AM, Aris Adamantiadis <aris [at] 0xbadc0de>wrote:

> Le 24/05/11 10:08, Damien Miller a écrit :
> >
> > 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.
> >
>
> I think that shooting in the dark in order to block unknown timing
> attacks is likely to worsen the problem rather to mitigate it. Wouldn't
> be better to "simply" analyze the upstream algorithm and try to make it
> O(1), whatever the situation ?
> As said in the thread, putting timer loops will not stop side infoleaks
> like cpu load, cache misses etc.
>


It's the quotes around "simply" that belie everything. I had someone swear
up and down that MD5 was always constant time. And it should be.

MD5 in Javascript isn't. It just isn't, not even close.

Other people can pretend local security works; I'm simply going to focus on
the network case. My assumption is that OpenSSH simply borrows the ECDSA
implementation from OpenSSL and doesn't have the degrees of freedom to learn
how to make it either constant or uncorrelated (as in RSA blinding) time.
It does have the freedom to delay network traffic, however.
_______________________________________________
openssh-unix-dev mailing list
openssh-unix-dev [at] mindrot
https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev


dan at doxpara

May 24, 2011, 1:38 AM

Post #13 of 14 (2342 views)
Permalink
Re: Security of OpenSSL ECDSA signatures [In reply to]

On Tue, May 24, 2011 at 1:08 AM, Damien Miller <djm [at] mindrot> 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.
_______________________________________________
openssh-unix-dev mailing list
openssh-unix-dev [at] mindrot
https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev


alon at nolaviz

May 27, 2011, 12:17 AM

Post #14 of 14 (2321 views)
Permalink
Re: Security of OpenSSL ECDSA signatures [In reply to]

Isn't it enough to limit the range of $k$ (the random value selected
during signature generation) to values with the top bit set?

(Or--if there are too few of those--only use values with "01" in the top
bits, still leaving 2^{158} possible values?)


-a

_______________________________________________
openssh-unix-dev mailing list
openssh-unix-dev [at] mindrot
https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev

OpenSSH dev RSS feed   Index | Next | Previous | View Threaded
 
 


Interested in having your list archived? Contact Gossamer Threads
 
  Web Applications & Managed Hosting Powered by Gossamer Threads Inc.