[147169] in cryptography@c2.net mail archive
Re: [Cryptography] The paranoid approach to crypto-plumbing
daemon@ATHENA.MIT.EDU (Watson Ladd)
Mon Sep 16 20:11:26 2013
X-Original-To: cryptography@metzdowd.com
In-Reply-To: <99F72F04-6365-4F10-8AA1-CF2B453834D3@lrw.com>
Date: Mon, 16 Sep 2013 16:52:04 -0700
From: Watson Ladd <watsonbladd@gmail.com>
To: Jerry Leichter <leichter@lrw.com>
Cc: "cryptography@metzdowd.com List" <cryptography@metzdowd.com>,
Bill Frantz <frantz@pwpconsult.com>
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
--===============1907572980840922627==
Content-Type: multipart/alternative; boundary=001a11c38cfe289e1404e688e491
--001a11c38cfe289e1404e688e491
Content-Type: text/plain; charset=UTF-8
On Mon, Sep 16, 2013 at 4:02 PM, Jerry Leichter <leichter@lrw.com> wrote:
> On Sep 16, 2013, at 6:20 PM, Bill Frantz wrote:
>>> Joux's paper "Multicollisions in iterated hash functions"
http://www.iacr.org/archive/crypto2004/31520306/multicollisions.ps
>>> shows that "finding ... r-tuples of messages that all hash to the same
value is not much harder than finding ... pairs of messages". This has
some surprising implications. In particular, Joux uses it to show that, if
F(X) and G(X) are cryptographic hash functions, then H(X) = F(X) || G(X)
(|| is concatenation) is about as hard as the harder of F and G - but no
harder.
>> This kind of result is why us crypto plumbers should always consult real
cryptographers. :-)
> Yes, this is the kind of thing that makes crypto fun.
>
> The feeling these days among those who do such work is that unless you're
going to use a specialized combined encryption and authentication mode, you
might as well use counter mode (with, of course, required authentication).
For the encryption part, counter mode with multiple ciphers and
independent keys has the nice property that it's trivially as strong as the
strongest of the constituents. (Proof: If all the ciphers except one are
cracked, the attacker is left with a known-plaintext attack against the
remaining one. The need for independent keys is clear since if I use two
copies of the same cipher with the same key, I end up sending plaintext!
You'd need some strong independence statements about the ciphers in the
set if you want to reuse keys. Deriving them from a common key with a
one-way hash function is probably safe in practice, though you'd now need
some strong statements about the hash function to get any theoretical
result. Why rely on such things when you
> don't need to?)
>
> It's not immediately clear to me what the right procedure for multiple
authentication is.
> -- Jerry
The right procedure would be to use a universal hash function together with
counter mode encryption. This has provable security relatable to the
difficulty of finding linear approximations to the encryption function.
But I personally don't think this is much use. We have ciphers that have
stood up to lots of analysis. The real problems have been in modes of
operation, key negotiation, and deployment.
Sincerely,
Watson Ladd
>
> _______________________________________________
> The cryptography mailing list
> cryptography@metzdowd.com
> http://www.metzdowd.com/mailman/listinfo/cryptography
--
"Those who would give up Essential Liberty to purchase a little Temporary
Safety deserve neither Liberty nor Safety."
-- Benjamin Franklin
--001a11c38cfe289e1404e688e491
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><br>On Mon, Sep 16, 2013 at 4:02 PM, Jerry Leichter <<a=
href=3D"mailto:leichter@lrw.com">leichter@lrw.com</a>> wrote:<br>> O=
n Sep 16, 2013, at 6:20 PM, Bill Frantz wrote:<br>>>> Joux's p=
aper "Multicollisions in iterated hash functions" <a href=3D"http=
://www.iacr.org/archive/crypto2004/31520306/multicollisions.ps">http://www.=
iacr.org/archive/crypto2004/31520306/multicollisions.ps</a><br>
>>> shows that "finding ... r-tuples of messages that all has=
h to the same value is not much harder than finding ... pairs of messages&q=
uot;. =C2=A0This has some surprising implications. =C2=A0In particular, Jou=
x uses it to show that, if F(X) and G(X) are cryptographic hash functions, =
then H(X) =3D F(X) || G(X) (|| is concatenation) is about as hard as the ha=
rder of F and G - but no harder.<br>
>> This kind of result is why us crypto plumbers should always consul=
t real cryptographers. :-)<br>> Yes, this is the kind of thing that make=
s crypto fun.<br>><br>> The feeling these days among those who do suc=
h work is that unless you're going to use a specialized combined encryp=
tion and authentication mode, you might as well use counter mode (with, of =
course, required authentication). =C2=A0For the encryption part, counter mo=
de with multiple ciphers and independent keys has the nice property that it=
's trivially as strong as the strongest of the constituents. =C2=A0(Pro=
of: =C2=A0If all the ciphers except one are cracked, the attacker is left w=
ith a known-plaintext attack against the remaining one. =C2=A0The need for =
independent keys is clear since if I use two copies of the same cipher with=
the same key, I end up sending plaintext! =C2=A0You'd need some strong=
independence statements about the ciphers in the set if you want to reuse =
keys. =C2=A0Deriving them from a common key with a one-way hash function is=
probably safe in practice, though you'd now need some strong statement=
s about the hash function to get any theoretical result. =C2=A0Why rely on =
such things when you<br>
> =C2=A0don't need to?)<br>><br>> It's not immediately cle=
ar to me what the right procedure for multiple authentication is.<br>> =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 -- Jerry<div>The right pro=
cedure would be to use a universal hash function together with counter mode=
encryption. This has provable security relatable to the difficulty of find=
ing linear approximations to the encryption function.</div>
<div><br></div><div>But I personally don't think this is much use. We h=
ave ciphers that have stood up to lots of analysis. The real problems have =
been in modes of operation, key negotiation, and deployment.</div><div>
Sincerely,<br>Watson Ladd<br>><br>> _________________________________=
______________<br>> The cryptography mailing list<br>> <a href=3D"mai=
lto:cryptography@metzdowd.com">cryptography@metzdowd.com</a><br>> <a hre=
f=3D"http://www.metzdowd.com/mailman/listinfo/cryptography">http://www.metz=
dowd.com/mailman/listinfo/cryptography</a><br>
<br><br><br>-- <br>"Those who would give up Essential Liberty to purch=
ase a little Temporary Safety deserve neither =C2=A0Liberty nor Safety.&quo=
t;<br>-- Benjamin Franklin<br></div></div>
--001a11c38cfe289e1404e688e491--
--===============1907572980840922627==
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
--===============1907572980840922627==--
