[147559] in cryptography@c2.net mail archive
Re: [Cryptography] Sha3
daemon@ATHENA.MIT.EDU (Jerry Leichter)
Mon Oct 7 19:32:18 2013
X-Original-To: cryptography@metzdowd.com
From: Jerry Leichter <leichter@lrw.com>
In-Reply-To: <WorldClient-F201310080004.AA04410130@futureware.at>
Date: Mon, 7 Oct 2013 18:44:53 -0400
To: =?iso-8859-1?Q?Philipp_G=FChring?= <pg@futureware.at>,
"cryptography@metzdowd.com List" <cryptography@metzdowd.com>
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
On Oct 7, 2013, at 6:04 PM, "Philipp G=FChring" <pg@futureware.at> wrote:
>> it makes no sense for a hash function: If the attacker can specify
>> something about the input, he ... knows something about the input! =
> Yes, but since it's standardized, it's public knowledge, and just knowing
> the padding does not give you any other knowledge about the rest.
You're assuming what the argument is claiming to prove.
> What might be though is that Keccak could have some hidden internal
> backdoor function (which I think is very unlikely given what I read about
> it until now, I am just speaking hypothetically) that reduces the
> effective output size, if and only if the input has certain bits at the e=
nd.
Well, sure, such a thing *might* exist, though there's no (publicly) known =
technique for embedding such a thing in the kind of combinatorial mixing pe=
rmutation that's at the base of Keccak and pretty much every hash function =
and block encryption function since DES - though the basic idea goes back t=
o Shannon in the 1940's.
I will say that the Keccak analysis shows both the strength and the weaknes=
s of the current (public) state of the art. Before differential cryptograp=
hy, pretty much everything in this area was guesswork. In the last 30-40 y=
ears (depending on whether you want to start with IBM's unpublished knowled=
ge of the technique going back, according to Coppersmith, to 1974, or from =
Biham and Shamir's rediscovery and publication in the late 1980's), the bas=
ic idea has been expanded to a variety of related attacks, with very sophis=
ticated modeling of exactly what you can expect to get from attacks under d=
ifferent circumstances. The Keccak analysis goes through a whole bunch of =
these. They make a pretty convincing argument that (a) no known attack can=
get anything much out of Keccak; (b) it's unlikely that there's an attack =
along the same general lines as currently know attacks that will work again=
st it either.
The problem - and it's an open problem for the whole field - is that none o=
f this gets at the question of whether there is some completely different k=
ind of attack that would slice right through Keccak or AES or any particula=
r algorithm, or any particular class of algorithms. If you compare the sit=
uation to that in asymmetric crypto, our asymmetric algorithms are based on=
clean, simple mathematical structures about which we can prove a great dea=
l, but that have buried within them particular problems that we believe, on=
fairly strong if hardly completely dispositive evidence, are hard. For sy=
mmetric algorithms, we pretty much *rely* on the lack of any simple mathema=
tical structure - which, in a Kolmogorov-complexity-style argument, just me=
ans there appear to be no short descriptions in tractable terms of what the=
se transformations do. For example, if you write the transformations down =
as Boolean formulas in CNF or DNF, the results are extremely large, with ir=
regular, highly inter-twined terms. Without that, various Boolean solvers =
would quickly cut them to ribbons.
In some sense, DC and related techniques say "OK, the complexity of the fun=
ction itself is high, but if I look at the differentials, I can find some p=
atterns that are simple enough to work with."
If there's an attack, it's likely to be based on something other than Boole=
an formulas written out in any form we currently work with, or anything bas=
ed on differentials. It's likely to come out of a representation entirely =
different from anything anyone has thought of. You'd need that to do key r=
ecovery; you'd also need it to embed a back door (like a sensitivity to cer=
tain input patterns). The fact that no one has found such a thing (publicl=
y, at least) doesn't mean it can't exist; we just don't know what we don't =
know. Surprising results like this have appeared before; in a sense, all o=
f mathematics is about finding simple, tractable representations that turn =
impossible problems into soluble ones.
-- Jerry
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
