Exact timestamps may be bad

[David Shaw]

On Sat, Jul 27, 2002 at 07:43:18PM -0700, Joel Ray Holveck wrote:
> There's been some discussion in the anonymous remailer community about
> problems with exact timestamps.

[..]

> The signature is the killer.  Remember that remailer (or chain of
> remailers) is taking measures to prevent traffic analysis, including
> adding artificial latency.  The problem is, the signature contains a
> timestamp.  Eve can look at the timestamp on the signature, and
> correlate it with one of the messages entering the remailer network,
> thereby finding out exactly who Alice is.
> 
> My thought is to allow GPG to add a scattering to the timestamp to
> prevent this.  The scattering should be user-configurable.  It should
> be long enough to prevent this attack, but short enough that it
> doesn't invalidate the timestamp's purpose.
> 
> Here's my trouble: I don't understand the purpose of the timestamp.
> It seems to be used in verifying that a signature was not made outside
> of a key's validity window, but a forger can easily alter the
> timestamp.  Perhaps it's used to avoid replay attacks in some
> scenarios, or something, but I don't know.

A forger cannot alter the timestamp, as it is (nearly) always part of
the hashed data.  By altering the timestamp, the forger would
invalidate the signature.

One way of handling the problem is simply to not include the timestamp
at all.  In OpenPGP signature packets, the timestamp is a distinct
subpacket and can be removed trivially when the signature is
generated.  It is somewhat unclear whether this violates the OpenPGP
RFC or not, as I can point to sections in the RFC that seem to say
this is not allowed, and some other sections that seem to say this is
allowed.  The point may be moot since you can't use OpenPGP data
signatures with most versions of PGP, and I imagine you want to be as
widely compatible as possible.

Another way is simply to always use the same timestamp, which is
doable with either OpenPGP or the older style signatures.  I think
this may be better than adding some skew to the timestamp since (as
you mention in one of the bits I've snipped) if Alice sends many
messages with the same skew, Eve may be able to get some clues about
the window size.  If zero is used for the timestamp (i.e. 1/1/1970),
then there is no way to even get a guess about the real setting of the
clock.

GnuPG will refuse to validate such a signature ("public key is
1027635505 seconds newer than the signature"), unless the
--ignore-time-conflict option is used to override this check.  PGP
seems to not mind either way, and will dutifully report that the
signature was "made" on 1/1/1970.

> There's also timestamps on key signatures, and other things.  I'm not
> sure whether these should have the same scattering applied as the
> other options, or what attacks this scattering may allow.

Yes, there can be two timestamps in signed OpenPGP messages.  The
first is in the signature, of course, but there is one other one in
the "literal data packet" that contains the material that is signed.
No big deal, but if you are removing one, you need to remember to
remove the other.  This second timestamp is in encrypted messages as
well, but since they're encrypted, they are not visible to anyone but
the recipient.

Clearsigned messages, which are used far more frequently, only contain
the one timestamp in the signature.

David

-- 
   David Shaw  |  dshaw@jabberwocky.com  |  WWW http://www.jabberwocky.com/
+---------------------------------------------------------------------------+
   "There are two major products that come out of Berkeley: LSD and UNIX.
      We don't believe this to be a coincidence." - Jeremy S. Anderson