Re: [Cfrg] Review of draft-irtf-cfrg-kangarootwelve-01
Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com> Mon, 17 February 2020 10:24 UTC
Return-Path: <jeanphilippe.aumasson@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id E10C51201E4; Mon, 17 Feb 2020 02:24:26 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.998
X-Spam-Level:
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 ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id kyUU0A5FmAGm; Mon, 17 Feb 2020 02:24:24 -0800 (PST)
Received: from mail-wr1-x441.google.com (mail-wr1-x441.google.com [IPv6:2a00:1450:4864:20::441]) (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 804B312081E; Mon, 17 Feb 2020 02:24:23 -0800 (PST)
Received: by mail-wr1-x441.google.com with SMTP id y17so18975003wrh.5; Mon, 17 Feb 2020 02:24:23 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=MF7U9AfIfPO5WhC99cUMgWqKPuwZ+s9OpX5nB6JGhhg=; b=i5CDdfHOEszmmca7zYSl1GjawceykVhoTBjyZQhILyIf75DvUJF3DcYnmiI8AIKcm5 EW5NlEP9KPVBL3v4f88eHynFtmulmyLYNT3a0Znpsw/b15WTn6rtwZme9PZSQgJ9R0O5 WTj2z/m8gHc7jPcFbzTSHsFkLWoZzKUOnxdATGmZAnTKA5bLuc+OhYi31UimboL/RK3s LEOZj8KBS9SmwmgcAs1xz4ZiEFNx/4FJpjej2nM1EVVH7mGSyRfkDYAHrY2F+H0XvHlE 5OmnEC5ch/V+hAQnmpihFzK1heqADr1juFO8qjodpZOVQbm0n0m+tTFFZktwPnp8AE2o lk/A==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=MF7U9AfIfPO5WhC99cUMgWqKPuwZ+s9OpX5nB6JGhhg=; b=GVEIOXAODIhm0Jsk8KIx8TAWXmmgC1Mf73mLG8Jlqe4eYjo+iqc4PAEJFykim+kG5f citQGriMlU8xJsXPp/C9CN5Yf8Vpo1etvrGX1YKKNZ9owcCYxINDNZTMQ4+fz3SHEMRN vPVXUFTPyTQNoMb8dFp3EiPqCnew3/jpWmhIae6qSe7TmFyejp6aDp6bFzxp+DuPkjNA 4n6mlt6rmlvLFD6oydsoOz+tYMJWHn3PXitOnd56vUg7LV+vY1tbopkBT7yB4JmXTY/9 QGVSlve4ezAGIwBhYkU93zw+82glXNyUcGbsVTH5kGIa1X454jcy9Z1sJ9dVtEP9Tp2k 8oFw==
X-Gm-Message-State: APjAAAVVcJ22CQPdKWAmy/g0fQf0DbpSsX3fijYWwJUY34QDDP3p0jko VvtVFEQp/dVlgtsWun0e7WJPQng6DpzYPZRa9H0wNEZcxAfo8Q==
X-Google-Smtp-Source: APXvYqx50ZlJmw/88T3Cy3Gf4289NFX+kIMcoe//UZ0fUn2HePvMREBZKJ4HIk6Cis7bSFJWczIJt6G+GcCeIThcXNE=
X-Received: by 2002:adf:f744:: with SMTP id z4mr17232490wrp.318.1581935061752; Mon, 17 Feb 2020 02:24:21 -0800 (PST)
MIME-Version: 1.0
References: <CAGiyFdfh0Uthb3EUEUVNQ9OoFGf-XVbFnY4goBG9wkssSS8sDg@mail.gmail.com>
In-Reply-To: <CAGiyFdfh0Uthb3EUEUVNQ9OoFGf-XVbFnY4goBG9wkssSS8sDg@mail.gmail.com>
From: Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>
Date: Mon, 17 Feb 2020 11:24:10 +0100
Message-ID: <CAGiyFdeHXQNp97ObUbFPMhq8Yhty2gBxMe4FxcGwPib8qTBq_g@mail.gmail.com>
To: cfrg@ietf.org
Cc: crypto-panel@irtf.org, cfrg-chairs@ietf.org
Content-Type: multipart/alternative; boundary="00000000000069de67059ec2f523"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/LYFNGOqpYLGKY5LeLjUJ1bHB21Y>
Subject: Re: [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: Mon, 17 Feb 2020 10:24:27 -0000
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 < jeanphilippe.aumasson@gmail.com> 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"). > > >
- [Cfrg] Review of draft-irtf-cfrg-kangarootwelve-01 Jean-Philippe Aumasson
- Re: [Cfrg] Review of draft-irtf-cfrg-kangarootwel… Jean-Philippe Aumasson
- Re: [Cfrg] Review of draft-irtf-cfrg-kangarootwel… Benoît Viguier