Subject: [ietf-dkim] Draft Side Channel Language

From: Eric Rescorla <[email-masked]>
Date: Mon, 27 Mar 2006 09:59:27 -0800

All popular of digital signature algorithms are subject to a variety of
side channel attacks. The most well-known of these are timing channels
[0], power analysis [2], and cache timing analysis [3]. Most of these
attacks require either physical access to the machine or the ability to
run processes directly on the target machine. Defending against these
attacks is out of scope for DKIM.

However, remote timing analysis (at least on local area networks) is
known to be feasible [1], particularly in server-type platforms where
the attacker can inject traffic which will immediately subject to the
cryptographic operation in question. With enough samples, these
techniques can be used to extract private keys even in the face of
modest amounts of noise in the timing measurements.

The three commonly proposed countermeasures against timing analysis are:

1. To make the operation run in constant time. This turns out in
   practice to be rather difficult.

2. To make the time independent of the input data. This can be
   difficult but see [1] for more details.

3. To use blinding. This is generally considered the best current
   practice countermeasure, and while not proved generally secure is a
   countermeasure against known timing attacks.  It adds about 2-10% to the
   cost of the operation and is implemented in many common cryptographic
   libraries. Unfortunately, ECDSA and DSA do not have standard methods
   though some defenses may exist. [4]

Note that adding random delays to the operation is only a partial
countermeasure. Because the noise is generally uniformly distributed,
a large enough number of samples can be used to average it out and
extract an accurate timing signal.

[0] P. Kocher, "Timing Attacks on implementations of Diffie-Hellman,
    RSA, and other cryptosystems", Advances in Cryptology, pages
    104-113, 1996.
[1] D. Boneh and D. Brumley, "Remote Timing Attacks are Practical",
    Proc. 12th USENIX Security Symposium, 2003.
[2] P. Kocher, J. Joffe, and B. Yun, "Differential Power Analysis:
    Leaking Secrets", Crypto '99, pages 388-397, 1999.
[3] D. Bernstein, "Cache Timing Attacks on AES", 2004.
    http://cr.yp.to/papers.html#cachetiming
[4] D. Boneh, Personal Communication.

-Ekr
_______________________________________________
NOTE WELL: This list operates according to 
http://mipassoc.org/dkim/ietf-list-rules.html

---

From: Eric Rescorla <[email-masked]>
Date: Mon, 27 Mar 2006 11:27:31 -0800

> extract an accurate timing signal.

I guess it wasn't clear from my text that none of these
countermeasures affect the bits on the wire so there's no
compatibility issue here. They only affect the signer's
implementation. Signers don't HAVE to do them any more
than they HAVE to have a strong RNG. It's just good
security practice. 

The only reason to mention this in the DKIM RFC at all is that unlike
(say) S/MIME, the fact that it's done under a server in semi-real-time
means that there's a potential risk.

-Ekr