Subject: [Cfrg] Review of draft-irtf-cfrg-kangarootwelve-01

From: Jean-Philippe Aumasson <[email-masked]>
Date: Sat, 15 Feb 2020 16:28:13 +0100

Document: draft-irtf-cfrg-kangarootwelve-01
Reviewer: Jean-Philippe Aumasson
Review Date: 2020-02-13

Summary: almost ready, editorial changes needed

Conflict of interest warning: I'm a co-designer of BLAKE3, another fast
hash function using a tree mode, recently announced at RWC, see
https://github.com/BLAKE3-team/BLAKE3/.

## Draft content

This draft specifies KangarooTwelve (K12), a Keccak variant introduced
[in 2016](https://teserakt.io/doc/teserakt-product.pdf) that can be seen
as a variant of the ParallelHash "SHA-3 derived function" standardized [by
NIST in SP 800-185](
https://www.nist.gov/publications/sha-3-derived-functions-cshake-kmac-tuplehash-and-parallelhash)
in December 2016.

The version specified in the draft seems identical to that described in
the [research paper](https://eprint.iacr.org/2016/770.pdf). The test
vectors are the same.

## Technical merits

The main selling point of K12 is its speed, from

1. doing 12 rounds instead of 24 for Keccak (which I believe is fine, as
commented in my Too Much Crypto paper where I suggest 10  rounds only).

2. a parallel mode with unbounded fan-out and one parent node, allowing
"unlimited parallelism".

Compared to ParallelHash, K12's mode is more efficient on short
messages. ParallelHash internally calls the variant cSHAKE, which is
essentially the SHAKE XOF. The ParallelHashXOF variants provide XOF
functionality as well but they are slower than K12 because of the round
numbers. I find K12 a bit simpler.

## Adoption

Like all the standard and non-standard SHA-3/Keccak variants (except
maybe for SHAKE), K12 hasn't received much interest from application
developers. But K12 is IMHO one of the variants that has the greatest
application potential, in part thanks to its pragmatic round number.

K12's official C code is available at https://github.com/XKCP/K12 and in
the Keccak family package https://github.com/XKCP/XKCP.

I found some third-party implementations: in
[JS](https://github.com/twuni/kangaroo12.js),
[Ruby](https://github.com/konsolebox/digest-kangarootwelve-ruby), and in
[Go](https://github.com/mimoo/GoKangarooTwelve).

K12 seems to be used in some PoW, at least  there's a miner tool:
https://github.com/Noob-X/Aeon-K12-cpuminer

## Editorial

I cannot comment with the compliance with IETF style and formatting
rules, not being familiar with these.

The specification looks to me mostly standalone and complete.

Specific comments:

* in 2.1, in "outputByteLen (..) the Length", "Length" does not seem to
  require capitalization

* 2.1  refers to "the absorbing phase" and to "the squeezing phase" for
  the first time, without said phases being defined/introduced. The
  notions are common in the Keccak ecosystem, but may be new to many
  readers.

* in 2.1, the pseudocode  refers twice to `inputBytes`, which is not
  defined; I think it should be `input` instead

* notations such as `S_n-2`, meaning `S_(n-2)` rather than `(S_n)-2`,
  are error prone and should probably be avoided; same comment for other
  occurrences such as `x_n-1`.

* "compute the 32-bytes Chaining Values": I believe the correct spelling
  is "32-byte".

* "This computation SHOULD exploit the parallelism available on the
   platform in order to be optimally efficient": maybe be more specific?
   parallelism may refer to SIMD instructions and/or multi-core
   processing, for example.

* pseudocode is sometimes spelled "pseudo code",  sometimes
  "pseudo-code", not sure what IETF prefers.

* "In the table below are gathered the values" would be clearer with
  active voice ("The table below gathers the values").

---

From: Jean-Philippe Aumasson <[email-masked]>
Date: Mon, 17 Feb 2020 11:24:10 +0100

Errata: major copypasta fail, K12 link should be [in 2016](
https://eprint.iacr.org/2016/770.pdf), corrected version below

## Draft content

This draft specifies KangarooTwelve (K12), a Keccak variant introduced
[in 2016](https://eprint.iacr.org/2016/770.pdf) that can be seen
as a variant of the ParallelHash "SHA-3 derived function" standardized [by
NIST in SP 800-185](
https://www.nist.gov/publications/sha-3-derived-functions-cshake-kmac-tuplehash-and-parallelhash)
in December 2016.

## Technical merits

## Adoption

## Editorial

Specific comments:

---

From: Benoît Viguier <[email-masked]>
Date: Tue, 18 Feb 2020 15:45:43 +0100

Dear Jean-Philippe,

Thank you for your review!
Please find below our answers and comments.

On 2/17/20 11:24 AM, Jean-Philippe Aumasson wrote:
> Errata: major copypasta fail, K12 link should be [in
> 2016](https://eprint.iacr.org/2016/770.pdf), corrected version below
>
> hash function using a tree mode, recently announced at RWC,
> see https://github.com/BLAKE3-team/BLAKE3/..
>
>
> ## Draft content
>
> NIST in SP
> 800-185](https://www.nist.gov/publications/sha-3-derived-functions-cshake-kmac-tuplehash-and-parallelhash)
> in December 2016.
>

Agreed, we fixed it.

>   notions are common in the Keccak ecosystem, but may be new to many
We added a brief description of absorbing phase and squeezing phase:
"/[...] consists of two phases: the absorbing phase that processes the//
input and the squeezing phase that produces the output./"
>   defined; I think it should be `input` instead

Thanks for spotting this, we fixed it.

>   occurrences such as `x_n-1`.

As suggested, we added brackets to avoid ambiguities.

> * "compute the 32-bytes Chaining Values": I believe the correct spelling

Agreed, we fixed this.

>    parallelism may refer to SIMD instructions and/or multi-core

We are now more specific and are referring to SIMD instructions.

>   "pseudo-code", not sure what IETF prefers.

https://tools.ietf.org/html/rfc4269 use "pseudo code".
https://tools.ietf.org/html/rfc7693 use "pseudocode".
https://tools.ietf.org/html/rfc3961 use "pseudocode".

We will follow "pseudocode" spelling.

>   active voice ("The table below gathers the values").

Agreed, we fixed this.

In summary, we integrated those changes in the github repository of CFRG:
https://github.com/cfrg/draft-irtf-cfrg-kangarootwelve/commit/87b7ed3ea7e3215194f9d93ab16bc3df3e8b4b9c

-- 
Kind regards,

Benoît Viguier
Software Engineer - PhD Student | Cryptography & Formal Methods
Radboud University | Mercator 1, Toernooiveld 212
6525 EC Nijmegen, the Netherlands | www.viguier.nl