Re: [Cryptography] Availability of plaintext/ciphertext pairs (was Re: In the face of cooperative end-points, PFS doesn't help)
On Sep 10, 2013, at 6:43 PM, Nemo n...@self-evident.org wrote: 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. according to http://en.wikipedia.org/wiki/Padding_(cryptography) , most protocols only talk about padding at the end of the cleartext before encryption. now, how about adding some random at the beginning of the cleartext, say, 2.5 times the block size, that is 40 bytes for the example above, of random stuff before the interesting text appears ? - Raphael smime.p7s Description: S/MIME cryptographic signature ___ 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)
On Wed, 11 Sep 2013 06:49:45 +0200 Raphael Jacquot sxp...@sxpert.org wrote: according to http://en.wikipedia.org/wiki/Padding_(cryptography) , most protocols only talk about padding at the end of the cleartext before encryption. now, how about adding some random at the beginning of the cleartext, say, 2.5 times the block size, that is 40 bytes for the example above, of random stuff before the interesting text appears ? The padding at the end is to make sure that you have a full block of data for a block cipher, since your actual message will usually be shorter than a full block. In symmetric systems, it is not per se a security feature. (Asymmetric Adding padding at the front to prevent cryptanalysts from using cribs (that is, known plaintext) seems useless to me. Even if the padding was of random length, it is of necessity going to be short. If you have a technique that depends on known plaintext, crib dragging (that is, trying all of the small number of possibilities) is easy. Perry -- Perry E. Metzgerpe...@piermont.com ___ 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)
On Sep 11, 2013, at 5:57 PM, Nemo n...@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 ___ 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 leich...@lrw.com 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 leich...@lrw.com 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] Availability of plaintext/ciphertext pairs (was Re: In the face of cooperative end-points, PFS doesn't help)
On Sep 10, 2013, at 5:49 PM, Perry E. Metzger pe...@piermont.com wrote:
Phil Rogoway has a paper somewhere discussing the right way to
implement cryptographic modes and API's.
It would be useful to get a URL for it.
In particular, he recommends changing the definition of CBC...to
E_0 = E(IV) # Not transmitted
E_{i+1} = E(E_i XOR P_{i+1})
You make no mention there of whether the key used to encrypt the IV
is the same as that used for the plaintext.
As I recall the proposal, it was the same key. (Generating a different one for
this purpose is pointless - it would have to be random, in which case you might
as well generate the IV randomly.)
I presume if you need a lot of IVs (see protocols like IPsec), and have
enough key material, a second key might be of value for that -- but I don't
know what all the ins and outs are, and would prefer to read the literature...
I searched around but couldn't find it; the proposal apparently was not
Rogoway's. It apparently appears in NIST 800-38A (2001), with no citation. In
searching around, I came across a recent, unpublished paper by Rogoway:
http://www.cs.ucdavis.edu/~rogaway/papers/modes.pdf
That paper - which does detailed analyses of a large number of modes -
indicates that more recent work has shown that this technique for choosing an
IV is *not* secure (against a certain class of attacks) and recommends against
using it.
I highly recommend that paper. In fact, I highly recommend everything Rogoway
has written. We've been discussing authentication and session key exchange -
he and Bellare wrote about the problem in 1993
http://cseweb.ucsd.edu/users/mihir/papers/eakd.pdf giving provably secure
algorithms for the 2-party case, and two years later
http://www.cs.ucdavis.edu/~rogaway/papers/3pkd.pdf extending the work to the
3-party case.
-- Jerry
___
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)
On Sep 10, 2013, at 12:43 PM, Nemo n...@self-evident.org wrote:
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.
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})
to
E_0 = E(IV) # Not transmitted
E_{i+1} = E(E_i XOR P_{i+1})
This eliminates known plaintext in the first block. If you use this definition
for chained CBC - where you use the final block of a segment as the IV for the
next segment - it also eliminates 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) that even caused
problems for CBC modes in either SSH or TLS.
Beyond this, it changes the requirements on the IV as provided by the user from
random to never repeated for any given key - an easier requirement that's
much less likely to be accidentally violated.
The cost of this is one extra block encryption at each end of the link, per CBC
segment - pretty trivial. When I implemented a protocol that relied on CBC, I
made this the exposed primitive. When I later learned of the prefix attack, I
was gratified to see that my code was already immune.
It actually amazes me that anyone uses the raw IV for the first XOR any more.
-- Jerry
___
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)
On Tue, 10 Sep 2013 17:04:04 -0400 Jerry Leichter leich...@lrw.com
wrote:
Phil Rogoway has a paper somewhere discussing the right way to
implement cryptographic modes and API's.
It would be useful to get a URL for it.
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})
to
E_0 = E(IV) # Not transmitted
E_{i+1} = E(E_i XOR P_{i+1})
You make no mention there of whether the key used to encrypt the IV
is the same as that used for the plaintext. I presume if you need a
lot of IVs (see protocols like IPsec), and have enough key material, a
second key might be of value for that -- but I don't know what all
the ins and outs are, and would prefer to read the literature...
Perry
--
Perry E. Metzgerpe...@piermont.com
___
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)
On 11/09/13 01:36 AM, Jerry Leichter wrote: (Generating a different one for this purpose is pointless - it would have to be random, in which case you might as well generate the IV randomly.) In a protocol I wrote with Zooko's help, we generate a random IV0 which is shared in the key exchange. http://www.webfunds.org/guide/sdp/sdp1.html Then, we also move the padding from the end to the beginning, fill it with a non-repeating length-determined value, and expand it to a size of 16-31 bytes. This creates what is in effect an IV1 or second transmitted IV. http://www.webfunds.org/guide/sdp/pad.html iang ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
