Assume there is a black box, that given a cryptographic hash function , finds some and in polynomial time, such that applying , times gives :
The question is if an oracle, denoted in the text, can be used to prove if this function is not collision resistant or pre-image resistant.
We claim the following, without proof (for now):
Theorem 1: Given a random hash function and an oracle (according to the above), then a collision can be found in time if has a cycle of length .
We will spend the following sections to prove this. Let us first consider the simplest construction for which the above claim holds. We also state the following corollary.
Corollary 1: If the function in Theorem 1 does not have a cycle, then there exists an polynomial-time probabilistic algorithm which randomizes the cycle structure and solves the problem with probability 1.
By Corollary 1, an adversary cannot craft a special function that averts the result of Theorem 1.
We start off by looking how the oracle can be used to derive fixed points, i.e. elements in such that . If the oracle was to return the shortest cycle, it would immediately tells us if there is a fixpoint or not.
Let us assume the oracle instead picks a cycle at random (which is a reasonable assumption, as this is how cycle-finding algoritm works). We create an auxilliary function as follows
Or (equivalently) in Python:
def h_prime(x): if h(x) == x: # is fixpoint return x else: return x + 1
Once our new modified function is fed to the oracle, the oracle in turn will give a fix point for both and if one such exists in . More specifically, upon calling the oracle with , it will return and for some .
Obviously, no other point can be a fixpoint nor in a cycle (unless the value of wraps around and no fixpoints exist), just leading up to a fixpoint. So, the oracle can only return fixpoints and will do so if one exists.
Assuming that the function behaves randomly, then the expected number of fixpoints is As a result, we can, with high probability find at least one element that is a fixpoint. We will see that this can in fact be fixed by using randomization of the cycle structure, by composition with a random permutation.
A preimage as also easy to find. Assume that we want to find . We then construct
Any value leading to will be a 1-cycle (or fixpoint) in the . No other cycles will exist.
Clearly, the above idea can be used to find fixpoints in any function acting as a random oracle (or any cycle of length that we see fit). We will now see how to extend this idea further.
If a point leads to a fixpoint , then necessarily we have a collision . We call a second-order fixpoint (c.f. , which is a first-order fixpoint).
To include the second-order points in the result from the oracle, we simply remove the first-order fixpoints and turn the second-order fixpoints into first-order fixpoints.
def h_prime(x): if h(x) == x: # is fixpoint return x+1 elif h(x) == h(h(x)): # leads to fixpoint, so x != h(x) return x else: return x+1
Now, we can use this to determinstically find a collision. Consider an algorithm which calls the oracle with the modified function . Assume that returns . If is of second order, then we have a collision.
Obviously a first-order fixpoint is a 1-cycle. But what about -cycles? Consider the following (efficiently computable function)
How does this work? Every element that is in a -cycle will be turned into elements leading to a 1-cycle, and every element that jumps into a cycle (but is not part of it) is turned into a 1-cycle.
By setting and calling the oracle with the function , we will ultimately find a collision if admits a cycle of length up to . If the cost of computing and can be neglected, then the complexity is constant.
Evidently, the collision is between the elements and . This concludes the proof.
If no cycle exists of length (let us assume the adversary created one with special structure to thwart this attack), then it is possible to do a re-randomization of . By composition with a random permutation , we create . This will alter the cycle structure (and can be done multiple times). After finding a collision in , we can find one in as .
Output: Colliding pair
- Pick a random (efficiently computable) permutation . Let .
- Ask oracle to find a cycle in , call this . If the returned length is not 1, to go 1 (first step).
- Return collision
As a final note: If the output should have a finite image in, say, bits, then the must be taken . This is no problem, as this will not constitute a cycle if there exists at least one 1-cycle.
A simple example
What would a result like this be without a real-world example? Here is a toy example, which assumes . Hence .
from random import randint from hashlib import sha256 def h(x): return int( sha256(str(x)).hexdigest()[2:6], 16 ) def h_prime(x): # x = h^6(x) if x == h(h(h(h(h(h(x)))))): return x + 1 elif h(x) == h(h(h(h(h(h(h(x))))))): return x else: return x + 1 def oracle(h): x0 = randint(0, 256**2) tortoise = x0 hare = h(x0) while True: tortoise = h(tortoise) y = h(hare) hare = h(y) if tortoise == y or tortoise == hare: break return hare y = oracle(h_prime) x = h(h(h(h(h(h(y)))))) assert(y != x) assert(h(x) == h(y))
The decision oracle flavour
Worth noting, we can solve this problem with a weaker form of the oracle. If we have a fixed-point (or -cycle) oracle that can be asked if the function has this property and replies with yes or no, then this can be turned into the original oracle. By construction, we can keep half of the function to remain the same, while the other part is crafted so that it has no cycles. Then, by using binary search, it is possible to determine the fixed point (or -cycle).