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

From: Eric Rescorla <[email-masked]>
Date: Sun, 03 Jun 2007 07:50:02 -0700

http://www3.tools.ietf.org/wg/tls/trac/ticket/12

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?

-Ekr

_______________________________________________
TLS mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/tls

---

From: <[email-masked]>
Date: Thu, 7 Jun 2007 15:51:43 +0300

> 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)...

Best regards,
Pasi

---

From: Bodo Moeller <[email-masked]>
Date: Fri, 8 Jun 2007 13:15:52 +0200

> 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

---

From: Bodo Moeller <[email-masked]>
Date: Fri, 8 Jun 2007 13:17:26 +0200

>   operations for better performance.)

Er,  k' = k/m' mod q,  of course.  (I.e., you need a mod-q inversion.)

Bodo