Hi John,
thanks for forwarding. There has been a short thread on this on
attack-interest yesterday and today.
The way that these timing attacks work is that the attacker will time
a lot of crypto operations (in this case the ECDSA signing operation)
and then exploit the fact that the time taken by the algorithm depends
to some extent on the private key or on another secret value (in this
case the secret "k" used in ECDSA signing). If the signing operation
has a branch on the bits of the secret key, so that a "1" bit will
cause an operation that takes longer that if a "0" bit is present,
then this will cause a key-dependent timing. In elliptic curve
cryptography, the "secret" is always the exponent used in the
exponentiation routine.
I think our implementation is safe against this type of attacks. We
use a sliding window method for exponentiation, so that the
"branching" takes place on windows. The exponent is broken up into 4-
bit windows. There is a loop over all the windows, and each window
gets processed by a switch statement to determine what
ec_group_element should get multiplied into the accumulator "r". In
the case in which all the bits of the window are zero, then this is a
multiplication by the identity element, and we can skip that
multiplication if we want. However, I put in a dummy operation to
make sure that a multiplication gets done even when the window is all
zero:
case 0x0:
/* multiply by IE, which we don't need to actually perform */
//printf("multiplying r by 1\n"); // ec_group_elementH_print(x0);
printf ("\n");
#ifdef DUMMY_MULT
ec_group_mult(dum, dum, r, C);
#endif
break;
So as long as the compiler doesn't optimize away that ec_group_mult()
operation, the execution time of the exponentiation routine ought to
be independent of the exponent.
I have skimmed over the paper, and it turns out that the dependency on
the exponent that they exploit is the fact that the openssl
exponentiation for binary curves skips over the initial zero bits in
the exponent. The signature only leaks information when there are a
significant number of leading zeros.
It would not be hard to write a function that collected timing
information based on different exponents, and could estimate/detect
this sort of vulnerability. That would be a *great* thing to add to
our test suite. But since it doesn't need to go inside the canister,
let's put off implementing it until after next Tues ;-)
David
On May 25, 2011, at 7:52 AM, John Foley wrote:
David,
Would your ECDSA implementation be subject to the following timing
attack?
-------- Original Message --------
Subject: New Timing Attack on OpenSSL ECDSA
Date: Wed, 25 May 2011 15:59:58 +0200
From: Mounir IDRASSI <[email protected]>
Reply-To: [email protected]
Organization: IDRIX
To: [email protected]
Hi all,
Is there any plan for implementing counter measures against the newly
discovered vulnerability in ECDSA operations of OpenSSL?
For those not aware of it, here is the US-CERT link of this
vulnerability : http://www.kb.cert.org/vuls/id/536044
Here is also the original paper that contains the vulnerability
details
: http://eprint.iacr.org/2011/232.pdf
The patch suggested by the paper seems simple enough. It can be
enhanced
by adding a random multiple of the order to the scalar k. Is there any
objection for getting this merged into OpenSSL source?
Cheers,
--
Mounir IDRASSI
IDRIX
http://www.idrix.fr
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List [email protected]
Automated List Manager [email protected]
