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).

  • 3
    $\begingroup$ @fgrieu I don't see how proving that helps. $\endgroup$ Jun 16 '14 at 16:48
  • $\begingroup$ Thanks I update my question because I thought about function that are compressing... $\endgroup$
    – Dingo13
    Jun 16 '14 at 22:18
  • $\begingroup$ @CodesInChaos: you are right that proving collision resistance implies second-preimage resistance won't help. $\endgroup$
    – fgrieu
    Jun 17 '14 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
    Jun 17 '14 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
    Jun 19 '14 at 5:46

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.

  • $\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
    Jun 23 '14 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
    Jun 23 '14 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
    Jun 23 '14 at 14:06

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.