[cryptography] blinding to protect against timing-attacks on RSA sigs (Re: OAEP for RSA signatures?)

Adam Back adam at cypherspace.org
Sun Jan 27 07:58:59 EST 2013


The RSA private key timing attack is much more likely than on padding
because the cost is so much higher.  Bleichenbacher like adaptive attacks
are not so much timing as error code attacks (app is too chatty about
whether padding was well formed afte decryption), so thats a separate issue.

For RSA timing the simple low tech solution is blinding, as in Chaum's blind
signature.  create random value b, raise it to power e, then sign
(b^e*pad(H(m))) = b*sig(pad(H(m)), then divide by b (multiply by b^-1 mod
n).

It'll cost a moderate amount of extra compute - two multiplies mod n a small
(e sized), modexp mod n and a modinv.  But then an app or server that spills
its private key is even less cool.

the obvious argument being the attacker doesnt know b, you dont store it as
its disposable so the bias from raising to power d is masked by that.  As I
recall it was Rivest who suggested this defense following Kocher et als
first publication about timing attacks.

I think that its only the modinv that is adding data related cost, so it
must be considered that that is enough.  b^e takes time irrespective of b
(of the same size) using window approach.  The multiplies are also should
not take data related time.  Same for window with montgomery.

Openssl has a flag/option to do that blinding defense for you.

Adam

On Sun, Jan 27, 2013 at 11:49:05AM +0300, ianG wrote:
>On 27/01/13 04:53 AM, Peter Gutmann wrote:
>>ianG <iang at iang.org> writes:
>>
>>>Could OAEP be considered reasonable for signatures?
>>
>>You need to define "appropriate".  For example if you mean "interoperable"
>>then OAEP isn't even appropriate for encryption, let alone signatures.
>
>
>Oh, interoperable is not an issue.  I've got that covered.  The one 
>class that produces the signatures is exactly and always the same 
>class that verifies the signatures.
>
>(This is what I would call better practice not "best practice" but 
>not everyone would agree, especially those that deal in multiple 
>languages ;) )
>
>
>>If
>>you're worried about timing channels then OAEP is also pretty inappropriate
>>for any use.  PKCS #1 OTOH will interop with pretty much anything, and you can
>>do the padding check in close enough to constant time that it doesn't matter.
>
>
>OK, timing channels are an issue in the back of my mind.  As the 
>client platform is the android phone, I'm guessing other apps could 
>sit there and do timing attacks at my app.
>
>However, I'm unsure about the above logic.  If a transform like OAEP 
>is constant time, then this is bad for timing attacks coz its time 
>drops out of statistics.  Ideally we want a transform that is either
>  * perfectly uncorrelated (0) and a time ratio >~ 2 std devs, or
>  * perfectly negatively-correlated (-1) with a factor of exactly 1.
>
>As the latter is implausible, we want the former:  some transform 
>that adds an amount of noise that is entirely independent, that 
>swamps the deviation.
>
>Or, where has my logic gone wrong?
>
>
>
>iang
>_______________________________________________
>cryptography mailing list
>cryptography at randombit.net
>http://lists.randombit.net/mailman/listinfo/cryptography



More information about the cryptography mailing list