2
$\begingroup$

I'm wondering why hash constructions aren't parallel like CTR mode for encryption?

For example: We have ideal block cipher E, where we encrypt message block with counter and xor output block with message block. Then we xor (sum) all blocks and encrypt it with length of message and xor with sum of all blocks to get hash. If last message block is shorter than block size it is padded with zeroes.

$H_{0} = E_{0}(m_{0}) \oplus m_{0}$

$H_{1} = E_{1}(m_{1}) \oplus m_{1}$

$...$

$H_{n} = E_{n}(m_{n}) \oplus m_{n}$

$H_{sum} = H_{0} \oplus H_{1} \oplus ...\oplus H_{n}$

$H = E_{Length}(H_{sum}) \oplus H_{sum}$

Parallel hash construction example

Is such construction known to be insecure? Or is it secure?

$\endgroup$
5
  • $\begingroup$ one acronym ... PMAC $\endgroup$ May 31, 2014 at 13:37
  • $\begingroup$ @user1028028: I'm asking about hash, not MAC. $\endgroup$
    – LightBit
    Jun 1, 2014 at 7:21
  • 1
    $\begingroup$ Related question: Counter mode secure hash algorithm $\endgroup$ Jun 1, 2014 at 17:02
  • $\begingroup$ You can build a hash the same way you build a MAC. If you look at how PMAC works you'll see why your construction is wrong and how to fix it $\endgroup$ Jun 2, 2014 at 7:51
  • $\begingroup$ @user1028028: PMAC without key is completely insecure. Fix it, how? $\endgroup$
    – LightBit
    Jun 2, 2014 at 16:18

2 Answers 2

4
$\begingroup$

It is insecure, since the XOR of many ($n$) independent compression function is much more vulnerable to collision attacks. The generalized birthday attack finds a collision with complexity $$ 2^{\frac{\text{block size}}{1+\lg n}}. $$

$\endgroup$
1
  • $\begingroup$ So XOR MACs are only good up to $2^{\frac{n}{2}}$ blocks? $\endgroup$
    – Melab
    Dec 6, 2017 at 23:25
7
$\begingroup$

Dmitry said that a collision in the xor can be found with a generalized birthday attack.

Actually, it's a lot worse than that; second preimages of sufficiently long messages can be found in polynomial time; hence an enormous block size (which might help against the birthday attack) doesn't help.

Let us call the size of the output of the ideal block cipher $n$. Then, let us consider a message that consists of (at least) $n$ blocks; and for each block, we consider two distinct alternatives, at position $i$, we would have arbitrary selected blocks $M_i$ and $M'_i$.

We would then compute $H_i = E_i( M_i ) \oplus M_i$ and $H'_i = E_i( M'_i ) \oplus M'_i$.

If we have a target value $Z$ for the exclusive or's (which we would have for a second preimage problem), we would then consider what sum of $H_i$ and $H'_i$ would exclusive-or to the target values; this can be viewed as a linear algebra problem, and can be solved with, say, Gaussian elimination in time $O(n^3)$

$\endgroup$
5
  • $\begingroup$ If $E$ were replaced with another hash function and still incorporated the length and the index, then would it be secure? $\endgroup$
    – Melab
    Oct 20 at 21:35
  • $\begingroup$ @Melab: no; it wouldn't frustrate the attack at all - the attack doesn't assume invertibility of $E$, so replacing it with a noninvertible function doesn't help. $\endgroup$
    – poncho
    Oct 26 at 14:30
  • $\begingroup$ Does this mean there is no secure parallelizable hash that is based on the XOR sum of data blocks individually processed along with their indices using a known secure hash algorithm? $\endgroup$
    – Melab
    Nov 15 at 3:34
  • $\begingroup$ What if the final hash operation on the XOR sum used a different function? $\endgroup$
    – Melab
    Dec 4 at 13:52
  • $\begingroup$ @Melab: that would depend entirely about what that different function is - if it is a strong hash function, than it is easy to show that the construction is secure. $\endgroup$
    – poncho
    Dec 4 at 14:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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