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

Taylor R Campbell <> Sat, 26 December 2020 21:29 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 61DF23A0FF2 for <>; Sat, 26 Dec 2020 13:29:57 -0800 (PST)
X-Virus-Scanned: amavisd-new at
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, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id EpfUr8z8197b for <>; Sat, 26 Dec 2020 13:29:55 -0800 (PST)
Received: from ( []) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id D392C3A0FF0 for <>; Sat, 26 Dec 2020 13:29:55 -0800 (PST)
Received: by (Postfix, from userid 1014) id 1A188604FE; Sat, 26 Dec 2020 21:29:53 +0000 (UTC)
From: Taylor R Campbell <>
To: Loup Vaillant-David <>
In-reply-to: <>
Date: Sat, 26 Dec 2020 21:29:41 +0000
Sender: Taylor R Campbell <>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Message-Id: <>
Archived-At: <>
Subject: Re: [CFRG] Security limits of ChachPoly (was: XChacha20 counter size)
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Sat, 26 Dec 2020 21:29:57 -0000

> Date: Sat, 26 Dec 2020 20:59:21 +0100
> From: Loup Vaillant-David <>
> 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.

The probability of each forgery attempt's success _independently_ is
bounded by 8*floor(L/16)/2^106, where L is the maximum message length.

If the adversary makes q forgery attempts, then the probability of
succeeding at _any_ forgery is bounded by q*8*floor(L/16)/2^106.

Note that both the number of forgery attempts _and_ the maximum
message length figure into this bound.


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

ChaCha/Poly1305 and AES-GCM are no different in this respect: for
fixed number of messages and total bytes encrypted, the forgery
probability is proportional to q/L for both of them, with a different
constant factor arising from differences in Poly1305 and GHASH.

Using a message sequence number as the nonce so you can quickly reject
outdated message numbers mitigates the issue for ChaCha/Poly1305, for
the reason you describe.  But that's not as relevant for XChaCha,
which is meant for applications where you may not have a reliable
message sequence number.

They also do scale differently in the number messages and total bytes:
AES-GCM is quadratic where ChaCha/Poly1305 is linear, because AES-GCM
is held back by AES as a PRP.  I attempted to sketch the qualitative
differences in this table in the Daence paper:
source code:

(Daence guarantees the adversary's advantage is below 1/2^32 per key
as long as you process at most 2^52 messages of at most 2^38 bytes
under each key, even if you manage to attain _both_ limits at the same
time for a single key.  I chose this so the usage limits wouldn't have
to be explained by a complicated series of tables and prose like
AES-GCM-SIV's <>.)

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

No objection to making the XChaCha draft clearer about what the hard
limit is.  I am a big fan of clearly articulated usage limits.