Subject: [openpgp] Timestamping

From: Peter Todd <[email-masked]>
Date: Fri, 3 May 2013 13:40:15 -0400

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

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.

-- 
'peter'[:-1]@petertodd.org
000000000000006513af2c989a1c0530f7676c1d1b621874fcbfe3065ff7d304

---

From: Ben Laurie <[email-masked]>
Date: Fri, 3 May 2013 20:06:43 +0100

You might be interested in Certificate Transparency:
http://www.links.org/files/CertificateTransparencyVersion2.1a.pdf

On 3 May 2013 18:40, Peter Todd <[email-masked]> wrote:
> _______________________________________________
> openpgp mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/openpgp
>

---

From: Peter Todd <[email-masked]>
Date: Sat, 4 May 2013 14:50:57 -0400

> http://www.links.org/files/CertificateTransparencyVersion2.1a.pdf

I think I've read that paper before actually, or perhaps the EFF's
version, but yes, CA transparency schemes are interesting to me and I
think they too could benefit from timestamping as an additional source
of auditing.

Bitcoin in particular I find interesting because it's the first
trustworthy *decentralized* timestamping scheme to be created. Its
timestamps aren't particularly accurate - Bitcoin has a rule where every
node accepts blocks with a timestamp less than 2 hours ahead of what it
believes the time is - but they can be used in conjunction with other
centralized timestamping schemes to give the guarantee that if the
timestamp was faked, it was at least done so in the past!

Obviously the same guarantee is useful for CA auditing, but I'm probably
getting off-topic here...

-- 
'peter'[:-1]@petertodd.org
000000000000001e37401431b5d24c5f798773655e7fe23cc6bbe3a6a871e492

---

From: "Daniel A. Nagy" <[email-masked]>
Date: Sun, 05 May 2013 22:44:30 +0200

Speaking of timestamps.

There is this feature in OpenPGP (RFC4880, section 5.2.1) called a
standalone signature that is calculated only on its own packet data. It
is, as I understand, useful for including (or referencing by hash) in
newer documents thereby proving (evidencing) that they are NEWER than
the standalone sig, provided that the maker of these standalone sigs can
be trusted to put correct timestamps into them. By contrast, timestamp
sigs prove (well, evidence) that the document is OLDER than the sig.

Question:

Is there any OpenPGP implementation that creates and correctly
interprets such signatures?

I am asking, because GnuPG 1.4.11 seems not to handle them the way I
think it should. I created a script that creates signatures on an empty
binary document, which verify fine with gpg, but if I change the
signature type to standalone sig, gpg complains. This might be a gpg
issue, but I would like to see a working reference implementation.

In general, I think the new standard (or a separate RFC) should include
test vectors (example data) for all packet and subpacket types discussed
in the standard to remove ambiguity.

Daniel