[CFRG] Security limits of ChachPoly (was: XChacha20 counter size)

Loup Vaillant-David <loup@loup-vaillant.fr> Sat, 26 December 2020 19:59 UTC

Return-Path: <loup@loup-vaillant.fr>
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 6770F3A0EF8 for <cfrg@ietfa.amsl.com>; Sat, 26 Dec 2020 11:59:27 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_MSPIKE_H2=-0.001, SPF_HELO_NONE=0.001, SPF_NONE=0.001] autolearn=ham autolearn_force=no
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id vSukOEtur-la for <cfrg@ietfa.amsl.com>; Sat, 26 Dec 2020 11:59:26 -0800 (PST)
Received: from relay10.mail.gandi.net (relay10.mail.gandi.net []) (using TLSv1.2 with cipher ADH-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id BF8463A0E67 for <cfrg@irtf.org>; Sat, 26 Dec 2020 11:59:25 -0800 (PST)
Received: from grey-fade ( []) (Authenticated sender: loup@loup-vaillant.fr) by relay10.mail.gandi.net (Postfix) with ESMTPSA id 4AB92240005; Sat, 26 Dec 2020 19:59:22 +0000 (UTC)
Message-ID: <a110fef12a184b1d28598a0e52a641fdf84cf9a8.camel@loup-vaillant.fr>
From: Loup Vaillant-David <loup@loup-vaillant.fr>
To: Taylor R Campbell <campbell+cfrg@mumble.net>
Cc: cfrg@irtf.org
Date: Sat, 26 Dec 2020 20:59:21 +0100
In-Reply-To: <20201225233709.9FF446053D@jupiter.mumble.net>
References: <20201225233709.9FF446053D@jupiter.mumble.net>
Content-Type: text/plain; charset="UTF-8"
X-Mailer: Evolution 3.28.5-0ubuntu0.18.04.2
Mime-Version: 1.0
Content-Transfer-Encoding: 7bit
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/8WZ_NAtRsfOVAgfIIrWDf4iVcjo>
Subject: [CFRG] Security limits of ChachPoly (was: 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: Sat, 26 Dec 2020 19:59:27 -0000

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

I did some digging, and in the case of Poly1305 as used in RFC 8439,
the number of messages is irrelevant. Only their maximum length
matters. Security does *not* drop as you send more messages. You can
send as many messages as you want.

I speculate (but don't know) that it might be because unlike GCM, the
secret multiplier is not reused across messages. (AES GCM could have
done the same, but it would have meant computing 2 additional blocks
per message instead of just one.)

The security bounds given by DJB's Poly1305 paper say that it was
designed this way specifically to preserve security as we send more
messages. Only message length matters. This is shown again in the
current AEAD limits draft:

   v = number of attempts
   p = target adversary attack probability
   l = maximum message length (in blocks)
   u = number of users or keys (multi-key attack)

   v <= (p * 2^103) / (l * u)

The biggest possible messages with a 64-bit counter would be 2^68
blocks (we have 4 Poly1305 blocks per Chacha20 block). So:

   v <= (p * 2^103) / (2^68 * u)
   v <= (p * 2^35) / u

That's the theoretical limit, though.  One does not simply encrypt 2^70
bytes in one block (my laptop barely exceeds 2^32 bytes per second).
More realistic (yet unreasonable) length would be in the Terabyte
range. With 8TiB, we'd have 2^43 bytes, or 2^39 blocks:

   v <= (p * 2^103) / (2^39 * u)
   v <= (p * 2^64) / u

Inadvisable for sure, but not broken either. Stream repetition would be
many orders of magnitude worse. In my opinion, the fact that short
messages are better does not justify breaking all security for long
messages. I'd sooner specify that applications "MUST" crash if the
input message is bigger than some threshold.