Skip to main content
added 31 characters in body
Source Link
Maarten Bodewes
  • 94.5k
  • 13
  • 165
  • 319

Given all message blocks $w[i],i \in 0:63$ and assume that $n<128$ (arbitrary) bits $x_1,x_2,...,x_n$ of the IV values are unknown (e.g., $h_7$ bits are unknown) while other IV values coincide with those in the SHA-256 algorithm. Let $h_{i}^{j}$ denotes $i$-th hash of $j$-th round that is $$(h_{0}^{0},h_{1}^{0},...,h_{7}^{0})\overbrace{\mapsto}^{SHA256}(h_{0}^{1},h_{1}^{1},...,h_{7}^{1})\overbrace{\mapsto}^{SHA256} ...\overbrace{\mapsto}^{SHA256}(h_{0}^{64},h_{1}^{64},...,h_{7}^{64}),$$ and $(h_{0}^{64},h_{1}^{64},...,h_{7}^{64})$ depends on $n$ unknown IV bits. Now let us take $n$ (arbitrary) bits $y_1,y_2,...,y_n$ of $(h_{0}^{64},h_{1}^{64},...,h_{7}^{64})$ and assign values to them.

Question: Is there a possibility to find $x_1,x_2,...,x_n$ giving the assigned values of $y_1,y_2,...,y_n$ faster than exhaustive search?

Remark. One can notice that for the fixed $w$ the function

SHA256$_{w}^{-64}(h_{0}^{64},h_{1}^{64},...,h_{7}^{64}) = (h_{0}^{0},h_{1}^{0},...,h_{7}^{0})$$\operatorname{SHA256}_{w}^{-64}(h_{0}^{64},h_{1}^{64},...,h_{7}^{64}) = (h_{0}^{0},h_{1}^{0},...,h_{7}^{0})$ can be constructed analytically, so if all the bits of $(h_{0}^{64},h_{1}^{64},...,h_{7}^{64})$ are known, it is easy to obtain IV values. However, if only $n<128$ bits are assigned it is needed to find $2^{256-n}$ preimages in the worst case.

Given all message blocks $w[i],i \in 0:63$ and assume that $n<128$ (arbitrary) bits $x_1,x_2,...,x_n$ of the IV values are unknown (e.g., $h_7$ bits are unknown) while other IV values coincide with those in the SHA-256 algorithm. Let $h_{i}^{j}$ denotes $i$-th hash of $j$-th round that is $$(h_{0}^{0},h_{1}^{0},...,h_{7}^{0})\overbrace{\mapsto}^{SHA256}(h_{0}^{1},h_{1}^{1},...,h_{7}^{1})\overbrace{\mapsto}^{SHA256} ...\overbrace{\mapsto}^{SHA256}(h_{0}^{64},h_{1}^{64},...,h_{7}^{64}),$$ and $(h_{0}^{64},h_{1}^{64},...,h_{7}^{64})$ depends on $n$ unknown IV bits. Now let us take $n$ (arbitrary) bits $y_1,y_2,...,y_n$ of $(h_{0}^{64},h_{1}^{64},...,h_{7}^{64})$ and assign values to them. Is there a possibility to find $x_1,x_2,...,x_n$ giving the assigned values of $y_1,y_2,...,y_n$ faster than exhaustive search?

Remark. One can notice that for the fixed $w$ the function

SHA256$_{w}^{-64}(h_{0}^{64},h_{1}^{64},...,h_{7}^{64}) = (h_{0}^{0},h_{1}^{0},...,h_{7}^{0})$ can be constructed analytically, so if all the bits of $(h_{0}^{64},h_{1}^{64},...,h_{7}^{64})$ are known, it is easy to obtain IV values. However, if only $n<128$ bits are assigned it is needed to find $2^{256-n}$ preimages in the worst case.

Given all message blocks $w[i],i \in 0:63$ and assume that $n<128$ (arbitrary) bits $x_1,x_2,...,x_n$ of the IV values are unknown (e.g., $h_7$ bits are unknown) while other IV values coincide with those in the SHA-256 algorithm. Let $h_{i}^{j}$ denotes $i$-th hash of $j$-th round that is $$(h_{0}^{0},h_{1}^{0},...,h_{7}^{0})\overbrace{\mapsto}^{SHA256}(h_{0}^{1},h_{1}^{1},...,h_{7}^{1})\overbrace{\mapsto}^{SHA256} ...\overbrace{\mapsto}^{SHA256}(h_{0}^{64},h_{1}^{64},...,h_{7}^{64}),$$ and $(h_{0}^{64},h_{1}^{64},...,h_{7}^{64})$ depends on $n$ unknown IV bits. Now let us take $n$ (arbitrary) bits $y_1,y_2,...,y_n$ of $(h_{0}^{64},h_{1}^{64},...,h_{7}^{64})$ and assign values to them.

Question: Is there a possibility to find $x_1,x_2,...,x_n$ giving the assigned values of $y_1,y_2,...,y_n$ faster than exhaustive search?

Remark. One can notice that for the fixed $w$ the function

$\operatorname{SHA256}_{w}^{-64}(h_{0}^{64},h_{1}^{64},...,h_{7}^{64}) = (h_{0}^{0},h_{1}^{0},...,h_{7}^{0})$ can be constructed analytically, so if all the bits of $(h_{0}^{64},h_{1}^{64},...,h_{7}^{64})$ are known, it is easy to obtain IV values. However, if only $n<128$ bits are assigned it is needed to find $2^{256-n}$ preimages in the worst case.

polish
Source Link
kelalaka
  • 49.5k
  • 12
  • 118
  • 205

Finding the IV values of SHA-256 given all message blocks

Given all message blocks $w[i],i \in 0:63$ and assume that $n<128$ (arbitrary) bits $x_1,x_2,...,x_n$ of the IV values are unknown (e.g., $h_7$ bits are unknown) while other IV values coincide with those in the SHA-256 algorithm. Let $h_{i}^{j}$ denotes $i$-th hash of $j$-th round that is $(h_{0}^{0},h_{1}^{0},...,h_{7}^{0})\overbrace{\mapsto}^{SHA256}(h_{0}^{1},h_{1}^{1},...,h_{7}^{1})\overbrace{\mapsto}^{SHA256} ...\overbrace{\mapsto}^{SHA256}(h_{0}^{64},h_{1}^{64},...,h_{7}^{64})$,$$(h_{0}^{0},h_{1}^{0},...,h_{7}^{0})\overbrace{\mapsto}^{SHA256}(h_{0}^{1},h_{1}^{1},...,h_{7}^{1})\overbrace{\mapsto}^{SHA256} ...\overbrace{\mapsto}^{SHA256}(h_{0}^{64},h_{1}^{64},...,h_{7}^{64}),$$ and $(h_{0}^{64},h_{1}^{64},...,h_{7}^{64})$ depends on $n$ unknown IV bits. Now let us take $n$ (arbitrary) bits $y_1,y_2,...,y_n$ of $(h_{0}^{64},h_{1}^{64},...,h_{7}^{64})$ and assign values to them. Is there a possibility to find $x_1,x_2,...,x_n$ giving the assigned values of $y_1,y_2,...,y_n$ faster than exhaustive search?

Remark. One can notice that for the fixed $w$ the function

SHA256$_{w}^{-64}(h_{0}^{64},h_{1}^{64},...,h_{7}^{64}) = (h_{0}^{0},h_{1}^{0},...,h_{7}^{0})$ can be constructed analytically, so if all the bits of $(h_{0}^{64},h_{1}^{64},...,h_{7}^{64})$ are known, it is easy to obtain IV values. However, if only $n<128$ bits are assigned it is needed to find $2^{256-n}$ preimages in the worst case.

Finding the IV values of SHA-256

Given all message blocks $w[i],i \in 0:63$ and assume that $n<128$ (arbitrary) bits $x_1,x_2,...,x_n$ of the IV values are unknown (e.g., $h_7$ bits are unknown) while other IV values coincide with those in the SHA-256 algorithm. Let $h_{i}^{j}$ denotes $i$-th hash of $j$-th round that is $(h_{0}^{0},h_{1}^{0},...,h_{7}^{0})\overbrace{\mapsto}^{SHA256}(h_{0}^{1},h_{1}^{1},...,h_{7}^{1})\overbrace{\mapsto}^{SHA256} ...\overbrace{\mapsto}^{SHA256}(h_{0}^{64},h_{1}^{64},...,h_{7}^{64})$, and $(h_{0}^{64},h_{1}^{64},...,h_{7}^{64})$ depends on $n$ unknown IV bits. Now let us take $n$ (arbitrary) bits $y_1,y_2,...,y_n$ of $(h_{0}^{64},h_{1}^{64},...,h_{7}^{64})$ and assign values to them. Is there a possibility to find $x_1,x_2,...,x_n$ giving the assigned values of $y_1,y_2,...,y_n$ faster than exhaustive search?

Remark. One can notice that for the fixed $w$ the function

SHA256$_{w}^{-64}(h_{0}^{64},h_{1}^{64},...,h_{7}^{64}) = (h_{0}^{0},h_{1}^{0},...,h_{7}^{0})$ can be constructed analytically, so if all the bits of $(h_{0}^{64},h_{1}^{64},...,h_{7}^{64})$ are known, it is easy to obtain IV values. However, if only $n<128$ bits are assigned it is needed to find $2^{256-n}$ preimages in the worst case.

Finding the IV values of SHA-256 given all message blocks

Given all message blocks $w[i],i \in 0:63$ and assume that $n<128$ (arbitrary) bits $x_1,x_2,...,x_n$ of the IV values are unknown (e.g., $h_7$ bits are unknown) while other IV values coincide with those in the SHA-256 algorithm. Let $h_{i}^{j}$ denotes $i$-th hash of $j$-th round that is $$(h_{0}^{0},h_{1}^{0},...,h_{7}^{0})\overbrace{\mapsto}^{SHA256}(h_{0}^{1},h_{1}^{1},...,h_{7}^{1})\overbrace{\mapsto}^{SHA256} ...\overbrace{\mapsto}^{SHA256}(h_{0}^{64},h_{1}^{64},...,h_{7}^{64}),$$ and $(h_{0}^{64},h_{1}^{64},...,h_{7}^{64})$ depends on $n$ unknown IV bits. Now let us take $n$ (arbitrary) bits $y_1,y_2,...,y_n$ of $(h_{0}^{64},h_{1}^{64},...,h_{7}^{64})$ and assign values to them. Is there a possibility to find $x_1,x_2,...,x_n$ giving the assigned values of $y_1,y_2,...,y_n$ faster than exhaustive search?

Remark. One can notice that for the fixed $w$ the function

SHA256$_{w}^{-64}(h_{0}^{64},h_{1}^{64},...,h_{7}^{64}) = (h_{0}^{0},h_{1}^{0},...,h_{7}^{0})$ can be constructed analytically, so if all the bits of $(h_{0}^{64},h_{1}^{64},...,h_{7}^{64})$ are known, it is easy to obtain IV values. However, if only $n<128$ bits are assigned it is needed to find $2^{256-n}$ preimages in the worst case.

Source Link

Finding the IV values of SHA-256

Given all message blocks $w[i],i \in 0:63$ and assume that $n<128$ (arbitrary) bits $x_1,x_2,...,x_n$ of the IV values are unknown (e.g., $h_7$ bits are unknown) while other IV values coincide with those in the SHA-256 algorithm. Let $h_{i}^{j}$ denotes $i$-th hash of $j$-th round that is $(h_{0}^{0},h_{1}^{0},...,h_{7}^{0})\overbrace{\mapsto}^{SHA256}(h_{0}^{1},h_{1}^{1},...,h_{7}^{1})\overbrace{\mapsto}^{SHA256} ...\overbrace{\mapsto}^{SHA256}(h_{0}^{64},h_{1}^{64},...,h_{7}^{64})$, and $(h_{0}^{64},h_{1}^{64},...,h_{7}^{64})$ depends on $n$ unknown IV bits. Now let us take $n$ (arbitrary) bits $y_1,y_2,...,y_n$ of $(h_{0}^{64},h_{1}^{64},...,h_{7}^{64})$ and assign values to them. Is there a possibility to find $x_1,x_2,...,x_n$ giving the assigned values of $y_1,y_2,...,y_n$ faster than exhaustive search?

Remark. One can notice that for the fixed $w$ the function

SHA256$_{w}^{-64}(h_{0}^{64},h_{1}^{64},...,h_{7}^{64}) = (h_{0}^{0},h_{1}^{0},...,h_{7}^{0})$ can be constructed analytically, so if all the bits of $(h_{0}^{64},h_{1}^{64},...,h_{7}^{64})$ are known, it is easy to obtain IV values. However, if only $n<128$ bits are assigned it is needed to find $2^{256-n}$ preimages in the worst case.