One gpg --gen-key per Decade

Tuesday 9 December 2008 by Bradley M. Kuhn

Today is an interesting anniversary (of sorts) for my cryptographic infrastructure. Nine years ago today, I generated the 1024 bit DSA key, DB41B387, that has been my GPG key every day since then. I remember distinctly that on the 350 MhZ machine I used at the time, it took quite a while to generate, even though I made sure the entropy pool remained nice and full by pounding on the keyboard.

The horribleness of the recent Debian vulnerability meant that I have spent a much time this year pondering the pedigree my personal cryptographic infrastructure. Of course, my key was far too old to have been generated on a Debian-based system that had that particular vulnerability. However, the issue that really troubled me this past summer was this:

Some DSA keys may be compromised by only their use. A strong key (i.e., generated with a ‘good’ OpenSSL) but used locally on a machine with a ‘bad’ OpenSSL must be considered to be compromised. This is due to an ‘attack’ on DSA that allows the secret key to be found if the nonce used in the signature is reused or known.

Not being particularly hard core on cryptographic knowledge — most of my expertise comes from only one class I took 11 years ago on Encryption, Compression, and Secure Hashing in graduate school — I found this alarming and tried my best to do some ancillary reading. It seems that DSA keys, in many ways, are less than optimal. It seems (to my mostly uneducated eye) in skimming academic papers that DSA keys are tougher to deploy right and keep secure, which leads to these sorts of possible problems.

I've resolved to switch entirely to RSA keys. The great thing about RSA is its simplicity and ease of understanding. I grok factoring and understand better the complexity situation of the factoring problem (this time, from the two graduate courses I took on Complexity Theory, so my comfort is more solid :). I also find it intriguing that a child can learn how to factor in grade school, yet we can't teach a computer to do it efficiently. (By contrast, I didn't learn the discrete logarithm problem until my Freshman year of college, and I still have to look up the details to remind myself.) So, the “simplicity brings clarity” idea hints that RSA is a better choice.

Fact is, there was only one reason why I revoked my ancient RSA keys and generated DSA ones in the 1990s. The RSA patent and the strict licensing of that patent by RSA Data Security, Inc. made it impossible to implement RSA in Free Software back then. So, when I switched from proprietary PGP to GPG, my keys wouldn't import. Indeed, that one RSA patent alone set back the entire area of Free Software cryptography at least ten years.

So, when I decided this evening that I'd need to generate a new key and begin promulgating it at key-signing parties sometime before DB41B387 turns ten, I realized I actually have the freedom to choose my encryption algorithm now! Sadly, it took almost these entire nine years to get there. Our community did not only have to wait out this unassailable patent. (RSA is among the most novel and non-obvious ideas that most computer professionals will ever seen in their lives). Once the RSA patent finally expired0, we had to then slowly but surely implement and deploy it in cryptographic programs, from scratch.

I'm still glad that we're free of the RSA patent, but I fear among the mountain of “software patents” granted each year, that the “new RSA” — a perfectly valid, non-obvious and novel patent that reads on software and fits both the industry's and patent examiner's definition of “high quality” — is waiting to be discovered and used as a weapon to halt Free Software again. When I finally type gpg --gen-key (now with --expert mode!) for the first time in nine years, I hope I'll only experience the gladness of being able to generate an RSA key, and succeed in ignoring the fact that RMS' old essay about this issue remains a cautionary tale to this very day. Software patents are a serious long-term threat and must be eradicated entirely for the sake of software freedom. The biggest threat among them will always be the “valid”, “high quality” software patents, not the invalid, poor quality ones.


0 Technically speaking, RSA didn't need to expire. In a seemingly bizarre move, RSA Data Security, Inc. granted a Free license to the patent a few weeks before the actual expiration date. To this day, I believe the same theory I espoused at the time: their primary goal in doing this was merely to ruin all the “RSA is Free” parties that had been planned.

Posted on Tuesday 9 December 2008 at 21:52 by Bradley M. Kuhn.

Submit comments on this post to <bkuhn@ebb.org>.
If you like this post, you can send me gifts and tips.



Creative Commons License This website and all documents on it are licensed under a Creative Commons Attribution-Share Alike 3.0 United States License .


#include <std/disclaimer.h>
use Standard::Disclaimer;
from standard import disclaimer
SELECT full_text FROM standard WHERE type = 'disclaimer';

Both previously and presently, I have been employed by and/or done work for various organizations that also have views on Free, Libre, and Open Source Software. As should be blatantly obvious, this is my website, not theirs, so please do not assume views and opinions here belong to any such organization. Since I do co-own ebb.org with my wife, it may not be so obvious that these aren't her views and opinions, either.

— bkuhn


ebb ® is a registered service mark of Bradley M. Kuhn.

Bradley M. Kuhn <bkuhn@ebb.org>