Subject: an attack against SSH2 protocol

From: Wei Dai <[email-masked]>
Date: Wed, 6 Feb 2002 13:41:17 -0800

[Posted to sci.crypt and the IETF SSH working group mailing list.]

Phil Rogaway observed that CBC mode is not secure against chosen-
plaintext attack if the IV is known or can be predicted by the attacker 
before he choses his plaintext [1]. Similarly, CBC mode is not secure if 
the attacker can observe the last ciphertext block before choosing the 
next block of plaintext, because the last block of ciphertext 
essentially serves as the IV for the rest of the message. 

The attack itself is very simple. Remember that in CBC mode, each 
plaintext block is XOR'ed with the last ciphertext block and then 
encrypted to produce the next ciphertext block. Suppose the attacker 
suspects that plaintext block P_i might be x, and wants to test whether 
that's the case, he would choose the next plaintext block P_j to be x 
XOR C_(i-1) XOR C_(j-1). If his guess is correct, then C_j = Encrypt(P_j 
XOR C_(j-1)) = Encrypt(P_i XOR C_(i-1)) = C_i, and so he can confirm his 
guess by looking at whether C_j = C_i.

The SSH2 protocol, when used with a block cipher in CBC mode, does allow 
the attacker to observe the last ciphertext block of a packet, which is 
then used as the (implicit) IV of the next packet. SSH2 also multiplexes 
multiple channels into one transport stream encrypted with a single key. 
This gives the attacker who can input data into one channel a chance to 
attack other channels. (Another possible attack scenario is a multi-user 
chat session.) Fortunately, the attacker may not have complete freedom 
to choose the first block of the plaintext of the next packet. For 
example, the first 4 bytes of the plaintext of any packet consist of the 
packet length. Assuming that the SSH2 application has a maximum packet 
size of 2^16, the attacker is constrained to choosing a plaintext block 
that begins with two zero octects. This implies that the attacker would 
have to wait at least 2^16 packets on average before he has a chance to 
perform this attack. 

However even with this and other potential constraints it seems very 
possible for the attacker to succeed in some situations. So I suggest 
that the SSH2 protocol be fixed. The simplest way to do this would be to 
deprecate the CBC mode block ciphers, and instead specify ciphers in 
CFB, CTR or OFB mode. Currently, the only cipher defined in the SSH2 
transport protocol draft that is not a block cipher in CBC mode is ARC4. 
Until this fix is implemented, users of SSH2 applications may want to 
consider switching to ARC4 for encryption.

[1] http://www.cs.ucdavis.edu/~rogaway/papers/draft-rogaway-ipsec-
comments-00.txt

-- 
http://cryptopp.com - free C++ cryptography and compression library

---

From: Bill Sommerfeld <[email-masked]>
Date: Fri, 08 Feb 2002 14:50:29 -0500

So, I'm surprised to see no technical comments on this so far, either
here or on my local view of sci.crypt.

The attack appears to be extremely narrow -- to restate it
(please correct me if i'm wrong)
 - real-time adaptive chosen plaintext attack
 - attacker can verify a guess at one block of plaintext occurring 
immediately before the injected plaintext
 - the chosen plaintext is chosen based on the ciphertext of the
 guessed plaintext. 

I do have to question the arcfour/RC4 recommendation, though -- as
currently specified, ssh is vulnerable to the RC4 "weak key" problem
because, as specified, it doesn't discard the start of the keystream.
(fixing this has been discussed, but there seemed to be very little
interest in doing work on RC4/arcfour when this was last raised).

Moreover, it appears to be fairly straightforward to make an
implementation resist the attack while retaining interoperability:

The basic ssh message framing is:

  uint32    packet_length
  byte      padding_length
  byte[n1]  payload; n1 = packet_length - padding_length - 1
  byte[n2]  random padding; n2 = padding_length
  byte[m]   mac (message authentication code); m = mac_length

As documented, the "mac" is transmitted in the clear; everything
before that is encrypted.

    Padding
      Arbitrary-length padding, such that the total length of
      (packet_length || padding_length || payload || padding) is a
      multiple of the cipher block size or 8, whichever is larger.
      There MUST be at least four bytes of padding.  The padding SHOULD
      consist of random bytes.  The maximum amount of padding is 255
      bytes.

With the 4-byte minimum, the random padding puts a floor on the
difficulty of guessing the previous block (no better than one chance
in 2**32).  An implementation could render the attack entirely
meaningless by always sending a full cipherblock of padding...

					- Bill

---

From: Wei Dai <[email-masked]>
Date: Fri, 8 Feb 2002 12:10:36 -0800

> here or on my local view of sci.crypt.

I have received some comments through private email. Apparently the exact
same weakness was known for IPSec and may also exist in TLS (I haven't
read enough of its RFC to be sure) so this seems to be a common problem.

(We really should drop the rule of thumb "use CBC mode unless there's a
reason not to" and replace it with "use CTR mode unless there's a reason
not to".)

> immediately before the injected plaintext

No, the attacker can verify a guess of any previous block of plaintext,
not just the block immediately before the injected plaintext.

> interest in doing work on RC4/arcfour when this was last raised).

That's why I didn't recommend ARC4, only suggested that it be considered
as an alternative while a better fix is implemented.

> implementation resist the attack while retaining interoperability:

This suggested fix is based on the above misunderstanding, and so doesn't
work.

I still think the easiest fix is to deprecate the existing CBC mode
ciphers and define new ciphers in OFB, CFB, or CTR modes. I suggest CTR
mode unless there's a reason not to use that, but we may also want to
define ciphers in other modes as a backup (in case some problem with CTR
mode is discovered down the road).

---

From: [email-masked] (Bodo Moeller)
Date: 9 Feb 2002 01:37:39 -0000

Wei Dai <[email-masked]>:

>> then used as the (implicit) IV of the next packet. [...]

>> [1] http://www.cs.ucdavis.edu/~rogaway/papers/draft-rogaway-ipsec-comments-00.txt

> read enough of its RFC to be sure) [...]

