Re: [CFRG] XChacha20 counter size

Scott Arciszewski <scott@paragonie.com> Sat, 26 December 2020 00:10 UTC

Return-Path: <scott@paragonie.com>
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 F2EE73A0E61 for <cfrg@ietfa.amsl.com>; Fri, 25 Dec 2020 16:10:57 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.898
X-Spam-Level:
X-Spam-Status: No, score=-1.898 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, SPF_HELO_NONE=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=paragonie-com.20150623.gappssmtp.com
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 2dLZIRvuSLGB for <cfrg@ietfa.amsl.com>; Fri, 25 Dec 2020 16:10:55 -0800 (PST)
Received: from mail-lf1-x12d.google.com (mail-lf1-x12d.google.com [IPv6:2a00:1450:4864:20::12d]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 850823A0E5F for <cfrg@irtf.org>; Fri, 25 Dec 2020 16:10:55 -0800 (PST)
Received: by mail-lf1-x12d.google.com with SMTP id m25so12035675lfc.11 for <cfrg@irtf.org>; Fri, 25 Dec 2020 16:10:55 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=paragonie-com.20150623.gappssmtp.com; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=mI3UdGxLvIuF72ae01zvjCdDWlOIfQBR1QXXmssELb8=; b=fyYIRSEleqZ1tydzDI9TSyaKqoYaAR2V6bUBNuIO9LJ6iru10DTc3/FI0eHQSQmCPO U6loIRLJu6QniYeSq3Li3ABakj7JZRRKA5XRPfCfMQU0Vodt+ilaGZlOWIt22BZ/fyn7 4nBj51gBU2irtyosFZMFI0jKKD7YeNWOG85BU4CFBS3Re9BzpqNfMvWgklCMg2qJBfLN j/x/zHgJ1timYone2P9a9vAdTcB038J+CEM7LRf5nvv7/zjZdMJdy/UMNmd15mzArmYA JZtkv1QQ2RaKLUZApU4xgqTjn5punl1Ttf9Jw/+hgil3/+5t8TBgG/qKckdpHs0hUD3q mykQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=mI3UdGxLvIuF72ae01zvjCdDWlOIfQBR1QXXmssELb8=; b=Or8rzAd87EfoYPc0dQYCyNM+KKJ+7eOXM0kE5YKySMUkOxzV4Fo2F8dsd+yN9Jk1xz cALyIYvYGRMzk6BJO5nt8cJgbnR1ccJlMceySzCMnnki9CueQ55FcICbSaqJTi9ggTVH A9tHV7EjZIh9luIGJXjWdeyqxyAIZ1et6x7UZRYWyFa3axdCVMppopPCOKTgS0hbwGkg W6r64WgWAzjNWBJ4/LqBA07DW4FxxzNOdhx9RAxMhaTGxmJ8IW0JpogrrJrDEKm2FCPv tLPEyIgPDzG8jEN8KG5mTatWloukwwLzVnTqeLZ1vC/pCoMvPQOUxa7GuDXmKm6p7nQL pi6g==
X-Gm-Message-State: AOAM532eKvjb5ozhAYNrX/hW2pu/LCI7oK0GnVwgmOeqik1zr3ZI+64N BOjZ4yFF7Ayo2O/rsfdjidXQ4iobzcRvcHf12drfZA==
X-Google-Smtp-Source: ABdhPJzmhlBKl1/Tnh9Wr64CEGXk1cl7vNFPsnChV/lRfJN5JmoTKx578UUULgTQIE6dh4rsKzqQuxSAZIswIesKr4Q=
X-Received: by 2002:a2e:996:: with SMTP id 144mr16098287ljj.341.1608941453576; Fri, 25 Dec 2020 16:10:53 -0800 (PST)
MIME-Version: 1.0
References: <e632e3291ced05b29c55fea0f064258cb3abfc1a.camel@loup-vaillant.fr> <2ad966e9-70f7-4201-884d-6ef0257fe839@www.fastmail.com>
In-Reply-To: <2ad966e9-70f7-4201-884d-6ef0257fe839@www.fastmail.com>
From: Scott Arciszewski <scott@paragonie.com>
Date: Fri, 25 Dec 2020 19:10:41 -0500
Message-ID: <CAKws9z3OnPaYiRTxStwCVQHY=rZoDVP7aXBE+yWPXLkL-cKhVA@mail.gmail.com>
To: Filippo Valsorda <filippo@ml.filippo.io>
Cc: IRTF CFRG <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="000000000000ce1f3005b752df04"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/LFrvhL8fwRTfhTSLxTwdNFMv_AI>
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: Sat, 26 Dec 2020 00:10:58 -0000

On Fri, Dec 25, 2020 at 6:59 PM Filippo Valsorda <filippo@ml.filippo.io>
wrote:

> 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
>
>
> _______________________________________________
> CFRG mailing list
> CFRG@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg



 As the author of the XChaCha RFC draft, I view making XChaCha20-Poly1305
incompatible with the IETF's ChaCha20-Poly1305 a non-goal.