Re: [Cryptography] Availability of plaintext/ciphertext pairs (was Re: In the face of "cooperative" end-points, PFS doesn't help)
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@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Summary of the discussion so far
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. > > http://www.ietf.org/id/draft-hallambaker-prismproof-req-00.txt 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 cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Availability of plaintext/ciphertext pairs (was Re: In the face of "cooperative" end-points, PFS doesn't help)
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 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. 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 >> 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: 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 concerned. 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 cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] Availability of plaintext/ciphertext pairs (was Re: In the face of "cooperative" end-points, PFS doesn't help)
Jerry Leichter 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
___
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
[Cryptography] Availability of plaintext/ciphertext pairs (was Re: In the face of "cooperative" end-points, PFS doesn't help)
(I apologize this message is not correctly threaded. I only subscribed to the list recently, and I have found no way to cannot construct a proper In-reply-to header from messages in the archive.) Peter Fairbrother wrote: > And most of their interception is passive, they just listen - you > generally need at least one plaintext/ciphertext pair to break a > cipher and find a session key, and most often they don't have the > plaintext, just the ciphertext. I agree with everything you have said, except for this. "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. In fact, _any_ aligned 16 bytes of plaintext in the conversation that are known, or that are in a guessable range, represent a plaintext/ciphertext pair if either of the following are true: 1) You sent the IV in the clear 2) You used CBC mode Of the modes I know (CBC, CTR, GCM, et. al.), the only one that does not freely give up such plaintext/ciphertext pairs is OCB. Of course, we assume our block ciphers are secure against even astronomical numbers plaintext/ciphertext pairs, because any evidence to the contrary would represent a publication-worthy if not Ph.D.-worthy result. But is it really such a good assumption against _this_ adversary? It seems to me that the IV could easily be negotiated at the same time as the session key. 2048-bit or 3072-bit RSA or DH already provide enough bits, so you can have a secret IV, independent of the session key, "for free". ECDH provides enough negotiated bits, too, once you are in the 256+ bit range. So, "avoid CBC" plus "negotiate the IV" seems like a simple way to stir extra entropy into the encryption. It does nothing for any security proofs, since those assume perfectly secure block ciphers... But it might make somebody's job just a little bit harder in practice. And since it would cost nothing, why not? - Nemo ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
[Cryptography] Seed values for NIST curves
I have been reading FIPS 186-3 ( http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf) and 186-4 ( http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf), 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. However... 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 wanted. Question: Who chose the seeds for the NIST curves, and how do they claim those seeds were chosen, exactly? - Nemo ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
