[Cfrg] Re: comments on draft-mcgrew-auth-enc-03.txt

Hi Phil,

thanks for your comments.  I'm sorry for the delay in replying, I've  
been out of the office  and away from email.

I have no doubt that your comments will improve this work, though I  
do think that some of your suggestions would be best followed in  
future work.  As background, the -03 version was created in response  
to comments given to me from the IESG review.  (The comments, if  
you're interested, are online at https://datatracker.ietf.org/ 
idtracker/draft-mcgrew-auth-enc/)  Also, this doc is a normative  
reference for some ongoing work (draft-ietf-tls-rsa-aes-gcm-00, draft- 
ietf-tls-ecc-new-mac-01).  So at this point we need to minimize the  
amount of changes to the document (or at least compartmentalize the  
changes), though of course correctness comes first.  Where there is a  
need for additions, extensions, or alternatives, we're best off  
addressing this need in future drafts.

More inline:

On Aug 15, 2007, at 2:29 AM, Phillip Rogaway wrote:

> Hi David,
>
>  In an earlier email (6 Oct 2006) (cc'ed to the cfrg) I passed on some
>  comments on draft-mcgrew-auth-enc-00.txt.  I've just taken a look at
>  latest incantation, draft-mcgrew-auth-enc-03.txt (July 6, 2007), so
>  thought to pass on some fresh comments.
>
>  Since my comments are critical, I think I should say up front that
>  I think the draft is greatly improved since the -00 version that I
>  reviewed last year, and, also, that I think that an RFC along these
>  lines might be valuable.
>
>
>  1. Nonces and the specific AEAD goals you intend
>
>  Your ID says that "Each nonce provided to distinct invocations
>  of the Authenticated Encryption operation MUST be distinct,
>  for any particular value of the key."  This statement stands in
>  direct contradiction to your later statement that "The number of
>  octets in the nonce MAY be zero".

It's not contradictory (since there is exactly one nonce of length  
zero) but this is an ambiguous point in the document!

> (This latter statement is
>  itself ambiguous, either asserting that a _given_ nonce may have
>  zero bytes (N_MIN = 0), or that all nonces will (N_MAX = 0).)

Agreed.  I suggest the following rewording:

       The number of octets in the nonce SHOULD be twelve (12).  Nonces
       with different lengths MAY be used with a particular key.   
However,
       zero-length nonces MUST NOT be used, unless each nonce used with
       a particular key is zero-length.  Randomized AEAD algorithms,  
which
       are defined in Section 4, are suitable for use with zero-length
       nonces.  When zero-length nonces are used, the nonce uniqueness
       requirement is not in effect.

Recall that the "Guidance on the use of AEAD algorithms section" says  
that:

    If an application is unable to meet the requirements on nonce
    generation, then it MUST use a zero-length nonce.  Randomized AEAD
    algorithms, which are defined below, are suitable for use with such
    applications.

>
>  The requirement that a nonce never repeats precludes the possibility
>  of an appropriately-long user-supplied random value. Say this  
> explicitly
>  if you really mean it.  But I myself would find this an odd  
> choice; to me,
>  a random nonce isn't just a _reasonable_ thing for the user to be  
> able
>  to supply, it's a _canonical_ thing to supply!  If you mean to
>  prohibit the user from providing random nonces, I can only assume  
> this
>  is rooted in experience that this is something so easily messed up
>  that users of a cryptographic interface must NOT be allowed to do  
> it....

That's right.

