On Oct 7, 2013, at 6:04 PM, "Philipp Gühring" <[email protected]> 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 end.
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
permutation 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 to
Shannon in the 1940's.
I will say that the Keccak analysis shows both the strength and the weakness of
the current (public) state of the art. Before differential cryptography,
pretty much everything in this area was guesswork. In the last 30-40 years
(depending on whether you want to start with IBM's unpublished knowledge 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 basic idea has
been expanded to a variety of related attacks, with very sophisticated modeling
of exactly what you can expect to get from attacks under different
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 against it either.
The problem - and it's an open problem for the whole field - is that none of
this gets at the question of whether there is some completely different kind of
attack that would slice right through Keccak or AES or any particular
algorithm, or any particular class of algorithms. If you compare the situation
to that in asymmetric crypto, our asymmetric algorithms are based on clean,
simple mathematical structures about which we can prove a great deal, but that
have buried within them particular problems that we believe, on fairly strong
if hardly completely dispositive evidence, are hard. For symmetric algorithms,
we pretty much *rely* on the lack of any simple mathematical structure - which,
in a Kolmogorov-complexity-style argument, just means there appear to be no
short descriptions in tractable terms of what these transformations do. For
example, if you write the transformations down as Boolean formulas in CNF or
DNF, the results are extremely large, with irregular, 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
function itself is high, but if I look at the differentials, I can find some
patterns that are simple enough to work with."
If there's an attack, it's likely to be based on something other than Boolean
formulas written out in any form we currently work with, or anything based 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 recovery; you'd
also need it to embed a back door (like a sensitivity to certain input
patterns). The fact that no one has found such a thing (publicly, 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 of mathematics is about
finding simple, tractable representations that turn impossible problems into
soluble ones.
-- Jerry
_______________________________________________
The cryptography mailing list
[email protected]
http://www.metzdowd.com/mailman/listinfo/cryptography
