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 b
in [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?
Absolutely not. If that was the case it would be trivial to find a collision. The strength of a cryptographic hash function is defined by how hard it is to find Hash(a) == Hash(b). Ideally you need to find all values of Hash(b) to find a collision, which is infeasible if Hash is a lot of bits.