# Parallel Skein Hash Construction based on the Subset Sum Problem?

Matt Ball matt.ball at ieee.org
Thu Oct 30 08:50:19 EDT 2008

```On Wed, Oct 29, 2008 at 9:23 AM, Stephan Somogyi wrote:
>
> The Skein team has announced its submission to the NIST hash competition:
>
> <http://www.schneier.com/skein.html>
>

Now that we've all had a chance to read the Skein algorithm, I've got
a question for the list:

Would it be possible to construct an efficient parallel version of
Skein with output size N by creating intermediate results of size >2N,
adding them as integers, and then hashing this sum of intermediate
results as the final result?  (That is, would such a construction be
faster than the Skein tree hashing?)  I suspect that this construction
would be secure according to the computational difficulty of solving
the Subset Sum problem (known to be NP-complete), but haven't
rigorously confirmed this.  Skein is able to efficiently create larger
outputs, so such a construction like this would be easier with Skein
than with, say SHA-512.

For example, with Skein-256, you could hash each 256-bit (or larger,
depending on leaf size choice) message chunk into a 512-bit, or
768-bit intermediate value.  This value would then be added to all
other similar hash results (mod 2^512 or 2^768), and this result would
be hashed one more time for the final result.

It's necessary to make the intermediate results at least 2x the final
hash size because the best known solution to the subset sum problem is
solvable in 2^(N/2) operations.  There's also the issue of tying the
complexity of an addition operation to the complexity of computing a
single hash result (e.g., 1 N-bit Hash might equal 100 N-bit modular
adds).  For this reason, using 3x the final hash size for
intermediates would be more conservative.

Overall, I'm very happy with the results of Skein, and the three-fish
project.  When Ron Rivest described his "Halloween" hashing function
during Crypto 2008, I liked its simplicity (only simple operators),
but disliked that it was slower than SHA-256 and SHA-512.  Skein has
both delivered on security (so we think) and is faster and simpler
than existing NIST hashing functions and block ciphers.  In my
opinion, SHA-2 and AES have already pegged the meter on practical
security (of course, this may one day be false...), but there hasn't
been enough emphasis on efficiency, cost, and parallelism.

By using 64-bit addition as one of Skein's basic operations, the
resistance against Shamir's "Cube attack" increases, although the
hardware complexity increases quite a bit over Ron Rivest group's
choice of operators that have no carry.

I suspect that (as with the AES competition), that all of the
contestants of the final round with be secure, and the winner will be
the one that is most efficient, and to some extend, most flexible
(although too much flexibility causes implementation issues when
non-cryptographers have to write code to support all the options, and
the designers have to be smart enough to pick the correct
configuration).

With more submissions like this, I expect we will be poised for an
exciting NIST hash competition!

Cheers,
-Matt

Matt Ball, IEEE P1619.x SISWG Chair
Cell: 303-717-2717