## Comment Re:No weakness (Score 1) 300

A "perfect" cryptographic hash must meet three criteria:

a) The best herustic for determining an input which will produce the same hash as a specific target input will require as many steps on average as brute-forcing. (ie: the probability of getting a collision is the same whether you are using a programmatic solution or guessing.)

b) If inputs A, A' and A'' produce the same output, where A and A' are known, the best herustic for determining A'' will remain no better than one that brute-forces.

c) If inputs A and A' produce the same output as each other, inputs B and B' likewise produce the same output as each other, and so on for some statistically-significant number of distinct outputs, the outputs will follow a random distribution.

In other words, the apparent strength of the hash is the actual strength of the hash, no matter how much information has been obtained (either by analysis or by chance). There are two "obvious" properties which are necessary but not in themselves sufficient to produce those criteria. These properties are:

a) The change in output in relation to a given change in input will follow a random distribution.

b) Where the change in input is a fixed increment of any kind, neither the output nor the change in output nor any other order differential may be constant or cycle as a whole (though unpredictable repeats are a requirement of randomness), no matter what the period of that cycle would be.

These properties are common to almost all systems that are sensitive to initial conditions, which is why some of the more elaborate hashing schemes use well-understood chaotic systems rather than trying to mess around with the underlying cryptographic theory. If you know the system is deterministic (ie: for identical input it must produce identical output) but is non-predictable (ie: there exists no method whatsoever for figuring out the output - or even guessing the range it might fall in, other than the entire allowable range - for a given input except to perform the operation) then predicting a collision should be impossible. In practice, chaotic systems aren't the easiest of beasts to work with when you want fixed-length hashes and you want them yesterday. You could produce extremely strong cryptographic hashes chaotically if you don't mind waiting a day or two for each one.

In practice, no cryptographic hash will be totally "perfect", it can only be approximate. And the faster it needs to be, the more shortcuts you need to take, so the less perfect it can be even in theory. This is one reason there is some commentary on the SHA3 mailing list on whether speed should be as emphasized in the current test as the criteria suggest - that maybe NIST should relax that a little and get something stronger. Weaknesses in MD4, MD5 and even IPSec have been pointed out in respect to an overemphasis on speed in the past. Not sure on how far you could go with that, but the very impressive speedups achieved on the posted hashes suggests that the speed of the algorithm is a non-issue, that there are so many avenues for making the code faster that you can disregard that side of things almost entirely. At least for this contest. The better choice may well end up being the stronger choice, no matter what the relative performance of the reference implementations.