[Cryptography] Sha3

[Jerry Leichter]

On Oct 7, 2013, at 6:04 PM, "Philipp Gühring" <pg at 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 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