In TLS, the "IV for subsequent records is the last ciphertext block
from the previous record" [RFC 2246], and plaintext blocks usually
consist of raw application data followed by a MAC, so the attack
applies.  (Having the MAC at the *beginning* of each packet would
avoid the attack.)

In his CRYPTO 2001 paper "The Order of Encryption and Authentication
for Protecting Communications (or: How Secure Is SSL?)", Hugo Krawczyk
supposedly shows that SSL/TLS with CBC encryption is secure -- but
he assumes a random IV for each encrypted block, which is not how the
actual SSL protocol works.

Another problem with CBC as used in SSL/TLS was pointed out by Serge
Vaudenay, see <URL:http://www.openssl.org/~bodo/tls-cbc.txt>.  That
one can easily be avoided by implementations.  To avoid the new attack
without changing the protocol definition, implementations would have
to send an empty fragment before application data to ensure IV
randomization.

-- 
Bodo Möller <[email-masked]>
PGP http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller/0x36d2c658.html
* TU Darmstadt, Theoretische Informatik, Alexanderstr. 10, D-64283 Darmstadt
* Tel. +49-6151-16-6628, Fax +49-6151-16-6036

---

From: Markus Friedl <[email-masked]>
Date: Mon, 11 Feb 2002 13:36:45 +0100

> meaningless by always sending a full cipherblock of padding...

i think this would only work if we restrict the actual payload
to the blocksize of the cipher.

---

From: [email-masked] (Niels Möller)
Date: 11 Feb 2002 17:02:36 +0100

Wei Dai <[email-masked]> writes:

> The simplest way to do this would be to 
> CFB, CTR or OFB mode.

Another simple "fix" for CBC might be to add one more encryption
operation between packets. If one packet consists of the ciphertext
blocks

  b_1, b_2, ..., b_n,

ssh uses b_n as the iv for the next packet. Would it help to instead
use C_k(b_n) as the iv? This would be equivalent to inserting one
(plain text) block of zeroes between packets, and keeping the
corresponding ciphertext block secret. (The same trick could be used
in other contexts that needs to send an iv in the clear: Encrypt the
cleartext iv once before using it).

To me, this attack doesn't look like a reason for general panic, but
in any case it would be a good thing to specify how to use counter
mode in ssh (but I think we should stay with a small number of modes,
and not add *every* reasonable mode).

A problem with counter mode is that the FIPS document doesn't define
it fully; it doesn't say how you should increment the counter, you can
do it in little endian order or big endian order or using any
permutation of your choice. Is there any IETF wg that has tried to
define a single standard way of doing counter mode?

/Niels

---

From: Wei Dai <[email-masked]>
Date: Mon, 11 Feb 2002 10:52:54 -0800

> operation between packets. If one packet consists of the ciphertext

I think your fix would be ok, but since it's not backwards compatible it
doesn't seem to have any advantage over defining new ciphers in CTR mode.

> define a single standard way of doing counter mode?

Google search for "ctr mode rfc" turned up a couple of drafts:

http://www.ietf.org/internet-drafts/draft-mcgrew-saag-icm-00.txt
http://www.vpnc.org/draft-moskowitz-aes128-ctr

I haven't read them yet.