[147051] in cryptography@c2.net mail archive
Re: [Cryptography] Availability of plaintext/ciphertext pairs (was
daemon@ATHENA.MIT.EDU (Jerry Leichter)
Wed Sep 11 18:37:03 2013
X-Original-To: cryptography@metzdowd.com
From: Jerry Leichter <leichter@lrw.com>
In-Reply-To: <87eh8vhvib.fsf@self-evident.org>
Date: Wed, 11 Sep 2013 18:34:56 -0400
To: Nemo <nemo@self-evident.org>
Cc: Peter Fairbrother <zenadsl6186@zen.co.uk>, cryptography@metzdowd.com
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
--===============6975608450416531367==
Content-Type: multipart/alternative; boundary="Apple-Mail=_884FC970-2D29-4574-8F27-6E1024370279"
--Apple-Mail=_884FC970-2D29-4574-8F27-6E1024370279
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
charset=utf-8
On Sep 11, 2013, at 5:57 PM, Nemo <nemo@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.
>=20
> 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:
>=20
> 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 =E2=80=9Cgive =
up=E2=80=9D in the ind$ advantage an amount proportional to the =CE=B5(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.
>=20
>> Incorrect on multiple levels. See the paper I mentioned in my
>> response to Perry.
>=20
> 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.
>=20
> 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.=20
-- Jerry
--Apple-Mail=_884FC970-2D29-4574-8F27-6E1024370279
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html;
charset=utf-8
<html><head><meta http-equiv=3D"Content-Type" content=3D"text/html =
charset=3Dutf-8"></head><body style=3D"word-wrap: break-word; =
-webkit-nbsp-mode: space; -webkit-line-break: after-white-space; =
"><div><div>On Sep 11, 2013, at 5:57 PM, Nemo <<a =
href=3D"mailto:nemo@self-evident.org">nemo@self-evident.org</a>> =
wrote:</div><blockquote type=3D"cite"><blockquote type=3D"cite">The =
older literature requires that the IV be "unpredictable" =
(an<br>ill-defined term), but in fact if you want any kind of security =
proofs<br>for CBC, it must actually be =
random.<br></blockquote><br>Wrong, according to the Rogaway paper you =
cited. Pull up<br><a =
href=3D"http://www.cs.ucdavis.edu/~rogaway/papers/modes.pdf">http://www.cs=
.ucdavis.edu/~rogaway/papers/modes.pdf</a> and read the =
last<br>paragraph of section I.6 (pages 20-21). Excerpt:<br><br> =
We concur, without trying to formally show theorems, =
that all of the<br> SP 800-38A modes that are secure =
as probabilistic encryption schemes<br> -- namely, =
CBC, CFB, and OFB -- will remain secure if the IV is not<br> =
perfectly random, but only =
unguessable.</blockquote><div class=3D"page" title=3D"Page 27"><div =
class=3D"layoutArea"><div class=3D"column"><div>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: "<span =
style=3D"font-size: 11pt; font-family: CMR10; ">A quantitative statement =
of such results would =E2=80=9Cgive up=E2=80=9D in the ind$ advantage an =
amount proportional to the </span><span style=3D"font-size: 11pt; =
font-family: CMMI10; ">=CE=B5</span><span style=3D"font-size: 11pt; =
font-family: CMR10; ">(</span><span style=3D"font-size: 11pt; =
font-family: CMMI10; ">q, t</span><span style=3D"font-size: 11pt; =
font-family: CMR10; ">) value defined =
above."</span></div><div><br></div></div></div></div><blockquote =
type=3D"cite"><blockquote type=3D"cite"><blockquote type=3D"cite">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.<br></blockquote></blockquote><br><blockquote =
type=3D"cite">Incorrect on multiple levels. See the paper I =
mentioned in my<br>response to Perry.<br></blockquote><br>If you are =
going to call me wrong in a public forum, please have the<br>courtesy to =
be specific. My statement was, in fact, correct in =
every<br>detail.<br><br>To rephrase:<br></blockquote>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.<br></div><div><br></div><div>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.)</div><div><br></div><div>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. </div><div><br></div><div><div> =
=
=
-- =
Jerry</div><div><br></div></div></body></html>=
--Apple-Mail=_884FC970-2D29-4574-8F27-6E1024370279--
--===============6975608450416531367==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
--===============6975608450416531367==--
