HOWTO prepare for migration away from SHA-1 in OpenPGP

Last week at eurocrypt, a small group of researchers announced a fairly serious attack against the SHA-1 digest algorithm, which is used in many cryptosystems, including OpenPGP. The general consensus is that we should be moving in an orderly fashion toward the theater exits, deprecating SHA-1 where possible with an eye toward abandoning it soon (one point of reference: US gov't federal agencies have been directed to cease all reliance on SHA-1 by the end of 2010, and this directive was issued before the latest results).

Since Debian relies heavily on OpenPGP and other cryptographic infrastructure, i'll be blogging about how Debian users can responsibly and carefully migrate toward better digests. This post focuses on some first steps for users of gpg, and for Debian Developers and Debian Maintainers in particular.

The good news is that gpg and gpg2 both support digest algorithms from the stronger SHA-2 family: SHA512, SHA384, SHA256, and SHA224.

By using these stronger digest algorithms some of your signatures may be un-readable by users of older software. However, gpg and PGP (a proprietary implementation) have both had support for at least SHA256 for well over 5 years. Debian's gnupg packages have supported the full SHA-2 family since sarge.

However, most existing signatures in today's Web of Trust were made over the SHA-1 digest algorithm, which means that abandoning it immediately would cause the Web of Trust as we know it to evaporate. So we need to rely on old signatures until a reasonably-fleshed out Web of Trust based on stronger digests is in place. Since we don't want to have to rely on SHA-1 for too much longer, we need to collectively start the transition now.

So what can you do to help facilitate the move away from SHA-1? I'll outline three steps that current gpg users can do today, and then i'll walk through how to do each one:

The first two are simple, quick, and painless actions. You'll be done with them in minutes! The third is tougher, and while you can start it today, key transitions take a little bit of time to complete. Read on for a HOWTO!
Start making data signatures and web-of-trust certifications using stronger digests

The simplest thing that you can do is to start making signatures using stronger digests by default. Add two lines to the end of your GnuPG configuration: 

cat >>~/.gnupg/gpg.conf <<EOF
personal-digest-preferences SHA256
cert-digest-algo SHA256
EOF

This will cover most messages sent out, including clearsigned messages that are sent to mailing lists, and signatures over Debian packages.

Indicate that you prefer stronger digests when receiving signed messages privately

Your preferences for the types of digest you wish to receive will be published to the public keyservers, so people who send you signed messages will know that you can (and prefer to) accept messages signed by stronger digests. The example assumes that your OpenPGP key ID is $KEYID: 

testy@foo:~ $ gpg --edit-key $KEYID
gpg (GnuPG) 1.4.9; Copyright (C) 2008 Free Software Foundation, Inc.
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.

Secret key is available.

pub  2048R/8A4EA1C3  created: 2009-05-06  expires: 2010-05-06  usage: SC  
                     trust: ultimate      validity: ultimate
[ultimate] (1). Test User (DO NOT USE) <test@example.org>

Command> showpref

[ultimate] (1). Test User (DO NOT USE) >test@example.org<
     Cipher: AES256, AES192, AES, CAST5, 3DES
     Digest: SHA1, SHA256, RIPEMD160
     Compression: ZLIB, BZIP2, ZIP, Uncompressed
     Features: MDC, Keyserver no-modify

Command> setpref SHA512 SHA384 SHA256 SHA224 AES256 AES192 AES CAST5 ZLIB BZIP2 ZIP Uncompressed
Set preference list to:
     Cipher: AES256, AES192, AES, CAST5, 3DES
     Digest: SHA512, SHA384, SHA256, SHA224, SHA1
     Compression: ZLIB, BZIP2, ZIP, Uncompressed
     Features: MDC, Keyserver no-modify
Really update the preferences? (y/N) y

You need a passphrase to unlock the secret key for
user: "Test User (DO NOT USE) <test@example.org>"
2048-bit RSA key, ID 8A4EA1C3, created 2009-05-06

                  
pub  2048R/8A4EA1C3  created: 2009-05-06  expires: 2010-05-06  usage: SC  
                     trust: ultimate      validity: ultimate
[ultimate] (1). Test User (DO NOT USE) <test@example.org>

Command> save
test@foo:~ $

The important command here is the weird, long setpref line — you need to type the whole thing: 

setpref SHA512 SHA384 SHA256 SHA224 AES256 AES192 AES CAST5 ZLIB BZIP2 ZIP Uncompressed
Note that we're setting digest, cipher, and compression preferences all at once here. Note also that gpg displays the implied 3DES cipher and SHA1 digest at the end of your stated preferences even though you did not ask for them. This is because RFC 4880 requires implementations to support these two algorithms, and gpg is subtly informing you that people might end up using them anyway, even though you aren't asking for them.

Now that the preferences are updated, publish them to the public keyservers so that your correspondents can discover them: 

test@foo:~ $ gpg --keyserver keys.gnupg.net --send-key $KEYID
gpg: sending key 8A4EA1C3 to hkp server keys.gnupg.net
test@foo:~ $

That does it!

Replace your 1024-bit DSA keys with 2048-bit RSA keys or larger

The Digital Signature Algorithm, in its original form, only allowed maximum 1024-bit asymmetric keys, and the signature process itself signs a 160-bit hash, initially officially specified as SHA-1. This means that 1024-bit DSA keys should be phased out as well.

So if you have a 1024-bit DSA key as your primary key (this is the vast majority of Debian Developers: 1675 out of 2243 keys in /usr/share/keyrings/debian-keyring.gpg are DSA-1024), you should consider creating a new primary key and starting the migration process.

Also, if you are responsible for a DSA-1024 OpenPGP primary key for a Debian team, role, or archive, please consider something similar to the process below for the Debian-related key as well. I'm happy to note that the Debian Archive Automatic Signing Key (5.0/lenny) <ftpmaster@debian.org> has a 4096-bit RSA primary key, but unfortunately most of our other important infrastructural keys are still 1024-bit DSA.

A reasonable migration process over the course of 3 months might be:

  1. (day 0) Create a new key, using 2048-bit RSA at least (gpg appears to be about to change the default key generation to 2048-bit RSA shortly, if you need more justification). Be sure to configure ~/.gnupg/gpg.conf to use the stronger digest before creating the new key, and set up strong digest preferences on the new key (see above) immediately after key creation. Send the new key to the public keyservers. Generate a revocation certificate too, and store it in a safe place!
  2. (day 0) Sign your new key with your old one (not the other way around!), and publish the signature. Write up a transition statement (here's an example from an earlier key transition), clearsign it with both keys (old and new), and publish it in a stable place.
  3. (day 0) Write up or print out the User IDs and fingerprint of your new key on paper to hand out to people.
  4. (day 0 through day 90) Collect certifications binding the new key to your User ID to re-establish your connection to the Web of Trust. Some reasonable ways to do this effectively are
    • local keysigning parties (e.g. in NYC this coming Friday, 2009-05-08),
    • debconf (less than 90 days away!), and
    • contacting known and trusted friends, pointing them to the transition statement and asking them to reissue their certifications.
  5. (day 0 through day 90) Review the set of public certifications you've made (keys you've signed) with your old key. For keys you believe to still be active (maybe you want to check with the key owner), issue a new certification with your new key. If you get a request for new keysignings, use your new key during this period.
  6. (well before day 90) Ensure that your new key is in available everywhere you need it to be (like the Debian keyring). Use your new key in those contexts and make sure it is accepted and acceptable.
  7. (day 90) Publish your stored revocation certificate for your old key. You had a revocation certificate for the old key already, right? If not, generate a new one, and publish it.

I welcome comments and suggestions about anything i've missed or screwed up here. The steps above do not complete the removal of SHA-1, but (if most of us take similar action soon) they lay the groundwork for an orderly and non-disruptive abandonment of SHA-1 in the future. The sooner this groundwork is in place, the less susceptible our infrastructure will be to potential compromise by reasonably-well-funded organizations.

That wraps up this set of suggestions. As i work through other consequences and practicalities around the gradual deprecation of SHA-1, i'll post more notes on this blog. Questions and pointers are welcome!