Subject: [Cfrg] AES-PMAC-SIV

From: Tony Arcieri <[email-masked]>
Date: Wed, 8 Nov 2017 08:29:35 -0800

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

---

From: Daniel Bleichenbacher <[email-masked]>
Date: Wed, 8 Nov 2017 19:29:43 +0100

Security in a multi user setting might be worth some thoughts.
The paper "Another Look at Tightness" by Chatterjee, Menezes and Sarkar,
SAC 2011
https://www.math.uwaterloo.ca/~ajmeneze/publications/tightness.pdf
has an attack against SIV in a multi-user setting in section 5.1.
In particular, if one wants to achieve 128 bit security in such a setting
then
it seems necessary to use a larger PMAC key.

On Wed, Nov 8, 2017 at 5:29 PM, Tony Arcieri <[email-masked]> wrote:

> 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
> 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
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>
>