1
$\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$
7
  • $\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
  • 1
    $\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
  • 3
    $\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
  • 1
    $\begingroup$ Thank you @fgrieu for expressing your concerns about an inquiry I had five years ago. I would like to point out that SHA-256 was used as an example, and my question was about hash functions in general. I agree that there are several mappings between bitstrings and integers, but it appears that all other people engaging with this topic understood which one was intended (hint: en.wikipedia.org/wiki/Binary_number ). And you may pick your favorite endianness. With respect to your last point, you may restrict your focus to the finite sequence enumerating the full domain. $\endgroup$ – Fredrik Savje Mar 10 at 23:34
3
$\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$
1
  • 1
    $\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
2
$\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$
4
  • $\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
0
$\begingroup$

I'll reformulate the question in light of recent addition. It asks: are modern cryptographic hash functions applied to consecutive integers periodical?. Let's assume agreement on how we hash an integer, even though two practitioners asked the common method will come with 10 different¹.

An answer argues that no, on the ground that for a hash function as in the question, $\operatorname{Hash}(n)=\operatorname{Hash}(n+k)$ with $0<k$, which is a collision, and goes against one of the design property of cryptographic hashes since their inception: collision-resistance. But, as the OP rightly commented, that reasoning falls short: a period could exist but be so large that it can't be found.

That same no conclusion can be reached by another line of reasoning: a modern hash attempts to be, and is often modeled as, a random function from $\{0,1\}^*$ (the set of finite bitstrings, which is infinite) to $\{0,1\}^h$ (the set of $h$-bit bistrings). Under that model, regardless of the mapping of integer to bitstring, the series of outputs of the hash with input the consecutive integers is a set of random bitsrings in $\{0,1\}^h$. It can be rigorously defined and computed the probability that such series is periodic, and that's zero².

But SHA-256 falls short of the above model: there are "only" $2^{(2^{64})}-1$ valid inputs to SHA-256, thus no matter how we uniquely map integers to bitstrings, the series has a finite number of terms $t$, with $t<2^{64}$. Hence the "all positive integers $a$" in the question must be somewhat restricted so that $\operatorname{SHA-256}(n+b+a\,k)$ remains well defined. And when we make that restriction, yes the condition stated in the question is met: $n=t-1$, $k=1$ (allowing only $b=0$) match it, for there remains no valid value of $a$ to contradict periodicity.

But SHA-256 was intended only as example, and SHA-3 also qualifies as a modern hash. AFAIK it's input set is $\{0,1\}^*$, thus the above argument fails; and SHA-3 is deterministic, processes it's input sequentially by finite blocks and has a finite state, invalidating the random function model. This reopens the question. I believe it's not periodical for any natural mapping of integers to bitstring, including if we stretch that to use base $2^b$ where $b$ is the input block size, and special-case the last block to make it constant; but I have no proof.


¹ I'm not joking about the 10 kinds of people: those who understand binary, and the others. I'm considering:

  • bases, with 2, 10, 16, 64, 256 (raw bytes), 232, or 264 the most common;
  • endianness, which can be big, little, or blended in a variety of ways;
  • and worse, standards (obligatory XKCD). One of several common in crypto is ASN.1 DER, which codes the integer 0 as the three bytes 02 01 00, $2^{1015}-1$ as 129 bytes, and the next integer with two extra bytes ($2^{1015}$ is coded as 131 bytes).

² Sketch: for any periodicity defined by $k$ and the minimum $n$, each additional value starting $n+2k$ only has probability $2^{-h}$ to match the periodicity. If we analytically compute the probability of that property after $x$ terms, and sum these over all the $k,n$ meaningful for $x$ terms, what we obtain goes to zero when $x$ goes to infinity.

$\endgroup$
-1
$\begingroup$

statrting with any and every hash , iterated rehash of hash must end in a cycle . It may be 2^256 long but it must end in a cycle. short cycles are very valuable as they may make bitcoin mining easy. each indiviual part of the hash algorithm may have its own cycle, predicting a cycle length for the amalgam of all the parts, likely around the product of all the cycle lengths for all the parts.

$\endgroup$
1
  • 2
    $\begingroup$ The question wasn't about iterated hashing; instead, it was about hashing a series of values (and in which the values happened to be incrementing). $\endgroup$ – poncho Mar 9 at 22:28

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.