Re: [TLS] Issue #12: RSA/DSA/DH timing attacks

[Bodo Moeller <bmoeller at acm.org>]

On Thu, Jun 07, 2007 at 03:51:43PM +0300, Pasi.Eronen at nokia.com wrote:
> Eric Rescorla wrote:

>> TLS 1.2 already requires some sort of defense against timing
>> analysis on RSA. It is known that timing analysis is possible
>> against DSA but I know of no published defense against it
>> other than fixed-length computations. (As opposed to the
>> blinding defense for RSA).

>> In San Diego, I asked Tim of NIST knew of one but haven't
>> heard back.

>> I'd like to put this to bed. I suggest that unless someone comes
>> up with a defense suggestion by Chicago we simply say that this
>> is an issue with DSA implementations and suggest fixed-length
>> computations as a possible defense. Comments?

> Well, if there's no publicly-known defense (like there is for RSA), 
> then I don't see what else we can do (other than require some
> countermeasure, and suggest fixed-length computations)...

Of course you could use blinding with DSA too (in many different
styles), but DSA isn't as vulnerable to timing attacks as RSA is, in
the first place: In RSA, you have a constant exponent that will be
used for many different inputs (allowing the adversary to observe the
same exponent in action in many different situations); in DSA, in
contrast, the exponentiation uses *ephemeral* exponents anyway, so
timing it doesn't quite as much useful information.

If you consider more fine-grained attacks (such as parallel spy
processes running on the same processor that obtain cache-access or
branch-prediction timings), then neither RSA with blinding nor
DSA is secure.  So even for RSA, you can't put down the one single
recommendation that will make it secure against timing attacks.

Having said that, here's how you could try to add blinding to DSA
exponentiations -- either base and exponent blinding or just exponent
blinding:

- Compute  g^k  as  g'^k'  where  g' = g^m  (m random) is a blinded
  base value, and where  k' = m'*k mod q.  (Just as with RSA, you
  could keep the blinding parameters for a number of cryptographic
  operations for better performance.)

- Compute  g^k  as  g^(k + m*q + m') * g^(q - m'),  where blinding
  parameters  m  and  m'  both can be quite short.

Bodo



_______________________________________________
TLS mailing list
TLS at lists.ietf.org
https://www1.ietf.org/mailman/listinfo/tls