Consider the naive hash function:
HASH = INPUT % 4. This function is periodic in the sense that if we call it with sequential numbers
0, 1, 2, 3, 4, 5, ... the produced hashed sequence will have periodicity of four:
0, 1, 2, 3, 0, 1, 2, 3, 0, ....
My question is whether modern cryptographic hash functions, such as SHA256, are periodic in this sense? In other words, are there some integers
0 <= n and
0 < k such that
HASH(n + b) = HASH(n + b + ak) for all integers
[0, k - 1] and all positive integers
a? For example, will the sequence
SHA256(0), SHA256(1), SHA256(2), SHA256(3), ... be periodic after some point?
One of the purposes of Hash function is, of course, to make collisions unlikely (both of the deliberate and undeliberate kind). With periodicity this would be broken. However, to avoid collisions in practice, we only need that
k are (very) large and unknown. Has it been proven that no
(This question was previously asked on Stack Overflow.)