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

Mihir Bellare <> Tue, 18 December 2018 18:29 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id CF0781311A6 for <>; Tue, 18 Dec 2018 10:29:42 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.999
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, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (1024-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id PCy0UNboZ69Z for <>; Tue, 18 Dec 2018 10:29:40 -0800 (PST)
Received: from ( [IPv6:2607:f8b0:4864:20::d2a]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 5A6741311A2 for <>; Tue, 18 Dec 2018 10:29:40 -0800 (PST)
Received: by with SMTP id p7so5916659iog.12 for <>; Tue, 18 Dec 2018 10:29:40 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=google; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=kIblGaUKqnxLVCV8csuI0ORxFebKpOftvHHiXLfDX8o=; b=VhxJaufLft6wUNfGgwvsVvqM0NDyl3AqwYvqcs4jMRlae0QocrLLaiVkNceMMPEYkL sE2YW+tnPFInIwUYZIIPk3+zvciXkgX/fbtcihgEbNrj13IzzBXqPF3K7520CS448FCI rx1LDiEJQAtb3bXMF2KTxq1uSs0aSmJwnYCJU=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=kIblGaUKqnxLVCV8csuI0ORxFebKpOftvHHiXLfDX8o=; b=Q29aB+JmOCumoxovDrmRR1AJIbSIWRYlaUKN89PPzcS+rs8Z70ky+Faihz6GFJUrBI O00zfO08/Z7wOuSTTdUcM5iooDnlwuWJ3IzThgednDTsab/pT8UuDRCPYtc98JLm1dJi 6c/LmIx1rM8WL/fV+ObF6S9AyXxcYTTgHF1wdxhIVPE15aR1DO3Ql4iTLoZ1+jdIC5o+ G5BqRYiemdHSKYcp96qPRIpBiyeIxTO2h3SzGclc4oytewlkiKMNceVnUhJkhC54W0kL 2flm9t9tC1t9jSYdkXxv4uiGbk7CPojKpxWfW1LvPbSJ3XIS+9ddugIY/TGH9u0tI4Fb qHbw==
X-Gm-Message-State: AA+aEWZfo6f3crrZprLqq2cVNvlCQNbD3cNa04jvwfh2MEgwc5dCTs4d O+ze4FtvYd+o2Vd0RPJX5UAs5Ta4b/72Yrmk7oQpXw==
X-Google-Smtp-Source: AFSGD/UbhqxynsyyJ7q6TxfMC8BT/ZXUQvQqcz8k4vm63PZJ0rj9l7aRWUBcRLq4quGQDM/O5f0JabSrBCJrxb0g9VA=
X-Received: by 2002:a6b:e305:: with SMTP id u5mr16405215ioc.85.1545157779582; Tue, 18 Dec 2018 10:29:39 -0800 (PST)
MIME-Version: 1.0
References: <>
In-Reply-To: <>
From: Mihir Bellare <>
Date: Tue, 18 Dec 2018 10:29:03 -0800
Message-ID: <>
Content-Type: multipart/alternative; boundary="000000000000931af4057d5014ad"
Archived-At: <>
Subject: Re: [Cfrg] Building a vector-input MAC by chained construction
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Tue, 18 Dec 2018 18:29:43 -0000

I may be missing something but this does not seem secure. Given the tag
tag1 = MAC(key,x1) of a length-1 vector x1, we can compute the tag of the
length-2 vector (x1,x2) as tag = MAC(tag1,x2).


On Tue, Dec 18, 2018 at 8:55 AM Neil Madden <> wrote:

> 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
> end
> 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]
> [2]
> [3]
> Kind regards,
> Neil
> _______________________________________________
> Cfrg mailing list