[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 7:27 PM, Nemo wrote:
>> 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...
Sure.  The intent was just that the ciphertext starts with E1.  IV has to be known to both sides, but it's part of the setup, not the ciphertext.

>> 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.
That's certainly true.  On the other hand, there's no mode I know of that denies the attacker access to (guessed or known or even chosen, if the attacker has a way to influence the data sent) plaintext/ciphertext pairs = which is exactly why no one would even begin to consider a cipher these days unless it was convincingly secure against chosen ciphertext attack.  (Before roughly the 1950's, it was the working rule that plaintext transmitted via a cryptosystem was never released.  Embassies receiving announcements via an enciphered channel would paraphrase them before making them public.)

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

>> 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.
No, something much simpler.  Consider a situation in which there's an ongoing exchange of messages:  Alice sends to Bob, Bob responds to Alice.  Alice uses CBC and just continues the CBC sequence from one message to the next.  In effect, this presents Eve with the initiation of a new CBC session, with a known IV.  Between the end of one of Alice's messages to Bob and the next, Eve knows the next IV.

Suppose Eve also knows a previously-transmitted plaintext block P2.  Let P1 be the (unknown) plaintext block immediately preceding P2.  P2 was transmitted as

	C2 = E(E(P1) XOR P2)

If Eve re-inserts C2 as the first message of the response to Bob, Bob will decrypt it as IV XOR D(C2) == IV XOR E(P1) XOR P2.  Thus Eve gets Bob to accept P2 modified by XOR'ing with a known quantity - which is not supposed to be possible in a secure mode.

BTW, this reveals an interesting and little-mentioned assumption about CBC:  That Eve can't insert a ciphertext block between two of Alice's in the time between two blocks.  Probably not a good assumption on a packet network, actually.

The older literature requires that the IV be "unpredictable" (an ill-defined term), but in fact if you want any kind of security proofs for CBC, it must actually be random.

> 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.
Incorrect on multiple levels.  See the paper I mentioned in my response to Perry.
                                                        -- Jerry