Damage control: Cleaning up compromised SSH keys

This morning, my laptop was stolen from my parked car while I was jogging. I do not want to make a big deal out of it.

Still, even though I am sure it was not targetted at my data (three other people at least were reporting similar facts in the same area), and the laptop's disk will probably just be reformatted, I am trying to limit the possible impact of my cryptographic identification being in somebody else's hands.

GPG makes it easy: I had on that machine just my old 1024D key, so it is just matter of generating a revocation certificate. I have done that, and uploaded it to the SKS keyservers - Anyway, here is my revocation certificate:

-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: A revocation certificate should follow

iHIEIBEIADIFAkyaOZwrHQJBIGNvbXB1dGVyIGNvbnRhaW5pbmcgdGhpcyBrZXkg
d2FzIHN0b2xlbgAKCRDYDvNai7UnrzWAAKC34eF76JQjxrZqSjNwcC0dU/5VbACg
gMIMmYg91Sl3y8KsZXdGj/rV7UE=
=rdlT
-----END PGP PUBLIC KEY BLOCK-----

But… What worries me more is access to the computers my ssh key works for. Yes, the ssh key uses a nontrivial passphrase, but still — SSH keys cannot be revoked (and this makes sense, as SSH should not add the delay, or potential impossibility, to check with a remote infrastructure whenever you want to start a session).

So, I generated a new key (and stored it at ~/.ssh/id_rsa.new / ~/.ssh/id_rsa.new.pub) and came up with this snippet:

$ OLDKEY=xyHywJuHD3nsfLh03G1TqUEBKSj6NlzMfB1T759haoAQ
$ for host in $(cat .ssh/known_hosts | cut -f 1 -d \ |cut -f 1 -d , |
                sort | uniq); do 
    echo == $host
    ssh-copy-id -i .ssh/id_rsa.new.pub $host && 
    ssh $host "perl -n -i -e 'next if /$OLDKEY/;print' .ssh/authorized_keys"
done

Points about it you might scratch your head about:

• .ssh/known_hosts' lines start with the server's name (or names, if more than one, comma-separated), followed by the key algorithm and the key fingerprint (space-separated). That's the reason for the double cut – It could probably be better using a regex-enabled thingy understanding /[, ]/, but... I didn't think of that. Besides, the savings would be just for academic purposes ;-)
• I thought about not having the ssh line conditionally depend on ssh-copy-id. But OTOH, this makes sure I only try to remove the old key from the servers it is present on, and that I don't start sending my new key everywhere just for the sake of it.
• my $OLDKEY (declared in Shell, and only literally interpolated in the Perl one-liner below) contains the final bits of my old key. It is long enough for me not to think I'm risking collision with any other key. Why did I choose that particular length? Oh, it was a mouse motion.
• perl -n -i -e is one of my favorite ways to invoke perl. -i means in-line editing, it allows me to modify a file on the fly. This line just skips (removes) any keys containing $OLDKEY; -n tells it to loop all the lines over the provided program (and very similarly, -p would add a print at the end – Which in this particular ocassion, I prefer not to have). It is a sed lookalike, if you wish, but with a full Perl behind.

Caveats:

• This assumes you have set HashKnownHosts: no in your .ssh/config. It is a tradeoff, after all – I use a lot tab-expansion (via bash_completion) for hostnames, so I do have the fully parseable list of hosts I have used on each of my computers.
• I have always requested my account names to be gwolf. If you use more than one username... well, you will have to probably do more than one run of it connecting to foo@$host instead.
• Although most multiuser servers stick to the usual port 22, many people change the ports (me included) either because they perceive concealing them gives extra security, or (as in my case) because they are fed up with random connection attempts. Those hosts are stored as [hostname]:port (i.e. [foo.gwolf.org]:22000). Of course, a little refinement takes care of it all.,/li>
• Oh, I am not storing results... I should, so for successive runs I won't try to connect to a system I already did, or that already denied me access. Why would I want to? Because some computers are not currently turned on. So I'll run this script at least a couple of times.

Oh, by the way: If you noticed me knocking on your SSH ports... please disregard. Possibly at some point I connected to that machine to do something, or it landed in my .ssh/known_hosts for some reason. I currently have 144 hosts registered. I am sure I triggered at least one raised eyebrow.

And I will do it from a couple of different computers, to make it less probable that I miss some I have never connected from while at the particular computer I am sitting at right now.

So... Any ideas on how to make this better?