Member preview

SHA-3: Keccak, Grøstl, Blake, SHAKE and Skein — The Final Versions

Researchers in Canada have defined that the SHA-3 method will take longer to crack that the time that the universe has existed. The total time to crack, with some of the best cracking hardware around, is 10²⁹ years or 1,000,000,000,000,000,000,000,000,000,000 years to crack the hash. But remember, too, Ron Rivest said that RSA was safe for 4 quadrillion years, but the numbers he used could be cracked within days now.

Introduction

And so I implemented SHA-3 and it worked, and then NIST decided to change it, so I’ve had to re-implement it. It’s taken me a while to get the C code to port properly, but the version here should work against NIST test vectors.

SHA-3 was known as Keccak and is a hash function designed by Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche. MD5 and SHA-0 have been shown to be susceptible to attacks, along with theoretical attacks on SHA-1. NIST thus defined there was a need for a new hashing method which did not use the existing methods for hashing, and a competition for competing algorithms.

In October 2012, Keccak won the NIST hash function competition and is proposed as the SHA-3 standard. It should be noted that it is not replacement SHA-2, which is currently a secure method. Overall Keccak uses the sponge construction where the message blocks are XORed into the initial bits of the state, and then inevitably permuted.

The sponge function takes a simple function f and involves a number of stages, and where we create a fixed output (dependent on the bit length of the hash function). Simple operations of XOR, AND, and bit shifts are used, and which leads to a fast generation of the hash function:

The f permutation function takes a variable-length input and produces an arbitrary output length. A is the bit rate, and each f function operates on b bits, and where a capacity is defined as c = b — r.

The SHAKE method is useful as it can be used to create a hash method of a variable length. For the 128-bit version will produce a hash value is 32 hex characters.

The contenders

NIST published the new standard, based on Keccak, on 5 August 2015 [here], and which beat off competition from BLAKE (Aumasson et al.), Grøstl (Knudsen et al), JH (Hongjun Wu), and Skein (Schneier et al.). After two rounds the final round an evaluation of security, performance and hardware space. Blake and Keccah did well in terms of the number of gates which implement the methods:

But it was in throughput that Keccak really shone, and beat the others by at least a factor of between three and four:

With energy consumption becoming a major factor within mobile devices and for IoT, the energy consumption for Keccak again trumped the other finalists:

In this Keccak consumed less than half of the power per bit than Blake.

Note: The tests were conducted by ETHZ — Eidgenössische Technische Hochschule Zürich, VT — Virginia Tech and GMU — George Mason University.

Skein

Skein was a contender for SHA-3 and was created by Bruce Schneier, Niels Ferguson, Stefan Lucks, Doug Whiting, Mihir Bellare, Tadayoshi Kohno, Jon Callas and Jesse Walker. It is based on Bruce’s Threefish block and is compressed using Unique Block Iteration (UBI). This supports a chaining mode which allows for variable sizes of hashes. It gets its name the intertwining of the input, which looks like the twining in a skein of yarn:

The following is a calculator for it [here].

Grøstl was designed cryptographers at the Technical University of Denmark (DTU) and TU and is defined as a new hashing method. Overall it is an iterated hash function, using two fixed and different permutations, along with a compression function [article]. Grøstl comes from an Austrian dish of hash.

The following is a calculator [here].

NIST

National Institute of Standards and Technology (NIST) has now released the final version of the method as a new standard: Federal Information Processing Standard (FIPS) 202, SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. A key factor in the definition of the new standard was that each of the methods submitted required signed statements that the method would be available on a royalty-free basis.

So here is the code [Keccak]:

I’ve tested all the vectors against the NIST spec, so they should be correct. If you want to try out Blake and Blake 2, they are [here].

Conclusions

But is SHA-3 now the standard? No! Many implementations now use the alternatives that were proposed for the standard. Ethereum, for example, uses Keccak in its original form, and SPHINC, a quantum robust hash-based signature method, uses Blake [here]. Confused?