[Cfrg] Review of draft-arciszewski-xchacha-02

Neil Madden <neil.e.madden@gmail.com> Tue, 18 December 2018 12:14 UTC

Return-Path: <neil.e.madden@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 80311130EC0 for <cfrg@ietfa.amsl.com>; Tue, 18 Dec 2018 04:14:48 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Status: No, score=-1.999 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, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham 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 0PGfQn4WwaQr for <cfrg@ietfa.amsl.com>; Tue, 18 Dec 2018 04:14:46 -0800 (PST)
Received: from mail-wm1-x32d.google.com (mail-wm1-x32d.google.com [IPv6:2a00:1450:4864:20::32d]) (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 42085128B14 for <cfrg@ietf.org>; Tue, 18 Dec 2018 04:14:46 -0800 (PST)
Received: by mail-wm1-x32d.google.com with SMTP id p6so2282101wmc.1 for <cfrg@ietf.org>; Tue, 18 Dec 2018 04:14:46 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:content-transfer-encoding:mime-version:subject:message-id:date :to; bh=JTxjPcYyaK1dODgRFcGotaEQdiIcooQyksubOhNJ4G0=; b=U3ueE+10Hicu3O+YOG6a8wUCFtYUCJzm6dvgemU+akhU2fxBCehbhuoF+3Wittjoq8 ylfMaM/PBVdjvJ4gJRVSkD8iTRURfmv/ITI5DDIbMwgCTVAu6JRIRLq+7AQtGqq+3Bhz q8oHImqBOIs5iHu5W7aCSz6GIjst4xs8PT9G7sG/JUvRVHgYYkL1igKNV/nzWEWKqxVe QLS+HrswoSmXWKrhFwU6pdzBTVbHiQ9ktCpPTFnNuD1zNf4jJLO2RWdrivbJGJlc0QA8 qvTtYYqh/tlGjBZKGONLOKeDFGHmzYtgTj4C+clkWaeVM83M4MJEYd+AkKcO2s6kYwRp cG7g==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:content-transfer-encoding:mime-version :subject:message-id:date:to; bh=JTxjPcYyaK1dODgRFcGotaEQdiIcooQyksubOhNJ4G0=; b=FL0XbIrcLUEU1PlLNB1uqZU0ibT6GC9FGHhOcam/sqPBZMrMHZF1kMQgtTu5sYwAgO X1PSnGV1ZFsNkjZ0Cc8uGddpeA4lATQ8N0HcouR6cUgfxfkjKdCxDXrsYzjjtLw89Zw5 nUwEo1M4nXgTJGxhSPj6DPkIhinuA11tIZCJTif6icWhGzqR69RR6uI+wcYop1ACAc7O Z12g/MN39M+9HX+4D8mJGoJxwVEPJFdCBvLu9BPmIJ2qJ7zwQTxTKm7xhpx+PU5KESp7 saFhJphsxnJfVn6ilegPjKeYPCCJhccXAR8xlBFZkuI48rhQbeMpCskWhTzLyeJnsMCh 5zeA==
X-Gm-Message-State: AA+aEWZlg3UEVsx4GJ+XudI9ZA/F116reqhbvGd8iGmqKKY2lXlVdvb+ QeFqUv04LUtu+cZoRNyTHI4xlkAR
X-Google-Smtp-Source: AFSGD/WJR868aFo92ftQpNaZMUZkwZAHGBGxB3qmWetN9zjTp4NeXPVQOq0d8oGL3yn2eDDOMOtpLA==
X-Received: by 2002:a1c:cc19:: with SMTP id h25mr2965416wmb.80.1545135284373; Tue, 18 Dec 2018 04:14:44 -0800 (PST)
Received: from guest2s-mbp.lan ( []) by smtp.gmail.com with ESMTPSA id 14sm2799047wmv.36.2018. for <cfrg@ietf.org> (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 18 Dec 2018 04:14:43 -0800 (PST)
From: Neil Madden <neil.e.madden@gmail.com>
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Mime-Version: 1.0 (Mac OS X Mail 12.2 \(3445.102.3\))
Message-Id: <99CCB4A1-9CC1-4611-95C5-CEEA985024F8@gmail.com>
Date: Tue, 18 Dec 2018 12:14:42 +0000
To: cfrg@ietf.org
X-Mailer: Apple Mail (2.3445.102.3)
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/-LUUpbLpGJjgELudFY-bQERcXtA>
Subject: [Cfrg] Review of draft-arciszewski-xchacha-02
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: Tue, 18 Dec 2018 12:14:48 -0000

I’ve had a good look through draft-arciszewski-xchacha-02 from an implementor’s perspective. I think it’s a good draft that describes the algorithms well. I have some comments on a few parts of the text below:

Section 1, Introduction:

The text currently says:

"However, a more straightforward strategy can prevent nonce misuse
   conditions in environments where a large number of messages are

We should be careful with the word “prevent” here. Nonce reuse can still happen with large random nonces, even if it is less likely - e.g., with a broken or compromised PRNG. See for example failures in the Android SecureRandom implementation that led to compromise of a Bitcoin transaction due to nonce reuse in an ECDSA signature [1]. In this case the random nonce would have been 256 bits I believe, so even larger than that for XChaCha.

I think “more straightforward” is also potentially subject to debate (if you ignore the S2V parts, SIV is pretty simple). Perhaps wording along the following lines:

“However, misuse resistant cipher constructions come at a cost in
performance as they must necessarily make two passes over the 
message to be encrypted. An alternative strategy can significantly 
reduce the chance of accidental nonce reuse in environments 
where a large number of messages are encrypted. [Simply use …]”

Ironically, the main reason that I am interested in XChaCha20 is precisely because the larger nonce makes it more suitable for use in an SIV construction, as per my recent draft.

Section 2.1 Motivation for XChaCha20-Poly1305:

It might be worth clarifying that a 96-bit nonce is too short to generate randomly where you need to encrypt lots of messages with the same key (more than a few million). If you are doing DH with forward secrecy and generating fresh keys for each message anyway, then a 96-bit random nonce is fine.

The text: "A more
   conservative threshold (2^-32 chance of collision) still allows for
   2^64 messages to be sent under a single key.”

This should say “still allows for 2^80 messages to be sent under a single key.”

2.2 HChaCha20

This could do with a reference to RFC 7539 section 2.3. It could be a bit clearer that the ChaCha20 block counter is replaced with the first 32 bits of the nonce (in little-endian) and the remaining 96 bits are used as per usual in ChaCha20.

I have verified the supplied test vector with an independent implementation of HChaCha20 that I wrote, and it matches.

2.3.1 XChaCha20 Pseudocode:

The code doesn’t include the 4 NUL bytes in the nonce it passes to ChaCha20.

Test vectors:

I have verified that the test vectors in A.1 and A.2 and produce the same results as documented.

[1] https://www.symantec.com/connect/blogs/android-cryptographic-issue-may-affect-hundreds-thousands-apps

Kind regards,