Subject: [Cfrg] authenticated encryption with replay protection (AERO) - internet draft

From: David McGrew <[email-masked]>
Date: Thu, 02 Jan 2014 19:40:51 -0500

Hi CFRG,

I have a new proposal for authenticated encryption, which is 
particularly well suited for communication security.   An internet draft 
describing the idea has been published at 
http://tools.ietf.org/html/draft-mcgrew-aero-00 and I would like to 
request a slot at the upcoming CFRG meeting to present this work. (I am 
assuming that we will be meeting in London in March along with IETF 
89).   I alluded to this work on the thread about misuse resistant 
authenticated encryption earlier today.

 From the draft:

Authenticated Encryption with Replay prOtection (AERO)

    This document describes Authenticated Encryption with Replay
    prOtection (AERO), a cryptographic technique that provides all of the
    essential security services needed for communication security. AERO
    offers several advantages over other methods: it has more compact
    messages, provides stronger misuse resistance, avoids the need to
    manage implicit state, and is simpler to use.  This document defines
    a particular AERO algorithm as well as a registry for such
    algorithms.

Comments are welcome, and I especially encourage discussion about the 
appropriate goals for authenticated encryption.  The draft explains the 
rationale well enough, I believe, though it does not mention decryption 
misuse.   I will send a separate note on that topic.

A formal proof of security has not yet been published, but is believed 
to be possible, and the draft does include a security analysis.

Just for the sake of formality - in requesting this review and a slot at 
the upcoming meeting, I am acting as a CFRG member and not a chair.

David

---

From: Watson Ladd <[email-masked]>
Date: Thu, 2 Jan 2014 21:26:03 -0500

On Thu, Jan 2, 2014 at 7:40 PM, David McGrew <[email-masked]> wrote:
> Hi CFRG,
>
> I have a new proposal for authenticated encryption, which is particularly
> well suited for communication security.   An internet draft describing the
> idea has been published at http://tools.ietf.org/html/draft-mcgrew-aero-00
> and I would like to request a slot at the upcoming CFRG meeting to present
> this work. (I am assuming that we will be meeting in London in March along
> with IETF 89).   I alluded to this work on the thread about misuse resistant

INT-PTXT+IND-CPA is pretty much expected.

My one question is why not submit to CAESER? Yes, you are judging it,
but it would bring more eyes
and perspective.

The big weakness of this proposal is speed. It requires one pass of
AES-CTR followed by several passes of a
GCM calculation. On commodity hardware this is very slow. SIV with the
nonce as AAD would get equivalent anti-replay
properties with greater speed, namely two AES passes.

>
> A formal proof of security has not yet been published, but is believed to be
> possible, and the draft does include a security analysis.

It's straightforward, if tedious: use the lemma of Bernstein on PRP vs
PRF, then argue that the messages emerging from
an attacker's insertion are indistinguishable from random, so the
forgery probability is low. For privacy argue that IND-* is
satisfied. Then use the fact that forgery is hard to get that IND-CCA
is satisfied. I haven't actually done this so there might be
a nontrivial obstacle.

Sincerely,
Watson Ladd

>
> Just for the sake of formality - in requesting this review and a slot at the
> upcoming meeting, I am acting as a CFRG member and not a chair.
>
> David
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Robert Ransom <[email-masked]>
Date: Sun, 5 Jan 2014 09:24:09 -0800

> to be possible, and the draft does include a security analysis.

Since AERO uses a large-block block cipher, I believe that the
folklore approach (‘count the bits’) used in the draft is adequate, as
long as it is used with care.  (It can be abused: section 4 (PDF page
6) of <https://www.cl.cam.ac.uk/~rja14/Papers/robustness.pdf> gives
the example of a standardized protocol which relies on a
replay-prevention counter for part of its message redundancy
(i.e. authentication), but obtains only one bit of redundancy due to
poor design of the replay-prevention mechanism.  Fortunately, the
standard replay-prevention practice in modern protocols would not have
introduced that weakness, and AERO uses the modern standard practice.)

(In other constructions, simply ‘counting the bits’ may require some
theoretical justification, and/or may produce the wrong result.  For
example, in Poly1305-AES, verification is equivalent to recovering s
from the MAC, decrypting it, and checking the result for equality to
the nonce; if w nonces are to be accepted when verifying a single
message, that is equivalent to allowing the attacker to try w times as
many forgery attempts; and the security bounds published for
Poly1305-AES turn out to have a term linear in the number of forgery
attempts (denoted D in the paper).  But the other term (probability of
distinguishing AES from a uniform random permutation after C + D
queries) is also a function of D, and is not necessarily linear in D.)

I noticed that there are IPR disclosures for AERO, with rather nasty
terms.  Exactly what parts of AERO are claimed by the patent and
patent application listed there?

Robert Ransom

---

From: David McGrew <[email-masked]>
Date: Sun, 05 Jan 2014 17:46:10 -0500

Hi Robert,

> introduced that weakness, and AERO uses the modern standard practice.)

Agreed.   Well, with AERO, it is not quite counting the number of bits, 
but rather counting the number of sequence numbers that the replay 
checking algorithm would accept.

> patent application listed there?

I do not agree that the terms are "rather nasty"; an IPR specialist 
would likely describe them as "defensive", in the sense of [1]. They 
say: " ... Cisco will not assert any patents owned or controlled by 
Cisco against any party for making, using, selling, importing or 
offering for sale a product that implements the standard, provided, 
however that Cisco retains the right to assert its patents (including 
the right to claim past royalties) against any party that asserts a 
patent it owns or controls (either directly or indirectly) against Cisco 
... " [2]   If you or your employer have suggestions on how the details 
of the terms can be tweaked in a way that makes the technology more 
accessible to other companies (that don't sue us), I encourage you to 
email the contact address in the IETF IPR disclosure (which is 
[email-masked]).

Like most employers, mine asks that I not make public statements or 
speculations about the scope of patent claims.

thanks,

David

[1]  The Defensive Patent License and Other Ways to Beat the Patent 
System, Julie Samuels, EFF, 
https://www.eff.org/deeplinks/2012/06/defensive-patent-license-and-other-ways-beat-patent-system

[2] Cisco's Statement about IPR related to draft-mcgrew-aero-00, 
https://datatracker.ietf.org/ipr/2219/

> .