>
>  In general, though, I find entire story on nonces, and how they  
> relate
>  to the cryptographic goal one is aiming for, to be kind of muddy.
>  Eg., we are told that a probabilistic encryption scheme may use a
>  zero-length nonce, but you don't say that a probabilistic scheme MUST
>  use a zero-length nonce, nor do hint at what would be the intended
>  cryptographic semantics when you have a nonce _and_ internal coins.
>  We are not told that _only_ a probabilistic scheme may use a
>  zero-length nonce and I cannot actually tell if you intend
>  deterministic AE (key-wrap) to be in scope or not.  You make clear
>  that a counter may be used as a nonce, but it's unclear if it may
>  be used (instead of coins) internally to an encryption mechanism
>  (perhaps creating the odd asymmetry that counters may be shipped  
> in or
>  generated internally, but random coins MUST be generated internally).
>  Must an (internal) counter-based scheme have N_MAX=0 and, if not,  
> what
>  is the meaning of supplying a nonce when there is also internal
>  state. And so forth ....

Yes, you're right about the murkiness, though I don't think that this  
draft should define things so precisely that it would exclude some  
potentially useful algorithms.

Good comments about deterministic AE and stateful algorithms.  Are  
you concerned that it will not be possible to define an AEAD  
algorithm based on deterministic AE?  I would expect that it would be  
easy to do so, by including a nonce in one of the inputs.   If I'm  
missing something, can you please suggest what changes you think  
would be needed?

>
>  Perhaps part of the problem is that there are multiple AEAD  
> formulations
>  in the literature, these corresponding to some genuine difference  
> about
>  concerning the use of coins and state in the encryption process  
> and whether
>  or not an external nonce is supplied:
>
>          
> -----------------------------------------------------------------
>         | Probabilistic| Stateful    | Nonce-based      |  
> Deterministic |
>         | AEAD  [BN00] | AEAD [BN00] | AEAD [RBBK01,R02]| AEAD    
> [RS06] |
>          
> -----------------------------------------------------------------
>  coins? |      yes     |     no      |       no         |      
> no        |
>  state? |       no     |    yes      |       no         |      
> no        |
>          
> -----------------------------------------------------------------
>  nonce? |       no     |     no      |       yes        |      
> no        |
>          
> -----------------------------------------------------------------
>
>  You can't quite ignore these subtleties in your ID because (a) what
>  the user supplies to the encryption and decryption algorithms vary;
>  (b) what is allowed in the underlying encryption algorithms varies
>  (in terms of maintaining state or using randomness);

OK, I do see one case here that's not allowed in the draft.  The spec  
allows randomized algorithms to have zero-length nonces, but it makes  
no allowance for stateful algorithms, which presumably could have  
zero-length nonces too.  We could change the draft to allow these  
algorithms as well.  (You probably recall that the earliest version  
of this draft incorporated the idea of stateful algorithms, but that  
facility was removed due to objections from some reviewers.)

If we want to explicitly allow AEAD algorithms that have zero-length  
nonces, but are not randomized, we will need to define something like  
"stateful AEAD algorithms" and then mention it in Section 4 and in  
the paragraph reworded above.  If you would prefer another term  
please suggest it.  This is not a big change in my opinion.

>  (c) some combinations either haven't been defined or don't seem to  
> make
>  a whole lot of sense; and
>  (d) a user of the interface needs to make an informed decision about
>  what service he wants.

Agreed.  Section 4 currently says that

    Each AEAD algorithm specification SHOULD describe what security
    degradation would result from an inadvertent re-use of a nonce  
value.

    Each AEAD algorithm specification SHOULD provide a reference to a
    detailed security analysis.  This document does not specify a
    particular security model, because several different models have  
been
    used in the literature.  The security analysis SHOULD define or
    reference a security model.

Perhaps you can suggest some additional text that would go here, but  
I think that the current approach of having each algorithm  
specification define the details of its security properties is a good  
one.

>
>
>  2. Mixing algorithms and interfaces, and SHOULD(|Nonce|=14)
>
>  An interface definition ought aim to be mechanism-neutral.
>  Indeed the high-level decision to specify in one ID both an
>  interface and four particular algorithms feels kind of "political".

Hmmm, that's not the intent.  If I wanted to push a particular set of  
algorithms, I wouldn't go to the trouble of writing an interface that  
abstracts them and thus makes it easier to slip in an alternative  
algorithm as a replacement!

