[Cfrg] AES-PMAC-SIV
Tony Arcieri <bascule@gmail.com> Wed, 08 November 2017 16:30 UTC
Return-Path: <bascule@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 1BD46128796 for <cfrg@ietfa.amsl.com>; Wed, 8 Nov 2017 08:30:00 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Level:
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, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-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 TJtlh4DMh3tc for <cfrg@ietfa.amsl.com>; Wed, 8 Nov 2017 08:29:57 -0800 (PST)
Received: from mail-ua0-x22e.google.com (mail-ua0-x22e.google.com [IPv6:2607:f8b0:400c:c08::22e]) (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 32BE31286B1 for <cfrg@irtf.org>; Wed, 8 Nov 2017 08:29:57 -0800 (PST)
Received: by mail-ua0-x22e.google.com with SMTP id f46so2334320uae.1 for <cfrg@irtf.org>; Wed, 08 Nov 2017 08:29:57 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:from:date:message-id:subject:to; bh=MB4otp9j7RxTHrN8FoV1ina0g04Bl0PhxH3OI6cHXCQ=; b=lm8pBcDizoGDVWtAo3aj6/v+VNGpRx9WaaHS39HAbMHbe9UsCcwNnc0iGWf1PkAdAP YTNNBwugVcxjrguqI0XHD5ofHb5mcf61lQWQAddEKtcj/tqzK9C/QDFBAUhHw2r0vJTE 1UmueKKlxshy1m6ZoE8YGs1Vv4/cnVUJ0dZdhsEUQqJDQm/yX50aNdc9/EAfmp/zgaw1 6I2pyvqa2bMuurgMloONw28o26TZH8PBipBLUd/UPEq10ZJ1v/96w9+2DrNEhnO4J4YY bdIswMu1rwVprOUn+p/BKidtCt5oqyM88KvizsttfkWB8muGBULVM0ZjsGYWmXKcSd7k uHdQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=MB4otp9j7RxTHrN8FoV1ina0g04Bl0PhxH3OI6cHXCQ=; b=BNejBEaLn+mOj2uDVqDzsh1PLMvRlnU0Y5gHiSfbsmsd+7ZZMNy+phrM1RD+VRzoD1 HnwtkJgHtSEm844XcPrc9D8fWnFv+CprNZGoUSBeBBzrZdOQ1Bz2e8P1vwrYLpfseXo8 +dgCLD7eBxEQmkTzPy+kU8QcyZaZtSPsJhxlS6YIuq1Ps4+z1Nj1pYwJPwA2UbFwBoU4 5+kMk/nM2gMKyjFcqZH5JkHk6VG/gteXtlJYnwKbIwvAdiB89JVDhrW32bJrFtDGSzq7 SDaYwEW210VRMN+JB6PMEsuSGIFgKl+hKiS7VAgWMMbTroqwIoVtIOO9TUPeI8XTBHkN CaqQ==
X-Gm-Message-State: AJaThX6vr4XfcCb3O45pOz9GLjUXM9duNsRh2rLLoeboIkt4ROCKRN/v np7zD16LWOG8/kWmupciBWOTuueW6RP9D5iEAbuAmO/w
X-Google-Smtp-Source: ABhQp+SWPr4L3b6ED2DboDF5KqR3xDiDhC+BAqd9mEKLuPeT3gHQUXfkFoueFLaCdJurxc6QmRd27GRAp2oX2aRZaSg=
X-Received: by 10.176.69.4 with SMTP id r4mr911813uar.125.1510158595858; Wed, 08 Nov 2017 08:29:55 -0800 (PST)
MIME-Version: 1.0
Received: by 10.103.14.199 with HTTP; Wed, 8 Nov 2017 08:29:35 -0800 (PST)
From: Tony Arcieri <bascule@gmail.com>
Date: Wed, 08 Nov 2017 08:29:35 -0800
Message-ID: <CAHOTMVJeb8+siu1j7CVQSGa+tiXDdvmPVp+GhDwdFjuWzD+L_w@mail.gmail.com>
To: "cfrg@irtf.org" <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="94eb2c0cfe06a926bf055d7b3209"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/rJQjDHJNtCTspXc-9RxfebOEALY>
Subject: [Cfrg] AES-PMAC-SIV
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.22
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: Wed, 08 Nov 2017 16:30:00 -0000
I am considering writing an I-D for AES-PMAC-SIV: a fully parallelizable misuse resistant AES mode based on generic composition, combining AES-CTR in SIV mode (ala RFC 5297) but substituting AES-PMAC[1] for AES-CMAC. All constructions I just named, aside from "AES-PMAC-SIV" itself, were originally designed by Phil Rogaway, who also suggested substituting PMAC for CMAC to me in the first place. I wrote a blog post about a set of 5 libraries I have written implementing the construction here: https://tonyarcieri.com/introducing-miscreant-a-multi-langua ge-misuse-resistant-encryption-library # Why? There are a number of other misuse resistant schemes available, including the (hopefully) nearly finalized work on AES-GCM-SIV being done through this group, and a misuse resistant scheme is almost certainly going to be part of the CAESAR portfolio. So why AES-PMAC-SIV? What makes it unique? AES-PMAC-SIV is, to my knowledge, the simplest fully parallelizable misuse resistant scheme, particularly applicable to environments that require small code size, have hardware accelerated AES, but do not have the analogue of a CLMUL instruction. Embedded and "Internet of Things" devices often fall into this category, with AES acceleration exceedingly common but CLMUL-style instructions generally only available on smartphone-class devices or x86 desktops/laptops/servers. For this reason we see a similar split in AES-GCM versus AES-CCM adoption. The latter is generally preferred in the sort of embedded environments I am referencing due to these restrictions. I think it would be nice to have an "IoT friendly" misuse resistant scheme. "IoT" seems like an area which could greatly benefit from misuse resistance, as these devices often have limited/poor random number generation capability, so a nonce-based misuse resistant scheme would provide an additional layer of defense in the event of catastrophic RNG failures. # Properties AES-PMAC-SIV is a two-pass offline mode of AES which provides misuse resistant authenticated encryption (MRAE) and supports fully parallel implementations. Traditionally using a 2-pass mode might be considered a blocker for IoT use cases, as devices in this class may generally be rather starved of RAM and unable to hold large messages for a two-pass encryption process. This is a valid concern, and one I think can be addressed in a provably secure manner by employing the CHAIN and/or STREAM constructions[2] to transform AES-PMAC-SIV (or other authenticated modes) into an online mode. STREAM in particular is very simple and easy to implement. Specifying these schemes is arguably out-of-scope for an AES-PMAC-SIV RFC, however. # Performance A naive Rust implementation of AES-PMAC-SIV performs* at ~2.4 cycles/byte for 16kB messages on a 3.1GHz i7. According to Rogaway, an ideal assembly implementation should perform at ~1.25 cycles/byte. I believe this is approximately half the speed of AES-GCM-SIV (AES-PMAC-SIV needs to run the AES function twice as often), although I have been having trouble finding implementations of the AES-GCM-SIV draft to benchmark against. *NOTE: Rough measurements, turbo boost not disabled, more due diligence required for a more accurate figure # Security The security proofs for AES-SIV rely on AES-CMAC being a secure PRF. As AES-PMAC is also a secure PRF, the proofs also hold for it as well. I asked Rogaway for some more specifics on this and whether the proofs of AES-SIV's security and security bounds hold for PMAC as well as they do with CMAC. Here's what he had to say: "The proof in the SIV paper uses generic properties of the SIV construction: you can stick in any provably-sound PRF. Quantitative results will depend on the quality of the PRF, but in the case of CMAC and PMAC, the ‘basic’ bounds are the same (within a small constant). I remember there being somewhat improved bounds for PMAC, like [Nandi, Mandal 2007], but by the time you throw in CTR, it probably doesn’t help. So, yes, effectively equivalent, as far as I know." I think this area could warrant some further study. If you're an academic cryptographer who is interested in studying (and potentially writing a paper about) AES-PMAC-SIV, please let me know. # IPR The IPR status of the underlying AES-SIV construction is covered in RFC 5297: there are no IPR concerns. Regarding PMAC specifically, it was originally patented by Phil Rogaway, but he has since abandoned his patents. A statement to this effect from Rogaway can be found in the PMAC FAQ[3]: "I abandoned all patent filings pertaining to PMAC many years ago. As far as I know, there is no IP relevant to using PMAC — nothing owned by me or by anyone else." # Other MRAE Constructions There are a number of newer constructions which are a variation in the same ideas as AES-PMAC-SIV and its component parts, such as SIVx / PMAC2x[4], ZMAC / ZAE[5], and 1k-PMAC_Plus[6], which try to attain higher security bounds i.e. Beyond Birthday Bound (BBB) security. In discussing these schemes with the chairs we agreed that the perhaps the main reason AES-PMAC-SIV is so attractive is because it's so simple and boring, with well-understood security properties and well-scrutinized component parts that have been around for over a decade and the basis of much cryptography research. Newer schemes may seem alluring but may not actually achieve their stated goals[7]. Several of the round 3 CAESAR candidates are MRAE, including some of Rogaway's latest work: AEZ. However these candidates are generally optimizing for performance and interesting security properties as opposed to simplicity of implementation and minimal code size. If you feel there's a candidate I've overlooked with similar properties please let me know. AES-GCM-SIV is quite interesting but has a more complex implementation requiring CLMUL-style acceleration and lower security bounds (2^32 due to GCM, as opposed to 2^64 AES birthday bound for AES-PMAC-SIV). As I mentioned earlier, GCM has previously been a no-go in the embedded space for lack of CLMUL-like instructions. # Status I have announced a set of libraries implementing this construction in several languages (see link at the top), however there is not yet widespread usage of this construction in the "running code" sense of "rough consensus and running code". In addition to writing a draft I'd like to encourage some organic usage, particularly in the IoT space, and get feedback as to how well this scheme works in the real world. [1] http://web.cs.ucdavis.edu/~rogaway/ocb/pmac.pdf [2] http://web.cs.ucdavis.edu/~rogaway/papers/oae.pdf [3] http://web.cs.ucdavis.edu/~rogaway/ocb/pmac-bak.htm [4] https://eprint.iacr.org/2016/1174 [5] https://eprint.iacr.org/2017/535 [6] https://eprint.iacr.org/2017/848 [7] https://eprint.iacr.org/2017/220 I appreciate any feedback from the group, including any clarifications on anything I have said above but most especially whether or not you think this is a good item for the group to work on. -- Tony Arcieri
- [Cfrg] AES-PMAC-SIV Tony Arcieri
- Re: [Cfrg] AES-PMAC-SIV Daniel Bleichenbacher