Re: Linus' sha1 is much faster!

From: Theodore Tso <tytso@mit.edu>
Date: Aug 16, 2009, 00:06 UTC
Message-ID: <20090816000640.GA7554@mit.edu>
In-Reply-To: <43d8ce650908151312o6a43416el27965c4b0ab8d83d@mail.gmail.com>

On Sat, Aug 15, 2009 at 09:12:58PM +0100, John Tapsell wrote:

Show 9 quoted lines

> 2009/8/15 Bryan Donlan <bdonlan@gmail.com>:
> > coreutils is licensed under GPLv3, and git under GPLv2 (only), so
> > you'd need permission from all contributors to the implementation in
> > order to relicense under GPLv3. A quick grep of the history suggests
> > these contributors to be:
> 
> X11 also requires a fast SHA1 implementation.  It uses this to check
> if two pixmaps are the same.  So it would be really nice to relicense
> under a liberal enough license that xorg can use it.

If the checksum isn't being exposed in the protocol (i.e., it's just internal to the X server), one possibility for X11 is to consider to use the SHA-3 candidate Skein instead. After receiving a large amount of evaluation by cryptographic experts, it was one of the 18 algorithms (our of an original 64 entries) that have made it the 2nd round of the NIST competition. It's also *substantially* faster than SHA:

    One exception to this is Skein, created by several well-known
    cryptographers and noted pundit Bruce Schneier. It was designed
    specifically to exploit all three of the Core 2 execution units
    and to run at a full 64-bits. This gives it roughly four to 10
    times the logic density of competing submissions.

    This is what I meant by the Matrix quote above. They didn't bend
    the spoon; they bent the crypto algorithm. They moved the logic
    operations around in a way that wouldn't weaken the crypto, but
    would strengthen its speed on the Intel Core 2.

    In their paper (PDF), the authors of Skein express surprise that a
    custom silicon ASIC implementation is not any faster than the
    software implementation. They shouldn't be surprised. Every time
    you can redefine a problem to run optimally in software, you will
    reach the same speeds you get with optimized ASIC hardware. The
    reason software has a reputation of being slow is because people
    don't redefine the original problem.

    http://www.darkreading.com/blog/archives/2008/11/bending_skein_c.html

For more information and some optimized implementation, see:

	http://www.skein-hash.info/

							- Ted