[openpgp] Timestamping

Peter Todd <pete@petertodd.org> Fri, 03 May 2013 17:43 UTC

Return-Path: <pete@petertodd.org>
X-Original-To: openpgp@ietfa.amsl.com
Delivered-To: openpgp@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id 914EE21F8233 for <openpgp@ietfa.amsl.com>; Fri, 3 May 2013 10:43:49 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1
X-Spam-Status: No, score=-1 tagged_above=-999 required=5 tests=[RCVD_IN_DNSWL_LOW=-1]
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id n7YtuQOdowz7 for <openpgp@ietfa.amsl.com>; Fri, 3 May 2013 10:43:44 -0700 (PDT)
Received: from outmail148110.authsmtp.com (outmail148110.authsmtp.com []) by ietfa.amsl.com (Postfix) with ESMTP id E1A7B21F8201 for <openpgp@ietf.org>; Fri, 3 May 2013 10:40:23 -0700 (PDT)
Received: from mail-c235.authsmtp.com (mail-c235.authsmtp.com []) by punt7.authsmtp.com (8.14.2/8.14.2/Kp) with ESMTP id r43HeIwm044980 for <openpgp@ietf.org>; Fri, 3 May 2013 18:40:18 +0100 (BST)
Received: from petertodd.org (petertodd.org []) (authenticated bits=128) by mail.authsmtp.com (8.14.2/8.14.2/) with ESMTP id r43HeFt6059137 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO) for <openpgp@ietf.org>; Fri, 3 May 2013 18:40:17 +0100 (BST)
Date: Fri, 3 May 2013 13:40:15 -0400
From: Peter Todd <pete@petertodd.org>
To: openpgp@ietf.org
Message-ID: <20130503174015.GA4310@petertodd.org>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="LZvS9be/3tNcYl/X"
Content-Disposition: inline
User-Agent: Mutt/1.5.21 (2010-09-15)
X-Server-Quench: 84fd25dc-b418-11e2-b5c5-002590a15da7
X-AuthReport-Spam: If SPAM / abuse - report it at: http://www.authsmtp.com/abuse
X-Authentic-SMTP: 61633532353630.1023:706
X-AuthFastPath: 0 (Was 255)
X-AuthVirus-Status: No virus detected - but ensure you scan with your own anti-virus system.
Subject: [openpgp] Timestamping
X-BeenThere: openpgp@ietf.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: "Ongoing discussion of OpenPGP issues." <openpgp.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/openpgp>, <mailto:openpgp-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/openpgp>
List-Post: <mailto:openpgp@ietf.org>
List-Help: <mailto:openpgp-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/openpgp>, <mailto:openpgp-request@ietf.org?subject=subscribe>
X-List-Received-Date: Fri, 03 May 2013 17:43:49 -0000

I've been working on and off on a open-source timestamping package
called OpenTimestamps (https://github.com/opentimestamps)

It's based on hashing, usually by combining many digests into a merkle
tree, with the tip digest being timestamped by some method. To date it's
been used with the Bitcoin blockchain as the timestamping method, but
the architecture is notary agnostic - RFC3161 support is on my TODO list
for instance.

The actual structure of a timestamp consists of a set of operations,
generally hash algorithms, forming a DAG. The operations are computed,
and provided the path from the input digest to the notarized
timestamp(s) is valid one can prove that the data existed before the
time. Nothing very exciting really in terms of actual crypto, but as far
as I know my project is the first to attempt a flexible, general
solution based on hashing that can, in principle, support a variety of
notary methods.

Timestamping came up on the GnuPG mailing list, and Werner Koch
suggested I look into adding timestamps to OpenPGP signatures as
Signature Notation Data. In short the timestamp would apply to the
digest of the data being signed proving that it existed before some
particular time; the timestamp would act to prove the Signature Creation
Time field was correct, at least in one direction.(1) Timestamps on data
is one obvious applications. Timestamping PGP keys is another, although
actually doing so usefully is tricky.

Lets look at data first. Signature Notation Data can either be signed or
unsigned. A timestamp should be stand-alone - its validity must depend
on the notary rather than the user - so there really isn't any need to
actually sign the timestamp itself other than to say the user intended
for it to be there.

Another factor favoring unsigned timestamps is that with hashing-based
timestamps they often can be extended after the fact. For instance, in
GuardTime's implementation a timestamp is first submitted to a 'level'
with a 1 second interval, quickly returning the timestamp. However its
only later that the merkle tree is timestamped permanently by inclusion
into a widely-witness newspaper ad. An unsigned timestamp allows you to
extend your timestamp after the fact to include all the intermediary
digests required to link it to that permanent, trustworthy record.
Similarly timestamps from different notaries may be collected at a later

However, timestamping signatures themselves can also be useful. If a key
is compromised after some known date, a timestamp of a signature before
that date can still be trusted.

As for timestamping PGP keys in theory it can help determine
trustworthyness by making the assumption that the earlier key is the one
that is valid. (in addition to WOT and other evaluations) However, it is
not as simple as just timestamping the fingerprint of the primary key,
because an attacker can always re-use an existing key, and create new
User ID packets and sign them; you need to sign the User ID packets as
well. Unfortunately this isn't a very easy to understand user
experience, and evaluating exactly what is being proven is subtle.

Regardless all this does suggest that one timestamp packet be used for
the whole signature allowing for multiple elements to be incorporated
into one merkle tree within that packet to be timestamped in one go,
saving space. In this case I think it would make most sense to either
define a new packet type, or simply use a signature packet missing the
actual signature. The latter doesn't really seem ideal though, for
instance it would require a redundent signature creation time.

Anyway, I'd appreciate some comments on my line of thought, in
particular what people think of trade-offs between the simplicity of one
timestamp per signature, and trying to have some sort of common
timestamp packet containing a DAG of hash operations for all timestamped
data, as well as the usefulness of integrating timestamping into OpenPGP
signatures in general.

1) Potentially random beacons such as the Bitcon blockchain or the under
development NIST beacon could be used to prove a signature was created
after a given time, but a random beacon can only prove the signature,
not the data being signed.