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

Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com> Sat, 15 February 2020 15:28 UTC

Return-Path: <jeanphilippe.aumasson@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id 30EF11200B1; Sat, 15 Feb 2020 07:28:29 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.998
X-Spam-Status: No, score=-1.998 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=unavailable autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id H1gCmnI6-FPt; Sat, 15 Feb 2020 07:28:26 -0800 (PST)
Received: from mail-wm1-x330.google.com (mail-wm1-x330.google.com [IPv6:2a00:1450:4864:20::330]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 2974F1200B2; Sat, 15 Feb 2020 07:28:26 -0800 (PST)
Received: by mail-wm1-x330.google.com with SMTP id m10so4134367wmc.0; Sat, 15 Feb 2020 07:28:26 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:from:date:message-id:subject:to:cc; bh=xIW4q8P01V3KhHVtYBnN0WJnqWjLx/jU/EkNVEbDUjA=; b=WxRkcZOo1GKWbINjk0Y3K/XcOFcjcjxixUJR5kGH7IvctVeyHnH+QOFhj5CEKnF59B oQ6D2vYo/jZn4miF0mZGc26bmFxW1OTykjUtraqv1lpPrAzgAuoaMVgZxl0M/Nqtl+ri m1ia6mUhYZTDLjhh8jl3o+4iWBrwudZZZVl1fV2HDx+VHqYXM4pw9uVsfvhdDgRsSlLK nQcqZ2UOe9/o931cbD9RwzFUTEj3NdI9XUSTxjal56Un66AXKbeoMIvKPSwb06E1ikPc qfHE93xOGQH6tOpVoTWj9fUjkb/yVfoJL+hSeNKyxIrlnH+UcI7i3NljtoCFdkIDbo3f mTeg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to:cc; bh=xIW4q8P01V3KhHVtYBnN0WJnqWjLx/jU/EkNVEbDUjA=; b=JgghzVhwUHYs5llhsdfMWQeKeP787HAaGNIMqTriFMFD5v+2esyT3pF31WbgmrMC4d 9XOXTBKSQZMCpBYVr0y1c/XJpoDQNs7CdTbIA5FJQUCWjRMdOvarEoYc3nDgijFosjib MajhV76O2STBkJOWxZOspdrSCuvGPhrapE9We+W9BW0uIJbsbE9nVsJIv+TjeYAUdlic S6ZNqTGEFXmUFQbKjnJx8clWLR31rARDNfsUf8MRpcKLvm7gfAFqDd6VZMq6wniN5Ppc RWkOkswvFP8ZrMxZ4qJyv5Y3lMq1cfNNB8dhozEGiE+xS41RW2jcKu3OVOfg9TfpsDLC q/1g==
X-Gm-Message-State: APjAAAVMPiFYuybkpefPjoyea/ylkUloBGE26ucRsVyZH8vxlJTfDUOA DMD8Vhy1XFAZ4xGiGe9WWNQUQv1p/4XIqAPOKCDDM0dyEb2MyQ==
X-Google-Smtp-Source: APXvYqwLmVzvya7wv0Q3DWdz1fFK8PABzi8OB7nwAj0b0FEABXEl8VbSFHaJpfBKu7q8Th8IOZ5uSsN9/RkMizuE558=
X-Received: by 2002:a7b:cb97:: with SMTP id m23mr10801442wmi.37.1581780504227; Sat, 15 Feb 2020 07:28:24 -0800 (PST)
MIME-Version: 1.0
From: Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>
Date: Sat, 15 Feb 2020 16:28:13 +0100
Message-ID: <CAGiyFdfh0Uthb3EUEUVNQ9OoFGf-XVbFnY4goBG9wkssSS8sDg@mail.gmail.com>
To: cfrg@ietf.org
Cc: crypto-panel@irtf.org, cfrg-chairs@ietf.org
Content-Type: multipart/alternative; boundary="0000000000001134b1059e9ef98c"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/vwkBr1gmYjZwjTN6cu0AESlvfaI>
Subject: [Cfrg] Review of draft-irtf-cfrg-kangarootwelve-01
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Sat, 15 Feb 2020 15:28:29 -0000

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

## 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](
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
[Ruby](https://github.com/konsolebox/digest-kangarootwelve-ruby), and in

K12 seems to be used in some PoW, at least  there's a miner tool:

## 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

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