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

[Jean-Philippe Aumasson <[e-mail]>]

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

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://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.

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


On Sat, Feb 15, 2020 at 4:28 PM Jean-Philippe Aumasson <
[e-mail]> wrote:

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