1
$\begingroup$

I know that Skein can output a digest of arbitrary size, with a kind of counter mode. Blocks of the resulting digest can be computed in parallel.

What about Keccak ? I know that a sponge function can generate a hash of arbitrary length, but is it possible to generate this output with a parallel algorithm ?

Improve this question
$\endgroup$
2
  • $\begingroup$ I don't know how Keccak works but a hash function usually has an internal compression function where it iterates its input. So (very informally) for input 2x the block length, it'll iterate it twice. As I said I'm not privy to Keccak's internals so I may be wrong. If this is true however, it means that parallelism is either hard or impossible. $\endgroup$
    – rath
    Commented Mar 24, 2014 at 17:41
  • $\begingroup$ @rath For Skein this is possible. For keccak I don't know because of the sponge property... $\endgroup$
    – Dingo13
    Commented Mar 24, 2014 at 19:17

1 Answer 1

Reset to default
2
+50
$\begingroup$

Keccak uses a sponge construction to output arbitrary length hashes. This is a distinctly serial operation. Although the inner permutation can be perfomed with a certain level of parallelism using bit-slicing, it is faster in software using native 64-bit operations.

enter image description here

P is the message input per block, z are outputs, and f is the inner permutation. In order to output a given length $x$, z is incremented until it meets or exceeds $x$, to which it is then truncated. The quantity of z required will vary due in implementation to the variable rate r not being a constant.

For example, if you need a 384-bit output and r is 128 bits, there will be 3 outputs which are then concatenated, and between each output is an additional permutation past the last input permutation (dashed line)

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ This does not mean you cant force Keccak to output in parallel, but it is not designed to, as the security properties no longer hold. For example, you can take the first output (truncated), add a block counter, then rehash that many times in parallel. Don't do this. $\endgroup$
    – Richie Frame
    Commented Mar 24, 2014 at 19:51

Your Answer

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

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