Skip to main content
add paragraph
Source Link
yyyyyyy
  • 12.3k
  • 4
  • 49
  • 68

Yes. Let $H$ be a collision resistant hash function and assume that one can find a collision $(x,y)$ for $H\circ H$, that is, $x,y$$x$ and $y$ with $x\neq y$ and $H(H(x))=H(H(y))$. Consider the results $H(x)$ and $H(y)$ of applying $H$ once to both inputs. Then either

  • $H(x)=H(y)$, hence $(x,y)$ is a collision for $H$; or
  • $H(x)\neq H(y)$, hence $(H(x),H(y))$ is a collision for $H$.

Therefore, obtaining a collision for $H\circ H$ allows an attacker to derive a collision for $H$, showing the claim.


What could suffer is the output distribution of $H\circ H$ as opposed to $H$, that is, even if $H$ is uniformly distributed on the set of all bit strings $\{0,1\}^\ast$, the distribution of $H\circ H$ may be arbitrarily bad. For instance, when $H$ is not bijective on its image (which is the usual case), there are always hash values that are not in $H\circ H$'s image while others may have lots of preimages. However, this doesn't break collision resistance in the cryptographic sense, as outlined above.

Yes. Let $H$ be a collision resistant hash function and assume that one can find a collision $(x,y)$ for $H\circ H$, that is $x,y$ with $x\neq y$ and $H(H(x))=H(H(y))$. Consider the results $H(x)$ and $H(y)$ of applying $H$ once to both inputs. Then either

  • $H(x)=H(y)$, hence $(x,y)$ is a collision for $H$; or
  • $H(x)\neq H(y)$, hence $(H(x),H(y))$ is a collision for $H$.

Therefore, obtaining a collision for $H\circ H$ allows an attacker to derive a collision for $H$, showing the claim.

Yes. Let $H$ be a collision resistant hash function and assume that one can find a collision $(x,y)$ for $H\circ H$, that is, $x$ and $y$ with $x\neq y$ and $H(H(x))=H(H(y))$. Consider the results $H(x)$ and $H(y)$ of applying $H$ once to both inputs. Then either

  • $H(x)=H(y)$, hence $(x,y)$ is a collision for $H$; or
  • $H(x)\neq H(y)$, hence $(H(x),H(y))$ is a collision for $H$.

Therefore, obtaining a collision for $H\circ H$ allows an attacker to derive a collision for $H$, showing the claim.


What could suffer is the output distribution of $H\circ H$ as opposed to $H$, that is, even if $H$ is uniformly distributed on the set of all bit strings $\{0,1\}^\ast$, the distribution of $H\circ H$ may be arbitrarily bad. For instance, when $H$ is not bijective on its image (which is the usual case), there are always hash values that are not in $H\circ H$'s image while others may have lots of preimages. However, this doesn't break collision resistance in the cryptographic sense, as outlined above.

clarified assumption
Source Link
yyyyyyy
  • 12.3k
  • 4
  • 49
  • 68

Yes. Let $H$ be a collision resistant hash function and assume that one can find a collision $(x,y)$ for $H\circ H$, that is $x,y$ with $x\neq y$ and $H(H(x))=H(H(y))$. Consider the results $H(x)$ and $H(y)$ of applying $H$ once to both inputs. Then either

  • $H(x)=H(y)$, hence $(x,y)$ is a collision for $H$; or
  • $H(x)\neq H(y)$, hence $(H(x),H(y))$ is a collision for $H$.

Therefore, obtaining a collision for $H\circ H$ allows an attacker to derive a collision for $H$, showing the claim.

Yes. Let $H$ be a hash function and assume that one can find a collision $(x,y)$ for $H\circ H$, that is $x,y$ with $x\neq y$ and $H(H(x))=H(H(y))$. Consider the results $H(x)$ and $H(y)$ of applying $H$ once to both inputs. Then either

  • $H(x)=H(y)$, hence $(x,y)$ is a collision for $H$; or
  • $H(x)\neq H(y)$, hence $(H(x),H(y))$ is a collision for $H$.

Therefore, obtaining a collision for $H\circ H$ allows an attacker to derive a collision for $H$, showing the claim.

Yes. Let $H$ be a collision resistant hash function and assume that one can find a collision $(x,y)$ for $H\circ H$, that is $x,y$ with $x\neq y$ and $H(H(x))=H(H(y))$. Consider the results $H(x)$ and $H(y)$ of applying $H$ once to both inputs. Then either

  • $H(x)=H(y)$, hence $(x,y)$ is a collision for $H$; or
  • $H(x)\neq H(y)$, hence $(H(x),H(y))$ is a collision for $H$.

Therefore, obtaining a collision for $H\circ H$ allows an attacker to derive a collision for $H$, showing the claim.

Source Link
yyyyyyy
  • 12.3k
  • 4
  • 49
  • 68

Yes. Let $H$ be a hash function and assume that one can find a collision $(x,y)$ for $H\circ H$, that is $x,y$ with $x\neq y$ and $H(H(x))=H(H(y))$. Consider the results $H(x)$ and $H(y)$ of applying $H$ once to both inputs. Then either

  • $H(x)=H(y)$, hence $(x,y)$ is a collision for $H$; or
  • $H(x)\neq H(y)$, hence $(H(x),H(y))$ is a collision for $H$.

Therefore, obtaining a collision for $H\circ H$ allows an attacker to derive a collision for $H$, showing the claim.