While Git supports PGP signing for tags and commits natively, like other uses of PGP a major caveat exists: How do you verify a signature from a revoked or expired key? Joanna Rutkowska, co-founder of QubesOS, explains the problem on her blog:

My signing keys (e.g. blog or Qubes code signing keys) do not have expiration dates. This is not laziness. There is a fundamental problem with using an expiration date on keys used for code signing (e.g. git tag -s), because it is unclear what the outcome should be when one verifies some old code (written and signed when the key was still valid) in the future when the key has already expired?

Naturally we would like the old code, written and signed when the key was still valid, to continue to verify fine also in the future, after the key expires (and the developer passed away, perhaps). However, it is very problematic to prevent the attacker from creating falsified code pretending to be an old one.

In this article we’ll outline the key revocation problem, explain how timestamping can help solve it, and show how OpenTimestamps integrates with PGP signed Git commits to do just that in the context of software integrity. If you don’t already know what OpenTimestamps is, you may want to read my previous post on it first.

Acknowledgements: The functionality described below was supported by BTCC’s funding of my Bitcoin development efforts.

Contents

  1. The Key Revocation Problem
    1. Dates in PGP Mean (Nearly) Nothing
    2. Timestamping Can Make Dates Mean Something
  2. Extending PGP Is Hard, But With One Weird Trick…
    1. How It Works
    2. Try It!
  3. What’s Next?
  4. Footnotes

The Key Revocation Problem

In fact, QubesOS itself is a good real-world example of how difficult it is to handle key revocation. I recently had to verify a QubesOS-related signature at a bad time, just after Joanna Rutkowska herself revoked her previous two PGP keys. At the time I happened to have reasonable assurance that this earlier key was in fact valid:

$ gpg --list-key 391764A2D7C45BCE
pub   1024D/391764A2D7C45BCE 2004-01-20 [revoked: 2016-07-14]
uid                          Joanna Rutkowska <joanna@invisiblethingslab.com>
uid                          Joanna Rutkowska <joanna@mailsnare.net>
uid                          Joanna Rutkowska <joanna@invisiblethings.org>
uid                          Invisible Things Lab <contact@invisiblethingslab.com>

I however needed to know if this later key was valid:

$ gpg --list-sigs 3393D8BF0DDC6718
pub   4096R/3393D8BF0DDC6718 2015-02-07 [expires: 2017-02-07]
uid                          Joanna Rutkowska (ITL Email Key) <joanna@invisiblethingslab.com>
sig          391764A2D7C45BCE 2015-02-11  Joanna Rutkowska <joanna@invisiblethingslab.com>
sig          391764A2D7C45BCE 2015-02-11  Joanna Rutkowska <joanna@invisiblethingslab.com>
sig          5FA6C3E4D9AFBB99 2015-02-07  Joanna Rutkowska (Master Signing Key)
sig          DA4230CC10B0B381 2015-03-03  Hadrien Majoie  <hadrien.majoie@gmail.com>
sig          1B9184DF9E117718 2015-11-14  tailsjoin
sig          EE2913AF59D39789 2016-03-13  Eugene Maartens <emaart111@gmail.com>
sig 3        3393D8BF0DDC6718 2016-02-08  Joanna Rutkowska (ITL Email Key) <joanna@invisiblethingslab.com>
sig 3        3393D8BF0DDC6718 2015-02-07  Joanna Rutkowska (ITL Email Key) <joanna@invisiblethingslab.com>
sub   4096R/B8556936AE919A53 2016-02-08 [expires: 2017-02-07]
sig          3393D8BF0DDC6718 2016-02-08  Joanna Rutkowska (ITL Email Key) <joanna@invisiblethingslab.com>

The later key is signed by the earlier key, which normally would indicate that if I believed the earlier key was valid and was in fact controlled by Joanna I could trust that the signature from that key on the later key indicated that the later key was also valid; I didn’t have any reason to trust the other signatures on that second key.

