From Kangaroos to KitTens

From Kangaroos to KitTens

Crypto KitTen

In a fantastic new paper, Jean-Philippe (JP) Aumasson proposes that we reduce the number of rounds in SHA-3 (Keccak) from 24 to just 10 rounds, and names it KitTen (get it … “10”). This, he proposes, would create a speed up of 2.4 times. JP’s focus is that it is possible to reduce the number of rounds within a given cryptography method without compromising security, and which then improves the overall performance of the method. He also proposes that we could reduce the number of rounds from 12 to 8 for the BLAKE2b hashing method, and with a resulting 1.5×speed-up [here]:

BLAKE2, BLAKE2b, Keccak and KangerooTwelve

The problem with competitions, is that the winner will often take all, until the next competition. Those competing could thus get better than the winner, but it is often too late. So let’s look at the SHA-3 competition, and how things have evolved.

NIST created a competition for SHA-3, and it was Keccak that was crowned the champion. Since then, SHA-3 has received good adoption levels, but you’ll also see BLAKE2 — one of the finalists — being used in many applications. Keccak won because it was fast, and where BLAKE2 was submitted too late to compete against it. Since many have seen BLAKE2 as the better alternative [here]. We see here that BLAKE2 (BLAKE2b — the 64-bit version — and BLAKE2s) performs much better than SHA3 implementations:

BLAKE2b improved its speed by reducing the number of round from 16 to 12 and where BLAKE2s went from 14 to 10 rounds, with respect to BLAKE. BLAKE2bvhad been benchmarked at being faster than MD5 and usiing 30% less memory, along with a 25% speed improvement over BLAKE.

So, in 2016, the Keccak research team came up with a new method: KangarooTwelve. For this they managed to get significant speed improvements and managed to reduce the number of rounds from 24 to 12 (and with a security level of around 128 bits). A new method of tree hashing was also added, and which supports the parallel hashing of large files [paper]:

SHA-3

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 SHA-3 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].

Speed tests

While Blake2 manage to beat MD5 for speed, KangarooTwelve beats off the other common hashing functions — in tests for the cycles per byte — by a considerable factor:

Initially we take a customization string and then add a message string. This then produces an output of any size (in the same way of SHAKE). The following is some sample Go code [here]:

package mainimport(
    "fmt"
    "github.com/mimoo/GoKangarooTwelve/K12"
    "encoding/hex"
    "os"
)func main(){    str1:=""
    message:=""    argCount := len(os.Args[1:])    if (argCount>0) {str1 = string(os.Args[1])}
        if (argCount>1) {message = string(os.Args[2])}    customString := []byte(str1)    payload := []byte(message)    out := make([]byte, 32)    K12.K12Sum(customString, payload, out)
    fmt.Printf("Custom string:\t%s\nMessage:\t%s\n\n",str1,message)    fmt.Printf("Hash:\t%s",hex.EncodeToString(out))
}

A sample run is [here]:

Custom string:  Hello
Message:    qwertyHash:   d7aa928c520c8d48a0734ad96c2b43d237197f7bedab6ef014c7ed5f60fc160b

Conclusions

SHA-3 was a starting point, and things move on. The world of security is not a static target, it is a moving one.