Skip to main content
added 727 characters in body
Source Link
fgrieu
  • 145.5k
  • 12
  • 319
  • 611

No, preimage-resistance or/and collision-resistance do not imply the infeasibility of finding fixed points in hash functions.

For example, define $H(x)=\begin{cases}0^{256}&\text{if }x=0^{256}\\\operatorname{SHA-256}(x)&\text{otherwise.}\end{cases}$

This function is just as preimage-resistant and collision-resistant as SHA-256 is, yet it holds that $H(x)=x$ and $H(H(x))=x$ for $x=0^{256}$.

Exhibiting a preimage-resistant and collision-resistant $H$, and matching $(x,y,z)$ such that $H(y\|H(z\|x))=x$, is almost as easy and is left as an exercise to the reader.


Per comment: a good general purpose cryptographic hash function is essentially a random function, and wide, with no special case like in the above counterexamples. We have no efficient algorithm to exhibit a fixed point (if there is one, which has probability $1-1/e\approx63\%$) for such functions. Essentially, we must compute the function at $O(2^k)$ points where $k$ is the width. Therefore, there can't be a good general purpose cryptographic hash with a known fixed point. And that extends to all general purpose cryptographic hashes that I know, including those which collision-resistance or preimage-resistance is seriously broken.

No, preimage-resistance or/and collision-resistance do not imply the infeasibility of finding fixed points in hash functions.

For example, define $H(x)=\begin{cases}0^{256}&\text{if }x=0^{256}\\\operatorname{SHA-256}(x)&\text{otherwise.}\end{cases}$

This function is just as preimage-resistant and collision-resistant as SHA-256 is, yet it holds that $H(x)=x$ and $H(H(x))=x$ for $x=0^{256}$.

Exhibiting a preimage-resistant and collision-resistant $H$, and matching $(x,y,z)$ such that $H(y\|H(z\|x))=x$ is almost as easy and is left as an exercise to the reader.

No, preimage-resistance or/and collision-resistance do not imply the infeasibility of finding fixed points in hash functions.

For example, define $H(x)=\begin{cases}0^{256}&\text{if }x=0^{256}\\\operatorname{SHA-256}(x)&\text{otherwise.}\end{cases}$

This function is just as preimage-resistant and collision-resistant as SHA-256 is, yet it holds that $H(x)=x$ and $H(H(x))=x$ for $x=0^{256}$.

Exhibiting a preimage-resistant and collision-resistant $H$, and matching $(x,y,z)$ such that $H(y\|H(z\|x))=x$, is almost as easy and is left as an exercise to the reader.


Per comment: a good general purpose cryptographic hash function is essentially a random function, and wide, with no special case like in the above counterexamples. We have no efficient algorithm to exhibit a fixed point (if there is one, which has probability $1-1/e\approx63\%$) for such functions. Essentially, we must compute the function at $O(2^k)$ points where $k$ is the width. Therefore, there can't be a good general purpose cryptographic hash with a known fixed point. And that extends to all general purpose cryptographic hashes that I know, including those which collision-resistance or preimage-resistance is seriously broken.

added 22 characters in body
Source Link
Maeher
  • 7.1k
  • 1
  • 35
  • 45

No, preimage-resistance or/and collision-resistance do not imply the infeasibility of finding fixed points in hasheshash functions.

For example, define $H(x)=\begin{cases}0^{256}&\text{if }x=0^{256}\\\operatorname{SHA-256}(x)&\text{otherwise}\end{cases}$$H(x)=\begin{cases}0^{256}&\text{if }x=0^{256}\\\operatorname{SHA-256}(x)&\text{otherwise.}\end{cases}$

This function is just as preimage-resistant and collision-resistant as SHA-256 is, yet verifiesit holds that $H(x)=x$ and $H(H(x))=x$ for $x=0^{256}$.

Exhibiting a preimage-resistant and collision-resistant $H$, and matching $(x,y,z)$ such that $H(y\|H(z\|x))=x$ is almost as easy, and is left as an exercise to the reader.

No, preimage-resistance or/and collision-resistance do not imply the infeasibility of finding fixed points in hashes.

For example, define $H(x)=\begin{cases}0^{256}&\text{if }x=0^{256}\\\operatorname{SHA-256}(x)&\text{otherwise}\end{cases}$

This is just as preimage-resistant and collision-resistant as SHA-256 is, yet verifies $H(x)=x$ and $H(H(x))=x$ for $x=0^{256}$.

Exhibiting a preimage-resistant and collision-resistant $H$, and matching $(x,y,z)$ such that $H(y\|H(z\|x))=x$ is almost as easy, and is left as an exercise to the reader.

No, preimage-resistance or/and collision-resistance do not imply the infeasibility of finding fixed points in hash functions.

For example, define $H(x)=\begin{cases}0^{256}&\text{if }x=0^{256}\\\operatorname{SHA-256}(x)&\text{otherwise.}\end{cases}$

This function is just as preimage-resistant and collision-resistant as SHA-256 is, yet it holds that $H(x)=x$ and $H(H(x))=x$ for $x=0^{256}$.

Exhibiting a preimage-resistant and collision-resistant $H$, and matching $(x,y,z)$ such that $H(y\|H(z\|x))=x$ is almost as easy and is left as an exercise to the reader.

Source Link
fgrieu
  • 145.5k
  • 12
  • 319
  • 611

No, preimage-resistance or/and collision-resistance do not imply the infeasibility of finding fixed points in hashes.

For example, define $H(x)=\begin{cases}0^{256}&\text{if }x=0^{256}\\\operatorname{SHA-256}(x)&\text{otherwise}\end{cases}$

This is just as preimage-resistant and collision-resistant as SHA-256 is, yet verifies $H(x)=x$ and $H(H(x))=x$ for $x=0^{256}$.

Exhibiting a preimage-resistant and collision-resistant $H$, and matching $(x,y,z)$ such that $H(y\|H(z\|x))=x$ is almost as easy, and is left as an exercise to the reader.