The SHAvite-3 Hash Function

SHAvite-3 is a secure and efficient hash function design by Eli Biham and Orr Dunkelman. SHAvite-3 is based on the HAIFA construction and the AES building blocks. SHAvite-3 uses a well understood set of primitives such as a Feistel block cipher which iterates a round function based on the AES round. SHAvite-3's compression functions are secure against cryptanalysis, while the selected mode of iteration offers maximal security against black box attacks on the hash function. SHAvite-3 is both fast and resource-efficient, making it suitable for a wide range of environments, ranging from 8-bit platforms to 64-bit platforms (and beyond).

News

• 23.11.2009 - SHAvite-3's bug fix. A small bug in the implementations is fixed, and two confusing typos are resolved. The cleared specifications can be found at here.
• 15.09.2009 - SHAvite-3 is tweaked. See the tweaked version at here.
• 23.07.2009 - SHAvite-3 was selected to the second round of NIST. For more information see here.
• 17.11.2008 - SHAvite-3 is presented in a seminar talk at the Institute of Information Science Academia Sinica, Taipei
• 12.01.2009 - SHAvite-3 is presented in Dagstuhl seminar.     Slides
• 26.02.2009 - SHAvite-3 is presented in NIST hash function workshop.     Slides

Original Submission to the NIST Competition

Our original submission to the NIST SHA-3 competition can be found Here.
After the submission deadline we have found out that there was a mistake in the submitted code. The mistake was in the code dealing with the counter (when generating digests of up to 256 bits) where the following lines were exchanged:

if (i==56)
       {
            rk[57] ^= counter[1];
            rk[58] ^= counter[0];
       }

if (i==84)
       {
            rk[86] ^= counter[1];
            rk[87] ^= counter[0];
       }

As a result, we had to change the reference code, as well as the test vectors. There was no change in the specification.

Updated Submission to the NIST Competition

Our updated submission to the NIST SHA-3 competition can be found Here.
For your convenience, you can find the ChangeLogs here:

1. Changes in the documentation
2. Changes in the code

Tweaked Submission to the NIST Competition

Our tweaked (and updated) submission to the NIST SHA-3 competition can be found Here.

1. The tweak (and the updates)
2. The tweak (including the bug fix)
3. Changes in the code
4. Changes in the code (including the bug fix of September)

Bug Fix to the Tweaked Submission

Due to a small bug in the reference implementation, we have issued a bug fix version. We also resolved two typos that may have confused implementers. The fixed submission version may be found Here.

The changes in the code can be found here, and the resolved typos (and changes to the documentation) can be found Here.

Please note that we have measured the performance of SHAvite-3 again, and received the same performance as before the bug fix.

Specification Documents

For your convenience, we provide here all the specification documents:

• Original Submission - 31.10.2008
• Updated Submission - 15.01.2009 (Changes from previous version)
• Updated Document - 01.02.2009 (Changes from previous version)
• Tweaked Submission - 15.09.2009 (the changes from the updated submission (version 15.01.2009), there were no changes in the specification in the bug fix of September 2009)
• Bug Fix - 23.11.2009 (the list of resolved typos and changes due to the bug fix)

Software Performance

Digests of up to 256 bits

Platform	CPU (RAM, Cache)	Compiler	Speed in cpb
32-bit	AMD Sempron(tm) Processor 3200+, 1800 MHz, 128 KB cache, 1 GB RAM, running in a full 32-bit mode	gcc 4.4.1	32.83
32-bit	Conjectured according to Bernstein and Schwabe speeds		26.6
32-bit	eBASH results	x86	28.73-84.42
32-bit	eBASH results	PowerPCs	20.62-43.99
64-bit	AMD Athlon(tm) 64 X2 Dual Core Processor 4200+, 2200 MHz, 512 KB cache, 1 GB RAM	gcc 4.4.1	25.13
64-bit	Conjectured according to Bernstein and Schwabe speeds		18.6
64-bit	eBASH results	Intel/AMD platforms	22.79-61.24
64-bit	eBASH results	PowerPCs	24.71-39.64
	With the new AES instruction of Intel	Measured speed	5.6

Digests of 257-512 bits

Platform	CPU (RAM, Cache)	Compiler	Speed in cpb
32-bit	AMD Sempron(tm) Processor 3200+, 1800 MHz, 128 KB cache, 1 GB RAM, running in a full 32-bit mode	gcc 4.4.1	55.90
32-bit	Conjectured according to Bernstein and Schwabe speeds		35.3
32-bit	eBASH results	x86	55.30-242.09
32-bit	eBASH results	PowerPCs	32.00-184.78
64-bit	AMD Athlon(tm) 64 X2 Dual Core Processor 4200+, 2200 MHz, 512 KB cache, 1 GB RAM	gcc 4.4.1	35.86
64-bit	Conjectured according to Bernstein and Schwabe speeds		28.4
64-bit	eBASH results	Intel/AMD platforms	40.28-255.10
64-bit	eBASH results	PowerPCs	38.41-64.39
	With the new AES instruction of Intel	Measured speed	5.5

Some timing results of several versions of our code can be found on the eBASH webpage.

Hardware Performance

The following are our hardware performance estimates. These estimates are based on implementations of AES from 2005, and thus are expected to be much slower than an actual implementation.

ASIC Implementations

Digest size	Optimization Target (speed/area)	Size	Throughput
256 bits	Size	10.1 Kgates	93.5 Mbps
256 bits	Speed	55 Kgates	604.4 Mbps
512 bits	Size	18.5 Kgates	4.7 Mbps
512 bits	Speed	81 Kgates	907.7 Mbps

FPGA Implementations

Digest size	Optimization Target (speed/area)	Size	Throughput
256 bits	Size	510 Slices	1.7 Mbps
256 bits	Speed	3585 slices	872.3 Mbps
512 bits	Size	895 slices	1.0 Mbps
512 bits	Speed	7170 slices	1.12 Gbps

Security

The original version of SHAvite-3 had one security concern for a specific value of message block, salt, and bit counter. This issue was first reported by Thomas Peyrin, and then further analyzed by Mridul Nandi and Souradyuti Paul (and then some more by us). Specifically, the bit counter has to be zero in order for all the results to work, and a zero counter is used only during the generation of the IVs and in the processing of an additional full padding block, where the attacker cannot use this property to his advantage. Hence, the original SHAvite-3 is a secure hash function. At the same time, as people may wish to use the compression function of SHAvite-3 outside the HAIFA context, we decided to tweak SHAvite-3 to answer this line of research.