CORE SDI S.A. Security Advisory
     
     February 7th, 2001
     
     SSH protocol 1.5 session key recovery vulnerability
     
     Date Published: 2001-02-07
     
     Advisory ID: CORE-20010116
     
     Bugtraq ID: 2344
     
     CVE CAN: Not currently assigned.
     
     Title: Session Key recovery in SSH protocol 1.5
     
     Class: Design/implementation error
     
     Remotely Exploitable: Yes
     
     Locally Exploitable: Yes
     
     Release Mode: USER RELEASE
     
     Vulnerability Description:
     
     SSH is a widely used client-server application for authentication and encryption of
     network communications. In order to ensure that all data exchanged between client and
     server is kept confidential a symmetric algorithm is used with a key obtained from the
     key exchange and authentication process done upon connection from the client to an SSH
     server.
     
     A would be attacker could obtain and store all the encrypted packets belonging to a
     specific client-server connection but that would provide no real value unless she is able
     to:
     
     . Decrypt them without having the session key used for the encryption
     This is equivalent to breaking the crypto algorithm used.
     or
     . Exploit some design or implementation problem on either client or server to obtain the
     session key and the proceed to decrypt the stored session using any implementation of the
     crypto algorithm used.
     
     This advisory describes a vulnerability in the SSH 1.5 protocol that allows an attacker
     to do the later.
     
     The key exchange in SSH protocol 1.5 uses PKCS#1_1.5 public key encryption standard to
     make the key exchange between client and server upon connection.
     
     An attack (see [1] and [2]) discovered by David Bleichenbacher on PKCS#1_1.5 can be
     exploited to recover arbitrary session keys.
     
     Combining Bleichenbacher's attack with a timing attack designed to obtain information
     about crypto operations performed on a SSH server it is possible to obtain a session key
     for an SSH session and therefore decrypt it or even alter it if it is still active.
     
     Vulnerable Packages/Systems:
     
     All versions of SSH supporting the protocol 1.5 key exchange.
     This vulnerability applies to SSH servers only.
     See the following section for vendor specific information.
     
     Solution/Vendor Information/Workaround:
     
     OpenSSH
     The vulnerability is present in OpenSSH up to version 2.3.0, although it is not possible
     to exploit it due to limits imposed on the number of simultaneous connections the server
     is allowed to handle, Nonetheless, Markus Friedl of OpenSSH.com has produced a patch that
     sets a random session key if RSA operations on the session key sent by the client fail.
     This effectively solves the problem by closing the oracle that leaks information.
     
     The patch was integrated to the OpenSSH source tree on January 29, 2001
     
     AppGate
     The default configuration of the AppGate server is not vulnerable since it has SSH-1
     support disabled. However it is possible for administrators to enable SSH-1 backwards
     compatibility to be able to use legacy clients. Those customers should apply the patches
     we have prepared. Patches can be downloaded from the AppGate support web or requested
     from support@appgate.com
     
     Mindbright
     The Mindbright ssh1-server is only an experimental product and we are not aware of
     anybody actually using it, it has never been sold or available as a separate entity.
     Since it is written in java it will need a really extreme machine to be able to handle
     the load needed to exploit this vulnerability. Anybody who feels that they need a patch
     for it is welcome to contact mindbright@mindbright.se.
     
     SSH.com
     ssh-1 up to version 1.2.31 is vulnerable.
     The official response from SSH.com follows:
     
     -SSH1 is deprecated and SSH.com does not support it anymore, the official response is
     upgrade to SSH2
     
     -The SSH1 compatibility code built into SSH-2.4.0 always executes a fresh copy of SSHD1,
     which causes the server key to be regenerated for every connection. Thus, the attack is
     not at all feasible when using SSH1 with an SSH2 server in compatibility mode.
     
     Ssh-2.4.0 also includes code for limiting the maximum number of simultaneous connections.
     The maximum is controlled by the MaxConnections flag in /etc/ssh2/sshd2_config or with
     the
     
        --with-ssh-connection-limit=<limit> compile-time configure option.
     
     However, as noted, the limit is not required for protection when using SSH1 with SSHD2 in
     compatibility mode.
     
     -The following unsupported and untested patch can be applied to ssh-1.2.31 and earlier.
     It addresses the problem by regenerating the server key when the RSA operations fail.
     This is done at a rate of at most one key regeneration per minute to avoid possible DoS
     attacks.
     
     -------------- cut here ----------------------------------------------
     
     --- rsaglue.c   1999/12/10 23:27:25     1.8
     
     +++ rsaglue.c   2001/02/03 09:42:05
     
     @@ -264,7 +268,15 @@
     
        mpz_clear(&aux);
     
        if (value[0] != 0 || value[1] != 2)
     
     -    fatal("Bad result from rsa_private_decrypt");
     
     +    {
     
     +      static time_t last_kill_time = 0;
     
     +      if (time(NULL) - last_kill_time > 60 && getppid() != 1)
     
     +       {
     
     +         last_kill_time = time(NULL);
     
     +         kill(SIGALRM, getppid());
     
     +       }
     
     +      fatal("Bad result from rsa_private_decrypt");
     
     +    }
     
        for (i = 2; i < len && value[i]; i++)
     
          ;
     
     -------------- cut here ---------------------------------------------
     
     LSH
     
     Not vulnerable. Does not support protocol version 1
     Cisco Systems, F-Secure, other SSH server vendors
     No information provided.
     
     Additionally, advisories and information on security issues in SSH can be obtained from:
     
      http://www.core-sdi.com/advisories/buffer_over_ing.htm
      http://www.core-sdi.com/advisories/ssh-advisory.htm
      http://www.core-sdi.com/bid/1949
      http://www.core-sdi.com/bid/1426
      http://www.core-sdi.com/bid/1323
      http://www.core-sdi.com/bid/1006
      http://www.core-sdi.com/bid/843
      http://www.core-sdi.com/bid/660
     
     Vendor notified on: 2001-01-16
     
     Credits:
     
     This vulnerability was found and researched by Ariel Waissbein and Agustin Azubel of CORE
     SDI, Buenos Aires, Argentina.
     
     This advisory was drafted with the help of the SecurityFocus.com
     
     Vulnerability Help Team. For more information or assistance drafting advisories please
     mail vulnhelp@securityfocus.com.
     
     This and other CORE SDI security advisories can be obtained from:
     
       http://www.core-sdi.com/english/publications.html
     
     Technical Description - Exploit/Concept Code:
     
     In Section 1 we introduce the SSH1 key exchange, in Section 2 we introduce the attack,
     finally in Section 3 we discuss the attack's feasibility and argue why it is insecure to
     continue using this protocol.
     
      1)  SSH1 KEY-EXCHANGE PROTOCOL DESCRIPTION:
     
       1.1.- The keys.
     
       Each host has a host unique permanent RSA key set which identifies it. A host is a SSH
     server (referenced as server), which runs the 'sshd' daemon or a SSH client (referenced
     as client) which runs the 'ssh' client program.
     
       The length of the host key is by default 1024 bits.
     
       Each server has its own server RSA key set which is automatically generated after a
     specified timeout (1 hour by default). This key set is never saved in any file. The
     length of this key is by default 768 bits. In every client-to-server connection, a 256
     bits session key is generated by the client using pseudo-random data provided by the same
     client.
     
       This session key will be used in a symmetric algorithm (e.g. DES, Blowfish, 3DES) to
     encrypt the data flow on the connected channel after the key exchange is completed.
     
       To send the session key over an insecure channel to the server, it is encrypted by the
     client with the server key and the server host key together with other data using an
     asymmetric encryption algorithm (RSA-PKCS #1 1.5) as we explain in Subsection 1.4. The
     purpose of the two separate  server keys is to make it impossible to decrypt a captured
     session by breaking into the server machine and getting access to the server key at a
     later time; one hour after the connection start not even the server machine can decipher
     the session key!
     
       1.2.- Initiating a connection.
     
       Whenever a client connects to the server, the daemon forks. The parent stays in a loop
     waiting to accept more connections and the child manages the accepted connection. Before
     authenticating both endpoints, they do an identification exchange.
     
       1.3.- The identification exchange.
     
        First, the server sends a formatted string to the client in plaintext,  specifying the
     protocol supported versions and the server version.
     
        This string looks like "SSH-1.99-OpenSSH_2.3.0", where "1" denotes the  protocol
     version major number, "99" the protocol version minor number and "OpenSSH_2.3.0" is the
     software version of the server.
     
        If the client does not support the received protocol, it closes the connection. If the
     protocol is supported by the client, it responds with a formatted string of the same
     plaintext format. The server then checks the client's response.  If the versions do not
     match or the client version is not valid, the server closes the connection.
     
        If the versions do match, the key exchange is started.
     
       1.4.- The key exchange.
     
       The server will send both of its public keys. First the server will fetch 64 bits from
     a PRNG, that will be used as a cookie to prevent IP spoofing attacks and TCP sequence
     number prediction. This only affects rhosts authentication.
     
       The client must send back this cookie when the session key is sent.
     
       This only works against somebody doing IP spoofing from a remote network; any machine
     on the local network can still see outgoing packets and catch the random cookie.
     
       The server then builds a packet of type SSH_SMSG_PUBLIC_KEY, concatenating  the cookie,
     the size of the 'n' component of the RSA server key, the 'e' public exponent of the RSA
     server key and the modulus 'n' of the RSA server key (the public RSA server key), the
     size of the 'n' component of the RSA host key, the 'e' public exponent of the RSA host
     key and the modulus 'n' of the RSA host key the public RSA host key), the SSH protocol
     flags, the supported symmetric ciphers, and the supported authentication methods.
     
       Once the client has received the SSH_SMSG_PUBLIC_KEY packet, it computes a session ID
     in the same way the server does:
     
       [mpaux.c:compute_session_id()]
     
       The session ID is equal to a MD5 hash of the concatenation of the modulus of the host
     key of the server, the modulus of the server key and the server generated cookie.
     
        session_id := MD5(HostKey_RSAModulus||ServerKey_RSAModulus||Cookie)
     
     The length of a session_id is the same as the output of the MD5 function: 128 bits.
     
       The client generates a session key of 256 bits fetching data from a PRNG. This key will
     be the used in a symmetric algorithm to encrypt all the future flow of this SSH session.
     
       Before this key is encrypted and sent, the first 128 bits of this key, are XORed with
     the session_id. The client then uses the RSA algorithm (PKCS1 1.5) to encrypt
     consecutively the XORed session key and session_id with the server key and host key.
     
       Encryption is made using the smaller key first.
     
       Finally the client builds a packet containing the symmetric algorithm to use, the
     received cookie, the encrypted session key and the SSH protocol flags and sends it to the
     server.
     
       The server receives this packet and retrieves the symmetric algorithm chosen by the
     client and checks its compliance sending a "Warning: client selects unsupported cipher."
     message if it is not.
     
       It then checks that the received cookie matches the old cookie sent, sending another
     error message if it is not.
     
       It retrieves the encrypted key, processes the SSH algorithm flags and decrypts the
     session key (OpenSSH does an integrity check on the packet lenght before this).
     
       We explain this in detail since it is of great interest for our attack.
     
       To do this we introduce the PKCS #1 1.5 encoding.
     
       1.5 - PKCS#1 - 1.5 (from rsaglue.c in ssh-1.2.30)
     
       To send a message m using a RSA public exponent e, with a public modulus n, the
     encrypter encodes the message m as
     
         M := 0x00 || 0x02 || P || 0x00 || m
     
       where 0x00 and 0x02 are the value of the first 2 bytes in hexa, and P is an hexadecimal
     padding string containing no zero octets.
     
       The ciphertext is:
     
       c := M^e mod (n) . (i.e. M to the e-th power modulo n)
     
       To recover m, the decrypter calculates c^d, where d is the private exponent, checks
     whether the first two bytes are 0x00 and 0x02 and calls the function fatal() in
     log-server.c closing the connection if the check failed.
     
       Otherwise it sets all the data after the second zero as the message (in case the format
     is correct this will return m).
     
       OpenSSH uses OpenSSL which behaves different, see the RSA_padding_check_PCKS1_type2()
     function for more details.
     
       The cleartext for this session key is recovered by checking which is the bigger public
     modulus and decrypting first with the key corresponding to the bigger modulus and
     secondly with the smaller one (in case of a tie the server key goes first). This is done
     using the rsa_private_decrypt() function.
     
       When this is done the server computes the session key, and does a XOR of the decrypted
     data with the computed session id to obtain the session key generated by the client.
     
       Finally the server sets the symmetric encryption scheme and key to the ones chosen by
     the client, and sends a packet describing the success to the client.
     
       This packet is the first encrypted packet of the flow secured by the symmetric
     algorithm.
     
      2) ATTACK DESCRIPTION.
     
       2.1.- Bleichenbacher's attack.
     
        Daniel Bleichenbacher presented an adaptive ciphertext attack to RSA encryption
     standard PKCS1_1.5 at the Crypto 98 Conference ([1]), which on input of a ciphertext c,
     outputs the cleartext m corresponding to this ciphertext.
     
        To carry out this attack the attacker needs to make use of a decryption  oracle. As we
     shall see, this is automatically provided by the RSA functions used in SSH1 ( or in the
     OpenSSL library used in OpenSSH).
     
        This is the protocol flaw that enables the attack we present.
     
        Specifically, an attacker needs only to access an oracle that will answer if a string
     c' calculated by her is or is not PKCS#1_1.5-format compliant, even less, she only needs
     to know if it holds true that the hexadecimal representation of the string (c')^d mod (n)
     starts with the octets 0x00 and 0x02 (here d is the private secret exponent and n the
     public modulus).
     
        To decrypt a ciphertext without the private key, the attacker needs to  access to this
     oracle 2^{20} times (average-time complexity).
     
        This estimation holds true for a 1024 bit key size.
     
        We shall not explain the attack in detail. To decrypt a ciphertext c an attacker will
     need to access the oracle with messages of the type
     
     c.s^e mod (n)
     
     where e and n are the public exponent and public modulus, and s is chosen by the attacker
     algorithm following certain rules.
     
        We refer to the paper [1] for further details.
     
        In each step of the attack, the attacker finds a collection of intervals in which the
     cleartext  is contained, first starting with a big interval of size 2^{1018}=2^{1024-16}
     and reducing it until a single interval
     of
        size one - whose only member is the cleartext-  is left.
     
       2.2.- The attack on SSH-1
     
       Suppose that we are sniffing a connection between a client and the server. We can then
     easily detect when this connection starts and get the packet containing the encrypted
     session key. We can then work in parallel, saving all successive packets exchanged
     between server and client, and at the same time attempt a session key decryption with the
     attack we present.
     
       Once the session key is decrypted all the saved encrypted packets sent between this
     client and the server can be decrypted in a straight-forward manner.
     
       To obtain the session key we will make use of Bleichenbacher's attack together with a
     simple timing attack technique.
     
       Let c := E_{K1}(E_{K2}(K)) denote the captured ciphertext, where K1 and K2 are the
     server and host key (the order of these keys does not alter the way in which the attack
     is made, since the order can be easily deduced as we explain in the following section, we
     suppose without loss of generality that K1 is the host key and K2 is the server key), K
     is the session key or rather the plaintext string containing the session key, and
     
       E_{A}(B) denotes RSA-PKCS1_1.5 encryption of the cleartext B using the
     
     Public key A. The attack is divided in two main steps,
     
       Firstly the attacker will first attempt to recover E_{K2}(K) from c using a plain
     Bleichenbacher attack, and secondly K is calculated by the attacker from E_{K2}(K) using
     a reduction we explain in the next subsection together with Bleichenbacher's attack.
     
       Notice that the calls to the function fatal() can be used as the needed oracle.
     
       Successful negotiation of  a session key will end with the reception of a
     SSH_SMSG_SUCCESS packet at the client. A failure will end with the connection being
     shutdown due to the calls to the fatal() function from within the rash_private_decrypt()
     function.
     
       An attacker can -prior to the attack- determine what is the time needed for the server
     to reach the connection shutdown call in the fatal() function if the first encryption is
     not format compliant, and what is the time needed for the server to reach it if the first
     encryption is format compliant and the second encryption is not. This  is basically the
     way of retrieving answers from the oracle and it implies a timing attack as well as a few
     modifications to Bleichenbacher's attack.
     
       To carry out the attack and recover the session key the host key needs to remain the
     same during the attack, we suppose that this is the case and shall discuss the
     feasibility of this in the following section.
     
       Suppose now that E_{K2}(K) is already calculated and known to the attacker, and call
     c':=E_{K2}(K).  The attacker then uses c' to recover K.
     
       To do this, instead of accessing the oracle with messages of the form c.s^e mod (n),
     she will access the oracle with messages of the form c'.s'^{e'} mod (n'), where c' is
     defined as c':=E_{K2}(K), and e' and n'are the second public exponent and modulus
     (corresponding to E_{K1}(-)), and s'  is chosen following the same rules as defined by
     Bleichenbacher's attack.
     
       3. Implementation and Feasibility
     
       The estimation for the number of times needed to access the oracle on a adaptive
     ciphertext Bleichenbacher's attack for a 1024 bits modulus is approximately 2^{20}, as we
     said before. This means that the server should handle about 2^{20} connections to make
     the first decryption, i.e. to get E_{K2}(K). After this is done, to recover K, another
     adaptive ciphertext attack of the same sort should be carried out, with presumably less
     accesses to the oracle --say 2^{19}-- since the second key is smaller than the first one,
     to recover K. Hence, to carry out the attack we present here, an attacker should perform
     around (2^{20}+2^{19}) connections to the server during the lifespan of  a server key K
     (default is one hour) which implies a rate of oracle queries of around 400/sec.
     
       Limiting the number of simultaneous connections to the server will greatly reduce the
     feasibility of this attack, this is in fact a standard feature in at least the OpenSSH
     implementation of SSH-1.
     
       It is necessary to note that the attacker also needs to perform crypto operations (RSA
     encryptions with a small exponent) for each query during the attack but those are
     computationally cheaper the ones performed on the server side.
     
       This seems to make our attack infeasible for most cases. nonetheless, high end  servers
     are still a possible target for this attack. It is also worth mentioning that the number
     of connections given is  for the average case and specifics cases will fall below the
     average.
     
       We follow to discuss other vulnerable cases in which our attack becomes  feasible.
     
       An issue to be taken into account is the order of the keys K1 and K2, that is whether
     K1 is the server key and K2 the host key, or the other way around.
     
       This issue, we deferred to this section, is of some importance to our attack.
     
       As we mentioned the order of the keys is changed to K2 for the host key, and K1 for the
     server key in case the size of K2 is strictly greater than K1.
     
       In that case, the attacker has limited time to recover E_{K2}(K)(because K1 has a
     default timeout of one hour), but has an indefinite amount of time to recover K from
     E_{K2}(K). This would make the attack easier since it reduces the initial recovery attack
     to 2^{20} oracle queries within an hour. The second phase could be done at a much slower
     connection rate.
     
       It might also happen that the public modulus n is much smaller than the specified
     values, and this lucky stroke would speed up the attack considerably.
     
       Another issue to be taken into account, is when the default settings for the server key
     timeout are changed increasing  the key lifespan and thus the time window for the attack.
     
       It is not likely, however, that the default settings for the key size will be purposely
     reduced.
     
       There is also a technology or rather server efficiency issue to be taken into account.
     Although the average case of the attack we present seems infeasible today, this might not
     be the case for specific attacks that deviates from the average or for specific attack
     scenarios en the present or the near future.
     
       The conclusion of this report is that although the attack described might not be a
     direct threat to the wide audience that relies on SSH1 for secure network communications,
     there is, nonetheless an exploitable flaw in the SSH-1 key exchange protocol that should
     be either fixed or addressed during the deployment of SSH as a security component.
     
     References
     
      [1] Daniel Bleichenbacher, "Chosen ciphertext attacks on RSA encryption standard PKCS
     #1", Advances in Cryptology, CRYPTO 98. Springer.
     
      [2] Daniel Bleichenbacher, Burt Kaliski and Jessica Staddon, "Recent results on PKCS#1:
     RSA encryption standard ". RSA Laboratories' Bulletin 7.  http://www.rsa.com/rsalabs
     
     DISCLAIMER:
     
   The content of this advisory are copyright (c) 2001 CORE SDI Inc. and may be distributed
   freely provided that no fee is charged for this distribution and proper credit is given.