Re: [Cfrg] I-D Action: draft-nir-cfrg-chacha20-poly1305-01.txt

Stefan Bühler <source@stbuehler.de> Fri, 28 February 2014 11:14 UTC

Return-Path: <source@stbuehler.de>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id A8CD51A0112 for <cfrg@ietfa.amsl.com>; Fri, 28 Feb 2014 03:14:55 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.802
X-Spam-Level:
X-Spam-Status: No, score=0.802 tagged_above=-999 required=5 tests=[BAYES_50=0.8, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HELO_EQ_DE=0.35, MIME_8BIT_HEADER=0.3, RP_MATCHES_RCVD=-0.547, SPF_PASS=-0.001] autolearn=ham
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 l3-XNvyFFkIQ for <cfrg@ietfa.amsl.com>; Fri, 28 Feb 2014 03:14:53 -0800 (PST)
Received: from mail.stbuehler.de (stbuehler.de [IPv6:2a01:4f8:150:5244::2]) by ietfa.amsl.com (Postfix) with ESMTP id 2BF331A0179 for <cfrg@irtf.org>; Fri, 28 Feb 2014 03:14:53 -0800 (PST)
Received: from chromobil.localdomain (unknown [IPv6:2a02:8070:a117:de00:baca:3aff:fed7:a10a]) by mail.stbuehler.de (Postfix) with ESMTPSA id 939D95E1C1F; Fri, 28 Feb 2014 11:14:49 +0000 (UTC)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=stbuehler.de; s=stbuehler1; t=1393586089; bh=Ke2oX6zcwRR/+QzlHhdFx9Vnaea4QDFPFeDCAvlC4hs=; h=Date:From:To:Subject:In-Reply-To:From; b=WBS5h4WsfkRs4kXS1laUUg78gZ8l7O2bQoMRBpJsibzCin5e8EReSxx+ldQeFfFjE vns/IcqmbP9tksuGFvLVQlhzjF5re/7f2USIIrPW/XIW3UaJr0stHQrztu00PC59h4 kBX0XfH9X8VHe5SbYjXEO5etsaOHRgvpEH/7NgNA=
Date: Fri, 28 Feb 2014 12:14:48 +0100
From: Stefan =?UTF-8?B?QsO8aGxlcg==?= <source@stbuehler.de>
To: Yoav Nir <ynir@checkpoint.com>, cfrg@irtf.org
Message-ID: <20140228121448.1c123bab@chromobil.localdomain>
X-Mailer: Claws Mail 3.9.3 (GTK+ 2.24.22; x86_64-pc-linux-gnu)
In-Reply-To: <16BFC02D-480F-472E-B781-56D1A8EF0EE5@checkpoint.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/euuRvOul8jYqP45HzTtxLrSZpkE
Subject: Re: [Cfrg] I-D Action: draft-nir-cfrg-chacha20-poly1305-01.txt
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Fri, 28 Feb 2014 11:16:59 -0000

Hi,

I propose using "HChaCha20" (analog to HSalsa20) to compress larger
nonces:
* supports nonce lengths of 8 and 24 bytes, and everything between by
  prefixing with zeros.
  (I can't claim to have understood the paper on XSalsa20/HSalsa20
  completely, so I'm not sure whether more than one HSalsa20 step would
  still be covered by the proof; but I guess it should work.
  This means one could support almost any nonce length >= 8 bytes)
* uses the original ChaCha20 algorithm (some implementations might not
  allow changing the length of nonce/counter; these implementations
  are still compatible with a nonce length of 8 bytes)
* compatible with draft-agl-tls-chacha20poly1305-04 (using nonce length
  of 8 bytes, plain ChaCha20)

Define P: extract 256-bit from 512-bit
P(z0, z1, z2, z3) := (z0, z3)  # z_i are 128-bit

Define HChaCha20: takes 256-bit key, 128-bit nonce
HChaCha20_k(n) := P(doublerounds^10(x))
    where
    x := (salsaconst, k, n)

Define Q: calculates HChaCha from 64-bit nonce and 512-bit ChaCha
Q(n, x) := P(x) - (salsaconst, n)  # subtraction on 32-bit words

HChaCha20_k(n) = Q(n, ChaCha20_k(n))
(Q is used in the proof: it is a public computation (salsaconst and
nonce are public) of HChaCha20_k(n) from ChaCha_k(n), and maps uniform
random strings to uniform random strings)

Define XChaCha20: takes 256-bit key, 192-bit nonce and a little-endian
64-bit counter
XChaCha20_k(n, i) = ChaCha20_k1(n2, i)
    where
    (n1, n2) := n # n1 is 128-bit, n2 64-bit
    k1 := HChaCha20_k(n1)

The proof for XSalsa20/HSalsa20 should work for XChaCha20/HChaCha20 too
afaics. (http://cr.yp.to/snuffle/xsalsa-20110204.pdf
on http://cr.yp.to/snuffle.html)

Now depending on the length of the nonce either use ChaCha20 (8 byte
nonce) or XChaCha20 (24 byte nonce).

I suggest the zero padding should be prefixed to the nonce, so the last
8 bytes of the AEAD nonce are always the 8 bytes used in the ChaCha20
stream. If only those are changed (typical nonce increment) the
key/nonce compression "k1" can be cached.

Padding nonces should be safe: if the input nonces were unique, the
padded nonces are unique too. As nonces are often counters anyway, they
already are almost 0 - adding more zeros shouldn't hurt.

regards,
Stefan