Re: [CFRG] XChacha20 counter size

Taylor R Campbell <campbell+cfrg@mumble.net> Fri, 25 December 2020 23:37 UTC

Return-Path: <campbell@mumble.net>
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 B4E0C3A0C88 for <cfrg@ietfa.amsl.com>; Fri, 25 Dec 2020 15:37:13 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Level:
X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
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 zmDp1Q7Jz5Gt for <cfrg@ietfa.amsl.com>; Fri, 25 Dec 2020 15:37:12 -0800 (PST)
Received: from jupiter.mumble.net (jupiter.mumble.net [74.50.56.165]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 2C31C3A0C87 for <cfrg@irtf.org>; Fri, 25 Dec 2020 15:37:11 -0800 (PST)
Received: by jupiter.mumble.net (Postfix, from userid 1014) id 9FF446053D; Fri, 25 Dec 2020 23:37:09 +0000 (UTC)
From: Taylor R Campbell <campbell+cfrg@mumble.net>
To: Loup Vaillant-David <loup@loup-vaillant.fr>
CC: cfrg@irtf.org
In-reply-to: <e632e3291ced05b29c55fea0f064258cb3abfc1a.camel@loup-vaillant.fr>
Date: Fri, 25 Dec 2020 23:36:59 +0000
Sender: Taylor R Campbell <campbell@mumble.net>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Message-Id: <20201225233709.9FF446053D@jupiter.mumble.net>
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/4n5d1Oj_8e3ulNX3pO64ThSj8So>
Subject: Re: [CFRG] XChacha20 counter size
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: Fri, 25 Dec 2020 23:37:14 -0000

> Date: Fri, 25 Dec 2020 23:32:27 +0100
> From: Loup Vaillant-David <loup@loup-vaillant.fr>
> 
> - A 32-bit counter limits the length of the messages to realistically
>   attainable lengths (256 GiB), thus introducing a new (and avoidable)
>   way to shoot ourselves in the foot.

An application that accepts 256 GiB messages is an application that's
already prepared to shoot itself in the foot.  Individual messages
shouldn't be that long -- especially messages transmitted over the
internet.  You should break large messages into pieces of reasonable
size for separate authenticated encryption.

Exactly what is `reasonable' varies from application to application,
depending on how much memory they can tolerate an adversary wasting
before rejecting a forgery, but >256 GiB is definitely unreasonable.

The NaCl authors recommend limiting messages, e.g. to 4096 bytes as is
the limit in the NaCl tests: https://nacl.cr.yp.to/valid.html
https://groups.google.com/g/boring-crypto/c/BpUmNMXKMYQ/m/EEwAIeQdjacJ

This is also relevant for authenticators based on universal hashes
like AES-GCM and ChaCha/Poly1305, whose security depends linearly on
the _maximum_ message length (not just the total amount of data):
Accept a single 256 GiB message, and the number of messages you can
safely handle -- even if all the others are tiny -- dramatically drops
compared to an application limited to 2^14 bytes per message like TLS.

> - This is a departure from existing implementations. XSalsa20 from
>   NaCl uses a 64-bit counter. XChacha20 in Libsodium also uses a 64-bit
>   counter. In general, all XChacha20 implementations I know of use a
>   64-bit counter.

Many Salsa20 and ChaCha implementations, including a number in
SUPERCOP and the implementations named amd64-xmm5 and amd64-xmm6
published by the designer (https://cr.yp.to/snuffle.html), silently
repeat the key stream if you try to use them for more than 2^32
blocks.