COMMAND
SSH
SYSTEMS AFFECTED
SSH
PROBLEM
Following is based on a CORE Security Advisory CORE-20010116. 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
he 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 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.
All versions of SSH supporting the protocol 1.5 key exchange.
This vulnerability applies to SSH servers only.
This vulnerability was found and researched by Ariel Waissbein
and Agustin Azubel of CORE SDI.
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,
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 that paper 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.
SOLUTION
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 solved the
problem by closing the oracle that leaks information. The patch
was integrated to the OpenSSH source tree on January 29, 2001
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
prepared. Patches can be downloaded from the AppGate support web.
The Mindbright ssh1-server is only an experimental product and
they 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 them.
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.
For Debian:
http://security.debian.org/dists/stable/updates/main/source/openssh_1.2.3-9.2.diff.gz
http://security.debian.org/dists/stable/updates/main/source/openssh_1.2.3-9.2.dsc
http://security.debian.org/dists/stable/updates/main/source/openssh_1.2.3.orig.tar.gz
http://security.debian.org/dists/stable/updates/main/binary-i386/ssh-askpass-gnome_1.2.3-9.2_i386.deb
http://security.debian.org/dists/stable/updates/main/binary-i386/ssh_1.2.3-9.2_i386.deb
http://security.debian.org/dists/stable/updates/main/binary-m68k/ssh-askpass-gnome_1.2.3-9.2_m68k.deb
http://security.debian.org/dists/stable/updates/main/binary-m68k/ssh_1.2.3-9.2_m68k.deb
http://security.debian.org/dists/stable/updates/main/binary-sparc/ssh_1.2.3-9.2_sparc.deb
http://security.debian.org/dists/stable/updates/main/binary-sparc/ssh-askpass-gnome_1.2.3-9.2_sparc.deb
http://security.debian.org/dists/stable/updates/main/binary-alpha/ssh-askpass-gnome_1.2.3-9.2_alpha.deb
http://security.debian.org/dists/stable/updates/main/binary-alpha/ssh_1.2.3-9.2_alpha.deb
http://security.debian.org/dists/stable/updates/main/binary-powerpc/ssh-askpass-gnome_1.2.3-9.2_powerpc.deb
http://security.debian.org/dists/stable/updates/main/binary-powerpc/ssh_1.2.3-9.2_powerpc.deb
http://security.debian.org/dists/stable/updates/main/binary-arm/ssh-askpass-gnome_1.2.3-9.2_arm.deb
http://security.debian.org/dists/stable/updates/main/binary-arm/ssh_1.2.3-9.2_arm.deb
http://security.debian.org/dists/stable/updates/main/binary-all/ssh-askpass-ptk_1.2.3-9.2_all.deb