Re: [Cfrg] How to handle block counter wrap in IETF's ChaCha algorithm?

Yoav Nir <ynir.ietf@gmail.com> Sat, 26 January 2019 18:40 UTC

Return-Path: <ynir.ietf@gmail.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 83586130F26 for <cfrg@ietfa.amsl.com>; Sat, 26 Jan 2019 10:40:22 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Level:
X-Spam-Status: No, score=-1.999 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_NONE=-0.0001, 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=gmail.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 UH-FmUwGDTiu for <cfrg@ietfa.amsl.com>; Sat, 26 Jan 2019 10:40:20 -0800 (PST)
Received: from mail-wr1-x42e.google.com (mail-wr1-x42e.google.com [IPv6:2a00:1450:4864:20::42e]) (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 F1472130F19 for <cfrg@irtf.org>; Sat, 26 Jan 2019 10:40:19 -0800 (PST)
Received: by mail-wr1-x42e.google.com with SMTP id r10so13557120wrs.10 for <cfrg@irtf.org>; Sat, 26 Jan 2019 10:40:19 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=Q4HOm1LoZ1/VN1SfjqPTz/6VIW56jvnckAkJK0Rk9Ig=; b=t0xJepvmaYcaxY09s1QMqSpUKO4lfUJorU2jlcZIRSacpASMnW5r+63UCTKOWTbmIX 6H5RKvVhXiFkoPp3l/Af856QrawVBKyGJPpDvkz2lDv/7ngksYn/by9B6b83MO9oIf8i tIwT+cKTl0UZCu6BjH/J4SMP/ELJ+gOu1cjeFkTnWJiJ3pl6IgvjfFjpPCrccRyRpjdg DEQbTjpM9z9Al1B4paxyt9j72J/AGcCNC+hKq6laJZGHbBgG2wfdFAgnZ3Y/7MRyzzEJ S40PCx0UfETBYJnEsh9a6k88zTUny6f+/1graVHCOlsDOMpaMS3jz033xFMRF18AGAfp 6Kew==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=Q4HOm1LoZ1/VN1SfjqPTz/6VIW56jvnckAkJK0Rk9Ig=; b=Q0KflE5r6NIOlT1f/DpDjudNAo+ehGx0vGzk9yQD4x6eyRspnkruLB3nNLpHZki9Bs lQkja7tQVWrqoY3ZuVHnvV16HNreWIWc4No7Vv0SN8aWas0OzV+3SSTMeCYFJOP2Xtb7 jyFuZNso091Vd4LHFUHWQAONAl8YoC7yGxwULcmHuHryRpYd9pnfkxx4NXXOXZpYIf6r jOqsvN4LCgf298dpMmiGtRxyrKY+1FW248WUl1iSIgKrKRSXMPL9RMES/sgvkJo++JmP BTozg2wFa5id9qq77If6HbbGv/Om7IAijZxWlyNBlc0QepQeeRTn+/xawHPk80iB3f8L En2Q==
X-Gm-Message-State: AJcUukcJL3NQE2E685GQCFL5ob/U9tv69EB3vYuKdlAL2JH3iaG/KKuX F00HdNzn+A8pDVleO/Bynag=
X-Google-Smtp-Source: ALg8bN726NE13+IjJLCm9snPsbmeyiI3FnD72LuQahGMDYd4cMG1S0f+00VTO/OnlQ3n9072vXIN+Q==
X-Received: by 2002:adf:a50c:: with SMTP id i12mr15048962wrb.220.1548528018234; Sat, 26 Jan 2019 10:40:18 -0800 (PST)
Received: from [192.168.1.12] ([46.120.57.147]) by smtp.gmail.com with ESMTPSA id h62sm51009009wmf.11.2019.01.26.10.40.16 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sat, 26 Jan 2019 10:40:17 -0800 (PST)
Content-Type: text/plain; charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 12.2 \(3445.102.3\))
From: Yoav Nir <ynir.ietf@gmail.com>
In-Reply-To: <CAH8yC8=0Y6qK0dHauib8fM-ybGozJJRA7b5vKnu8-dPVxwytLQ@mail.gmail.com>
Date: Sat, 26 Jan 2019 20:40:14 +0200
Cc: cfrg@irtf.org
Content-Transfer-Encoding: quoted-printable
Message-Id: <DA990C3D-DD2A-4636-8E92-83FE6C39438B@gmail.com>
References: <CAH8yC8=0Y6qK0dHauib8fM-ybGozJJRA7b5vKnu8-dPVxwytLQ@mail.gmail.com>
To: noloader@gmail.com
X-Mailer: Apple Mail (2.3445.102.3)
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/1E8mE9uByXA4HWqyYO_jwz4nLZ8>
Subject: Re: [Cfrg] How to handle block counter wrap in IETF's ChaCha algorithm?
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 Jan 2019 18:40:22 -0000

