Re: [Cfrg] new authenticated encryption draft

Phillip Rogaway <> Fri, 06 October 2006 15:18 UTC

Received: from [] ( by with esmtp (Exim 4.43) id 1GVrSu-0006q0-34; Fri, 06 Oct 2006 11:18:20 -0400
Received: from [] ( by with esmtp (Exim 4.43) id 1GVrS1-00062m-Np for; Fri, 06 Oct 2006 11:17:25 -0400
Received: from ([]) by with esmtp (Exim 4.43) id 1GVrPT-0001eW-SE for; Fri, 06 Oct 2006 11:14:50 -0400
Received: from localhost ( []) by (8.12.8/8.12.8) with ESMTP id k96FBFqY011784; Fri, 6 Oct 2006 08:11:15 -0700
Date: Fri, 06 Oct 2006 08:14:35 -0700
From: Phillip Rogaway <>
To: David McGrew <>
Subject: Re: [Cfrg] new authenticated encryption draft
In-Reply-To: <>
Message-ID: <Pine.WNT.4.60.0610060803060.900@rogawaynew>
References: <>
X-X-Sender: rogaway@rogawaynew
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset="US-ASCII"; format="flowed"
X-Spam-Score: 0.0 (/)
X-Scan-Signature: 6ffdee8af20de249c24731d8414917d3
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>

Hi David,

  Here are some comments and suggestions on draft-mcgrew-auth-enc-00.txt.
  Sorry that my comments come later than those of others.

(1) [IV better an input than an output]  Regarding the IV as an output and not
     an input of an AEAD algorithm seems to me quite undesirable. It is also at
     odds with the formalizations of AEAD schemes from my papers [ad, dae, ocb].
     Basically, because IVs are often instantiated by protocol elements not
     under the control of the encryption mechanism (eg, a packet sequence
     number), and because IVs are often misused (eg, a sequence-number IV in
     CBC encryption), an IV needs to be regarded as an input to an AEAD
     mechanism, but as little as possible should be demanded of it: only that
     it be a nonce.  I speak of this especially in [nonce]. When I moved
     several years ago to formalizing symmetric encryption schemes in this way,
     it was precisely to make safe and rigorous this widespread
     conceptualization (with us since at least FIPS 81) of a
     symmetric-encryption scheme depending on an input IV, a conceptualization
     then at odds with the formal treatment of symmetric encryption schemes.
     Formalizing things in this newer way leads to a stronger (and therefore
     harder-to-use-wrong) and more versatile notion of AEAD than the
     internal-coin/internal-state approach. Other works, like [cwc], have
     now followed this same approach.

(2) [make AD a vector] The SIV algorithm [dae, siv] that I designed with
     Tom Shrimpton takes a *vector* of strings as the associated data (AD).
     I think this will prove to be more convenient than having the AD be a
     single string. It is a conceptual simplification for protocol designers
     that would use an AEAD scheme, and it enables efficiency advantages, too.
     While a particular AEAD mechanism may place restrictions on what AD
     vectors are allowed (including: "only 1-vectors"), it would be better
     if the general interface for an AEAD scheme encompassed the
     possibility of a vector of strings as the AD.

(3) [kill that tag]  You say that the AEAD scheme outputs a ciphertext C and
     a separate authentication tag T. While I appreciate that candidate AEAD
     schemes have something that one can naturally see as an "authentication
     tag", let me remind you that in none of the definitions for an AE/AEAD
     scheme does such a thing appear -- and an AEAD scheme need not have
     anything that resembles a tag in its output. Thus it is better that the
     output ciphertext "include" the tag.

(4) [refine your goal(s)]  You speak of "randomized" and "deterministic"
     authenticated-encryption (AE), but it looks like you are using these terms
     in a way at odds with the [bkn] and [ad] notions.  Regardless, to maximize
     ease-of-correct-use and increase conceptual clarity, I suggest you align
     your notions with nonce-based AEAD and, possibly, deterministic
     authenticated-encryption (DAE), as defined in [ad] and [dae]. You should
     also specify more precisely the definition that you intend a compliant
     scheme to satisfy.

(5) [drop the IV for DAE]  If you want to encompass DAE then the treatment of
     that goal should drop the IV: DAE schemes have none (but one can always
     regard the IV as a component of the header in order to define a
     nonce-based AEAD scheme out of a DAE scheme [dae]).

(6) [facilitate constant ADs]  One of the motivations underlying the design
     of EAX [eax], SIV [dae, siv], and OCB 2.0 [ocbspec, offsets] was to
     efficiently deal with AD-values that are held constant across a session.
     I'm not sure just how directly your interface is supposed to get
     translated into a programmatic API, but, when it is made into an API,
     it seems good to define it where one needn't repeatedly pay for a
     constant AD. This issue is orthogonal to your Internet Draft (ID) if you
     take your ID not as suggesting an API but only abstract functionality.
     But specifying an "interface" seems pretty close to suggesting an
     actual API.

(7) [support on-line (incremental) data]  Following the lead of the
     incremental ("append this") API popularized by Ron Rivest's MD4
     implementation [md4], it seems desirable if plaintext, ciphertext, and
     associated data can be entered into the computation chunk-by-chunk
     (imagine a very long message arriving on-line). Not every AEAD algorithm
     can support on-line authenticated encryption (using constant memory), but
     many algorithms can.  I suggest that an interface document specify a
     required all-in-one interface and an optional incremental one.  See [eax]
     (authors' full version) for more discussion of this, and an
     example of an incremental AEAD interface.

(8) [improve rigor]  Among the more conspicuous places where the spec seemed
     to become informal: when you speak of including something verbatim
     in the IV; when you say that the associated data "must be left
     unencrypted" (there is no meaningful way to mandate such a thing);
     and when you say that the IV may be "included" in the associated data.
     Also, you speak of "IV contributions", as though there is an IV a user
     provides and a different IV that is "internal" to some mechanism.
     But there is only the one IV that you should be speaking to: the one
     that is provided by the user.

(9) [maybe split]  It might be cleaner to have separate documents for
     specifying an interface and for populating the list of mechanisms.
     And when mechanisms do get selected, EAX [eax], OCB [ocbspec, offsets],
     and SIV [dae, siv] might be good algorithms to include. (Of course
     I do realize that it can be undesirable to have too many choices on
     such a matter).

(10) As I myself did throughout this note, I suggest using the term
      "associated data" (AD) instead of "additional authenticated data" (AAD);
      I think the former term has become pretty standard by now.

References    // my own papers are at

      [ad] P. Rogaway. Authenticated-encryption with associated-data.
           ACM CCS '02.
     [bkn] M. Bellare, T. Kohno, and C. Namprempre. Breaking and provably
           repairing the SSH authenticated encryption scheme: a case study
           of the encode-then-encrypt-and-MAC paradigm. ACM TISSEC, 7(2), 2004.
     [cwc] Y. Kohno, J. Viega, and D. Whiting. A high-performance conventional
           authenticated encryption mode.  FSE 2004.
     [dae] P. Rogaway and T. Shrimpton. Deterministic authenticated-encryption:
           a provable-security treatment of the key-wrap problem. Eurocrypt '06.
     [eax] M. Bellare, P. Rogaway, and D. Wagner. The EAX mode of operation
           (a two-pass authenticated-encryption scheme optimized for simplicity
           and efficiency). FSE 2004.
     [md4] R. Rivest. The MD4 message-digest algorithm. RFC 1320. April 1992.
           Corresponding academic paper in CRYPTO '90.
   [nonce] P. Rogaway. Nonce-based symmetric encryption. FSE 2004.
     [ocb] P. Rogaway, M. Bellare, J. Black, and T. Krovetz.  OCB: a
           block-cipher mode of operation for efficient authenticated
           encryption. ACM CCS '01 and ACM TISSEC 6(3), 2003.
[ocbspec] T. Krovetz and P. Rogaway. The OCB authenticated-encryption
           algorithm.  Internet draft, March 2005.  draft-krovetz-ocb-00.txt
[offsets] P. Rogaway. Efficient instantiations of tweakable blockciphers and
           refinements to modes OCB and PMAC. Asiacrypt '04.

Kind regards, 

Cfrg mailing list