Security of OpenSSL ECDSA signatures

[Damien Miller]

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;
 }
 
 /*