Daniel Bleichenbacher <> Wed, 08 November 2017 18:29 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id F3C631295A0 for <>; Wed, 8 Nov 2017 10:29:48 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.7
X-Spam-Status: No, score=-2.7 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id LD0kBuOAWjaJ for <>; Wed, 8 Nov 2017 10:29:45 -0800 (PST)
Received: from ( [IPv6:2607:f8b0:4001:c06::232]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id BDBA41294F0 for <>; Wed, 8 Nov 2017 10:29:45 -0800 (PST)
Received: by with SMTP id h70so6973564ioi.4 for <>; Wed, 08 Nov 2017 10:29:45 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=/xXbxwzZmYZVab0sxqNFjziF0MAmaMquP+tbu4z3O58=; b=DJr1pSpqtywxQwKS8y1rLM1wsNSFwO5zisAIDdgSb3xrr8vvchYzzL17ACnC7B5UlJ 9zfuQEly2Lr1hDAAQ10HrumMxJuXwiOC55ImvBl0J++qtNOjISx/D0p4Ye/94viRzrVC yNwQQkCfJgbWsoO+KYDD1/2K3f8wkDL/5fgtFWEkSKEx96OYMMW4Pi+7xT7q0CJPlLa8 bqbFd6Wd2B+FVAA9tm3nr1lW6ger72JG65755Xmdn6BpkRSPSsnlcFBIN3/8We2YFENa ZZZMdwkVzR7wurOQE85kLB88lN1fk0FVtjSPj4Kr8J++n8/glwC0hn7nKljUpnANCbhm E5ww==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=/xXbxwzZmYZVab0sxqNFjziF0MAmaMquP+tbu4z3O58=; b=ElUQ3kFS5MeyN6nK0CvXfTarsgeGItLbUC8aLlikhzAAjfaMks0Uza7emhflqxaT+Y KQdQwur43J5WsmDIAPGvJ0aipuGvs+TezFSTBLw8gdq3iXbO12x6PwsSdpOMWjxGo6Kw N+wv5LHBBsvoUR5a2QpZtc4JtGMuoH1EvuUjXiNcOq4/WL7FHuhRXqn2f2PyG8HPsyeU TfN8ngUrZg3XvvZQ8eRpAbanaN+XFNgg62csladjnHkEO8gpLPjl8GV9d2IhwmJttwOZ UzpqrDzPl9/XNifutOih8NxV5VOBaD0NMoHUAodXzn6hj6y6dcqw44rlCTiXHq7GMI/o mYGw==
X-Gm-Message-State: AJaThX5gRSf+Wq8z4Hwpn8k/88zZ0JnKwAypvU9paKcbwMeQWAUHcHGj grhO1s3Y7qlEqfrAYXllP4TUE5KVvW/XfjDKkVVnQg==
X-Google-Smtp-Source: ABhQp+QpFj1Gmm6/eioyJ4av6ug4E+oW0n9pr4eKnecQPpYCQJ5v4cIXiZpoK8ZyqbZAwADqAgkWLK2JgtzQFHlq/Nk=
X-Received: by with SMTP id m19mr2002322iob.166.1510165784383; Wed, 08 Nov 2017 10:29:44 -0800 (PST)
MIME-Version: 1.0
Received: by with HTTP; Wed, 8 Nov 2017 10:29:43 -0800 (PST)
In-Reply-To: <>
References: <>
From: Daniel Bleichenbacher <>
Date: Wed, 08 Nov 2017 19:29:43 +0100
Message-ID: <>
To: Tony Arcieri <>
Cc: "" <>
Content-Type: multipart/alternative; boundary="f403043cd170224d5d055d7cdfb0"
Archived-At: <>
Subject: Re: [Cfrg] AES-PMAC-SIV
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Wed, 08 Nov 2017 18:29:49 -0000

Security in a multi user setting might be worth some thoughts.
The paper "Another Look at Tightness" by Chatterjee, Menezes and Sarkar,
SAC 2011
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
it seems necessary to use a larger PMAC key.

On Wed, Nov 8, 2017 at 5:29 PM, Tony Arcieri <> 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:
> 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]
> [2]
> [3]
> [4]
> [5]
> [6]
> [7]
> 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