However at the time, the earlier key had just been revoked. I didn’t happen to know why, but one possiblity of course what that the key had been compromised. If this were true, the later key might have been a fake created by an attacker.

Dates in PGP Mean (Nearly) Nothing

Now, you’ll notice in the GnuPG listings above how PGP has dates all over the place - why I’m talking “earlier” and “later” keys in the first place. But these can be highly misleading, because the only thing certifying them is the keys signing them.

For instance, notice how the later key was signed by the earlier key on 2015-02-11, over a year before the apparent revocation of that key on 2016-07-14. You might naively think that means that the certification signature can’t be created by the attacker - obviously it was created a year prior right?

Unfortunately, without additional evidence, we just don’t know that: since the only thing guaranteeing dates in PGP is the keys themselves; if an attacker now has access to Joanna’s earlier key, they can create as many backdated certification signatures on fake keys as they want.

So what did I do? I cross-checked that the key was correct in few ways, including checking archive.org and asking Joanna on Twitter. Frankly, quite a bit of work, and this is a problem I’ve run into multiple times in this past year alone.

People say we need to make PGP easy enough for a gorilla to use, but at this rate we’ll be lucky if we succeed at making PGP easy enough for Phil Zimmerman to use.

Timestamping Can Make Dates Mean Something

However with timestamp proofs we can improve this situation greatly. If OpenTimestamps was integrated into PGP, it’d be possible to timestamp certification signatures, proving that the signature existed at the time the date on it claimed it existed. With this proof, I could have been confident that even though the Joanna’s earlier key was revoked, the signature certifying her later key by that now-revoked earlier was in fact created by her, not an attacker. It’s a better UX too: with timestamps dates in PGP would mean what people expect them to mean, accurate dates, rather than having to think carefully about what keys signed what date.

Interestingly you don’t even need particularly accurate timestamps to accomplish this. While people often complain about the accuracy of Bitcoin timestamps - a few hours with conservative assumptions - in this example, even if the timestamp was only accurate to the nearest week it’d be more than good enough proof: the data the revocation claims1 to have happened is over a year after that signature was created.

Extending PGP Is Hard, But With One Weird Trick…

Unfortunately, for a variety of reasons adding OpenTimestamps support to the OpenPGP protocol directly isn’t easy. GnuGP doesn’t support plugins, and there doesn’t even exist a fully-featured GnuPG library to use - just the highly limited GPGME library, which doesn’t give you anything close to direct access to the underlying OpenPGP protocol.

However adding OpenTimestamps to Git is surprisingly easy, and we can do it in a way that’s backwards compatible with non-OpenTimestamps-aware Git clients. Here’s it in action, verifying a tag:

$ git tag -v opentimestamps-client-v0.2.1
object fe19cd28c0685505ff3c2f6bfcb4d18abc85efa2
type commit
tag opentimestamps-client-v0.2.1
tagger Peter Todd <pete@petertodd.org> 1474872017 -0400

Release opentimestamps-client-v0.2.1
ots: Success! Bitcoin attests data existed as of Mon Sep 26 02:45:43 2016 EDT
ots: Good timestamp
gpg: Signature made Mon 26 Sep 2016 02:40:18 AM EDT
gpg:                using RSA key 6399011044E8AFB2
gpg: Good signature from "Peter Todd <pete@petertodd.org>"
gpg:                 aka "[jpeg image of size 5220]"

Similarly, we can verify timestamps on PGP-signed Git commits:

$ git log --show-signature 6a1c61a8dfbbcca672858500fcd11ecfeb34d8cc
commit 6a1c61a8dfbbcca672858500fcd11ecfeb34d8cc
ots: Got 1 attestation(s) from https://alice.btc.calendar.opentimestamps.org
ots: Got 1 attestation(s) from https://bob.btc.calendar.opentimestamps.org
ots: Success! Bitcoin attests data existed as of Mon Sep 26 01:29:48 2016 EDT
ots: Good timestamp
gpg: Signature made Mon 26 Sep 2016 01:28:08 AM EDT
gpg:                using RSA key 6399011044E8AFB2
gpg: Good signature from "Peter Todd <pete@petertodd.org>"
gpg:                 aka "[jpeg image of size 5220]"
Author: Peter Todd <pete@petertodd.org>
Date:   Mon Sep 26 01:27:51 2016 -0400

    Improve error message when ./ots stamp encounters IO errors

