Re: SSH1 key recovery patch

[Markus Friedl <markus.friedl () INFORMATIK UNI-ERLANGEN DE>]

On Tue, Feb 20, 2001 at 12:48:09PM +0100, Johannes Geiger wrote:
> Wouldn't it be much easier and less error prone to actually disable the
> oracle, which is the real problem leading to the attack, instead of all
> this key regeneration stuff?

This is what OpenSSH-2.5.1 tries to do.

> So all you have to do is to always do both RSA operations, record a
> failure of the first but call fatal() only after the second. Or did I
> miss something?

OpenSSH checks whether the two calls to rsa_private_decrypt()
success and the resulting session keys has the correct size.

Otherwise it just uses a 'random' session key. Now the attacker no
longer can tell whether the RSA operations failed and the
oracle is (almost) closed. See

http://www.openbsd.org/cgi-bin/cvsweb/src/usr.bin/ssh/sshd.c?r1=1.158&r2=1.159

However, as Simon Tatham points out:

% It's just occurred to me what this means: if I send the same mp_int
% in two successive connections, the session key I get back will be
% _different_ if the decryption failed and the same if it didn't.
%
% This is _almost_ making the problem worse: if it wasn't for the
% random padding in the SSH1_SMSG_SUCCESS packet, I could still get
% the Bleichenbacher leakage by sending the same string twice and
% seeing if the encrypted data I got back was the same twice or not.
%
% Fortunately, it's not _that_ bad, because of the 3 bytes of random
% padding in the packet. But, correct me if I'm wrong, it's still
% theoretically possible to get the information out: I send 2^24+1
% copies of the same mp_int, and see if I get 2^24+1 different encrypted
% blocks back. If not, there's a good chance my string was valid.

This means that the oracle is not completely closed, but you
need about 2^23 connections (this is not possible because of
OpenSSH's MaxStartups option) if you want to know whether it's a
fake or a real encryption key.

Because of this problem future OpenSSH releases will include the
following change:  The faked session keys is not 'random' but
depends on the values sent by the attacker:

        dig1 = md5(cookie|session_key_int);
        dig2 = md5(dig1|cookie|session_key_int);
        fake_session_key = dig1|dig2;

where the 'cookie' is a re-generated at the same time as
the server key:

Index: sshd.c
===================================================================
RCS file: /home/markus/cvs/ssh/sshd.c,v
retrieving revision 1.168
diff -u -r1.168 sshd.c
--- sshd.c      2001/02/19 23:09:05     1.168
+++ sshd.c      2001/02/20 23:40:17
@@ -145,6 +145,7 @@
        Key     **host_keys;            /* all private host keys */
        int     have_ssh1_key;
        int     have_ssh2_key;
+       u_char  ssh1_cookie[SSH_SESSION_KEY_LENGTH];
 } sensitive_data;

 /*
@@ -265,13 +266,23 @@
 void
 generate_empheral_server_key(void)
 {
+       u_int32_t rand = 0;
+       int i;
+
        log("Generating %s%d bit RSA key.", sensitive_data.server_key ? "new " : "",
            options.server_key_bits);
        if (sensitive_data.server_key != NULL)
                key_free(sensitive_data.server_key);
        sensitive_data.server_key = key_generate(KEY_RSA1, options.server_key_bits);
-       arc4random_stir();
        log("RSA key generation complete.");
+
+       for (i = 0; i < SSH_SESSION_KEY_LENGTH; i++) {
+               if (i % 4 == 0)
+                       rand = arc4random();
+               sensitive_data.ssh1_cookie[i] = rand & 0xff;
+               rand >>= 8;
+       }
+       arc4random_stir();
 }

 void
@@ -429,6 +440,7 @@
                }
        }
        sensitive_data.ssh1_host_key = NULL;
+       memset(sensitive_data.ssh1_cookie, 0, SSH_SESSION_KEY_LENGTH);
 }
 Key *
 load_private_key_autodetect(const char *filename)
@@ -1319,9 +1331,6 @@
            sensitive_data.ssh1_host_key->rsa->n,
            sensitive_data.server_key->rsa->n);

-       /* Destroy the private and public keys.  They will no longer be needed. */
-       destroy_sensitive_data();
-
        /*
         * Extract session key from the decrypted integer.  The key is in the
         * least significant 256 bits of the integer; the first byte of the
@@ -1342,14 +1351,27 @@
                }
        }
        if (rsafail) {
+               int bytes = BN_num_bytes(session_key_int);
+               char *buf = xmalloc(bytes);
+               MD5_CTX md;
+
                log("do_connection: generating a fake encryption key");
-               for (i = 0; i < SSH_SESSION_KEY_LENGTH; i++) {
-                       if (i % 4 == 0)
-                               rand = arc4random();
-                       session_key[i] = rand & 0xff;
-                       rand >>= 8;
-               }
+               BN_bn2bin(session_key_int, buf);
+               MD5_Init(&md);
+               MD5_Update(&md, buf, bytes);
+               MD5_Update(&md, sensitive_data.ssh1_cookie, SSH_SESSION_KEY_LENGTH);
+               MD5_Final(session_key, &md);
+               MD5_Init(&md);
+               MD5_Update(&md, session_key, 16);
+               MD5_Update(&md, buf, bytes);
+               MD5_Update(&md, sensitive_data.ssh1_cookie, SSH_SESSION_KEY_LENGTH);
+               MD5_Final(session_key + 16, &md);
+               memset(buf, 0, bytes);
+               xfree(buf);
        }
+       /* Destroy the private and public keys.  They will no longer be needed. */
+       destroy_sensitive_data();
+
        /* Destroy the decrypted integer.  It is no longer needed. */
        BN_clear_free(session_key_int);