[prev in list] [next in list] [prev in thread] [next in thread] 

List:       openssl-dev
Subject:    Re: New Timing Attack on OpenSSL ECDSA
From:       Mounir IDRASSI <mounir.idrassi () idrix ! net>
Date:       2011-05-25 18:57:09
Message-ID: 4DDD5105.1090600 () idrix ! net
[Download RAW message or body]

Hi all,

The paper is clearly indicating that they successfully mounted a 
practical attack againt OpenSSL TLS implementation that uses elliptic 
curves and ECDHE_ECDSA based ciphers. They used the OpenSSL s_server 
utility and the versions indicated in their paper is 0.9.8o and 1.0.1a. 
I'm not aware of any changes in this part of OpenSSL since these 
versions were release so all current OpenSSL version are vulnerable.

David: Can explain a little more you argument? I couldn't find the code 
referenced in your email in the OpenSSL source and I'm not sure how the 
details you gave are linked to OpenSSL implementation.

As I stated in my first email, the paper comes with a temporary patch 
that should mitigate this issue. Is there any one working on this? I 
think it should be taken seriously even if ECDSA based ciphers are not 
widely used.

Cheers,
--
Mounir IDRASSI
IDRIX
http://www.idrix.fr

On 5/25/2011 7:20 PM, Paul Suhler wrote:
>
> 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 | paul.suhler@quantum.com 
> <mailto:paul.suhler@quantum.com>
> *Preserving the World's Most Important Data. **Yours**.™*
>
> *From:*owner-openssl-dev@openssl.org 
> [mailto:owner-openssl-dev@openssl.org] *On Behalf Of *David McGrew
> *Sent:* Wednesday, May 25, 2011 8:25 AM
> *To:* John Foley
> *Cc:* openssl-dev@openssl.org
> *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 <mounir.idrassi@idrix.net> 
> <mailto:mounir.idrassi@idrix.net>
>
> *Reply-To: *
>
> 	
>
> openssl-dev@openssl.org <mailto:openssl-dev@openssl.org>
>
> *Organization: *
>
> 	
>
> IDRIX
>
> *To: *
>
> 	
>
> openssl-dev@openssl.org <mailto:openssl-dev@openssl.org>
>
> 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 Projecthttp://www.openssl.org
> Development Mailing Listopenssl-dev@openssl.org  <mailto:openssl-dev@openssl.org>
> Automated List Managermajordomo@openssl.org  <mailto:majordomo@openssl.org>
>   
>
> ------------------------------------------------------------------------
> 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.

______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
Development Mailing List                       openssl-dev@openssl.org
Automated List Manager                           majordomo@openssl.org
[prev in list] [next in list] [prev in thread] [next in thread]