3
$\begingroup$

For any SHA-family of algorithms (including Keccak) except for SHA1, would it be theoretically possible for there to exist a pre-image a whose hash digest b is the pre-image to the hash digest c which is the pre-image to a thus completing a circle (i.e. circular hash or collision of pre-image a with the digest a)?

${{hash(A)\to B}}$, ${{hash(B)\to C}}$ , ${{hash(C)\to A}}$

Given the use of XOR and bit-rotations, as well as padding and pre-processing and the many steps involved in hash functions such as SHA256 or SHA512, would it be possible for the above circular hash scenario to exist? (despite the unlikelihood of it being found)

P.S. candidate values include an all-zero string for pre-image or digest, or any valid-length output (i.e. 256, 512).

$\endgroup$
8

1 Answer 1

4
$\begingroup$

We like to think of hash functions as random functions, and there is no reason a random function shouldn't have a cycle of size 3 which is what you describe. Obviously it would be very difficult to find such a cycle, we can discuss how likely is it a random function over space size $n$ has a cycle of size 3.

Ignoring cycles of size 1 and 2 which acount for a small portion of the space we have $n/3$ independent size 3 prefixes. each of these has probability $1/n$ to close a size 3 cycle. the chance they all miss is $(1-1/n)^{(n/3)}$ which is $(1/e)^{(1/3)}$ or 0.71653131057. so the chance of at least 1 such cycle is 28% which is consistent with simulation results in comments above by poncho.

$\endgroup$
1
  • $\begingroup$ My hand wavy answer was wrong, this is a better one $\endgroup$
    – Meir Maor
    Commented Aug 10, 2019 at 4:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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