Secure hashes are single threaded in conventional implementations. In the past, this made sense because only single cores were available. Today, however, multicore machines leave cores idle as the software crunches slowly using only one. This idea provides a small part of the solution.

A hash function reduces (compresses) a large amount of data (eg a file) to a small residue (the hash). It does so by repeatedly compressing blocks of the input into a residue which becomes the final hash. The individual compression steps use a function called a one-way compressor which takes two inputs (A and B) and gives a result C. It is called one way because knowing C and either of the inputs does not allow you to deduce the other input.

The usual combination is to feed C from the i-th step into A of the i+1-th step, while successive chunks of the input file provide the respective values for B. This forces the processing of the i+1-th step to wait until the completion of the i-th step.

The idea is to form a tree of steps. Given the input file is broken into blocks F1, F2 .. Fn; the Initialization Vector (IV) is paired with F1, F2 with F3 and so on with the natural count of input bytes appended to the file just before chunking. Any odd block left over is paired with the IV again. These pairs are fed in as A and B and processed in parallel to give C1, C2 .. Cm. Rinse, wash, repeat until one block is left, which is the hash result.

On uniprocessor systems, this will require a stack of intermediate results to be maintained, but only approx (64*log b) bytes for a 512bit calculation, where log b is log base 2 of the number of blocks. 2Kbytes of workspace should be overkill.

There are a number of fairly simple variations, and the usual refinements can, of course, be made.

What do you think of this idea or comment?
(You can change your vote at any time)

I agree

No opinion

I disagree