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

Taylor R Campbell <campbell+cfrg@mumble.net> Sat, 26 December 2020 21:29 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 61DF23A0FF2 for <cfrg@ietfa.amsl.com>; Sat, 26 Dec 2020 13:29:57 -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 EpfUr8z8197b for <cfrg@ietfa.amsl.com>; Sat, 26 Dec 2020 13:29:55 -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 D392C3A0FF0 for <cfrg@irtf.org>; Sat, 26 Dec 2020 13:29:55 -0800 (PST)
Received: by jupiter.mumble.net (Postfix, from userid 1014) id 1A188604FE; Sat, 26 Dec 2020 21:29:53 +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: <a110fef12a184b1d28598a0e52a641fdf84cf9a8.camel@loup-vaillant.fr>
Date: Sat, 26 Dec 2020 21:29:41 +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: <20201226212953.1A188604FE@jupiter.mumble.net>
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/D21uRHcrZbE4WcSAjkkXxAAi7yI>
Subject: Re: [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 21:29:57 -0000

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

References:
https://cr.yp.to/highspeed/naclcrypto-20090310.pdf#page=30
https://eprint.iacr.org/2014/613.pdf#page=4

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

https://eprint.iacr.org/2020/067.pdf#page=5
source code: https://github.com/riastradh/daence/blob/master/adv.py

(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 <https://tools.ietf.org/html/rfc8452#page-12>.)

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