2
$\begingroup$

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?

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.)

$\endgroup$
  • $\begingroup$ Related are the notion of hash cycles. Those are known to exist, it is just that the cycles (where $H^n(m) = m$) are very large, which is not surprising giving the size of the output alone. Note that 256 bits is a digit followed by about 75 other digits (!). Storing some $2^{128}$ hashes to see if something repeats is a bit of an issue. $\endgroup$ – Maarten Bodewes Sep 22 '16 at 18:01
  • $\begingroup$ There is no SHA hash that directly takes a number as input, you'd first have to encode it into a bit or byte string before the hash function can accept it as input. $\endgroup$ – Maarten Bodewes Sep 22 '16 at 18:03
  • $\begingroup$ There are estimates how long it will take you on average to hit a cycle and how long the cycle will be with random functions. Now the question would be: Can the SHA functions actually be modeled as random functions for this... $\endgroup$ – SEJPM Sep 22 '16 at 18:13
  • $\begingroup$ @SEJPM Good point, you might hit a cycle earlier if it's not a random function. I expect that proof may take a while, but without for now the current state of crypto-analysis will have to do... $\endgroup$ – Maarten Bodewes Sep 22 '16 at 18:30
  • 2
    $\begingroup$ @Gilles: The question you linked to is about cycles in the sequence $x_i = \text{SHA-256}(x_{i-1})$, whereas this one is about the sequence $x_i = \text{SHA-256}(i)$. See this clarifying comment by the OP. $\endgroup$ – Ilmari Karonen Sep 24 '16 at 14:41
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you! However, I suspect that you might have misunderstood me. Reading in the handbook you linked to, I understand that the cycle length is defined as cycles/periodicity in the sequence of functional powers for a certain input. I.e., the sequence SHA(x), SHA(SHA(x)), SHA(SHA(SHA(x))), .... Because of a finite range of the hash function, some n and k must exists for every x (but, as you note, they're usually very large). However, I don't see how that implies the same for the sequence I'm interested in. If it's implied, could you perhaps explain it? Thanks! $\endgroup$ – Fredrik Savje Sep 22 '16 at 22:16
1
$\begingroup$

They shouldn't have. If they do, they are fundamentally flawed, and would never be used.

For cryptographically secure hashes, when working through sequential input, each new number will increase the statistical chance of a collision by an amount proportional to the number of terms so far.

If this were not the case, it would be trivial to construct hash collisions. Hash collisions - just add the period, and the hash (and therefore, the signature which is based on the hash) will be the same.

For example, using your naive hash, if you sign a document saying you would give me "3" dollars, then I could "prove" that you signed a document saying you owe me "7" dollars, or "11" dollars, or "1,000,003" dollars. All I would have to know is the period of the hash.

$\endgroup$
  • $\begingroup$ Thank you AMADANON. You are, of course, right: if the periodicity was known and quite short, it would be trivial to construct collisions. However, let's say that the period is some number greater than 10^(10^100) -- a number with more digits than atoms in the universe -- the hash function would be periodic but not in a way that can be exploited. My question is whether it's proven that even unexploitable periodicity doesn't exists. $\endgroup$ – Fredrik Savje Sep 23 '16 at 0:58
  • $\begingroup$ Since sha256 (as all practical hashes) is block based, the periodicity can never exceed the length of the internal state + the length of one block. I'm pretty sure that for sha256, this is 256 + 256 bits, or about 150 digits. $\endgroup$ – AMADANON Inc. Sep 26 '16 at 22:26
  • $\begingroup$ Are you sure this is true? You're right, of course, that the input is broken up into blocks, but the internal state is accumulating the effect of all previous blocks. Thus, even if the input is processed in fixed-sized chunks, the output still depends on the complete input. Don't really see how your conclusion follows. Besides, a periodicity of 512 bits corresponds to 64 ASCII characters; it would be trivial to construct collisions. $\endgroup$ – Fredrik Savje Sep 27 '16 at 7:05
  • $\begingroup$ The total number of calculable output blocks cannot exceed (length of state + length of 1 block) - if it doesn't repeat within this period, it definitely won't repeat. In fact, if it repeats, it must repeat a factor of this number. If it repeats (consistently), then it must either go through each possibility once, or there are 2 chains with half of the possibilities each, or 3 chains with 1/3 each (not possible for sha, as the hashspace is not divisible by 3!), or 4 chains with 1/4 each.... $\endgroup$ – AMADANON Inc. Oct 13 '16 at 21:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.