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

[Wei Dai <weidai%eskimo.com@localhost>]

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. 

On Mon, Mar 11, 2002 at 04:54:18PM -0500, Bill Sommerfeld wrote:
> [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
>