Re: [Cfrg] AES-PMAC-SIV

[Daniel Bleichenbacher <[e-mail]>]

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 <[e-mail]> wrote:

> 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 mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg
>
>