Re: [Cfrg] new authenticated encryption draft

Hi Ken,

many thanks for these detailed comments.

On Aug 30, 2006, at 9:09 PM, Ken Raeburn wrote:

> It sounds like the intent is that application protocols and AEAD
> algorithm descriptions to both be written to interface in a way to be
> described in (the final version of) this document.  I think that's
> extremely useful -- and the sort of thing I wish I could've done
> better with RFC 3961 (crypto bits for Kerberos protocols and
> applications), which came out looking kind of warped because of
> historical baggage, among other things.
>
> The list of little details that ought to be covered will probably get
> kind of tedious.  Well, scratch that "probably".  For example, in your
> algorithm descriptions you specify the maximum size of the IV
> contribution, but you don't say in the general description that the
> algorithm description MUST specify it.

agreed, the algorithm definitions need to be expanded, and the  
requirements on them made clear.

>
> I think there are several properties that an application protocol may
> want to refer to when describing what kinds of algorithms are
> permitted, or influencing how the algorithm is applied.  For example:
> Deterministic vs random; tag lengths; IV contribution lengths; key
> sizes; statefulness; padding characteristics.  In general these are
> (or should be) clear from the algorithm descriptions, but it may be a
> good idea to call them out specially as properties that MUST be clear
> from the specification -- easy to derive, if not explicitly stated --
> and, if someone comes up with a scheme where such properties don't
> have clear, fixed values, then that scheme isn't usable under this
> specification.

Agreed.

> And application protocols must be prepared to either
> deal with interesting restrictions (only a 3-byte IV contribution?),
> or specify required properties for algorithms (at least 18 byte IV
> contribution? zero ciphertext expansion?).
>

Right.  There are a lot of potential pitfalls here, I think.   
Ideally, the interface should allow an application to be ignorant of  
which algorithm is in use.  In practice, the idiosyncrasies of the  
algorithms and their existing applications make this hard.

> They don't have to be fixed values, necessarily, but that's the
> easiest way for an application protocol implementation to
> programmatically evaluate the suitability of an AEAD scheme for the
> application's use, if the application and AEAD implementation come
> from different sources.
>
> On the flip side, defining a list of properties should make it clear
> that other properties cannot simply be assumed by the application
> protocol designer to always hold.  For example, just because the first
> N algorithms have no expansion in generating the ciphertext, or never
> vary the IV-output size, doesn't mean the application protocol writer
> (or implementor) can assume that the next one won't.
>

Good point.

> Section 2:
>
>      The inputs and outputs of these algorithms
>    are defined in terms of bit strings.  However, an implementation  
> MAY
>    choose to accept only inputs whose bit-lengths are multiples of 8;
>    that is, it may accept only octet strings.
>
> This implies that application protocol writers must not assume that
> either party can use bit-lengths that are not multiples of 8; you
> might make it a recommendation that they assume that they can't.

Sounds good to me.

>
>    An AEAD algorithm is called deterministic if the outputs of the
>    encryption algorithm are a deterministic function of its inputs.
>    Otherwise, the AEAD algorithm is called random.
>
> If an AEAD algorithm can generate either of two outputs for a given
> input, is it "random"?  It's not really suitable for uses requiring
> unique outputs, nor uses requiring low or zero probability of
> identical results from multiple encryptions.  But it could still be a
> perfectly valid AEAD algorithm, I think?  (Clearly in the realm of
> "why in the world would you want to do it that way?", but not, so far
> as I can tell, actually ruled out.)
>
> Do I get any guarantees about being able to do "random" encryption
> given a deterministic algorithm by factoring in random bits in some
> algorithm-independent way?  Or might some output bits corresponding to
> the message plaintext still be deterministic?
>
>    An AEAD algorithm MAY be stateful, that is, it may require that  
> state
>    is maintained between each invocation of the authenticated  
> encryption
>    operation, and/or between each invocation of the authenticated
>    decryption operation.
>
> Perhaps I'm just failing to imagine it, but is there a case where
> stateful decryption doesn't imply some kind of ordered message
> streams?
>
>
> Section 2.1:
>
> You don't discuss key generation.  I assume, then, that it's just "N
> random bits" with no structure, so, for example, a triple-DES-based
> AEAD algorithm would have to specify how the 168-bit input key is
> turned into the typical 192-bit key with parity, and similarly for any
> other kind of encryption algorithm that might want some structure to
> the key data it uses (e.g., anything based on asymmetric-key schemes).

That's right; good idea to make that explicit.

>
> I see your notes in section 8 regarding tag length.  If the tag is
> going to be allowed to be truncated, I think there should be some
> recommendation for application protocols aimed towards preventing an
> attacker from sending forged messages with extremely short tags.
> E.g., specify minimum or exact tag length, negotiate tag size securely
> in protocol, ....  It seems pretty obvious, but someone looking to
> sprinkle some magic security dust on his protocol may overlook it.

Agreed.

>
> In the "random" algorithm case, at least, is it actually useful to
> distinguish between IV and ciphertext?  In RFC 3961, we just glommed
> them together.  (Actually, the IV was generally fixed, and we had a
> randomized confounder value, more or less the equivalent of a random
> IV in CBC mode, stuck on the front of the plaintext, and its encrypted
> version was part of the ciphertext output.)  I suppose you often want
> to align the ciphertext on some boundary, despite random IV sizes.

