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. General Comments on Skein: 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 http://www.linkedin.com/in/matthewvball http://www.mavaball.net/ --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]