Hi

For a little context, if you are using straight ChaCha20 as a cipher, the initial block counter should always be zero. This is true both for Bernstein’s original version (with a 64/64 split of block counter/nonce) and with the RFC 8439 version (with the 32/96 split).

The only reason we made this a parameter is because of the AEAD construction where we use the zero block counter for creating the Poly1305 key, and encryption starts at block counter = 1.

In retrospect we could have made the API simpler by eliminating this parameter and always starting with zero.  Generating the Poly1305 key only requires a unique value for block counter, not any specific one.  We could have,  perhaps should have gone with 0xffffffff.

Unfortunately, by now it’s too late to make this change, as this algorithm is implemented in many libraries. That said, the only thing that is seeing a lot of usage is the AEAD, and for the AEAD the initial block counter is set at 1.

Yoav

> On 26 Jan 2019, at 5:20, Jeffrey Walton <noloader@gmail.com>; wrote:
> 
> Hi Everyone,
> 
> This question is moved from another list to CFRG. It was suggested
> CFRG is a better forum for the question.
> 
> I'm working on test vectors for an implementation of the IETF's
> version of ChaCha from RFC 8439. According to Section 2.4, page 9
> (https://tools.ietf.org/html/rfc8439#section-2.4):
> 
>   The inputs to ChaCha20 are:
>      o  A 256-bit key
>      o  A 32-bit initial counter.  This can be set to any number, but will
>         usually be zero or one...
>      o  A 96-bit nonce.  In some protocols, this is known as the
>         Initialization Vector.
>      o  An arbitrary-length plaintext
> 
> Now a test vector. We set:
> 
>    Key - All 0's
>    IV - All 0's
>    Initial Counter Block - 0xfffffffe
>    Plaintext -  256 bytes of all 0's
> 
> After the first two 64-bit blocks the counter will wrap around to 0.
> This is where the problem arises.
> 
> One implementation I am aware wraps the block counter. It produces a keystream:
> 
> 032CC123482C31711F94C941AF5AB1F4155784332ED5348FE79AEC5EAD4C06C3
> F13C280D8CC49925E4A6A5922EC80E13A4CDFA840C70A1427A3CB699166991A5
> ACE4CD09E294D1912D4AD205D06F95D9C2F2BFCF453E8753F128765B62215F4D
> 92C74F2F626C6A640C0B1284D839EC81F1696281DAFC3E684593937023B58B1D
> 76B8E0ADA0F13D90405D6AE55386BD28BDD219B8A08DED1AA836EFCC8B770DC7
> DA41597C5157488D7724E03FB8D84A376A43B8F41518A11CC387B669B2EE6586
> 9F07E7BE5551387A98BA977C732D080DCB0F29A048E3656912C6533E32EE7AED
> 29B721769CE64E43D57133B074D839D531ED1F28510AFB45ACE10A1F4B794D6F
> 
> Another implementation I am aware wraps the block counter, but it also
> increments the high word of the nonce, similar to the way original
> ChaCha used a 64-bit block counter. It produces a keystream:
> 
> 032CC123482C31711F94C941AF5AB1F4155784332ED5348FE79AEC5EAD4C06C3
> F13C280D8CC49925E4A6A5922EC80E13A4CDFA840C70A1427A3CB699166991A5
> ACE4CD09E294D1912D4AD205D06F95D9C2F2BFCF453E8753F128765B62215F4D
> 92C74F2F626C6A640C0B1284D839EC81F1696281DAFC3E684593937023B58B1D
> 3DB41D3AA0D329285DE6F225E6E24BD59C9A17006943D5C9B680E3873BDC683A
> 5819469899989690C281CD17C96159AF0682B5B903468A61F50228CF09622B5A
> 46F0F6EFEE15C8F1B198CB49D92B990867905159440CC723916DC00128269810
> 39CE1766AA2542B05DB3BD809AB142489D5DBFE1273E7399637B4B3213768AAA
> 
> I don't believe the issue arises in Bernsein's version of ChaCha
> because the block counter is 64-bits and always starts at 0. Bernstein
> does not allow arbitrary values for the initial block counter. The
> constraint is unstated in Bernstein's paper on ChaCha, but it is
> obvious when examining his reference implementation (from chacha-ref.c
> version 20080118):
> 
>    void ECRYPT_ivsetup(ECRYPT_ctx *x,const u8 *iv)
>    {
>        x->input[12] = 0;
>        x->input[13] = 0;
>        x->input[14] = U8TO32_LITTLE(iv + 0);
>        x->input[15] = U8TO32_LITTLE(iv + 4);
>    }
> 
> My question is, what should happen when the block counter wraps?
> 
> Thanks in advance.
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg