Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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 ?

share|improve this question
    
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. –  rath Mar 24 at 17:41
    
@rath For Skein this is possible. For keccak I don't know because of the sponge property... –  Dingo13 Mar 24 at 19:17
add comment

1 Answer 1

up vote 2 down vote accepted
+50

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)

share|improve this answer
1  
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. –  Richie Frame Mar 24 at 19:51
    
Thanks for that clarification. –  Dingo13 Mar 24 at 20:03
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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