If you or anyone else is interested in writing up a specification for  
an alternate AEAD algorithms, I would be happy to help.  (For that  
matter, I have a not-yet-published draft defining an AES-CBC HMAC- 
SHA1 algorithm.)

>
>  One problem with mixing algorithms and an interface in one document
>  is that it can lead one to favor the specified mechanisms (CCM and  
> GCM)
>  in somewhat hidden ways.  For example, you say that a nonce SHOULD
>  be 12 octets, the (somewhat idiosyncratic) choice of CCM, GCM.  Why?
>  The best reason I can think of for suggesting a particular nonce  
> length
>  would be the hope that a user could select this length and be sure  
> that
>  any mechanism conforming to all SHOULDs would support this choice.

Yes, that's right, and even more importantly, we want applications to  
choose nonce lengths that will be supported.  Users of the interface  
that conform to the recommended nonce length will avoid having to  
construct nonces with different lengths.  The recommendation helps to  
keep algorithm-specific logic out of the applications that make use  
of the interface.

The choice of 12 octets was a bit idiosyncratic, as you point out,  
but that choice got made years ago.  It is easy for an algorithm that  
accepts longer nonces to accept 12 octet ones, so this shouldn't be a  
big deal, since nonces tend to be at least that size nowadays.

> But if
>  that's the goal you'd want to say   SHOULD (N_MIN <= 12 and N_MAX  
> >= 12),
>  not SHOULD (N_MIN = N_MAX = 12).   Still, even the relaxed SHOULD
>  denigrates probabilistic, stateful, and deterministic encryption;  
> perhaps
>  one might say SHOULD ((N_MIN<=12 and N_MAX>=12)) OR (N_MIN=N_MAX=0)?

Paragraph 2 of Section 3 covers some of this:

    If an application is unable to meet the requirements on nonce
    generation, then it MUST use a zero-length nonce.  Randomized AEAD
    algorithms, which are defined below, are suitable for use with such
    applications.  Otherwise, an application SHOULD use nonces with a
    length of twelve octets.  Since algorithms are encouraged to support
    that length, applications should use that length to aid
    interoperability.

You're right that stateful algorithms get short shrift.  The above  
could be changed to "Randomized AEAD algorithms, and stateful AEAD  
algorithms, ... "   Note that we need to retain the term "randomized"  
because of other uses in the document.

>  But by that point it really seems better to remove any SHOULD about
>  nonce lengths....
>
>

I respectfully disagree here.  We need to have a preferred length in  
order to avoid the need for logic in the application that deals with  
the different cases of the different nonce lengths.

>  3. Vector-value AD
>
>  The ID says that the AD must be a string, but SIV mode, an AEAD  
> scheme
>  by Tom Shrimpton and me [RS06], uses a vector-valued AD.  Your own ID
>  might itself be seen as having some contents that motivate a
>  vector-valued AD, eg, when you indicate that the AD could include
>
>     addresses, ports, sequence numbers, protocol version numbers,
>     and other fields that indicate how the plaintext or ciphertext
>     should be handled, forwarded, or processed. In many situations,
>     it is desirable to authenticate these fields.
>
>  Note the plural, "fields"; I think the AD is quite often a list
>  of values (more often then is a plaintext, nonce, or key).
>  If this list must be formed into a string by the user there is
>  a conceptual gap, a specificational gap, and a lost opportunity
>  for optimization.  See [RS06].
>
>  I am not trying to suggest that it's a terrible a thing for the AD
>  to be a string; indeed a string AD has a different kind of elegance
>  on it side. I'm only saying that it might be nice not to _preclude_
>  the AD from being a vector of strings.

It would be a significant change to the document to rewrite it to  
have a vector input, so the SIV is best addressed through future  
work.  Besides, given an algorithm with a vector-valued AD, it seems  
easy to define an AEAD algorithm, as Dan Harkins did in his SIV draft.