Once Git integration has been setup, creating a timestamped Git commit or tag is no different than a normal PGP-signed commit or tag. OpenTimestamps does all the work for you automatically, and with its public calendar system you don’t have to wait for a Bitcoin confirmation; timestamps that anyone with a Bitcoin node can verify later are created in about a second.

How It Works

Under the hood a Git commit is simply a few lines of text:

$ git cat-file -p 7b94d37a71a236227c443e0f46e885101401020c
tree 8faa3b9a240f4742d41b12fb62e95f8af25feb5e
author Peter Todd <pete@petertodd.org> 1349397737 -0700
committer Peter Todd <pete@petertodd.org> 1349397737 -0700

Initial commit

A signed Git commit adds a ASCII-armored PGP signature:

$ git cat-file -p a9d1ffc2e10dafcf17d31593a362b15c0a636bfc
tree 548b1c88f537cd9939edeea094bfaff094f20874
parent 53c68bc976c581636b84c82fe814fab178adf8a6
author Peter Todd <pete@petertodd.org> 1432826886 -0400
committer Peter Todd <pete@petertodd.org> 1432827857 -0400
gpgsig -----BEGIN PGP SIGNATURE-----
 
 iQGrBAABCACVBQJVZzfSXhSAAAAAABUAQGJsb2NraGFzaEBiaXRjb2luLm9yZzAw
 MDAwMDAwMDAwMDAwMDAwMjFmZmUwZDk5ZmY5ZTJmNjI4YTc2M2JmN2NkZDUzYjY4
 YzEzYzYxNzg5ZTdhNDMvFIAAAAAAFQARcGthLWFkZHJlc3NAZ251cGcub3JncGV0
 ZUBwZXRlcnRvZC5vcmcACgkQJIFAPaXwkfuCcgf9HXnqAF17nzlv6slq4qdX2agQ
 7rPWUtD8tGt0KVYAPmmijZ3guDRF4ISuUgcer4ixmBBezssKQG3ghqnlhq6OudBW
 T/MpVhkhIG3EDs58muhCsORPqO0CirhDiA5QFcZdCj/R7PDbZEygmI5OpS0HJK1j
 9oeDEDuItV/450tfjd4eSOcnSkqvQBO822U70VdmO4MbHkG5kZ1mHJ6FyxfW737b
 hgayzXP1rEURmobsczBXa8jUyg/c30vxwV9yJkzWNFISvZK4/nXgnyWk5ft8cn5V
 YzMjt5lQuJwX/r6/MdRPRorPIOxdxUQzSN+8s8soZ3gqdIH/fuqCra7s2cntrw==
 =Lfsu
 -----END PGP SIGNATURE-----

Add working ots command line utility

What the signature actually signs is simply the commit minus the signature itself; in the above example the exact data the signature signs is:

$ git cat-file -p a9d1ffc2e10dafcf17d31593a362b15c0a636bfc
tree 548b1c88f537cd9939edeea094bfaff094f20874
parent 53c68bc976c581636b84c82fe814fab178adf8a6
author Peter Todd <pete@petertodd.org> 1432826886 -0400
committer Peter Todd <pete@petertodd.org> 1432827857 -0400

Add working ots command line utility

You can verify this yourself manually with a bit of cut-and-pasting. Interestingly, if you ask GnuPG to verify a ASCII-armored signature with additional stuff at the end that it doesn’t recognise, the verification still works. This allows us to append our timestamp to the end of the signature, while still maintaining compatibility2 with non-OpenTimestamps-aware Git clients:

