Eli Biham
Orr Dunkelman

Valid HTML 4.01 Transitional

Valid CSS!

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).

SHAvite-3_{256} Message
Expansion

News

  • 23.8.2010 - SHAvite-3's update - identifying a mistake in reference implementation, addressing security issues, and suggesting a tweak. Have it all here.
  • 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.

For your convenience, you can find the changes 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:

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 Estimates

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 Estimates

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

Implementation Results

The following are reports concerning the hardware implementations of SHAvite-3 made by various teams.

ASIC Implementations

Source Digest size Technology Optimization Target (speed/area) Size Throughput
High-Speed Hardware Implementations of BLAKE, Blue Midnight Wish, CubeHash, ECHO, Fugue, Grostl, Hamsi, JH, Keccak, Luffa, Shabal, SHAvite-3, SIMD, and Skein by Stefan Tillich et al. 256 bits ASIC 0.18 Speed 58,826 2.387 Gbps @ 88.57Mhz

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.

Contact Orr regarding this website.
The design of the website is based on the design of the Haifa Linux Club website we would like to thank the webmasters of that website (besides Orr) for the design.