a more detailed analysis of "known IV" vulnerability.

[Bill Sommerfeld <sommerfeld%east.sun.com@localhost>]

[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