Authenticated Encryption in SSH: Provably Fixing the SSH Binary Packet Protocol

Mihir Bellare, Tadayoshi Kohno, and Chanathip Namprempre Proceedings of 2002 ACM Conference on Computer and Communications Security

Summary (Greg Koenig):

This paper analyzes the Secure Shell (SSH) Binary Packet Protocol (BPP) and describes a class of vulnerabilities discovered. The authors then describe several provably-secure fixes to these vulnerabilities and present the potential trade-offs for using the various fixes they advocate.

The SSH BPP specification states that SSH implementations should use CBC mode encryption with chained initialization vectors. That is, the initialization vector used when encrypting a plaintext block is the last block of the previous ciphertext. The authors refer to this protocol as SSH-IPC (for "inter-packet chaining"). As described elsewhere (P. Rogaway, "Problems with Proposed IP Cryptography"), CBC mode encryption with chained initialization vectors is insecure, and this insecurity extends to SSH-IPC. Briefly, the difficulty is that an attacker knows the initialization vector for the next message to be encrypted before the next message is actually encrypted. If he can control the entire first block of input into SSH-IPC, he then correspondingly controls input into the underlying block cipher and can use this to gain information about messages encrypted with the cipher.

A natural fix to the deficiency described above might be to replace the encryption used in SSH-BPP with CBC mode encryption with randomized initialization vectors. In this mode, a new random initialization vector is chosen for each message, and the initialization vector to be used for the next message is sent along inside the ciphertext of the current message. The authors refer to this protocol as SSH-NPC (for "no packet chaining"). Unfortunately SSH-NPC is susceptible to a "reaction attack". If the padding values used to pad a plaintext block are fixed (e.g., all zero) or easily guessed, an attacker can intercept two ciphertext blocks and make a guess about the two corresponding plaintexts. The attacker then creates a new ciphertext based on the guessed plaintext and injects it into the network. If the receiver disconnects its side of the SSH connection (as described in the SSH specification), the attacker knows that its guess was incorrect and can make future guesses about the plaintext accordingly. Also, if the connection is not re-keyed after 2^32 messages (re-keying is left as an implementation-dependent decision), the connection is vulnerable to replay attacks, out-of-order delivery attacks, and information leakage attacks. (The information leakage attack comes from the fact that a 32-bit counter is used in BPP and this counter makes up a portion of the MAC. If the counter recycles, then information is leaked through the MAC portion of the underlying BPP ciphertext packet.)

The authors then describe three secure fixes to SSH-BPP. All three secure fixes assume that re-keying takes place at least once in every 2^32 messages.

* SSH-$NPC -- CBC mode encryption with a randomized initialization vector and >= 1 full block of random padding. The difficulty with this fix is that since SSH tends to involve interactive traffic where a small number of keystrokes are sent across the network, the extra padding involved is a high overhead.

* SSH-CTRIV-CBC -- CBC mode encryption with the initialization vector generated by encrypting a counter with a different key from the primary key used to encrypt plaintext packets.

* SSH-CTR -- CTR mode encryption where the sender and receiver both maintain a counter used as the initialization vector.

Pros (Damon Cook):

- clear statement of problem

- credit to Dai for finding problem

- multiple solutions discussed

- building blocks for solutions discussed

(chained IV -> random IV -> random IV with random padding)

- provably secure (against some attacks)

- ease of modification is a big deal, good that they included it

- acknowledged deficits up front

- I like that they included the Appendix at the end of the long version

of the paper

- good slides (for the SRG discussion of the paper)

Cons:

None received.

Discussion:

* Under "Theoretical Contributions" in Section 1 of the paper, the authors state that a potential disadvantage of their notions of security is that they may be "too strong" for some applications. The authors suggest that for some analysis, the concept of secure channels might be more appropriate. In analyzing security protocols, what factors determine whether one should use a more abstract analysis (which eliminates some complexity at the cost of some details) or a more complicated analysis (which is more difficult to follow but offers a more thorough understanding)?

* Are the problems described in this paper enough to warrant modifications to the protocol? That is, the vulnerabilities described in this paper are very pointed and require an attacker to be able to work in very constrained ways (e.g., to control the first plaintext fed into a block cipher; or to make a guess at a plaintext and see if the guess was correct by possibly disconnecting an in-progress SSH session, which would require the attacker in a large sense to "start over" with his attack if the guess was incorrect). Given these constraints, is it worth the time and energy necessary to fix the vulnerabilities in question since they are unlikely to be able to be encountered in practice? (Devil's Advocate question.)

* The authors suggest that the method of analysis described in this paper could be used in analyzing other security protocol specifications. What are some of these?

Voting:

Strong Accept: 0

Accept: 14

Reject: 1

Strong Reject: 0