If I feed the output of H back into H will it cover the entire output space of H before repeating?
Consider the following scenario:
A=1;
While(){
A=H(A);
print(A)
}
Will there be short cycles? E.g. Are there values of A that H(A) = A (a cycle of 1) Values of A where H(A) = B and H(B) = A (cycle of 2)
Is there a way to prove that either no such cycles exist for a given hash, or to put a lower bound on the shortest cycle.
Douglas Hofstadter in one of his books (Either "The Mind's I", or "Metamathematical Themas" I think) has a sentence
This sentence has one 'a', one 'b', ...
The problem is to find the values that make it true. If you just count the current crop, and correct the sentence, and repeat, the sentence converges on a true statement fairly quickly.
So how does this connect to cryptography.
I suspect, but haven't demonstrated, that the 'strange attractor' above is fairly arbitrary.
{Entire text of War and Peace} This statement has...
will also converge on a correct statement.
Consider a hash, H. Suppose that there are short cycles of H. Will there also be cycles of (D+H) where D is an arbitrary chunk of data. Will these be the same length? (I don't see a good reason why they should be)
If an appreciable fraction of hashes are members of a short cycle (for some value of short: 1 million? 1 billion?) then the following vulnerability exists:
Take file D.
- Modify D to suit your purposes. Part of this process should be to shorten by length(hash value) Call this file D'
+ stands or concatenate
- Compute A = H(D)
- Compute A2 = H(A+D')
- Compute A3 = H(A2+D')
If A is cyclic you will eventually reach some A_n whose next iteration produces A.
- Replace file D with A_n+D'
In terms of security we need to know what the probability of a given A being cyclic in reasonable time. Of course reasonable depends on how important the document is. But if you can show that there is a vanishingly small probability to find a cycle under 10^15 or so, then this sort of attack isn't practical. If there is a 2% chance of a given hash being cyclic in under a million iterations, there is a potential problem.