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

Jeffrey Walton <noloader@gmail.com> Sat, 26 January 2019 03:21 UTC

Return-Path: <noloader@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 CD9CF1310F4 for <cfrg@ietfa.amsl.com>; Fri, 25 Jan 2019 19:21:03 -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 9PPI0OtUMxjH for <cfrg@ietfa.amsl.com>; Fri, 25 Jan 2019 19:21:01 -0800 (PST)
Received: from mail-it1-x143.google.com (mail-it1-x143.google.com [IPv6:2607:f8b0:4864:20::143]) (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 E568F1310F0 for <cfrg@irtf.org>; Fri, 25 Jan 2019 19:21:00 -0800 (PST)
Received: by mail-it1-x143.google.com with SMTP id z20so12536083itc.3 for <cfrg@irtf.org>; Fri, 25 Jan 2019 19:21:00 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:reply-to:from:date:message-id:subject:to; bh=vIstwHcDGU967ceVjkGq7fvrkqn/UfMES9Nakv1C7Sg=; b=hvhaWOkuG2ME+grf5xmCIvdkdFrCPQ0oFLGM000lz+MnWaqjXyFSLPqu2kYbwTDJ8+ cJ/GXkrB3dh+ozQJrIS/SCNwFSCP0+MJbHPqIZtsz/1nTHOdr7/L9MJPu/vr2Wl4sX89 eVlqvCOx3sciRCUFiK7Jt6uyh+bhYeDBDnj4XgORomRrsq8ZGOEtQnPRtSj9x2JvmuFJ +1YpaoQmp9V/IxsVD4lNbBew02cS2dhc4+Y1ijZoKioAiGiPVRzF7ioCQUE+lObH/1oZ StsvkBPhFTPivwyOPdfcg+v96RERqL+5qc6kBC2iQL5hvscO5RAw/dMOuKqvgj+n4Ng7 JCcA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:reply-to:from:date:message-id :subject:to; bh=vIstwHcDGU967ceVjkGq7fvrkqn/UfMES9Nakv1C7Sg=; b=rk+OFpj8MBNugZrs704KI7DT2jiTEITjA9qjFezrjdNHTHKi2dZA/OANDfa8gkBuhl yLoYvbRfYTPFxR6jlhvFx+uBPY7wte9HhUkoaSiVd0lNI7kzJXxHfFiAEpq91vuY/Gra Jj2vLOJeEpWx+QZdKF6y0kDNmkGhpuXB0qUyF0O/zvENwlyYVj/cUbotcz5ZoqFouPvl bxXY7Gg7YbR15xb+eUOUvHqyEgA2S5jzgkelVk/8+PGPL/RWR6jgzgYjOIlTRsw+bYex IbryaYagKzRM6FT0qkza5fOwuoViTKF2mAiyfs58oo+I40WaH5pGbmJe2w58s/+pSXGP jNHw==
X-Gm-Message-State: AJcUukcyuBbrK+iANJyX6AkU613MLCQdgG3DPcsIw+Ho4/al9SYskTcF hFNc9Fn2X5E/K37I5/grLTXbIJgYVJzKKzk/b4FoaCva
X-Google-Smtp-Source: ALg8bN7wkZmjiPEy75WMp+d6RIlkn7t4s49VBWScCzUNogvoDkT6Kmk9ybuPtCEPrOQQEfwHYlNkVrRfHNh6Y2i+j6w=
X-Received: by 2002:a02:2b2d:: with SMTP id h45mr8673549jaa.75.1548472860134; Fri, 25 Jan 2019 19:21:00 -0800 (PST)
MIME-Version: 1.0
Reply-To: noloader@gmail.com
From: Jeffrey Walton <noloader@gmail.com>
Date: Fri, 25 Jan 2019 22:20:38 -0500
Message-ID: <CAH8yC8=0Y6qK0dHauib8fM-ybGozJJRA7b5vKnu8-dPVxwytLQ@mail.gmail.com>
To: cfrg@irtf.org
Content-Type: text/plain; charset="UTF-8"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/gsOnTJzcbgG6OqD8Sc0GO5aR_tU>
Subject: [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 03:21:04 -0000

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.