Welp, there go my Git signatures

Hello!  If you already know about the RoCA vulnerability, and you know what I did about it (or you don’t care), then feel free to skip down to the good stuff!

Signs of Trouble

Monday morning, as I was on the bus to work, I received a very curious email from GitHub.

Hello akkornel,

GitHub has recently implemented new measures to identify and block insecurely generated SSH keys from being added to accounts. GitHub has also analyzed all existing keys that were added before this additional validation was in place.

As a result of these new measures the following key was identified and removed from your account:

Yubikey-based key
58:1a:a7:99:fd:14:3e:3b:f9:67:a5:ca:d4:00:cb:dd

My first thought was that I was being phished somehow.  I assumed that the key fingerprint was valid—GitHub’s API allows anyone to get any user’s public keys—but the email was a plain-text mail with no links and no attachments, so it didn’t seem like phishing.  That, plus the fact that my SSH key description was included in the email (something that isn’t something available publicly), made me concerned.

The first place I went to was Yubico’s site, where I found a link to their blog post about the Infineon RSA Issue, also known as CVE-2017-15361 or the “Revenge of Coppersmith’s Attack” (RoCA).  When I got to work, I was able to use the public key tester to confirm that my two Yubikey-generated public subkeys (one for signing; one for authentication) were vulnerable.  Great.

A quick aside: After reading the Yubico post, I went to post it to Hacker News, only to find it had already been posted overnight.  Yubico had apparently (and likely accidentally) posted about the issue the previous evening, and the post was later pulled.  The Hacker News item hadn’t gotten much attention, but since Yubico’s post was back, I emailed the Hacker News mods, and it got re-posted.  Kudos to them for that!

Making New Keys

My subkeys were affected because I used the Yubikey to generate the private keys.  It’s pretty easy to do!  Assuming that you already have a private key…

  1. Insert your Yubikey NEO or Yubikey 4.
  2. Use gpg --card-status to make sure that GPG can see your key.
  3. Run gpg --edit-key YOUR_KEY_ID addcardkey to have the card generate a key for one of the three slots (encryption, authentication, or signing).  You’ll need your GPG key’s passphrase, the Yubikey’s PIN, and also the admin PIN.

I used the above method to generate my signing and authenticating subkeys, so the Infineon chip handled all the private key generation.  GPG then took the public part of the key (provided by the chip), signed it with my main private key, and added the result to my public GPG key.  As for the private key, GPG stores the serial number of the device, so when it needs the private key, GPG knows which device to ask for!

The upside of all of this is that it’s really hard to get the private key out from where it is stored.  The downside is that I’m trusting in the hardware to generate a good key.

Yubico fixed this issue with firmware 4.3.5, but since Yubikey firmware can’t be upgraded, I had to get a new one.  Happily, Yubico are providing free replacements for people who have vulnerable Yubikeys.  I put my order in on Monday, and the replacement was in my mailbox by Friday.  Kudos to Yubico for the transparency and for offering free replacements!

Another aside: I was thinking of generating ECC keys instead of RSA keys, because the vulnerability only affected RSA key generation.  Unfortunately, the Yubikey 4 implements version 2.1 of the OpenPGP Card specification.  ECDSA keys were added in Version 3.0, so I’m stuck with RSA keys for now.  Also, OpenSSH doesn’t support ECDSA on cards right now, so the most I’d be able to do is a signing ECC key.

Once I had the replacement, I generated new authentication and signing subkeys, and copied my existing encryption subkey to the card.  I also revoked my original signing and authentication subkeys.  The updated public key is available directly now, and will be live on the key servers over the next day or two.

A third aside!  If you copy a subkey to a new card, but GPG keeps asking for you to insert your old card, you’re probably being hit by GnuPG T1983.  Either update GPG or delete the appropriate files from the ~/.gnupg/private-keys-v1.d directory.

Spreading the Word

My new authentication subkey was converted into an SSH public key, and promptly uploaded to both GitHub and Stanford’s GitLab.  But now, what do I do about my signing key?

There are two things about GPG signatures that are working against me here:

  1. I don’t have a record of every signature I made.
  2. GPG signatures include a timestamp, but that comes from the computer’s clock; if someone has my private key, they just need to change their computer’s clock to a time before I revoked my sub-key.

Probably #1 could be solved by better record-keeping, but there’s no way I’d be able to keep the Notary Public-level records that would be required.  Problem #2 can be solved by a third-party timestamp service, which others would have to trust, and which I would have to remember to use.

The best I can do is assume that most of my signatures aren’t really going to be of any importance in the future, except for the ones I’ve recently made.  My most-recent signatures were made for a PGP key signing I went to a week or so before this all happened, so I will just email those participants, letting them know that the signatures from my previous mails will likely fail validation.

That takes care of my regular signatures, but there’s one set left, and these are gonna be much harder to deal with: I have to figure out a way to re-sign all of my signed Git commits.

Ummmmm, What About Git?

This is the big problem.  I have used my now-revoked key to sign tags and commits; in public repositories, and in Stanford-internal repositories.  One of the internal Git repositories mandates that all commits be signed; that repository validates signatures against keys kept in a separate, server-local keyring.

The signed tags are easy enough to deal with: I simply re-create them, using my new key.  The annoyance is that I have to go through each tag to find the ones that I have signed.  Luckily, our Git servers allow overwriting existing tags, so this can be done.

The git commits are harder.  With my now-revoked subkey, old signed commits now come with warnings.  You can see this if you clone my syncrepl project and run git log --show-signature dfddd1a676cdea723fc077972e9588df0cd2730b:

gpg: Signature made Mon Oct 16 22:58:35 2017 PDT
gpg: using RSA key F0C1EF2714C50582915C59F814A7B2A56335B8D5
gpg: Good signature from "Alfred Karl Kornel <karl@kornel.us>" [ultimate]
gpg: aka "Alfred Karl Kornel <akkornel@stanford.edu>" [ultimate]
gpg: aka "Alfred Karl Kornel <karl@kornel.name>" [ultimate]
gpg: aka "Alfred Karl Kornel <kornel.1@osu.edu>" [ultimate]
gpg: WARNING: This subkey has been revoked by its owner!
gpg: reason for revocation: Key has been compromised
gpg: revocation comment: CVE-2017-15361

Tags have a similar problem:

$ git tag -v v0.75
object d802d4410b98726bbe94b8c647aab567ea6da3fa
type commit
tag v0.75
tagger A. Karl Kornel <akkornel@stanford.edu> 1497770140 -0700

The first "release"

This is the point where we actually have a proper setup script!

Of course, it doesn't work yet...
gpg: Signature made Sun Jun 18 00:16:29 2017 PDT
gpg: using RSA key 14A7B2A56335B8D5
gpg: Good signature from "Alfred Karl Kornel <karl@kornel.us>" [ultimate]
gpg: aka "Alfred Karl Kornel <akkornel@stanford.edu>" [ultimate]
gpg: aka "Alfred Karl Kornel <karl@kornel.name>" [ultimate]
gpg: aka "Alfred Karl Kornel <kornel.1@osu.edu>" [ultimate]
gpg: WARNING: This subkey has been revoked by its owner!
gpg: reason for revocation: Key has been compromised
gpg: revocation comment: CVE-2017-15361

The above output comes from Git running locally.  If you look at the syncrepl project’s commits on GitHub, as of posting the commits are all showing Verified.  That is because I have control over the GPG key I upload to GitHub, and I haven’t (yet) updated it to include my revoked sub-keys.

So, what can be done?  The brute-force option would be to go through all of my old commits, identifying which ones were signed by me.  I would then start a new branch off of the next-oldest commit (that is, the one right before my first signed commit).  I would then start a long sequence of git cherry-pick operations.  Each time I cherry-pick a commit that I signed, I would instead do a git cherry-pick -S to update the signature.  In the end, I would have a new branch whose contents match the old branch, but whose signatures have been updated.  My new branch would then take the name of the old branch, and I would force-push up to the server to make it so.

The brute-force method would work, but besides being extremely time-consuming and annoying, there are two other problems:

  • The force-push means everyone else using my repository would have to essentially git reset themselves onto my new branch head.  Any commits others have made since then would have to be cherry-picked.
  • If anyone else in the sequence has signed commits, we would all have to work together in a carefully-coreographed sequence of cherry-pick-sign—push—wait—pull—cherry-pick-sign—push—et-cetera.  This would have to be done even if other people’s signatures were fine: Because git cherry-pick makes a new commit object, the signature is lost unless the original signer uses git cherry-pick -S to sign the new commit.

Revocation Commit

The solution I devised involves two commits, and a separate out-of-band posting.  Things start before I revoke my now-revoked sub-keys.

First, I make sure that my repository is completely up-to-date.  If I had to pull anything, I make sure that none of the pulled commits use my soon-to-be-revoked sub-key.  I then make a signed empty commit.  An empty commit can be made by appending --allow-empty to your git commit line, in a Git repository where there is nothing ready to be committed.  Git will prompt you for a commit message as normal, and then make the commit as normal.

Here is what my commit message looked like:

No longer using key 14A7B2A56335B8D5

This is an empty commit, in that no files are being changed. This
commit is just here to leave a message, which is that I am revoking my
current signing key:

Signature key ....: F0C1 EF27 14C5 0582 915C 59F8 14A7 B2A5 6335 B8D5
      created ....: 2015-12-13 06:54:47

Today (Monday, October 16, 2017) will be the last day I sign anything
with the above key.

I am revoking this key because of CVE-2017-15361. My signing key was
generated by, and lives on, a Yubikey 4 that is affected by the
vulnerability described in the CVE. Once the details of the
vulnerability are out, it will be possible for others to get my
signing private key.

This affects all of my signed commits and tags. Although re-signing
the tags is possible (which I will do once I have a new key),
re-signing commits is not really possible, because that would cause
the commit ID to change, affecting the rest of the tree, and making it
really hard for other people.

So, I am leaving this note. By leaving this note, I make a new commit
ID. Once I have my new key, I will leave another note, which says
that this commit ID is valid. That makes kind of a chain of trust,
even though it's likely that Git will say the signature of this note
is invalid.

Not only that, but every commit after this one will make it harder for
someone to go back and change the note: The more commits there are
after this note, the more commit IDs will change if this node is
modified; and the more people who have clones of this repo, the bigger
the commit difference will be when they do a pull. Of course, it's
not perfect, but I think it's better than nothing!

Maybe there will be a future way to re-sign commits, in a way that
does not disrupt the repository.

For reference, here are all of my current tags, and their commit IDs:

TAG_NAME COMMIT_ID

The above commit was signed by my now-revoked key.  I then put the following message into another non-empty commit:

Confirming commit dfddd1, and past signatures

This commit-which has been made with my new key-is to confirm that
commit dfddd1a676cdea723fc077972e9588df0cd2730b is valid, and was
signed by the following key:

Signature key ....: F0C1 EF27 14C5 0582 915C 59F8 14A7 B2A5 6335 B8D5
      created ....: 2015-12-13 06:54:47

That commit's signature, and the signatures of the previous commits
which have been signed by the above key, should be trusted as much
as the signatures made with this key.

The commit ID referenced above is the ID of my revoked-signing-key commit.  In this example, this second commit has ID 5204c0a.

As a third party, you start from a known point—the commit ID of the branch tip—and you begin walking back through the commits.  In your trip back, you first come across my signed-and-currently-valid commit, 5204c0a.  That commit says commit dfddd1a is also valid, even though it was signed by a now-revoked key.  I also give the ID of the now-revoked sub-key, for future reference.

Eventually you reach commit dfddd1a.  Git confirms that it is signed by a revoked sub-key, but the signature comes from the sub-key mentioned in the validly-signed commit 5204c0a.  Commit dfddd1a lists the same sub-key ID, and explains the reason for the revocation.

At this point, as long as you trust my current sub-key (which signed commit 5204c0a), you should also trust commit dfddd1a.  At that point, you can decide on the validity of my other commits:

  • Commits older than commit dfddd1a, and which were signed by my now-revoked sub-key, should still be OK, because you can trace a direct path back from the “validating commit” 5204c0a.
  • Commits newer than commit dfddd1a, and which were signed by my now-revoked sub-key, are to be treated with suspicion, because they were made after I explicitly said that I would stop using my now-revoked sub-key.

At this point, I can only think of two ways for someone with my revoked sub-key to get new commits into the repository:

  1. Someone could have slipped in a signed commit before commit dfddd1a, and gotten that pushed to the Git server, before I did my pull.  Or they could have gotten it onto my computer by some other means.
  2. Someone could do a force-push, adding new (bad) commits; and replacing commit dfddd1a with a new commit, using the same text, and signed by my now-revoked key.

The defense against threat #1 is to do the “revocation commit” as soon as possible when it is known that the key is compromised.  For extra safety, do a manual review of recent previous signed commits, and do a git fsck --strict to make sure your local copy is intact.

The defense against threat #2 is to have a separate out-of-band posting.  This posting takes the form of a table, containing three items:

  1. The Git repository in question.
  2. The commit ID of my “revocation commit”.
  3. The commit ID of the first commit with my new sub-key.

In my case, I have both public and private repositories, and I do not want to expose the names of the private repositories, so I am just including the commit IDs.  Here is the table:

Last commit signed by my revoked sub-key  First commit signed using my new sub-key
2af1083219692bf5046bac2c815656358fcda71f  4793f2c8fa5a69dcc351927039724704fca5dac0
bedb51ebee32838e0c9359fcca044e97ff1c3677  ccf9d4e03d757759c4b34579dad763be4e1cf21d
0473090599c505e78dd9fa8399d4b858e2ecc653  bf148ded0854093e0e4ce05c81210583b193997d
dfddd1a676cdea723fc077972e9588df0cd2730b  5204c0a9c834d6832383d79befae47e0493570de
922844e6c6c24f38be7bb8fca8c2c001a399a87e  0e0c349cac0dc4bcfec297403ecb04faccc64a2c
f087f79ec6d9f58d19a16b1ec15d7627430835c1  ec3f51d4d03d1663d851f969b73adaff013e370e

I also have the table available separately as a GitHub Gist, the idea being that having the same info around in multiple places will make it hardware for that info to be lost or modified.  I’m also having this post picked up by the Internet Archive‘s Wayback Machine.  The Gist is also signed by my new sub-key.

I think it is OK to leave off the repository identifier from the table, because commit IDs should be unique enough that the chance of the same commit ID appearing twice in one of the columns is very unlikely.  It does make things harder to verify (you don’t know which row to check), but to be honest, it’s unlikely that you’ll need this table (though it’s still good to have!).

Future Alternatives

What I’ve done is, in my opinion, a good human-readable solution.  I’m sure there are problems that I’ve missed, but I hope this provides at least some protection.  Of course, this only works if a human actually reads it: programs using git verify-commit will continue to complain about commits made with my revoked sub-key.

I already discussed the brute-force solution, where a careful dance is performed to make a new sequence of re-signed commits.  But I wonder if—in the future—there could be another way, one that doesn’t involve rewriting history?

The problem to be addressed is this: You need to be able to sign objects that already exist, without rewriting the object (because changing the object will likely change the history).  My suggestion is that there be a new object type, like a detached signature, and a new file free under .git or .git/refs.

For reference, a signed tag object looks like this:

object 30b86d0364c624ca6608dcf678e55d93f61f79c0
type commit
tag v0.95
tagger A. Karl Kornel <karl@kornel.us> 1502868191 -0700

Tag message here

-----BEGIN PGP SIGNATURE-----
Comment: GPG version 2.x

PGP Signature here
-----END PGP SIGNATURE-----

The signed object includes the name of the tag (which should match the filename in .git/refs/tags), the identity of the signer (which should match the signature), and the type and ID of the tagged commit.  Let’s use that as a template to make a new object, to represent an additional, “detached” signature on an existing object:

object 30b86d0364c624ca6608dcf678e55d93f61f79c0
type commit [or "tag"]
sign [Key ID]
signer A. Karl Kornel <karl@kornel.us> 1502868191 -0700

-----BEGIN PGP SIGNATURE-----
Comment: GPG version 2.x

PGP Signature here
-----END PGP SIGNATURE-----

Again we have the type and ID of the tagged commit, but we now explicitly include the ID of the signing sub-key (which should match the signature).  And we still have the identity and time that the signature was made.  All of these pieces help to ensure that we get a unique object hash.

Now that we have an object hash, where do we put it?  My thought is to have a new directory—either in .git or in .git/refs—called signatures.  The directory would be structured similar to the object directory:  The first level would be two-character hash prefixes (00 through ff).  The second level would be object hashes: If you have an object with multiple signatures, the second level will have a directory whose name is the hash.  Finally, on the third level, you would have files: The file name would be the ID of the signing key or sub-key; the contents would be the object ID of the detached signature object (which I described above).

Checking for detached signatures would involve a check of the signatures directory.  If detached signatures were found, then Git would be able to evaluate all of the signatures, and make a decision about the validity of the commit.

So, what do you think?  It seems to me that signed commits aren’t used very much right now, but the functionality exists, and I think my experience exposes a weakness in how signed commits are implemented.  I want to keep the history, but keys either age out (through loss or expiration) or are revoked; there has to be a way of dealing with commits that are good, but whose signing keys have been revoked some time after the signature was made.

I’ve done the best I can with my weird, “empty” commits, and I hope a way is found to implement something appropriate!