5
$\begingroup$

Are there functions that satisfy the second-preimage resistance property without satisfying the others (preimage and collision resistance) ?

I'm looking about such functions that compress data (exit the identity function).

$\endgroup$
9
  • 3
    $\begingroup$ @fgrieu I don't see how proving that helps. $\endgroup$ Commented Jun 16, 2014 at 16:48
  • $\begingroup$ Thanks I update my question because I thought about function that are compressing... $\endgroup$
    – Dingo13
    Commented Jun 16, 2014 at 22:18
  • $\begingroup$ @CodesInChaos: you are right that proving collision resistance implies second-preimage resistance won't help. $\endgroup$
    – fgrieu
    Commented Jun 17, 2014 at 6:52
  • 1
    $\begingroup$ Hint: assume a compressing function that satisfies all three properties; tweak it by changing the image of a single element to break collision resistance. $\endgroup$
    – fgrieu
    Commented Jun 17, 2014 at 6:54
  • $\begingroup$ Such functions exist ? I've seen universal one way hash functions, but this one satisfy one-wayness, a property that I don't need. $\endgroup$
    – Dingo13
    Commented Jun 19, 2014 at 5:46

1 Answer 1

7
$\begingroup$

Take a function $H:\mathbb S\to\{0,1\}^k$ where $\mathbb S$ is a large finite subset of $\{0,1\}^*$, such that $H$ "compress data" [however this is defined], and $H$ is [conjectured] collision-resistant [thus second-preimage-resistant] and first-preimage-resistant; e.g., SHA-512, for $k=512$. Let $«0»$ and $«1»$ be two public distinct elements of $\mathbb S$. Define $H':\mathbb S\to\{0,1\}^k$ by $$H'(M)= \begin{cases}H(«1»)&\text{if }M\text{ is }«0»\\H(M)&\text{otherwise}\end{cases}$$

This $H'$ is compressing, and not collision-resistant [argument: $H'(«0»)=H'(«1»)$]. However $H'$ remains preimage-resistant, both first and second [argument: preimage resistance is defined for random message, thus the minor change we made to $H$ in order to build $H'$ does not matter, for odds that a random choice of message hits $«0»$ or $«1»$ are negligible].

Hence $H'$ is second-preimage resistant, but not collision resistant. Which answers the question by the affirmative [I'm reading "without satisfying the others" as "not (satisfying the others)"].

Note: I conjecture without proof that the answer is negative when reading "without satisfying any of the others".


Informal definitions: a function $F$ is

  • collision-resistant when a [computationally bounded] adversary can't exhibit any $(a,b)$ with $a\ne b$ and $F(a)=F(b)$;
  • first-preimage-resistant when, given $f$ determined as $F(a)$ for an unknown random $a$, a [computationally bounded] adversary can't [with sizable odds] exhibit any $b$ with $F(b)=f$;
  • second-preimage-resistant when, given a random $a$, a [computationally bounded] adversary can't [with sizable odds] exhibit any $b$ with $a\ne b$ and $F(a)=F(b)$.

Note: these definitions are a compromise between simplicity and precision, but lacking about what random $a$, sizable odds and computationally bounded means. However they can be made formal by making $F$ a parameterized function family; and adding some appropriate parameterized upper bound for the size of that random $a$ when the input domain $\mathbb S$ is unbounded.

$\endgroup$
3
  • $\begingroup$ @otus: yes, $H′(0)=H′(1)$ imply $H'$ isn't collision resistant; that's because from the definition of $H'$ we know a particular $(a,b)$ [that is, $(0,1)$] such that $a\ne b$ and $F(a)=F(b)$. We assume the adversary knows this definition too, and is at least as smart as we are. $\endgroup$
    – fgrieu
    Commented Jun 23, 2014 at 5:36
  • $\begingroup$ The definition of collision resistance means "find two values, which result in the same hash". If such a value is already baked in the definition of the function, collision resistance is broken. Additionally, the (small) difference between first and second preimage resistance becomes clear when you look for the $a\neq b$ statement, although in real functions are considered pretty much the same. But for example the identity function is collision resistant and second preimage resistant but not first preimage resistant. $\endgroup$
    – tylo
    Commented Jun 23, 2014 at 12:55
  • $\begingroup$ My point was that there's a reason rigorous definitions of collision resistance consider families of hash functions. However, with your added definitions your proof is clearly correct, so I've removed the comment. $\endgroup$
    – otus
    Commented Jun 23, 2014 at 14:06

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.