4
$\begingroup$

Warning: Possibly ill-posed question.

I'm using the following definition from a recent paper available here. I believe their terminology is slightly different but reproduce my understanding of it here.

The concept of a 2 to 1 trapdoor collision free function satisfies the following properties. For every $y$ such that $f(x) = y$, there exists $f(x') = y$ and $x\neq x'$. If one has access to the trapdoor, it is easy to find $(x,x')$ for any $y$ and it is otherwise computationally hard.

In a recent talk posted online, the authors talk about information theoretic generalizations to this but give no further details. The obvious obstacle is that a computationally unbounded attacker can try all possible inputs to $f$ and eventually know the collisions. My guess is that somehow, $f$ is given in an obfuscated way so that the attacker cannot know of collisions. Is something like this possible at all and how might one achieve this?

$\endgroup$
  • 2
    $\begingroup$ Should it be $x\neq x'$ instead of $x\neq x$? $\endgroup$ – Martin Rosenau Dec 4 '18 at 11:54
0
$\begingroup$

Any fixed function $f\colon A \to B$ of a finite domain $A$ is guaranteed to have collisions if the range $B$ has fewer elements than $A$, so there always exists a random algorithm $C()$ which returns a collision: the algorithm that just returns one of the collisions. We just don't know how to find $C$ for functions like SHA-256 (although we do for MD5 and SHA-1!). This is why the notion of ‘collision resistance’ as applied to fixed hash functions like SHA-256 doesn't even have a formal definition, although there are attempts to formalize this elusive issue of human ignorance[1][2].

We might consider a probabilistic, or ‘information-theoretic’, model: a random function $f\colon A \to B$ drawn with uniform distribution from all functions from $A$ to $B$. Any random algorithm $C(f)$ to find a collision is limited to birthday attacks that make $O(\sqrt{|B|})$ calls to $f$ to attain nonnegligible probability of success.*

Of course, choosing a function uniformly at random takes a lot of bits: in general, you need storage for a table of $|B|^{|A|}$ entries if you want to be able to specify all of them. We might pick a smaller family of functions $f_k\colon A \to B$ with a short key $k$, and consider separately the adversary's knowledge about the key:

  • If the adversary never knows the key (and, of course, can't learn anything about it from side channels like time of hash table operations), there are many cheaply computed functions to choose from that have ‘information-theoretically’ guaranteed bounded collision probabilities called universal hash families—that is, for any $x$ and $y$, $\Pr[f_k(x) = f_k(y)] \leq \varepsilon$ for some small $\varepsilon$. This is a theorem that is easily proven for many cases like GHASH or Poly1305. See [3] for more related notions and references.

  • If the adversary doesn't know the key in advance, Rogaway and Shrimpton gave the standard formal definition[4] of the notion of collision resistance of the family $f_k$ in terms of the best cost of a random algorithm $C(k)$ to find a collision in $f_k$ (or, more specifically, the best success probability of a cost-limited algorithm in terms of the cost). Families that we conjecture to be collision-resistant in this formal sense include HMAC-SHA256 and keyed BLAKE2b.

Obviously, for each $k$, there is a collision as long as $|B| < |A|$, but even if we had a precomputation oracle to find them all for us in advance, there is an extremely high cost to storing a table mapping every value of $k$ to a collision in $f_k$, and we assume the adversary probably can't afford $2^{128}$ bytes of RAM or even ROM to store it all. Functions like HMAC-SHA256 and BLAKE2b seem to exhibit this notion of collision resistance, but proving any theorems about it seems difficult. In contrast, functions like Poly1305 are easily proven to have low collision probabilities.

What about trapdoor functions like $m \mapsto x^m \bmod n$ where $n = pq$ for secret factors $n$? Anyone who can find collisions in this function can factor $n$, so as long as factoring $n$ is hard—and until whoever knows $p$ and $q$ publishes a single collision!—it seems difficult to find collisions. But as above, the domain and range are finite, and if $n$ is limited to a particular size then the space of these functions is finite too. So there's no way you can guarantee a finite but cost-unlimited attacker has a limited probability of finding collisions.

I don't know what the authors might have meant by an information-theoretic generalization to this—you'll have to ask them. Incidentally, the paper seems to be discussing claw-free function pairs $f_0$ and $f_1$ for which it is difficult to find $x_0$ and $x_1$ with $f_0(x_0) = f_1(x_1)$, not collision-resistant functions $f$ for which it is difficult to find $x_0 \ne x_1$ with $f(x_0) = f(x_1)$.


* You could naively make a table of results so far and check it for collisions each time you call $f$, but that costs $O(\sqrt{|B|})$ time and $O(\sqrt{|B|})$ space for a total area*time cost (which is a proxy for rubles or ergs) of $O(|B|)$. In contrast, it takes about the same number of calls to $f$, and only constant memory, to use van Oorschot and Wiener's collision search algorithm[5], which can also be parallelized to speed it up with higher power consumption. It doesn't even seem to help to have a quantum computer that can evaluate superpositions of $f$[6].

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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