5
$\begingroup$

How to construct a CRHF (collision resistant hash function) that is not a OWF (one-way function)? Not sure but I think it probably needs another CRHF?

Improve this question
$\endgroup$

4 Answers 4

Reset to default
10
$\begingroup$

It is going to be pretty hard to achieve collision resistance without one-wayness. Indeed, negation of one-wayness means that for a given output, you can find a corresponding input. So a collision is easily obtained by simply choosing a random input m, hashing it into output x, then finding a preimage m' for the obtained output x. The only way for such a method not to work is to have an output space at least as large as the input space, so that, with high probability, the input m' is identical to m. However, since hash functions have a much larger input space than output space (e.g. SHA-256 output space has size 2256, but its input space has size 218446744073709551616-1, which is substantially greater), chances are that the m' you get from leveraging the non-one-wayness will be distinct from the m you started with, and that yields a collision.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ "negation of one-wayness means that for" the output for randomly chosen input, you have non-negligible probability of finding "a corresponding input. " ​ Thus, the "only way for such a method not to work is to have" [[size of input space] divided by [size of output space]] be non-negligible. ​ (Although, when that quotient is negligible, even second-preimage resistance will imply onewayness.) ​ ​ ​ ​ $\endgroup$
    – user991
    Commented Apr 19, 2016 at 23:55
3
$\begingroup$

Thomas Pornin already explained why such a thing is not usually possible, but I would like to quote a graphic from Rogaway and Shrimpton's "Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance" (pdf):

Summary of the relationships among seven notions of hash-function security. Solid arrows represent conventional implications, dotted arrows represent provisional implications (their strength depends on the relative size of the domain and range), and the lack of an arrow represents a separation.

The dotted arrow from Collision resistance to Preimage resistance means that the implication depends on the message and hash sizes. You will find the exact notion in Theorem 7 of the paper.

Improve this answer
$\endgroup$
0
$\begingroup$

By "one way function" do you mean preimage resistant, or do you mean that the function doesn't ever reveal the input?

Assume H(x) is a collision-resistant function. Let L(x) = the last 256 bits of x. Then, let

G(x) = H(x) || L(x)

That is, G(x) is the concatenation of a collision-resistant hash of x, and the last 256 bits of x.

Now, over all possible inputs, this is almost always preimage resistant. However, for a special subset of inputs (those where all but the last 256 bits are some fixed known value), preimages are trivial to find. And for any input x, G(x) leaks the low 256 bits of the input.

Improve this answer
$\endgroup$
0
$\begingroup$

A Cryptographic hash function as described in the literature has 3 criteria:

  1. Preimage resistance: Given $H,y$, it is "hard" to find an $x$ with $H(x)=y$
  2. Second Preimage resistance: Given $H,x,$ it is hard to find $x'\neq x$ with $H(x')=H(x)$
  3. Collision resistance. It is hard to find 2 $x,y$ with $H(x)=H(y)$

The very definition used (the first 1 and the weakest!) has a notion of one-wayness.

Improve this answer
$\endgroup$

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.