CODEWITHSUNDEEP
hashsha
Fredrik Savje
Fredrik Savje

Reputation: 565

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 <= 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?

Upvotes: 1

Views: 216

Answers (2)

Eduardo Ro&#231;adas
Eduardo Ro&#231;adas

Reputation: 1

While hash functions are not periodical in the mathematical sense it is possible to create and manipulate hash behaviors in order to predict what values the hash will follow like truncating it. This is where Floyd’s cycle-finding (rho) algorithm comes in. By repeatedly hashing a value with the same hash you will eventually create a cycle with a period around square root of n of the size of the hash. What happens with current hashes is that they are too big and these calculations take too much time to be found, they are infeasible. So SHA(1) SHA(2) etc. wont be periodical but u can indeed find that mentioned periodicity if u did SHA(fn), SHA(SHA(fn) etc.

Upvotes: 0

starmole
starmole

Reputation: 5068

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.

Upvotes: 1

Related Questions