$ git cat-file -p 48034652a83bb2119777bac5d84d24552454ab1f
tree 25ebb56d6818abc82c8ff7ce9ac801b7ef052094
parent d265224445754a997d0bf06662567ed8c0d4dc25
author Peter Todd <pete@petertodd.org> 1473060568 -0400
committer Peter Todd <pete@petertodd.org> 1473060568 -0400
gpgsig -----BEGIN PGP SIGNATURE-----
 
 iQEcBAABCAAGBQJXzR7wAAoJEGOZARBE6K+yMT4H/jEhfBqe3Nr93SHdwVJ14rGg
 WIOtBG4t9KmJjYCBTXgQRTTI/0F+gGulMRr5jeDTgmQpPNKIHKjv62kPPtcxqQQr
 3AfByOjNLja3saAxEwFI++gkNgdeD7eqJex6P0OnVVixklyznVXvtEq1UoESBHRp
 MIGbLpR3jAgxT58ZPrezHu9p2ifT/uT6MrwjYlvJzOfjK2t9sBLXfUUtzWfmxUNA
 +wfQv/X5vePzcZth0AIKWwPAm77HtBGlJXYg9e8GPUBS6t6t2nHkyQIsgXYeFwFy
 9nf4W3yi1hbuvEV2DtqGQZjF/s9GIhLBS5I5p0RGy4zt55inGImlSekPBSuKzmo=
 =7pUu
 -----END PGP SIGNATURE-----
 -----BEGIN OPENTIMESTAMPS GIT TIMESTAMP-----
 
 AQDwEPyUcFjpQf0P0ntzUeqBn8MI8QRXzR7zAIPf4w0u+QyOLi1odHRwczovL2Fs
 aWNlLmJ0Yy5jYWxlbmRhci5vcGVudGltZXN0YW1wcy5vcmc=
 -----END OPENTIMESTAMPS GIT TIMESTAMP-----

Add Git GnuPG wrapper

Allows signed git commits to be timestamped.

Finally, how do we actually get Git to verify and create timestamps? Simple: Git allows you to override the default GnuPG binary (/usr/bin/gpg) using the gpg.program config option. We use this feature to replace the original gpg binary with a wrapper, git-gpg-wrapper, that in addition to creating and verifying PGP signatures, also creates and verifies timestamps on those signatures.

Try It!

  1. If you haven’t already, setup PGP signing for your Git commits — Wladimir J. van der Laan’s guide aimed at Bitcoin Core developers is a good resource.

  2. Install the OpenTimestamp Client — As of writing v0.2.2 is the most recent release.

  3. Follow the instructions to setup Git integration, under doc/git-integration.md.

That’s it!

What’s Next?

In the short term, I’ve been also working on a scheme to timestamp individual files in Git repositories in a way that allows timestamps for those files to be extracted on an individual basis. The idea here is to make it easier and more efficient to manage timestamps for large numbers of files, where you may want to prove the existence of a particular file without revealing anything about other files. The code to do this is written and I personally use it all the time. I’ll discuss this in a later blog post, although the idea is still experimental and needs a bit more peer review and testing before I’d suggest anyone use it without reading the source first.

In the long term, OpenTimestamps needs to be added to PGP, or quite possibly, PGP needs to be replaced. I’ve been working on a project, Dex, that could one day be the basis for a PGP replacement of some kind; a major goal of my recent work on OpenTimestamps is to eventually provide timestamping infrastructure for Dex and systems like it.

Footnotes

  1. Note how an attacker can also backdate the revocation, making it impossible to verify the signature. Fortunately this is less of a problem, and there are a number of possible solutions such as requiring revocations to commit to random beacons; beyond the scope of this post, but we’ll cover it in a later post.

  2. As of writing, GitHub does not support OpenTimestamp-using signed Git commits, and shows them as “unverified”; I don’t know of any other incompatible Git implementations. Fixed!