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] 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)
On Sep 11, 2013, at 5:57 PM, Nemo 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)
On Wed, 11 Sep 2013 06:49:45 +0200 Raphael Jacquot 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 10, 2013, at 10:57 PM, ianG wrote: > 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 You should probably look at the Rogoway paper I found after Perry pushed me to give a reference. Yes, CBC with a true random IV is secure, though the security guarantee you can get if you don't also do authentication is rather weak. The additional padding almost certainly doesn't help or hurt. (I won't say that any more strongly because I haven't look at the proofs.) -- 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 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
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 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 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
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 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
___
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
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
[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
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 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 Sep 10, 2013, at 5:49 PM, "Perry E. Metzger" 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
