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.
Fixed points
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.
Random oracles
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
.
Algorithm 1:
Input: function
Output: Colliding pair
- Pick a random (efficiently computable) permutation
. Let
.
- Construct
- 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).