Re: [Cfrg] new authenticated encryption draft

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:

On Oct 6, 2006, at 8:14 AM, Phillip Rogaway wrote:

> 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].

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.

>     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.

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.

>
> (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.

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.

>
> (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.

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.

>
> (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.

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
>     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:

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

> 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]).

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).

>
> (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.

GCM supports this feature as well.

>     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.

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 ...

>
> (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.

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]
>     (authors' full version) for more discussion of this, and an
>     example of an incremental AEAD interface.
>
> (8) [improve rigor]

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

> 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.

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

>     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.

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.

>     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).

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

>
> (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.
>

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.

> 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
Cfrg@ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg