2
$\begingroup$

Let $F_{512}(B, C)$ denote the underlying function (single block manipulation function) of SHA-256. This function takes a 512-bit block $B$, 256-bit initialization vector $C$ and produces 256 pseudo-random bits (eight 32-bit words). Then I can define the following function (that operates on a 1024-bit block $B$ given a 512-bit initialization vector $C$ and outputs 512 pseudo-random bits):

$$G_{1024}(B, C) = (x_1 \oplus x_3) \mathbin\Vert (x_2 \oplus x_4),$$

where $$\begin{array}{l} {x_1} = F_{512}({B_1}, {C_1}),\\ {x_2} = F_{512}({x_1} \oplus {B_2}, {C_2}),\\ {x_3} = F_{512}({x_2} \oplus {B_1}, {C_1}),\\ {x_4} = F_{512}({x_3} \oplus {B_2}, {C_2}), \end{array}$$

$B_i$ denotes the first/second half of the 1024-bit block and $C_i$ denotes the first/second half of the 512-bit initialization vector.

Let $F_{1024}(B, C)$ denote the underlying function (single block manipulation function) of SHA-512. This function takes a 1024-bit block $B$, 512-bit initialization vector $C$ and produces 512 pseudo-random bits (eight 64-bit words).

Yes, $G_{1024}$ may be slower than $F_{1024}$, but is $G_{1024}$ weaker than $F_{1024}$ from the cryptographic point of view? If yes, in what aspects?


EDIT

I think that xoring the 256-bit $x_k$ with the 512-bit $B_i$ was a mistake, but I can also define the following function (that operates on a 1024-bit block $B$ given a 512-bit initialization vector $C$ and outputs 512 pseudo-random bits):

$$H_{1024}(B, C) = (x_1 \oplus x_3) \mathbin\Vert (x_2 \oplus x_4),$$

where $$\begin{array}{l} {x_1} = F_{512}({B_1}, {C_1}),\\ {x_2} = F_{512}({B_2}, {C_2}),\\ {x_3} = F_{512}((x_1 \mathbin\Vert x_2) \oplus {B_1}, {C_1}),\\ {x_4} = F_{512}((x_1 \mathbin\Vert x_2) \oplus {B_2}, {C_2}), \end{array}$$

$B_i$ denotes the first/second half of the 1024-bit block and $C_i$ denotes the first/second half of the 512-bit initialization vector.

Similarly, $H_{1024}$ may be slower than $F_{1024}$, but is $H_{1024}$ weaker than $F_{1024}$ from the cryptographic point of view? If yes, in what aspects?

$\endgroup$
  • $\begingroup$ wouldnt $F_{1024}$ produce 512 bits? $\endgroup$ – Richie Frame Dec 20 '17 at 20:01
  • $\begingroup$ Usually XOR isn't a brilliant operation if you want to avoid collissions. I'm not sure if the dependence of the x values will completely negate the security issues wrt the XOR, but I guess you would need to prove that this construct works rather than the other way around. There aren't any subkeys introduced, so this isn't directly related to a Feistel cipher, I presume. Note that SHA-512 is faster than SHA-256 on 64 bit machines, so this construction is unlikely to the extreme to be faster than SHA-512. $\endgroup$ – Maarten Bodewes Dec 20 '17 at 21:43
  • $\begingroup$ @RichieFrame: Yes, the compression function outputs 256 or 512 bits; there were a few typos, I edited the question. $\endgroup$ – lyrically wicked Dec 21 '17 at 4:16
  • $\begingroup$ Which function is $F$ supposed to be? The compression function takes both the current block (512 bits for SHA-256) and the IV/current state (256 bits for SHA-256). How would $G$ handle state if it is meant to be the compression function? $\endgroup$ – otus Dec 21 '17 at 6:24
  • $\begingroup$ @perror (the editor) please do not make such minimal changes until you've got full capabilities as it simply takes too much time to review them - just adding a line is not worth it $\endgroup$ – Maarten Bodewes Dec 21 '17 at 16:34
2
$\begingroup$

The original question did not have $C$, introduced to address otus's comment. The next section of the present answer was written with that in mind, or equivalently $C_1=C_2$ and the second input of functions removed; we'll get $C$ back in the final section.


Yes, $G_{1024}$ is weaker than $F_{1024}$ from a cryptographic point of view. For example, about $2^{257}$ evaluations of $F_{512}$ have a sizable chance to be enough to find a 512-bit value $B$ such that $G_{1024}(B)$ is the all-zero 512-bit bitstring, when doing so should require an expected $2^{512}$ evaluations of $G_{1024}$, that is about $2^{257}$ times more work.

To form such $B=B_1\mathbin\|B_2$, we use incremental 256-bit $B_1$, compute $x_1=F_{512}(B_1)$, compute $B_2=x_1\oplus B_1$, know without computation that $x_2=x_1$, compute $x_3=F_{512}(x_2\oplus B_1)=F_{512}(B_2)$, until it happens that $x_1=x_3$ or we have exhausted all 256-bit $B_1$. This gives non-negligible odds to find $B_1$ with $x_1=x_3$, in which case $x_2=x_4$, and thus $G_{1024}(B)$ is the all-zero 512-bit bitstring.


Back to the question as it stood in its second major revision, with $C_1$ and $C_2$, presumably distinct in the first round of the 512-bit hash.

In that first round, for random $B_1$ and $B_2$, $x_1\oplus x_3=x_2\oplus x_4$ has odds about $2^{-256}$, and the expected work to find such $B_1$ and $B_2$ is about ${3\over4}2^{258}$ evaluations of $F_{512}$. With such $B_1$ and $B_2$ as first block, in the next round of the 512-bit hash, the round function will have its 512-bit chaining input $C$ such that $C_1=C_2$, and we can carry the previous attack on the second round. If that attack fails, we now can retry by redoing the attack on the first round, with one full try costing on average about ${5\over4}2^{258}$ evaluations of $F_{512}$ . $2^{260}$ evaluations of $F_{512}$ can with good probability exhibit a 2048-bit input such that the 512-bit intermediary hash after two rounds of $G_{1024}$ is all-zero; that's $2^{254}$ times easier than it should.

We can attack the full 512-bit hash obtained from $G_{1024}$ with length-strengthening, and find a 239-octet input hashing to all-zero with an additional $2^{136}$ work factor (because the length-strengthening forces 17 octets in $B_2$ of the second round). This is a break of first-preimage resistance by a factor of $2^{118}$, albeit specialized to the all-zero result.

Sure, that's not devastating, and in particular does not break a 256-bit security claim. But attacks only get better; they never get worse.


The last system can be attacked as follows: chose an arbitrary first block, yielding fresh $C_1$ and $C_2$ for the second block. For each, try to find find $B_2$ yielding $x_2=0$ and ending with the 17-octet length-strengthening prescribed for a 239-octet hash input; if none of the $2^{120}$ such values of $B_2$ is fit, try another first block. If one is found, try to find $B_1$ yielding $x_1=0$; otherwise start over with another first block. That yields a 239-octet string hashing to all-zero per the full 512-bit hash with length-strengthening. The length-strengthening was less taxing than in the previous system, and the attack is a break of first-preimage resistance by a factor of like $2^{252}$ (albeit still specialized to the all-zero result).

Comment: modern crypto does not design its cryptosystems by trial and error until no error is found. We want at least a security argument, if possible a proof under some security model and plausible assumptions.

$\endgroup$
  • $\begingroup$ Please, see the edited question. Now I see that xoring the 256-bit $x_k$ with the 512-bit $B_i$ was a mistake. So I need to propose a significant modification to the construction. $\endgroup$ – lyrically wicked Dec 21 '17 at 8:51
  • 3
    $\begingroup$ @lyricallywicked, you should not make significant modifications after the question has been answered, especially this well. Better to ask a new question in that case. $\endgroup$ – otus Dec 21 '17 at 12:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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