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

[Nemo]

Jerry Leichter <leichter at lrw.com> writes:

> 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})

Not sure what "not transmitted" means here. In typical CBC
implementations, the IV is certainly transmitted...

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

As written, this does nothing to deny plaintext/ciphertext pairs further
along in the stream. Typical encrypted streams have lots of
mostly-predictable data (think headers), not just the first 16 bytes.

I agree with Perry; a reference to a paper would be nice.

> 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)

I think you mean BEAST.

The security proof of CBC against Chosen Plaintext Attack requires that
the IV be unpredictable to the attacker. (I am working my way through
Dan Boneh's lectures on Coursera. Great stuff.) This was a "purely
academic" consideration, until BEAST came along.

Which leads to a personal pet peeve... If NSA is your adversary, then
**there is no such thing as a "purely academic" attack**. Any weakness,
no matter how theoretical, is worth avoiding if feasible. Implementors
keep making this mistake again and again -- "it's a purely academic
attack because blah blah blah so relax" -- and then something bad
happens years later. It would be nice if we could all finally learn this
lesson.

Back to CBC mode and secret IVs. I do not think we will too find much
guidance from the academic side on this, because they tend to "assume a
can opener"... Er, I mean a "secure block cipher"... And given that
assumption, all of the usual modes are provably secure with cleartext
IVs. Nonetheless, there is no danger in keeping IVs secret, so why not?
Negotiating 512 bits of secret costs little more than 256. So just
negotiate the IVs. Or, more plausibly, negotiate a second key to encrypt
the IVs. (Since you never reuse an IV anyway, ECB mode for the IVs is
fine.)

All of this is secondary to securing the key exchange, of course. That
part is much more scary because NSA's math skills are scary. In my
opinion, it is virtually certain NSA knows something about integer
factoring and/or integer discrete log and/or elliptic curves that we do
not. So I would build in some margin.  I would start with 3072 bits for
RSA/DH and 384 bits for ECC and only go up from there...

 - Nemo