[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, 8 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