Subject: Re: [Cfrg] new authenticated encryption draft

From: Phillip Rogaway <[email-masked]>
Date: Fri, 6 Oct 2006 08:14:35 -0700 (Pacific Daylight Time)

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 http://www.cs.ucdavis.edu/~papers

      [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, 
phil

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: David A. McGrew <[email-masked]>
Date: Mon, 9 Oct 2006 15:53:19 -0700

Hi Phil,

many thanks for the well considered comments.  I agree completely  
with your comments 6, 7, 8, and 10, but I disagree with some of the  
others.  More inline:

>     odds with the formalizations of AEAD schemes from my papers  

I think that you misunderstand some of the intent of the  
specification.  The interface that it defines is intended for use  
between applications or protocol implementations and a crypto  
module.  There is no intent to dictate the formalizations used to  
analyze the security of the algorithms contained within the crypto  
module.  (No doubt the draft should have made this point explicit.)    
As you put it in [nonce], the draft is just drawing the abstraction  
boundary a little differently; in this case, the AEAD interface that  
you have in mind is one that is internal to the module.

>     now followed this same approach.

I agree with you that the "notion" is stronger, but surely it does  
not follow from this fact that an implementation of counter mode can  
be made stronger by moving the counter-generation functionality from  
inside of a high-assurance boundary to outside of it!   The point of  
the current interface is to keep it inside.

In dictating the IV, the interface in the draft follows the advice  
given in [G02]: "Don’t leave hard problems as an exercise for the  
user" and "Provide crypto functionality at the highest level possible  
in order to prevent users from injuring themselves and others through  
misuse of low-level crypto functions with properties they aren’t  
aware of."   It also follows the strategy of information hiding  
[P72], in keeping the requirements regarding IVs hidden from the  
user.  Having an IV as an output does limit flexibility (or  
equivalently, it eliminates some potential optimizations, as Dan  
Bernstein pointed out earlier), but that's a worthwhile price to pay  
IMO.

If I understand you correctly, you are suggesting that random nonces  
not be supported.  I'm reluctant to do this because in some  
applications, random IVs are easier to provide than IVs that are  
unique across all invocations of the encrypt function for a  
particular key.  In some implementations, it may be difficult or  
impossible to maintain a counter over a long period of time (e.g.  
across reboots).  When there are multiple encrypters using a single  
key, requiring unique IVs puts a burden of IV coordination on the  
system.  This may be onerous, especially for distributed systems that  
do not require any such coordination for any other reason.  And as a  
practical matter, a lack of random nonces would prevent the use of  
the draft in places where automated key management is unavailable  
[BH05].

All that said, several others have spoken out against random nonces  
and IVs-as-output, so you are in good company.   They are open issues  
as far as I'm concerned, though I have retained the random nonces in  
the next version of the draft and will be seeking input from the  
community of potential users.

>     possibility of a vector of strings as the AD.

There is a strong motivation to use an interface that matches the one  
used by current AEAD specifications [38C][38D].  That, plus the  
simplicity of that interface, overrides the advantages of the vector  
interface in my opinion.  As an aside, I have not been able to find  
any motivation to support authenticated "trailing" data mentioned in  
Section 8.

>     output ciphertext "include" the tag.

It is very tempting to eliminate the tag as a separate output, since  
that simplifies the interface.  However, there are several  
complications that motivated me to not do this.  Existing protocols  
typically expect a separate tag, and existing AEAD standards provide  
one.  And when the plaintext is zero-length but the AD is not, the  
AEAD algorithm acts as a message authentication code.  It seems less  
confusing to the user to have the output of this MAC be called an  
authentication tag, rather than a ciphertext.

>     in a way at odds with the [bkn] and [ad] notions.

Probably the draft is not clear enough on these definitions.  But how  
are they at odds - do you mean in the fact that they do not accept a  
nonce?

> Regardless, to maximize
>     that goal should drop the IV:

In specification language, you're saying that the IV should be  
optional, right?

> DAE schemes have none (but one can always

The DAE work is very interesting - I had a brief exchange with Tom  
about it.  Actually, the current draft supports SIV perfectly well,  
since the IV is an output of the encryption algorithm, and the IV is  
recommended to precede the ciphertext (Section 2.3).

>     efficiently deal with AD-values that are held constant across a  

GCM supports this feature as well.

>     But specifying an "interface" seems pretty close to suggesting an

The draft uses the term "interface" rather than API for generality;  
the interface is intended to be specific enough for real-world use.   
More below ...

>     required all-in-one interface and an optional incremental one.

I like this suggestion.  I implemented support for an init/update/ 
final API it in the GCM reference code, but have not added anything  
like it the draft.  Seems like it would be useful to have in an  
appendix, perhaps along with a suggested API.  (I've also seen an  
iovec API, but the init/update/final one is more fundamental.)

> See [eax]
> (8) [improve rigor]

No doubt the references that you've provided will help there.

> Among the more conspicuous places where the spec seemed

Please see earlier discussions on this list r.e. the IV contribution.

>     specifying an interface and for populating the list of mechanisms.

It is best to retain at least one mechanism in the draft, in order to  
facilitate the standards process.  My preference is also to have at  
least one mechanism for each of the major options in the draft.  Of  
course, future drafts can easily define new methods that can be added  
to the IANA registry.

>     I do realize that it can be undesirable to have too many  

My personal inclination is to set an inclusive policy, but to put the  
burden of specification and test cases on the proposer of each  
algorithm.  According to the draft, what's needed to add an algorithm  
to the registry is:

       a reference to a specification that completely defines an AEAD
       algorithm and provides test cases that can be used to verify the
       correctness of an implementation

>      I think the former term has become pretty standard by now.

You're right, that's certainly the accepted term in the academic  
literature, thanks for pointing it out.  Unfortunately, though, the  
standards don't always use that term; several use "AAD" [H05][VM04] 
[38D].  Oddly, the CCM specification [38C] uses "AD", but some of its  
applications use "AAD" [H05].  FWIW, during an early review of the  
GCM specification, someone from the user community suggested the AAD  
term as being more explanatory of the purpose of the input.  I don't  
care much which gets used, though obviously we will need to declare  
the equivalence in the draft.

Best regards,

David

[G02] P. Gutmann, Lessons Learned in Implementing and Deploying  
Crypto Software, 11th USENIX Security Symposium, 2002.  Online at  
http://www.usenix.org/publications/library/proceedings/sec02/ 
full_papers/gutmann/gutmann_html/index.html

[P72] D. Parnas, On the Criteria to Be Used in Decomposing Systems  
Into Modules, Communications of the ACM, December, 1972.

[BH05]  S. Bellovin, R. Housley, Guidelines for Cryptographic Key  
Management, RFC 4107, June 2005.  Online at http://www.ietf.org/rfc/ 
rfc4107.txt

[38C] Draft Special Publication 800-38D: Recommendation for Block  
Cipher Modes of Operation: The CCM Mode for Authentication and  
Confidentiality

[38D] Draft Special Publication 800-38D: Recommendation for Block  
Cipher Modes of Operation: Galois/Counter Mode (GCM) for  
Confidentiality and Authentication

[H05] R. Housley, Using Advanced Encryption Standard (AES) CCM Mode  
with IPsec Encapsulating Security Payload (ESP)", IETF RFC 4309.

[VM04] J. Viega, D. McGrew, The Use of Galois/Counter Mode in IPsec  
Encapsulating Security Payload (ESP), IETF RFC 4106.

> Kind regards, phil