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

Neil Madden <> Tue, 18 December 2018 18:51 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id CA36B1311E9 for <>; Tue, 18 Dec 2018 10:51:53 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.997
X-Spam-Status: No, score=-1.997 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, HTML_MESSAGE=0.001, MIME_QP_LONG_LINE=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 (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id Sw3RLAgUTBSL for <>; Tue, 18 Dec 2018 10:51:51 -0800 (PST)
Received: from ( [IPv6:2a00:1450:4864:20::335]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id D182D128D09 for <>; Tue, 18 Dec 2018 10:51:50 -0800 (PST)
Received: by with SMTP id d15so3715440wmb.3 for <>; Tue, 18 Dec 2018 10:51:50 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=f789sVqEjOohOc6KoMkRrfVu0HzSwOY3lUiPNF4ZfA4=; b=enob03xiJYbQrhbuRT+vteJzhApHXNd4frijXNQQ3pndIjOfxNC0ZaGrmpoHmyeAoC vkO0vr+IstVEJRZPlto3bnfp27eMGCISIlRPxO9PyLNYXCI/cHuxNTdJGlCCyhGtlyf/ 5fXQd54zlGCRpaeNgaH0yJn1gqvOaYVix4EO7q+m+7uZzbH41chYcAEPEyt1W3ZO6eFA cmluCTmb8Xs4D5MgWdxcaXdZPtImO+1Y1lWNXhQPgjshQ4BrcGPYkyP6bMzKGZux+eXq tW/cU5rSAFueHsxezipI0oBdF1fIioQaBMm3JwFTTMYoepuMuOtKsQjd8bBgTPud5o3S V26Q==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=f789sVqEjOohOc6KoMkRrfVu0HzSwOY3lUiPNF4ZfA4=; b=hXhaTpi8RAEm9fq/rvzE0U9LG2ePIUEuZc7G/aqPNvVha3vKuqGOoR9YDmGbmT2R3B wQ5BDxXTU3TNxW5SFzPkGXQ/gBBfO9oSMrLpeDVnn7aWx4vZU+RvafdbkPLOdgLh3bTD yuWqJfxLucLYgdZIQLGp18JTaKWUOZay7iOZ3NhB6ru3jaFtwyB+wCwlnayall/hYYtz FzAyCxw6rL/mmBQDWF+rDjgwdTHrrQcO1l2cOcWhWaZb5PU7uidBg56jFaW05W5nYxKR 2pN6ZBEvxSeEMKgKXpC6pA6QbHjxOhcU0ouz5RllkfLIKKsoPG0VUdqnW/+cfKaatSTF tycQ==
X-Gm-Message-State: AA+aEWbRcHnQyVkg3OWQ6tnA3/roj374GeOOBP9qThyuIx2SEUJ3DXPW Fpyy9yOK+iYMqNW9E3aJ2EI=
X-Google-Smtp-Source: AFSGD/UTbpwTFNmNJA4sV5M1yS38cR6SQOP1DMnYeM0eDwrlvL+XbIUdBdnxHESCMWBvAOeYu/aVsA==
X-Received: by 2002:a1c:cc2:: with SMTP id 185mr4490120wmm.1.1545159109115; Tue, 18 Dec 2018 10:51:49 -0800 (PST)
Received: from [] ( []) by with ESMTPSA id j24sm3949760wrd.86.2018. (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 18 Dec 2018 10:51:48 -0800 (PST)
Content-Type: multipart/alternative; boundary=Apple-Mail-D4B774F1-38A9-4BA6-A14B-1CDD7C09DB33
Mime-Version: 1.0 (1.0)
From: Neil Madden <>
X-Mailer: iPhone Mail (16B92)
In-Reply-To: <>
Date: Tue, 18 Dec 2018 18:51:47 +0000
Content-Transfer-Encoding: 7bit
Message-Id: <>
References: <> <>
To: Mihir Bellare <>
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:51:55 -0000

In the context of SIV, encrypting the last input prevents any further extension, as any extension will destroy the SIV rendering the plaintext undecryptable and the tag then unverifiable. You’re right that as a general purpose MAC it would either need to have a fixed number of inputs or else encode the length into the first input. 

— Neil

> On 18 Dec 2018, at 18:29, Mihir Bellare <> wrote:
> 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). 
> Mihir
>> 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