Non-weak DSA key? oxymoronic, perhaps

The bottom line is that with a DSA key, just using it on a system with a flawed pRNG is enough for someone sniffing enough of your traffic to derive your private key.

I.e., you need not have generated your DSA key on a system with broken pRNG support, but merely to have used it on such a system while someone was recording your "encrypted" traffic. There is no way to detect this case, since there's no hint in your DSA key, so the sole solution, if you want to avoid the risk, is to banish all DSA keys. I presume that is why Debian imposed a strict RSA-only key policy for developers.

Until May of 2008, my primary ssh key was an old 1024-bit DSA one (too old to be blatantly weak, at least). It was DSA because back when I generated it, the RSA patent hadn't yet expired and I had little choice. However, ssh-keygen now generates RSA keys by default for a good reason: RSA keys are better. For example, using an RSA key on a client system with PRNG-impaired OpenSSL libraries wouldn't have been a problem, but using a DSA key on such a system renders the key easily crackable by anyone who can record enough of your "encrypted" traffic. I confess that I have used such systems.

Over the weekend I finally read enough (hmm, that content "disappeared". Here are related references: 1 2 3 4 ) to convince myself that if I were to continue with that old DSA key, I'd be posing an unacceptable risk not only to myself, but to each system I can access with it.

So I generated a new key with this command (and a carefully chosen passphrase):

    ssh-keygen -b 4096 -f ~/.ssh/id_rsa-2008

Then there was the chore of updating many accounts to accept the new key -- and to reject the old one. i.e., to update all of those ~/.ssh/authorized_keys files. And don't forget any with the old ~/.ssh/authorized_keys2 name (I had more than a few). Initially I merely appended the new key to the file on each system with a personal account, then logged in and used an editor to manually remove the old key. To be on the safe side for each remote system, I'd remain connected and verify that "ssh $hostname date" still works[*] after the change. In one case a copy/paste somehow introduced a single-byte error in the key string and I had to re-do it.

[*] if you use ssh session sharing (i.e., ControlPath/ControlMaster in ~/.ssh/config), be sure the test actually creates a new session -- either go via a different route or socket, or turn it off temporarily.

If you have to update more than 5 or 10 accounts, even that small amount of manual work gets old fast, so I started doing the following for personal accounts (clobbering the existing contents):

    h=personal.some.dom
    # First start an ssh session in another window, ...
    ssh $h
    ssh $h 'cat > .ssh/authorized_keys' < ~/.ssh/id_rsa-2008.pub

and for shared accounts, simply append the new key:

    h=shared-account.other.dom
    ssh $h 'cat >> .ssh/authorized_keys' < ~/.ssh/id_rsa-2008.pub

or equivalently, use the ssh-copy-id script:

    ssh-copy-id -i ~/.ssh/id_rsa-2008.pub $h

And that worked fine... almost

I forgot that one account on a remote system was shared, so my clobbering the shared authorized_keys file locked out everyone else; password access was not possible. Luckily I heard about it quickly and restored from a backup. Could have been worse.

In retrospect, I should have automated it carefully, e.g., with shell code like this (but my ssh-update-key script is better still):

    #!/bin/sh
    hostname=$1
    old=$(cut -d' ' -f2 ~/.ssh/id_dsa.pub)
    new=$(cut -d' ' -f2 ~/.ssh/id_rsa-2008.pub)
    auth=.ssh/authorized_keys
    exec ssh -n $hostname \
      "perl -pi -e 's,ssh-dss \\Q$old\\E .*,ssh-rsa $new my\@addr.com,' $auth"

Of course, you'd replace "my\@addr.com" with your own address, and "old" and "new" are the encoded key strings verbatim from each .pub file. You have to be careful to \Q-quote the old one, because it may contain '+', and to use something like "," as the substitution delimiter, since the encoded key can contain "/", too. To be slightly more careful, tell perl to make a backup:

    ssh $h "perl -pi.bak ...

But even that isn't enough if your old key is only in ~/.ssh/authorized_keys2. To handle that case too, simply change this:

    auth='.ssh/authorized_keys .ssh/authorized_keys2'

However, these days, you should move any keys you care about into .ssh/authorized_keys and remove the old "2"-suffixed file.

If you're new to ssh, you might not know you can use more than one key at a time. Doing that helps to ease the transition. Assuming you're already using ssh-agent or gpg-agent, just run this command:

    ssh-add ~/.ssh/id_rsa-2008

Then you can ssh to systems that accept either the new or the old key.

With a 4096-bit RSA key under my pillow now, maybe I'll sleep easier.