Periodicity of hash functions 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 &lt;= n and 0 &lt; 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?

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 n and/or k are (very) large and unknown. Has it been proven that no n and k exists?

(This question was previously asked on Stack Overflow.)
What you're actually looking for is called the cycle length most of the time in cryptography.

For a random mapping $f:\{1,2,\ldots,k\} \rightarrow \{1,2,\ldots,k\}$ the cycle length is expected to be $\sqrt{\pi k/8}$ and the tail length is expected to be the same.
If you want more details and some fancy illustrations, the Handbook of Applied Cryptography (PDF) has them.

If you model a cryptographic hash function as a random mapping (which you do most of the time), then you'd expect a cycle length of $\sqrt{\pi 2^n / 8}=\sqrt{\pi}\cdot 2^{\frac{n-3}{2}}$ which is $\approx 2^{127.325748064736}$ for $n=256$, which is the case for SHA-256.

So the TL;DR is:
No it has not been proven that no such $n,k$ exist, but chances are that they exist and range in the area of the values I showed above, which are of no practical relevance as of today.