Re: [CFRG] XChacha20 counter size

Filippo Valsorda <filippo@ml.filippo.io> Fri, 25 December 2020 23:59 UTC

Return-Path: <filippo@ml.filippo.io>
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 F35293A0D74 for <cfrg@ietfa.amsl.com>; Fri, 25 Dec 2020 15:59:35 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.997
X-Spam-Level:
X-Spam-Status: No, score=-1.997 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_EF=-0.1, HTML_MESSAGE=0.001, RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=0.001, 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=filippo.io header.b=NBBOguhe; dkim=pass (2048-bit key) header.d=messagingengine.com header.b=ljPjT5yt
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 QX4NSql6phLO for <cfrg@ietfa.amsl.com>; Fri, 25 Dec 2020 15:59:33 -0800 (PST)
Received: from wout4-smtp.messagingengine.com (wout4-smtp.messagingengine.com [64.147.123.20]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 9DC2B3A0D3E for <cfrg@irtf.org>; Fri, 25 Dec 2020 15:59:33 -0800 (PST)
Received: from compute3.internal (compute3.nyi.internal [10.202.2.43]) by mailout.west.internal (Postfix) with ESMTP id 9CF479E4 for <cfrg@irtf.org>; Fri, 25 Dec 2020 18:59:32 -0500 (EST)
Received: from imap1 ([10.202.2.51]) by compute3.internal (MEProxy); Fri, 25 Dec 2020 18:59:32 -0500
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=filippo.io; h= mime-version:message-id:in-reply-to:references:date:from:to :subject:content-type; s=fm2; bh=5Bqz3/WX5L5p+yTpnBlTqQeKp0eBNaQ y1oje8WQHgcQ=; b=NBBOguheCPKqSGFJPzumbe8wDc4tOX1J8ErCljqKp6bE4rm VO8S5wLAzV+KDhtXVCYylCwKYIVsHNPw0mnkJ0/1tDKhGJ1/wVKnU/Jid+Yw/ukB rD5cGZS0DLWPnWQOvlaf3jtjdGgfxXsTKqLei3cc+lRkBkpSPl6oLfOhLGsvqp04 D45cYyz7KY8k6CiDRFSSW5XbDc8ai0PgqJ3ON/CtTLgiSDiOhuTYsBzTZwh0XyXJ Q/cCgGUKoXE+0H0AqXTPBgYxhtGchM/gtSB4tH5BE5nl96YYnHZxTzDtE3kAJ/5j mUEoGOnD8tAs1Er5z94zPwcbXIXZWlsGxioYXRQ==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=content-type:date:from:in-reply-to :message-id:mime-version:references:subject:to:x-me-proxy :x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s=fm1; bh=5Bqz3/ WX5L5p+yTpnBlTqQeKp0eBNaQy1oje8WQHgcQ=; b=ljPjT5yt1vhtFYvGJG7NoE 75YpbhDCDDHCALD5bnGSbXA+t9zFlXOK39U4ZhJl7ZiX0n+YJA5Bt8PX3F06yngW UB2mqp9OcJfGi23Z+UMNr/h1GpLciot2sJFqajIoR1RJhdp2dAf9RIo48MbN/aDh HKHTsRRPTcjZcRuCDh9jgTa/w5N6aIwCJY0abjaCFFPrYqRL5Q12yQB2+23r3uY3 nr/iU+MZMwOM8NdIwd3BZTyW4CUIGDWgN+SvIA1Y0mr/zCVklDSflRE2nRgBM83A CH62qYVOZSUxoQpVdGTedhvTQUa95iXu7DTepidXeYSNd2dkL4V7WFot9Z7Qwjow ==
X-ME-Sender: <xms:43zmXxOav09A9LFv7gSRDEOgueCGRH7v6juw6inaLulj4VrzoZYjcw> <xme:43zmXz_Ie-Qqnuie5Qhh6DRkcP6RmP9IbVwiYwGieVxehY7f68GBEcG_B289yWbDx XQqtS5H54u5TIApGg>
X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedujedrvdduvddgudehucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucgoufhushhpvggtthffohhmrghinhculdegledmne cujfgurhepofgfggfkjghffffhvffutgesrgdtreerreertdenucfhrhhomhepfdfhihhl ihhpphhoucggrghlshhorhgurgdfuceofhhilhhiphhpohesmhhlrdhfihhlihhpphhord hioheqnecuggftrfgrthhtvghrnheptdekhffggfdtkeetveeuteelhffgtdegleeutdel fedtleduvdeggfekiedujeefnecuffhomhgrihhnpeihphdrthhopdhgohhoghhlvgdrtg homhdpihhrthhfrdhorhhgnecuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpehm rghilhhfrhhomhepfhhilhhiphhpohesmhhlrdhfihhlihhpphhordhioh
X-ME-Proxy: <xmx:43zmXwQ1EbJkPLR36UCnNLC2LM7OWmL7AMqyO17x5RgLn_nnYp9vdQ> <xmx:43zmX9uWiOMIwiOA41zF57QiitP2SSBODYNi-vQ4Ezru8krnLOkaJg> <xmx:43zmX5fB2ND05NXZlbkSQP_qMBcYKPh0-FNfo4f8r-hSR9N6ogcESQ> <xmx:5HzmXzoUdOaHJFEf0xEZU8dydr2GFZHvXyrjyscrDRtB-UhKLiGimA>
Received: by mailuser.nyi.internal (Postfix, from userid 501) id 2B998C200A5; Fri, 25 Dec 2020 18:59:32 -0500 (EST)
X-Mailer: MessagingEngine.com Webmail Interface
User-Agent: Cyrus-JMAP/3.3.1-61-gb52c239-fm-20201210.001-gb52c2396
Mime-Version: 1.0
Message-Id: <2ad966e9-70f7-4201-884d-6ef0257fe839@www.fastmail.com>
In-Reply-To: <e632e3291ced05b29c55fea0f064258cb3abfc1a.camel@loup-vaillant.fr>
References: <e632e3291ced05b29c55fea0f064258cb3abfc1a.camel@loup-vaillant.fr>
Date: Sat, 26 Dec 2020 00:58:52 +0100
From: "Filippo Valsorda" <filippo@ml.filippo.io>
To: cfrg@irtf.org
Content-Type: multipart/alternative; boundary=48b515962d764a45bcbd1e663a513648
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/yTG7Q-QMsfgwkZuGGHWcwZQ5im0>
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:59:36 -0000

2020-12-25 23:32 GMT+01:00 Loup Vaillant-David <loup@loup-vaillant.fr>fr>:
> Hi, Merry Christmas,
> 
> I've just learned that draft-irtf-cfrg-xchacha-03 specifies a 32-bit
> counter. From what I can see, this is because it leans on the Chacha20
> variant described in RFC 8439.
> 
> This is problematic on two levels:
> 
> - 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.

I don't know about XSalsa20, but DJB's Salsa20 code as distributed with NaCl and from the Salsa20 homepage wraps shortly after overflowing a 32-bit counter, even if it's defined to have a 64-bit counter, so the originalism argument is not that strong.

He declined to acknowledge it as an issue because of the policy at https://nacl.cr.yp.to/valid.html, because he claimed support for counters larger than 32 bits is an incomplete experiment, and because there is an empty file named warning-256gb in the SUPERCOP benchmarks tarball.

https://groups.google.com/g/golang-announce/c/tjyNcJxb2vQ/m/n0NRBziSCAAJ

The Go XChaCha20 implementation will panic if the counter reaches 32 bits, per the draft.

> - 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.
> 
> If this draft is adopted as is, users could end up vulnerable when they
> switch to a pedantically conformant implementation. I believe we don't
> want that. XChacha20 has 256 bits available for the nonce and counter,
> we should use them all. Shrinking the counter down to 32 bits put end
> users at risk, without giving them any benefit in return.
> 
> My suggestion is the following: instead of leaning on the Chacha20
> variant described in RFC 8439, we should stick to the original
> Chacha20, as designed by DJB.
> 
> ---
> 
> While we're at it, I note that RFC 8439 is slightly at odds with
> existing implementations as well (I know of Libsodium and my own
> Monocypher). Instead of using a genuine 32-bit counter, we initialise
> the Chacha block just like the RFC say we should, then we pretend we
> had a 64-bit counter all along. That way we can use the same core loop
> for all variants: original DJB, IETF, and XChacha20.
> 
> The only difference is what happens when we overflow the 32-bit
> counter. This can happen in two cases:
> 
> - We use RFC 8439, and the message is too long (>256 GiB). This is
>   arguably an error, and the user must make sure it never happens.
> - We use XChacha20, and the message exceed 256 GiB. This should be
>   allowed, to eliminate a dangerous edge case.
> 
> Would it be possible to add an note to RFC 8439, that explicitly allows
> implementations to increment the least significant word of the nonce
> when the counter wraps back to zero?

Please don't. Overlapping ranges make bounds analysis way harder, and most importantly generating the same keystream for (key, nonce, large message) and (key, nonce + 1, message) is unexpected, contradicts the definition of the cipher, and can leak plaintext when sequential nonces are in use. Sequential nonces are a perfectly acceptable and widespread practice, especially with ChaCha20 where the nonce is too small for random nonces, although to be fair I don't know what endianness is most commonly in use.

In fact, if a library implements this behavior in plain ChaCha20, I would report it as a security issue. Either applications never generate messages longer than 256GiB, in which case failing after the overflow would make no difference, or they are insecure if they use sequential nonces in little endian.

If you offer a short-nonce long-counter variant, that's different since 32-bit counter overflow will not increase the application-provided nonce.

> That's a detail, though. My most
> important request remains that XChacha20 use all 64 bits for its
> counter.
> 
> Thank you for your time,
> Loup.
> 
> 
> _______________________________________________
> CFRG mailing list
> CFRG@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>