Subject: a more detailed analysis of "known IV" vulnerability.

From: Bill Sommerfeld <[email-masked]>
Date: Mon, 11 Mar 2002 16:54:18 -0500

[folks, please look this over and let me know if I missed anything..]

Summary:

For 64-bit block ciphers in CBC mode, the probability that a given ssh
session key could be exposed to a known-IV chosen-plaintext CBC
guessing attack is somewhere around 1 chance in 2**23 assuming the key
is used for the maximum recommended 1 gigabyte of data.  

Given the one-hour lifetime of ssh session keys, the chance of success
is also influenced by the round trip time between the attacker and the
victim; the 1  chance in 2**23 above assumes  a roughly 100microsecond
RTT.  A 10ms RTT decreases this to roughly one chance in 2**30.

To put this in perspective, the chance that a similar 1 gigabyte
session encrypted using CBC mode with a 64-bit block will contain a
pair of duplicate ciphertext blocks (exposing the XOR of the
corresponding plaintext blocks) is about one chance in 2**11.

With 128-byte-block CBC mode, the attack is much more difficult; the
guessing attack is possible on a session about 1 time in 2**71.

Details:

[Note: One thing not considered here is compression, which fits
between the ssh transport and connection layers -- it may allow
additional user-chosen data in the first block, but requires the
attacker to have perfect or near-perfect knowledge of the previous
plaintext in order to allow the state of the compressor to be tracked.
I've chosen to ignore it for now.]

Given the multilayered message framing in ssh v2, it appears that the
earliest raw user data can appear is 14 bytes into a message; before
that, an attacker can really only influence message lengths.

Messages in the encrypted stream look like:

     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

[http://www.ietf.org/internet-drafts/draft-ietf-secsh-transport-13.txt]

However, that's not all that's involved.. the typical 'payload' starts:

     byte      SSH_MSG_CHANNEL_DATA
     uint32    recipient channel
     string    data
[http://www.ietf.org/internet-drafts/draft-ietf-secsh-connect-15.txt]

and a "string" in ssh encoding is a is a uint32 N followed by N
bytes..
[http://www.ietf.org/internet-drafts/draft-ietf-secsh-architecture-12.txt]

Assuming a max message length of 64k (a typical implementation limit),
an attacker can, at best, influence 16 bits out of the first 64 bits
of the packet by adjusting the length of the injected message.

so, rolling it all together, the first 16 bytes would be:

        len3 len2 len1 len0  plen 0x5e chan chan
        chan chan sln3 sln2  sln1 sln0 dat0 dat1

len is packet length
plen is padding length
chan are the bytes of channel id (small integer)
slen are the string length bytes
dat0 and dat1 are the actual payload being sent to the channel.

len3/len2 are likely to be zero; high order bits of len1 are likely to
be zero (short messages); the three low order bits of len0 are all
zero (since packets are always a multiple of the block size or 8
bytes, whichever's larger), though those bits effectively move to the
low order bits of plen..

high order bytes of chan are very likely to be zero or at the very
least fixed for a given injection point.

For an 8-byte block size:

Of the first 8 bytes, attacker picks at most 16 bits, and has to wait
for the remaining 48 bits of the IV to line up "just so"; i.e., on
average, they have a suitable IV only once every 2**48 messages.

There's a keychange every gigabyte.  Let's assume a minimum message
size of 32 bytes (the sshv2 implementation I use seems to send
slightly larger messages than that, but using power of two makes the
math easier), so that's 2**25 messages per key.

This means that any given ssh session will be vulnerable to the
message-guessing attack roughly one chance in 2**23.

For a 16-byte block size:

attacker controls at most 32 independant bits (the string length and
packet length are going to be interdependant), so suitable IV comes
along only once in 2**96 messages.  

With 2**25 messages per key, this means a session will be vulnerable
at most one chance in 2**71.

---

Effects of the one-hour maximum session key lifetime:

		plaintext insertion -> victim => snoop point =======> peer
		     ^			              |
		     +--------------------------------+

In order to effect the attack, the attacker must trick the attacked
system into generating a large number of messages (in order to
generate as many possible IV's as possible) but must also be able to
react very quickly to inject the chosen plaintext immediately after
the IV appears; this suggests that the attack will be limited by the
round-trip delay around the feedback loop diagrammed above.

In order to get 2**25 "usable" IV's in an hour, the victim must
generate roughly 9321 packets per second, and the total delay around
the feedback loop (including the processing time on the victim) must
be less than 107 microseconds.  

Increasing the delay will reduce the chance that the session will be
vulnerable.

					- Bill

---

From: Wei Dai <[email-masked]>
Date: Wed, 13 Mar 2002 20:23:22 -0800

Couple of problems in this analysis:

1. You're assuming that there is only one packet per session that the
attacker wants to confirm a guess for. A more conservative figure would be
2^16 target packets per session.

2. By opening 2^24 channels, the attacker can gain control over 8 more
bits of the plaintext for 8-byte block size, and 24 more bits for 16-byte
block size.

Together, these two changes in the analysis imply that an attacker can on
average confirm guesses on two packets per session for 8-byte block size.
For 16-byte block size, it's once every 2^31 sessions.

---

From: [email-masked] (Niels Möller)
Date: 14 Mar 2002 11:58:55 +0100

> bits of the plaintext for 8-byte block size, and 24 more bits for 16-byte

Do implementations allow that? My implementation has an arbitrary
limit of 2^17 channels per connection. (And channel numbers are
allocated sequentially).

/Niels

---

From: Wei Dai <[email-masked]>
Date: Thu, 14 Mar 2002 18:12:05 -0800

> limit of 2^17 channels per connection. (And channel numbers are

The attacker does not need to keep all of the channels open. He can open
and close 2^24 channels to iterate through the channel numbers, and just
keep 2^8 channels, each with a different id mod 2^16, open for the attack.

---

From: [email-masked] (Niels Möller)
Date: 15 Mar 2002 11:49:57 +0100

> keep 2^8 channels, each with a different id mod 2^16, open for the attack.

That depends on how channel numbers are allocated. I think a typical
implementation uses a linear channel table indexed by its local
channel numbers, and it will not allocate large local channel numbers
as long as small numbers are available (as that would imply growing
the tables). E.g., my implementation will never allocate a channel
number larger than 2^17, and it always allocates the smallest
available number. ("sequentially" above was perhaps not the right
word, sorry about that).

But an implementation has control only over its *local* numbers, the
numbers it transmits over the wire are chosen by the remote peer. If
the attacker has control over the peer, he gets full control over the
channel numbers I send. I don't know how likely that is; if the
attacker has control over the software at the remote peer, we may well
have bigger problems.

/Niels

---

From: [email-masked] (David Wagner)
Date: 16 Mar 2002 07:13:55 GMT

>[folks, please look this over and let me know if I missed anything..]

Ahh.  Thanks for the detailed analysis.

I must admit I'm not 100% convinced by your numbers, though they seemed
like a good start.  It looked to me like a better estimate is that
around four blocks of plaintext might leak in an average 1 GB session,
assuming circumstances most favorable to the attacker.

However, that's still not so bad.  If all those assumptions on the
upper layers hold, then the leakage is still not very severe, I guess.
(Of course, we're relying heavily on these assumptions about the upper
layers, so it is crucial that the upper layers not be re-designed --
e.g., by allowing provisions for fragmentation in the upper layers.)

Bottom line: the exposure is quite limited, and I think it's reasonable to
conclude that this attack will not be easiest way to break SSH sessions.
If this is the best attack on SSH, that's a pretty good place to be at.
So I think I agree with the decision to defer these changes in order to
encourage SSH deployment as soon as possible.  I withdraw any objections
I may have had.  Thanks for the explanations.

I believe this rationale should be carefully explained in the SSH RFC.
Otherwise, some readers might get the wrong impression.  Also, it will
help inform those who might re-use the SSH encoding transform without
also maintaining the upper layers that they are in a danger zone.

---

From: RJ Atkinson <[email-masked]>
Date: Sat, 16 Mar 2002 13:51:09 -0500

On Saturday, March 16, 2002, at 07:13 , David Wagner wrote:
>  I think it's reasonable to conclude that this attack will not
> be easiest way to break SSH sessions.

This has been my conclusion as well, based largely on
Ross Anderson's paper on how crypto is typically broken.

> also maintaining the upper layers that they are in a danger zone.

I'm not sure whether the detailed analysis really belongs in the
core SSH RFCs.  Documenting in some RFC, possibly a parallel RFC
with Informational status, seems eminently reasonable.

Ran

---

From: Damien Miller <[email-masked]>
Date: Sun, 17 Mar 2002 21:27:24 +1100 (EST)

> with Informational status, seems eminently reasonable.

Can we put some text in the "security considerations" referring someone
to a published document without delaying the drafts?

-d

---

From: Bill Sommerfeld <[email-masked]>
Date: Sun, 17 Mar 2002 14:38:21 -0500

> with Informational status, seems eminently reasonable.

[wg chair hat off]

agreed.  

I think it's best to split detailed analysis of this form into a
separate document.  An analysis of this form, while important, will
dilute the specification and make it harder for an implementor to find
the actual "meat" of the protocol.

						- Bill