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

Neil Madden <neil.e.madden@gmail.com> Tue, 18 December 2018 20:19 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 [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id D334D130F28 for <cfrg@ietfa.amsl.com>; Tue, 18 Dec 2018 12:19:59 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.997
X-Spam-Level:
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: 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 9ASkGn-P2v3j for <cfrg@ietfa.amsl.com>; Tue, 18 Dec 2018 12:19:58 -0800 (PST)
Received: from mail-wr1-x42d.google.com (mail-wr1-x42d.google.com [IPv6:2a00:1450:4864:20::42d]) (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 7914F130F23 for <cfrg@ietf.org>; Tue, 18 Dec 2018 12:19:57 -0800 (PST)
Received: by mail-wr1-x42d.google.com with SMTP id t6so17058158wrr.12 for <cfrg@ietf.org>; Tue, 18 Dec 2018 12:19:57 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=yvBMCB/H7n0YzquLgyQA4BO42MYCQK7h9YRSr3ORino=; b=Kgo0rL5Y1Q8/eBFETJXZsvh454zH4yOS8ec1JsMQhFNKb7brUnYkmQ5x2GT6ugobx8 M9006fQ071dDuNFoZoVwKbKMnuGVHAIokkM7eB+Ge3dv4NTSgr/puBNEjgRTu53ytL3P Lz3twXumoFrAvpipczLEg12U87kipdP+frNBFNKoRQcWajQdgcWysOCY6WmrHy3fxckM fANSJHDdL6+S3zgXlbNQcxmuQGN9CIIDZW3G8U04LjXzIHun+2mZh0rRI7UyKfNPvr1x bF/yDI5AwMOLggQTN1c/qKzGxuF+hvsRhCk4PkLCC+giN5QIbnUUQ6DUQZWkAiv4VzcK y+rg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=yvBMCB/H7n0YzquLgyQA4BO42MYCQK7h9YRSr3ORino=; b=LlliXCvKji6xc9AP53Wv4xfY4QDC3vxmJ0fajWMZqhHCNZrLNeK9tR/kyGEDQEj44H trnXSll3E9zQy6/04x+5/3umcs0JpalbVMe9uYkBLx0Eg1DcPfrJV3fWJedRnpCgptc9 Mb8RD1eYO12CEjzrLgnTCi8iAF8CjwJB+aW3qaVh3vL0WJA3ybk3G53pxQ1T5dGmdtFr dpU8ZJUJX+rEu+6pZ+8KcVGzD6U3jNT9RySRm2AjmKpGd1Tb9oTLSFCSxe+6n9Z/sOXM m8NUQ8WrPtzEvvLf0OBoXdQ95m8GWuwKiHajF4wFihxREZcDtTEGnKoNkt9l2MVT98GK qxZw==
X-Gm-Message-State: AA+aEWY2J7mdIyToLJABRkDk8mMRQSmbtktiIaghjYqUue0LY6KopCSj Q5VM66yByNnDDcRGepQqSXQ=
X-Google-Smtp-Source: AFSGD/XNmAKU39mYsooICraHyayssJ+pc0lQJ0BWOPprbiwl50WFCr1taXYGkyc6jzaWnThwSY16gQ==
X-Received: by 2002:adf:f149:: with SMTP id y9mr17299411wro.284.1545164395906; Tue, 18 Dec 2018 12:19:55 -0800 (PST)
Received: from [192.168.1.65] (92.150.32.217.dyn.plus.net. [217.32.150.92]) by smtp.gmail.com with ESMTPSA id q9sm5946815wrp.0.2018.12.18.12.19.54 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 18 Dec 2018 12:19:54 -0800 (PST)
Content-Type: multipart/alternative; boundary=Apple-Mail-F6DC6DDC-A34C-4E1C-B504-5B3BD60EF82D
Mime-Version: 1.0 (1.0)
From: Neil Madden <neil.e.madden@gmail.com>
X-Mailer: iPhone Mail (16B92)
In-Reply-To: <F9E1D18B-2C9E-4ED1-8F23-C25A0A8AF2C6@gmail.com>
Date: Tue, 18 Dec 2018 20:19:54 +0000
Cc: cfrg@ietf.org
Content-Transfer-Encoding: 7bit
Message-Id: <9CAF2774-33BF-4CE1-BCDF-98EA9DE1C643@gmail.com>
References: <A44A80BE-030B-4D1E-9889-F727EB0BF142@gmail.com> <CACEhwkQKHkHEyLbmZ6oeDtvuvmwgifyuTUsb6Xy1CDR+4RE9PA@mail.gmail.com> <F9E1D18B-2C9E-4ED1-8F23-C25A0A8AF2C6@gmail.com>
To: Mihir Bellare <mihir@eng.ucsd.edu>
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/_G3fSuliJtVK9pHVK07UXRAycxM>
Subject: Re: [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 20:20:00 -0000

On further consideration, there are enough details* even with an encrypted last block that I’d like to have a proof of correctness for it before I recommend anyone use that approach. As an RFC is not the place for security proofs, I’ll withdraw my suggestion to add this to the draft and concentrate on S2V. 

* eg if somebody appends a block that is a duplicate of the SIV that would not prevent decryption, but then the ciphertext would also not be the last block so would not be decrypted anyway, which means the tag would be computed over the ciphertext and not the plaintext. I need to think about it some more. 

— Neil

> On 18 Dec 2018, at 18:51, Neil Madden <neil.e.madden@gmail.com> wrote:
> 
> 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 <mihir@eng.ucsd.edu> 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 <neil.e.madden@gmail.com> 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] 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,
>>> 
>>> Neil
>>> _______________________________________________
>>> Cfrg mailing list
>>> Cfrg@irtf.org
>>> https://www.irtf.org/mailman/listinfo/cfrg