[Cryptography] Availability of plaintext/ciphertext pairs (was Re: In the face of "cooperative" end-points, PFS doesn't help)

[Jerry Leichter]

On Sep 10, 2013, at 12:43 PM, Nemo <nemo at self-evident.org> wrote:
> "GET / HTTP/1.1\r\n" is exactly 16 bytes, or one AES block. If the IV is
> sent in the clear -- which it is -- that is one plaintext-ciphertext
> pair right there for every HTTPS connection.
Phil Rogoway has a paper somewhere discussing the right way to implement cryptographic modes and API's.  In particular, he recommends changing the definition of CBC from:

E_0 = IV     # Not transmitted
E_{i+1} = E(E_i XOR P_{i+1})

to

E_0 = E(IV)  # Not transmitted
E_{i+1} = E(E_i XOR P_{i+1})

This eliminates known plaintext in the first block.  If you use this definition for chained CBC - where you use the final block of a segment as the IV for the next segment - it also eliminates the known attack (whose name escapes me - it was based on an attacker being able to insert a prefix to the next segment because he knows the IV it will use before it gets sent) that even caused problems for CBC modes in either SSH or TLS.

Beyond this, it changes the requirements on the IV as provided by the user from "random" to "never repeated for any given key" - an easier requirement that's much less likely to be accidentally violated.

The cost of this is one extra block encryption at each end of the link, per CBC segment - pretty trivial.  When I implemented a protocol that relied on CBC, I made this the exposed primitive.  When I later learned of the prefix attack, I was gratified to see that my code was already immune.

It actually amazes me that anyone uses the raw IV for the first XOR any more.

                                                        -- Jerry