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

2013-09-11 Thread Nemo
Jerry Leichter writes:

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

Thank you for the reference, by the way; it is an excellent paper.

 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

 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

To rephrase:

Security proofs for block cipher modes never depend on keeping the IV
confidential from the attacker. Standard practice (e.g. TLS, SSH) is to
send it in the clear, and this is fine as far as provable security is

Rogaway's paper does point out, among other things, that naive handling
of the IV can break the security proofs; e.g., for the scheme you
described earlier in this thread and incorrectly attributed to Rogaway.

My point is that if the IV can be kept confidential cheaply, why not? (I
am particularly thinking of CTR mode and its relatives.)

 - Nemo
The cryptography mailing list

Re: [Cryptography] Summary of the discussion so far

2013-09-11 Thread Nemo
Phillip Hallam-Baker writes:

 I have attempted to produce a summary of the discussion so far for use
 as a requirements document for the PRISM-PROOF email scheme. This is
 now available as an Internet draft.

First, I suggest removing all remotely political commentary and sticking
to technical facts.  Phrases like questionable constitutional validity
have no place in an Internet draft and harm the document, in my opinion.

Second, your section on Perfect Forward Secrecy ignores the purpose of
PFS, which has nothing to do with defense against cryptanalytic attacks.
The purpose of PFS is this: Should an attacker compel you to disclose
your private key, or should they compromise or confiscate the system
where your private key is stored, they could then decrypt all of your
earlier communications...  unless you used PFS.

 - Nemo
The cryptography mailing list

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

2013-09-11 Thread Nemo
Jerry Leichter writes:

 The real problem is that unpredictable has no definition.

Rogaway provides the definition in the paragraph we are discussing...

 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 e(q, t) value defined above.

That e(q,t) value defined above is the probability that the attacker
can predict the IV after q samples given time t. That appears to be a
very precise definition of predictability, and the smaller it gets,
the closer you get to random-IV security.

But enough of this particular rat hole.

 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.

Fair enough; I apologize for my flippancy. Of course the assumption of a
strong block cipher is justified by massive amounts of painstaking
effort expended in attempts to crack them.

Nonetheless, I think it would be wise to build in additional margin
anywhere we can get it cheaply.

 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.

I doubt we will have provable complexity lower bounds for useful
cryptographic algorithms until well after P vs. NP is resolved.  That
is, not soon.

Until then, provable security is purely about reductions. There is
nothing wrong with that. And as I said before, I believe we should worry
greatly about theoretical attacks that invalidate those reductions,
regardless of how purely academic they may seem to an engineer.

 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.

Yes, obviously... which is why I wrote I am particularly thinking of
CTR mode and its relatives.

It's a pity OCB mode is patented.

 - Nemo
The cryptography mailing list

[Cryptography] Seed values for NIST curves

2013-09-09 Thread Nemo
I have been reading FIPS 186-3 ( and 186-4 (, particularly
Appendix A describing the procedure for generating elliptic curves and
Appendix D specifying NIST's recommended curves.

The approach appears to be an attempt at a nothing up my sleeve
construction. Appendix A says how to start with a seed value and use SHA-1
as a psuedo-random generator to produce candidate curves until a suitable
one is found. Appendix D includes the seed value for each curve so that
anyone can verify they were generated according to the pseudo-random
process described in Appendix A.

Unless NSA can invert SHA-1, the argument goes, they cannot control the
final curves.


To my knowledge, most nothing up my sleeve constructions use clearly
non-random seed values. For example, MD5 uses the sines of consecutive
integers. SHA-1 uses sqrt(2), sqrt(3), and similar.

Using random seeds just makes it look like you wanted to try a few -- or
possibly a great many -- until the result had some undisclosed property you

Question: Who chose the seeds for the NIST curves, and how do they claim
those seeds were chosen, exactly?

 - Nemo
The cryptography mailing list