How Many Kangaroos? Twelve!

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…

12 Kangaroos and A KitTen

Reducing security and improving performance?

Crypto KitTen

In a fantastic 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 speedup 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]:

Kangaroos

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 rounds from 16 to 12 and where BLAKE2s went from 14 to 10 rounds, with respect to BLAKE. BLAKE2bvhad been benchmarked as being faster than MD5 and using 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 got significant speed improvements and reduced the number of rounds from 24 to 12 (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 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 a 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. 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 was 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 from 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 by 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 manages 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 as SHAKE). The following is some sample Go code [here]:

package main

import(
    "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:    qwerty

Hash:   d7aa928c520c8d48a0734ad96c2b43d237197f7bedab6ef014c7ed5f60fc160b

BLAKE3

For SHA-3, 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 evaluated security, performance and hardware space. But things have moved on greatly, and just as you thought that Keccak was leading the way with SHA-3, along comes BLAKE3 and does this:

For performance, BLAKE3 basically wipes the floor its previous version (BLAKE2b), and which was already faster than SHA-3. It gives the equivalent of 128 bits of security. At its core is the Bao tree mode and the original BLAKE2 method, and it has been created by Jack O’Connor, Jean-Philippe Aumasson, Samuel Neves, and Zooko Wilcox-O’Hearn [here]:

The method has now been released onto a GitHub in Rust (Version 0.1.0) — and there’s even a Go version on GitHub. So let’s give it a try. First, we create with:

cargo new blake3

We then go into the blake3 folder and add the following to the cargo.toml file [here]:

[package]
name = "blake3"
version = "1.0.0"
authors = ["Bill"]
[dependencies]
blake2 = "0.8"
blake3="0.1"
sha2 = "0.8"
sha3 = "0.8"
digest = "0.8"
sha1="0.6"

This will import the Blake2, Blake3, SHA2, SHA3, and SHA1 crates. Next, we go into the src folder, and edit the main.rs file with [here]:

extern crate blake2;

extern crate digest;
extern crate sha2;
extern crate sha1;
extern crate sha3;


use blake2::{Blake2b, Blake2s, Digest};
use sha2::Sha256;
use sha3::{Sha3_224,Sha3_256,Sha3_384,Sha3_512};

use std::env;

 
fn main() {

	let mut string = String::from("Hello world!");

	let args: Vec = env::args().collect();

	if args.len() >1 {

		string = args[1].clone();
	}

	println!("Data: {}",string);
	let data = string.as_bytes();


	let hash = Blake2b::digest(data);

	println!("\nBlake 2b Hash: {:x}", hash);


	let hash = Blake2s::digest(data);

	println!("\nBlake 2s Hash: {:x}", hash);


	let hash1 = blake3::hash(data).to_hex();

	println!("\nBlake3 Hash: {}", hash1);


	let mut m = sha1::Sha1::new();
	m.update(data);

	println!("\nSHA-1 Hash: {}", m.digest().to_string());

	let hash = Sha256::digest(data);

	println!("SHA-256 Hash: {:x}", hash);

	let hash = Sha3_224::digest(data);

	println!("SHA3-244 Hash: {:x}", hash);


	let hash = Sha3_256::digest(data);

	println!("SHA3-256 Hash: {:x}", hash);


	let hash = Sha3_384::digest(data);

	println!("SHA3-384 Hash: {:x}", hash);


	let hash = Sha3_512::digest(data);

	println!("SHA3-512 Hash: {:x}", hash);



}

A sample run is [here]:

Data: The quick brown fox jumps over the lazy dogBlake 2b Hash:  Blake3 Hash: 2f1514181aadccd913abd94cfa592701a5686ab23f8df1dff1b74710febc6d4aSHA-1 Hash: 2fd4e1c67a2d28fced849ee1bb76e7391b93eb12
SHA-256 Hash: d7a8fbb307d7809469ca9abcb0082e4f8d5651e46d3cdb762d02d0bf37c9e592
SHA3-244 Hash: d15dadceaa4d5d7bb3b48f446421d542e08ad8887305e28d58335795
SHA3-256 Hash: 69070dda01975c8c120c3aada1b282394e7f032fa9cf32f4cb2259a0897dfc04
SHA3-384 Hash: 7063465e08a93bce31cd89d2e3ca8f602498696e253592ed26f07bf7e703cf328581e1471a7ba7ab119b1a9ebdf8be41
SHA3-512 Hash: 01dedd5de4ef14642445ba5f5b97c15e47b9ad931326e4b0727cd94cefc44fff23f07bf543139939b49128caf436dc1bdee54fcb24023a08d9403f9b4bf0d450

We can see here that the BLAKE3 hash is “2f1514181aa..c6d4a”, and which has 64 hex characters (or 256 bits). With BLAKE2b we can have a varying digest size. In this case, it has a 512-bit output.

Here is the Python version:

https://asecuritysite.com/encryption/blake3

Rust, Golang and C will obviously be faster than Python, but, it at least, provides the implementation to a wide range of platforms.

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. For the competitor to KangarooTwelve, we now have BLAKE3, and which is super fast.