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

Jerry Leichter leichter at lrw.com
Wed Sep 11 18:34:56 EDT 2013


On Sep 11, 2013, at 5:57 PM, Nemo <nemo at self-evident.org> wrote:
>> 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.
> 
> Wrong, according to the Rogaway paper you cited.  Pull up
> http://www.cs.ucdavis.edu/~rogaway/papers/modes.pdf and read the last
> paragraph of section I.6 (pages 20-21).  Excerpt:
> 
>    We concur, without trying to formally show theorems, that all of the
>    SP 800-38A modes that are secure as probabilistic encryption schemes
>    -- namely, CBC, CFB, and OFB -- will remain secure if the IV is not
>    perfectly random, but only unguessable.
The real problem is that "unpredictable" has no definition.  E(0) with the session key is "unpredictable" to an attacker, but as the paper shows, it cannot safely be used for the IV.  Rogoway specifically says that if what you mean by "unpredictable" is "random but biased" (very informally), then you lose some security in proportion to the degree of bias:  "A quantitative statement of such results would “give up” in the ind$ advantage an amount proportional to the ε(q, t) value defined above."

>>> I do not think we will too find much guidance from the academic side on [secret IV's], 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.
> 
> If you are going to call me wrong in a public forum, please have the
> courtesy to be specific. My statement was, in fact, correct in every
> detail.
> 
> To rephrase:
I actually have no problem with your rephrased statement.  My concern was the apparently flippant dismissal of all "academic" work as "assuming a can opener".  Yes, there's some like that.  There's also some that shows how given weaker assumptions you can create a provably secure block cipher (though in practice it's not clear to me that any real block cipher is really created that way).  Beyond that, "provably secure" is slippery - there are many, many notions of security.  Rogoway's paper gives a particular definition for "secure" and does indeed show that if you have a random IV, CBC attains it.  But he also points out that that's a very weak definition of "secure" - but without authentication, you can't get any more.

Do I wish we had a way to prove something secure without assumptions beyond basic mathematics?  Absolutely; everyone would love to see that.  But we have no idea how to do it.  All we can do is follow the traditional path of mathematics and (a) make the assumptions as clear, simple, limited, and "obvious" as possible; (b) show what happens as the assumptions are relaxed or, sometimes, strengthened.  That's what you find in the good cryptographic work.  (BTW, if you think I'm defending my own work here - far from it.  I left academia and theoretical work behind a very long time ago - I've been a nuts-and-bolts systems guy for decades.)

On the matter of a secret IV:  It can't actually help much.  Any suffix of a CBC encryption (treated as a sequence of blocks, not bytes) is itself a valid CBC encryption.  Considered on its own, it has a secret IV; considered in the context of the immediately preceding block, it has a non-secret IV.  So a secret IV *at most* protects the very first block of the message.  I doubt anyone has tried to formalized just how much it might help simply because it's so small. 

                                                        -- Jerry

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20130911/1f1b4541/attachment.html>


More information about the cryptography mailing list