Upgrading Debian's keys

One of the requirements of being a Debian Developer (DD) is to have a GnuPG public key on the Debian keyring. But a surprising number of those keys are still 1024 bits in length, even though the keyring maintainers have had a policy of only accepting larger keys (at least 2048 bits, but preferably 4096) since 2010. The keys are used to sign packages that are uploaded to the Debian repositories, so shorter keys could, potentially, allow an attacker to upload a compromised package. The number of shorter keys is starting to concern some in the project, who are now looking at ways to encourage and/or require key-size upgrades. But getting signatures from (at least) two other DDs on a new key may pose a bit of a problem for some.

The discussion started when Clint Adams posted some statistics from the three keyrings (debian, debian-maintainers, and debian-nonupload). As Debian project secretary Kurt Roeckx pointed out, that means that 61.5% of keys are only 1024 bits in length. He continued:

Roeckx suggested that those DDs generate new, longer keys immediately. In fact, Bart Martens thinks it is so critical that the 1024-bit keys should just be removed from the keyring immediately. But, as Gunnar Wolf, one of the keyring maintainers, said, it is not possible to lock out that many keys, so the keyring maintainers are currently trying to figure out how to handle the problem. Many of those keys are integral to the web of trust (WoT), so new keys would need to get signed and to sign other keys before they will be good replacements. And for those DDs who are not particularly "socially connected", what can be done to help them get their keys signed by the requisite two other DDs?

On the other hand, Martens believes that the web of trust is already compromised by the weak keys. Removing those keys from the Debian keyring doesn't delete their existence, just their trust by Debian (so the WoT is unaffected from that perspective).

The keys are used by DDs to sign packages for the distribution, so removing them from the Debian keyring would mean those packages could not be updated—at least by the usual maintainer. Another DD could step in to sign the package, but there are logistical problems with that approach. It would be best to get the keys updated voluntarily, but soon.

There were suggestions that perhaps a majority of the short keys belong to inactive DDs, but Debian project leader Lucas Nussbaum indicated that is not the case. Several advocated setting some kind of deadline, and possibly relaxing the two-signature requirement in some cases. There were arguments both for and against allowing fewer signatures, but there are DDs in isolated locations, so some accommodation for them needs to be found.

Jonathan McDowell, who is another keyring maintainer, described the process to be followed when a DD needs or wants to change a key that has not been compromised (not surprisingly, compromised keys are dealt with quickly, and without any bureaucracy). It is a rather involved process that include a formal request (with old and new key signatures, along with a reason for the change) signed by the existing key, a new key that must be signed by the old key, and the new key that must already have the requisite signatures from two DDs.

Even some who have new keys and the signatures needed have been waiting, though. Some DDs have been gathering more signatures (for the web of trust) and waiting for another, more urgent call to switch. That led Enrico Zini to suggest increasing the urgency by requesting an immediate switch. After a few months, he suggested emailing those who still have 1024-bit keys directly; a few months after that, start removing keys from the keyring (with announcements to a mailing list).

It's a logistical headache, but one worth solving. Unfortunately, many of the 1024-bit keys are digital signature algorithm (DSA) keys that are using the deprecated SHA-1 hash algorithm. Even those using 1024-bit Rivest-Shamir-Adleman (RSA) keys with SHA-256 or SHA-512 hash algorithms are vulnerable to brute-force attacks (which can be done completely silently, unlike "rubber-hose cryptanalysis" and other techniques, as Russ Allbery pointed out). We have seen efforts to insert backdoors into various source distribution chains, so compromising a Debian key to distribute malware is certainly not beyond imagination.

It is a bit unfortunate, perhaps, that the effort to get keys updated to version 4 of the OpenPGP standard (which was completed in 2010) did not mandate a larger key size. At the time, 1024-bit keys were a reasonable choice, but, as expected, compute power has started to outrun them. Requiring 2048-bit (or even 4096-bit) keys back then might have avoided the current logjam. But hindsight is always 20/20, they say.