It is intriguing to consider lumping the IV into the ciphertext,  
since it makes for a simpler interface in some respects, but OTOH I  
think it is valuable to have the IVs be treated uniformly, and for  
deterministic IVs there is motivation to treat IVs as separate (e.g.  
so that they can be implicit).

>
>    A deterministic AEAD encryption algorithm MUST accept an additional
>    input, and that value MUST be included verbatim in the IV.  This
>    input is called the IV contribution.
>
> You don't explicitly say: Can the IV contribution be fixed for a given
> key, user, session, protocol?  Must it vary, and if so, how
> frequently, or under what other conditions?  (Your message to David
> Wagner gives an interesting example of a case you're trying to
> address, but that's not an answer to the question.)

Right, more needs to be said here.

>
> Can a non-deterministic encryption algorithm accept an IV
> contribution?
>

Great question.  It is somewhat tempting to require that an "IV  
contribution" be provided in all cases, in order to simplify the  
interface and eliminate the need for an application to know what sort  
of algorithm is being used.  Obviously, we don't want to have an  
application be responsible for providing randomness, so if we made  
this change we'd want to rename the "IV contribution" to something  
like "diversification parameter".

>    The IV is authenticated internally to the algorithm, and it is not
>    necessary to include it in the AAD input.  The IV MAY be  
> included in
>    the AAD if it convenient to the application.
>
> If the IV is output to the encryption operation run over (among other
> inputs) the AAD, I don't see how it could be included in the AAD
> input.

Good point; I'd meant to say the "IV contribution" here.

>
>    The IV MAY be transported along with the plaintext.  The entire IV
>    need not be transmitted; it is sufficient to provide the receiver
>    with enough information to allow the IV to be reconstructed.
>
> The parties obviously must either communicate or independently compute
> the contributed part; as for the rest, if it can always be
> reconstructed, presumably you would never bother including it in the
> IV output.
>
> An exception might be a counter in the IV in strictly sequenced
> messages.  If messages can be reordered or dropped, it must be sent
> each time, but if strict sequencing is required, the counter can be
> dropped from all messages after the first.  (And, obviously, both
> encryption and decryption algorithms must be stateful.)
>
> But the sequencing requirement lives in the application protocol spec,
> and the determination of which bits can be dropped under certain
> conditions ("this message is in a strictly-ordered sequence of
> messages, but not the first"?) lives in the AEAD algorithm, so if this
> little optimization is to be allowed, the framework must allow some of
> that information to pass through.
>
>

Seems to me that the right thing is to recommend that the entire IV  
be carried along with the ciphertext, but then to allow other  
approaches as an optimization (made by applications that hopefully  
will understand the implications of re-ordering on the reconstruction  
of IVs).  Perhaps should add a sentence about reorder and loss.

> Section 2.2:
>
> I can't come up with a good example yet, but might there be cases
> where the additional authenticated data is somehow selected or
> influenced by something in the plaintext, such that doing the
> decryption and authentication in one step wouldn't work?  At least,
> not without providing some hook for letting the application feed
> additional data into the middle of the process.
>
> Like I said, I don't have a good example -- or even a bad one :-) --
> and to avoid stupid implementation mistakes like failing to actually
> do the authentication test, it may be better just not to allow it.
>
>
> Section 3.1:
>
>      The integer part of the IV is equal to
>    one for the first IV, and increments by one for each successive IV
>    that is generated.  The integer part is never equal to the all-zero
>    value.
>
> This leads to the obvious question of what happens after the
> all-bits-one integer value is used.  As described, the encrypt
> operation does not have FAIL as an allowable output.
>

Probably ought to describe this sort of error condition.

> And that leads to questions about the maximum number of messages
> allowed as an attribute of the algorithm, especially if it's specified
> based on "when you get to around 2**n messages your protection is
> weakening" versus "if you repeat values it's all over".  And whether
> an application (protocol) is supposed to keep track and re-negotiate
> keys (or just shut down the session), or if it can choose to keep
> going with weaker protection.  And likewise for a maximum number of
> bytes.

In the current draft, with the IV as an output, key usage tracking  
ought to be a responsibility of the algorithm, esp. deterministic  
ones.  If we adopt the suggestion of moving IV generation out of the  
algorithm, and making the IV an input to the encryption process, then  
we can't expect an algorithm to be responsible for enforcing these  
restrictions.

>
>
> Section 8:
>
> IANA assignments: Technically, a separate registry for experimental
> use seems like the wrong approach, especially if you want protocol
> designers to be able to drop in algorithms and numeric algorithm
> identifiers in their protocols.  I'd suggest designating parts of the
> name and number spaces for experimental algorithms, with a different
> policy, or reserved for private use and no public registration at all.
> (Say, names starting with "X_", or "EXP_", and negative numbers.)
>

Sounds good.

>    [regarding tag lengths]  If backwards
>    compatibility is desirable, a length of 12 octets would be best; if
>    security is considered paramount, then the longest is the best.
>
> I'm unclear what you're referring to -- the general specification, or
> the specific algorithms defined here?

A 12 octet authentication tag is recommended for ESP and for ESP-CCM  
and ESP-GCM; that's the compatibility issue that I'd meant to refer to.

David

>
> Ken

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