Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

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

1 Answer 1

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.

share|improve this answer
    
@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. –  fgrieu Jun 23 at 5:36
    
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. –  tylo Jun 23 at 12:55
    
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. –  otus Jun 23 at 14:06
    
Thank you very much for all your explanations fgrieu –  Dingo13 Jun 27 at 15:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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