Skip to main content
deleted 693 characters in body
Source Link
ambiso
  • 706
  • 4
  • 13

Your proof starts with the correct approach, but $h_1$ is not collision-resistant (CR), and therefore your proof should give you a hint as to why it's not CR.

Counterexample

Take a random distinct $w_0, z_0$ and compute $w_1 = h(w_0 \| w_0)$ and $z_1 = h(z_0 \| z_0)$.

Additionally take arbitrary $x_3, x_4$.

Then $(x^a = (w_1, z_0, x_3, x_4), x^b = (z_1, w_0, x_3, x_4))$ is a collisionEdit:

\begin{align*} &h_1(x^a) \\ =& h((x_1 \oplus h(x_2 || x_2))\ ||\ (h(x_3 || x_3) \oplus x_4))\\ =& h((w_1 \oplus h(z_0 || z_0))\ ||\ (h(x_3 || x_3) \oplus x_4))\\ =& h((w_1 \oplus z_1)\ ||\ (h(x_3 || x_3) \oplus x_4))\\ \end{align*}

and

\begin{align*} &h_1(x^b) \\ =& h((x_1 \oplus h(x_2 || x_2))\ ||\ (h(x_3 || x_3) \oplus x_4))\\ =& h((z_1 \oplus h(w_0 || w_0))\ ||\ (h(x_3 || x_3) \oplus x_4))\\ =& h((z_1 \oplus w_1)\ ||\ (h(x_3 || x_3) \oplus x_4))\\ =& h((w_1 \oplus z_1)\ ||\ (h(x_3 || x_3) \oplus x_4))\\ =& h_1(x^1)\\ \end{align*} I have removed the counterexample, since it should be easy to figure out using the proof attempt below.

Attempt to prove

You want to prove that:

If $h$ is CR, then $h_1$ is CR.

We prove the contraposition of that statement:

If there exists an adversary $\mathcal{A}^{h_1}$ breaking $h_1$, then there exists an adversary $\mathcal{A}^{h}$ breaking $h$.

We want to assume the existence of $\mathcal{A}^{h_1}$ and use it to construct $\mathcal{A}^{h}$.

$\mathcal{A}^{h}$ is playing the CR game, and is supposed to output a collision for $h$. To achieve that, we let $\mathcal{A}^{h_1}$ run. Since by assumption $\mathcal{A}^{h_1}$ has a non-negligible probability of succeeding, it will output a collision of $h_1$ with non-neglibile probability, i.e. a $x^a \neq x^b$ such that $h_1(x^a) = h_1(x^b)$.

We now want to win the CR game against $h$ and construct a collision for $h$ from $x^a$, $x^b$.

We know that $h_1(x^a) = h_1(x^b)$, and $x^a \neq x^b$. Therefore, using your $g(\cdot)$, $h(g(x^a)) = h(g(x^b))$.

There are two cases here:

1. Either: $g(x^a) \neq g(x^b)$

then we immediately find a collision: since $h(g(x^a)) = h(g(x^b))$ and $g(x^a) \neq g(x^b)$, the pair $(g(x^a), g(x^b))$ is a collision for $h$.

2. Or not: $g(x^a) = g(x^b)$

then we have to look further for a collision. by $g(x^a) = g(x^b)$ we know that

$\underbrace{(x^a_1 \oplus h(x^a_2 || x^a_2))}_\text{first part}\ ||\ (h(x^a_3 || x^a_3) \oplus x^a_4) = (x^b_1 \oplus h(x^b_2 || x^b_2))\ ||\ (h(x^b_3 || x^b_3) \oplus x^b_4)$.

By $x^a \neq x^b$ we know that at least one of these 4 cases must hold:

2.1. $x^a_1 \neq x^b_1$

By $g(x^a) = g(x^b)$, the first part of the input of the outer $h$ must be equal:

$x^a_1 \oplus h(x^a_2 || x^a_2) = x^b_1 \oplus h(x^b_2 || x^b_2)$.

This is where the proof breaks down. You cannot construct a collision from this.

2.2. $x^a_2 \neq x^b_2$

2.3. $x^a_3 \neq x^b_3$

2.4. $x^a_4 \neq x^b_4$

Hope I could help!

Your proof starts with the correct approach, but $h_1$ is not collision-resistant (CR), and therefore your proof should give you a hint as to why it's not CR.

Counterexample

Take a random distinct $w_0, z_0$ and compute $w_1 = h(w_0 \| w_0)$ and $z_1 = h(z_0 \| z_0)$.

Additionally take arbitrary $x_3, x_4$.

Then $(x^a = (w_1, z_0, x_3, x_4), x^b = (z_1, w_0, x_3, x_4))$ is a collision:

\begin{align*} &h_1(x^a) \\ =& h((x_1 \oplus h(x_2 || x_2))\ ||\ (h(x_3 || x_3) \oplus x_4))\\ =& h((w_1 \oplus h(z_0 || z_0))\ ||\ (h(x_3 || x_3) \oplus x_4))\\ =& h((w_1 \oplus z_1)\ ||\ (h(x_3 || x_3) \oplus x_4))\\ \end{align*}

and

\begin{align*} &h_1(x^b) \\ =& h((x_1 \oplus h(x_2 || x_2))\ ||\ (h(x_3 || x_3) \oplus x_4))\\ =& h((z_1 \oplus h(w_0 || w_0))\ ||\ (h(x_3 || x_3) \oplus x_4))\\ =& h((z_1 \oplus w_1)\ ||\ (h(x_3 || x_3) \oplus x_4))\\ =& h((w_1 \oplus z_1)\ ||\ (h(x_3 || x_3) \oplus x_4))\\ =& h_1(x^1)\\ \end{align*}

Attempt to prove

You want to prove that:

If $h$ is CR, then $h_1$ is CR.

We prove the contraposition of that statement:

If there exists an adversary $\mathcal{A}^{h_1}$ breaking $h_1$, then there exists an adversary $\mathcal{A}^{h}$ breaking $h$.

We want to assume the existence of $\mathcal{A}^{h_1}$ and use it to construct $\mathcal{A}^{h}$.

$\mathcal{A}^{h}$ is playing the CR game, and is supposed to output a collision for $h$. To achieve that, we let $\mathcal{A}^{h_1}$ run. Since by assumption $\mathcal{A}^{h_1}$ has a non-negligible probability of succeeding, it will output a collision of $h_1$ with non-neglibile probability, i.e. a $x^a \neq x^b$ such that $h_1(x^a) = h_1(x^b)$.

We now want to win the CR game against $h$ and construct a collision for $h$ from $x^a$, $x^b$.

We know that $h_1(x^a) = h_1(x^b)$, and $x^a \neq x^b$. Therefore, using your $g(\cdot)$, $h(g(x^a)) = h(g(x^b))$.

There are two cases here:

1. Either: $g(x^a) \neq g(x^b)$

then we immediately find a collision: since $h(g(x^a)) = h(g(x^b))$ and $g(x^a) \neq g(x^b)$, the pair $(g(x^a), g(x^b))$ is a collision for $h$.

2. Or not: $g(x^a) = g(x^b)$

then we have to look further for a collision. by $g(x^a) = g(x^b)$ we know that

$\underbrace{(x^a_1 \oplus h(x^a_2 || x^a_2))}_\text{first part}\ ||\ (h(x^a_3 || x^a_3) \oplus x^a_4) = (x^b_1 \oplus h(x^b_2 || x^b_2))\ ||\ (h(x^b_3 || x^b_3) \oplus x^b_4)$.

By $x^a \neq x^b$ we know that at least one of these 4 cases must hold:

2.1. $x^a_1 \neq x^b_1$

By $g(x^a) = g(x^b)$, the first part of the input of the outer $h$ must be equal:

$x^a_1 \oplus h(x^a_2 || x^a_2) = x^b_1 \oplus h(x^b_2 || x^b_2)$.

This is where the proof breaks down. You cannot construct a collision from this.

2.2. $x^a_2 \neq x^b_2$

2.3. $x^a_3 \neq x^b_3$

2.4. $x^a_4 \neq x^b_4$

Hope I could help!

Your proof starts with the correct approach, but $h_1$ is not collision-resistant (CR), and therefore your proof should give you a hint as to why it's not CR.

Edit: I have removed the counterexample, since it should be easy to figure out using the proof attempt below.

Attempt to prove

You want to prove that:

If $h$ is CR, then $h_1$ is CR.

We prove the contraposition of that statement:

If there exists an adversary $\mathcal{A}^{h_1}$ breaking $h_1$, then there exists an adversary $\mathcal{A}^{h}$ breaking $h$.

We want to assume the existence of $\mathcal{A}^{h_1}$ and use it to construct $\mathcal{A}^{h}$.

$\mathcal{A}^{h}$ is playing the CR game, and is supposed to output a collision for $h$. To achieve that, we let $\mathcal{A}^{h_1}$ run. Since by assumption $\mathcal{A}^{h_1}$ has a non-negligible probability of succeeding, it will output a collision of $h_1$ with non-neglibile probability, i.e. a $x^a \neq x^b$ such that $h_1(x^a) = h_1(x^b)$.

We now want to win the CR game against $h$ and construct a collision for $h$ from $x^a$, $x^b$.

We know that $h_1(x^a) = h_1(x^b)$, and $x^a \neq x^b$. Therefore, using your $g(\cdot)$, $h(g(x^a)) = h(g(x^b))$.

There are two cases here:

1. Either: $g(x^a) \neq g(x^b)$

then we immediately find a collision: since $h(g(x^a)) = h(g(x^b))$ and $g(x^a) \neq g(x^b)$, the pair $(g(x^a), g(x^b))$ is a collision for $h$.

2. Or not: $g(x^a) = g(x^b)$

then we have to look further for a collision. by $g(x^a) = g(x^b)$ we know that

$\underbrace{(x^a_1 \oplus h(x^a_2 || x^a_2))}_\text{first part}\ ||\ (h(x^a_3 || x^a_3) \oplus x^a_4) = (x^b_1 \oplus h(x^b_2 || x^b_2))\ ||\ (h(x^b_3 || x^b_3) \oplus x^b_4)$.

By $x^a \neq x^b$ we know that at least one of these 4 cases must hold:

2.1. $x^a_1 \neq x^b_1$

By $g(x^a) = g(x^b)$, the first part of the input of the outer $h$ must be equal:

$x^a_1 \oplus h(x^a_2 || x^a_2) = x^b_1 \oplus h(x^b_2 || x^b_2)$.

This is where the proof breaks down. You cannot construct a collision from this.

2.2. $x^a_2 \neq x^b_2$

2.3. $x^a_3 \neq x^b_3$

2.4. $x^a_4 \neq x^b_4$

Hope I could help!

Source Link
ambiso
  • 706
  • 4
  • 13

Your proof starts with the correct approach, but $h_1$ is not collision-resistant (CR), and therefore your proof should give you a hint as to why it's not CR.

Counterexample

Take a random distinct $w_0, z_0$ and compute $w_1 = h(w_0 \| w_0)$ and $z_1 = h(z_0 \| z_0)$.

Additionally take arbitrary $x_3, x_4$.

Then $(x^a = (w_1, z_0, x_3, x_4), x^b = (z_1, w_0, x_3, x_4))$ is a collision:

\begin{align*} &h_1(x^a) \\ =& h((x_1 \oplus h(x_2 || x_2))\ ||\ (h(x_3 || x_3) \oplus x_4))\\ =& h((w_1 \oplus h(z_0 || z_0))\ ||\ (h(x_3 || x_3) \oplus x_4))\\ =& h((w_1 \oplus z_1)\ ||\ (h(x_3 || x_3) \oplus x_4))\\ \end{align*}

and

\begin{align*} &h_1(x^b) \\ =& h((x_1 \oplus h(x_2 || x_2))\ ||\ (h(x_3 || x_3) \oplus x_4))\\ =& h((z_1 \oplus h(w_0 || w_0))\ ||\ (h(x_3 || x_3) \oplus x_4))\\ =& h((z_1 \oplus w_1)\ ||\ (h(x_3 || x_3) \oplus x_4))\\ =& h((w_1 \oplus z_1)\ ||\ (h(x_3 || x_3) \oplus x_4))\\ =& h_1(x^1)\\ \end{align*}

Attempt to prove

You want to prove that:

If $h$ is CR, then $h_1$ is CR.

We prove the contraposition of that statement:

If there exists an adversary $\mathcal{A}^{h_1}$ breaking $h_1$, then there exists an adversary $\mathcal{A}^{h}$ breaking $h$.

We want to assume the existence of $\mathcal{A}^{h_1}$ and use it to construct $\mathcal{A}^{h}$.

$\mathcal{A}^{h}$ is playing the CR game, and is supposed to output a collision for $h$. To achieve that, we let $\mathcal{A}^{h_1}$ run. Since by assumption $\mathcal{A}^{h_1}$ has a non-negligible probability of succeeding, it will output a collision of $h_1$ with non-neglibile probability, i.e. a $x^a \neq x^b$ such that $h_1(x^a) = h_1(x^b)$.

We now want to win the CR game against $h$ and construct a collision for $h$ from $x^a$, $x^b$.

We know that $h_1(x^a) = h_1(x^b)$, and $x^a \neq x^b$. Therefore, using your $g(\cdot)$, $h(g(x^a)) = h(g(x^b))$.

There are two cases here:

1. Either: $g(x^a) \neq g(x^b)$

then we immediately find a collision: since $h(g(x^a)) = h(g(x^b))$ and $g(x^a) \neq g(x^b)$, the pair $(g(x^a), g(x^b))$ is a collision for $h$.

2. Or not: $g(x^a) = g(x^b)$

then we have to look further for a collision. by $g(x^a) = g(x^b)$ we know that

$\underbrace{(x^a_1 \oplus h(x^a_2 || x^a_2))}_\text{first part}\ ||\ (h(x^a_3 || x^a_3) \oplus x^a_4) = (x^b_1 \oplus h(x^b_2 || x^b_2))\ ||\ (h(x^b_3 || x^b_3) \oplus x^b_4)$.

By $x^a \neq x^b$ we know that at least one of these 4 cases must hold:

2.1. $x^a_1 \neq x^b_1$

By $g(x^a) = g(x^b)$, the first part of the input of the outer $h$ must be equal:

$x^a_1 \oplus h(x^a_2 || x^a_2) = x^b_1 \oplus h(x^b_2 || x^b_2)$.

This is where the proof breaks down. You cannot construct a collision from this.

2.2. $x^a_2 \neq x^b_2$

2.3. $x^a_3 \neq x^b_3$

2.4. $x^a_4 \neq x^b_4$

Hope I could help!