[Cfrg] Building a vector-input MAC by chained construction

Neil Madden <neil.e.madden@gmail.com> Tue, 18 December 2018 16:55 UTC

Return-Path: <neil.e.madden@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id 4D80813111F for <cfrg@ietfa.amsl.com>; Tue, 18 Dec 2018 08:55:44 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.099
X-Spam-Status: No, score=-0.099 tagged_above=-999 required=5 tests=[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 ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id AJrk7-cZSCUQ for <cfrg@ietfa.amsl.com>; Tue, 18 Dec 2018 08:55:42 -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 6BC7C130EDE for <cfrg@ietf.org>; Tue, 18 Dec 2018 08:55:42 -0800 (PST)
Received: by mail-wr1-x42e.google.com with SMTP id u4so15675281wrp.3 for <cfrg@ietf.org>; Tue, 18 Dec 2018 08:55:42 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:content-transfer-encoding:mime-version:subject:message-id:date :to; bh=w6n9qUnII28kkc6JERGYxlHuvO2l3gd41VDWCWkRtOg=; b=Su6vEMkbnkbVmYKAveDpQh5WuHLGCuVYYNWev4BsyBGACqaoxz1xj8Rtu+aOPSXT/c wLt/oPKPX9+cKXsUOtfb7/VgMqXsbUCy3KET+0VyYjQOhG/NZ/lb2aqIm096n5LpSeMW MCw5d7fQD0ahvkdRRP5IMym5e0PT/ntOsLgoR6Qwy+HpJEMC5aRgJ1n76fE1x/I1GqRV 3o1/7KvOrcyHZoaPxUvGTxeRa7lzP/FIOgL+pVbdZhyy1kfndpaSZSrhjioCQqjkwwgy /pElG5GQ9Nrrjpn8nf+9KALMTqTKOBHgRyJEXaM5CLQr/PAXYGXUJfoS1p36ayM/+zTP lyMQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:content-transfer-encoding:mime-version :subject:message-id:date:to; bh=w6n9qUnII28kkc6JERGYxlHuvO2l3gd41VDWCWkRtOg=; b=WkyQkBhKCqhJYD0YvKwUvUycF/ZzytgUcDeopxdBh2pR9y4XIkRSGS4CmJS0GJpMVJ x41qA8N/CzIjafDsgX7jFlAaAbxGxyQre4cx4vb8NfKa0Cbt4TsO4mWzyLIEeTK2vf/q /1NCAjj6Cg+SsM1db9Pc6JgFZeuagw+CobyVs1yrWuWlVlOpxeXVeqi+sVAY1h5nwX5i P5rTjbU4vRq5UugB3DnWOuUHcjKTa165SvI50xSTAeQx5DDnNStQX0HHi36lIhVHJMgN cRpSyEi5Sq/QMofFKVlW64rn3lYMeqsTAQw9un0Hz1oditvJOVkXPw1ioBvGyBkgBLNL UKYQ==
X-Gm-Message-State: AA+aEWYKm03g8HpOQuuPjvuemyeH9TEwNejUVhsD3JG5Qfh0/G4CEv13 fFyblzRuyTJ7n8PZSdKl2F1GNIN0
X-Google-Smtp-Source: AFSGD/UgM/NFBpAw2ViL/mjLYpRANiJmlhHIrnW64lnaBWtESmMQbEGD5PFnat/R7vwX+h+sxjvWOQ==
X-Received: by 2002:adf:e983:: with SMTP id h3mr14860027wrm.232.1545152140367; Tue, 18 Dec 2018 08:55:40 -0800 (PST)
Received: from guest2s-mbp.lan ( []) by smtp.gmail.com with ESMTPSA id 10sm2669080wmy.40.2018. for <cfrg@ietf.org> (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 18 Dec 2018 08:55:39 -0800 (PST)
From: Neil Madden <neil.e.madden@gmail.com>
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: quoted-printable
Mime-Version: 1.0 (Mac OS X Mail 12.2 \(3445.102.3\))
Message-Id: <A44A80BE-030B-4D1E-9889-F727EB0BF142@gmail.com>
Date: Tue, 18 Dec 2018 16:55:38 +0000
To: cfrg@ietf.org
X-Mailer: Apple Mail (2.3445.102.3)
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/4ESyaebIsKbnbIpieQBwicrkiRU>
Subject: [Cfrg] Building a vector-input MAC by chained construction
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: Tue, 18 Dec 2018 16:55:44 -0000

While mulling over some ways to improve JOSE [1], I was looking at the Macaroons paper [2] and realised that the chained-MAC construction they use to allow new caveats to be appended to a Macaroon also serves as a way to convert a normal string-input MAC into one that takes a vector of strings as input instead. This is exactly what the S2V construction in AES-SIV does, and most of the detail in the SIV RFC (and my internet draft extending it to non-AES ciphers) is around S2V.

The chained-MAC construction used in Macaroons is basically the following. If you want to authenticate a vector of strings s[0]…s[n] with a key k, you do the following:

key = k
tag = null
for i = 0 to n:
    tag = MAC(key, s[i])
    key = tag

That is, on each iteration you simply use the tag from the last iteration as the MAC key.

Compared to S2V, this is very easy to implement and naturally generalises to different MACs (so long as the tag size is the same as the key size), however it would be costly if MAC has an expensive key setup.

Based on this observation I mocked up a variant of SIV that uses this instead of S2V. The code is almost comically simple - you just perform the above MAC calculation and then encrypt (in-place) the final element s[n] using a stream cipher (e.g. AES-CTR or XChaCha20) using the tag as the SIV. 

The paper [3] has security proofs for this construction based on the assumption that the MAC is a secure PRF (Construction 1 in section 3.1.1). Based on this, my plan is to include this construction as an alternative to S2V in the generalised SIV draft, unless there are strong objections. 

[1] https://neilmadden.blog/2018/12/16/simplifying-jose/
[2] https://ai.google/research/pubs/pub41892
[3] https://cs.nyu.edu/media/publications/TR2013-962.pdf

Kind regards,