Circular hash collision where digest is pre-image: Could hash(a) = b, hash(b)=c, then hash(c)=a?

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

• – Gilles 'SO- stop being evil' Aug 9 at 16:11
• A quick simulation indicates that a random function has an approximately 0.283 probability of having a cycle of length precisely 3... – poncho Aug 9 at 16:29
• @Gilles thanks for those related references, I hadn't seen them. Not sure if this answer would be applicable to SHA in terms of the Rho structure mentioned: security.stackexchange.com/a/10661/213344 – Steven Hatzakis Aug 9 at 17:16
• @poncho does that would mean there could be many such collisions at length 3? – Steven Hatzakis Aug 9 at 17:18
• @StevenHatzakis: potentially, yes. However, it would seem to me that the probability of there being a large number of such cycles would likely be small... – poncho Aug 9 at 18:42

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.

• My hand wavy answer was wrong, this is a better one – Meir Maor Aug 10 at 4:05