I owe you and Dan and Tom some comments on SIV; I'll write those up  
separately.

>
>  4. Unbounded strings and the constants P_MAX, A_MAX, and N_MAX
>
>  I understand P_MAX, A_MAX, and N_MAX to be bounds on what the
>  mechanism is algorithmically capable of handling. One might guess
>  the "type" of these values to be nonnegative integers. But it's more
>  like that or "infinity": some algorithms can handle strings of any
>  length (and indeed this is generally desirable). Be sure to indicate
>  that these values can be nonnegative integers OR infinity.
>
>
>  5. Nomenclature
>
>  Getting to some lower-level stuff, I'll repeat my suggestion that the
>  term "additional authenticated data" and the acronym "AAD" be  
> replaced
>  by the term "associated data" and the acronym "AD". While I realize
>  that there's some precedent for the term AAD, (a) the (relatively
>  small amount of) scientific literature making mention of this concept
>  seems to favor "associated data" (eg, compare google-scholar hits);
>  (b) The phrase "additional authenticated data" makes no English- 
> language
>  sense: the data isn't authenticated, it's something the user  
> _wants_ to
>  have authenticated. (Calling it (additional) authenticated data is
>  a bit like naming a plaintext a "jumbled string" because the user
>  wants to encrypt it.) (c) you already use the term AEAD extensively,
>  an acronym that stands for "authenticated encryption with associated
>  data" -- not "authenticated encryption with additional  
> authenticated data".
>
>  I'll mention too that, given the centrality of AEAD to this document,
>  you probably should reference [R02], where AEAD was first named,  
> defined,
>  and formally investigated.

I'd meant to do that.

>
>
>  6. Questionable prose
>
>  Finally, a few specific statements that didn't make a whole lot of
>  sense to me and probably should be cut:
>
>  a. "When [AD, A, is used], authentication is provided without
>     copying the data [A] into the ciphertext."  Not formally
>     meaningful, not something you're in any position to mandate, and
>     not something anyone would even think to do! [Encode A in the
>     plaintext, perhaps....]

Ah, thanks, I'd meant " copy the data into the plaintext" here.

>
>  b. "The nonce MAY be included in P or A if it is convenient to
>     the application."   An odd suggestion.

Maybe, but I added this sentence because I've been specifically asked  
about it.

> A user-supplied nonce is
>     needed for decryption, so somehow encoding it into the plaintext
>     would serve no ostensible purpose; regardless, a user doesn't
>     need your blessing to put anything he wants into P. Similarly, it
>     would be weird to put a nonce into A, since, as you point out,
>     the nonce is already authenticated; but, regardless, this isn't  
> for
>     you to judge.  (Actually, the one thing a user actually SHOULDN'T
>     drop into P or A -- the key K or something derived from
>     it -- you're silent on.)
>

That's a good point.  I can't imagine why anyone would want to do  
that, but a disclaimer doesn't hurt.  I suggest "The secret key K  
MUST NOT be included in any of the other inputs."

>  c. "The authenticated decrypt operation will, with high probability,
>     return FAIL whenever its inputs were not created by the encrypt
>     operation with the identical key (assuming that the AEAD algorithm
>     is secure)."  This sentence has two interpretations, the way I  
> read
>     it, one of which is incorrect: that the decryption of a  
> ciphertext C
>     under a key K' different from the encryption key K will usually
>     result in FAIL. That reading makes sense, but the claim isn't  
> implied
>     by any standard notion of AE security.
>

How do you like this, then:

                     The authenticated decrypt operation will, with high
    probability, return FAIL whenever the inputs N, P, and A were  
crafted
    by a nonce-respecting adversary that does not know the secret key
    (assuming that the AEAD algorithm is secure).

Best regards,

David

>
>  Best wishes,
>  phil
>

_______________________________________________
Cfrg mailing list
Cfrg@ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg