Hi, David.
So what is the meaning of the "Affected" status for OpenSSL? Is that simply because ECDSA is supported by OpenSSL? Or did they actually test against an implementation that exhibited the vulnerability? Either way, FIPS 140-3 will only require protection against non-invasive attacks at level 3 and higher. Cheers, Paul ________________________________________________________________________ _____________________________ Paul A. Suhler | Firmware Engineer | Quantum Corporation | Office: 949.856.7748 | [email protected] <mailto:[email protected]> Preserving the World's Most Important Data. Yours.(tm) From: [email protected] [mailto:[email protected]] On Behalf Of David McGrew Sent: Wednesday, May 25, 2011 8:25 AM To: John Foley Cc: [email protected] Subject: Re: New Timing Attack on OpenSSL ECDSA 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]> <mailto:[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] ---------------------------------------------------------------------- The information contained in this transmission may be confidential. Any disclosure, copying, or further distribution of confidential information is not permitted unless such privilege is explicitly granted in writing by Quantum. Quantum reserves the right to have electronic communications, including email and attachments, sent across its networks filtered through anti virus and spam software programs and retain such messages in order to comply with applicable data security and retention requirements. Quantum is not responsible for the proper and complete transmission of the substance of this communication or for any delay in its receipt.
