Re: [Cfrg] new authenticated encryption draft

[David McGrew <[e-mail]>]

Hi David,

thanks for your detailed comments, more inline:

On Aug 29, 2006, at 1:20 AM, David Wagner wrote:

> David A. McGrew wrote:
>> Authenticated Encryption (draft-mcgrew-auth-enc-00.txt)
>
> This looks like a useful document.  Thanks for putting this together.
>
> Here are a slew of minor comments:
>
> Saying that the IV is generated by the AEAD algorithm seems a little
> unusual.  Many AEAD algorithms permit the application to provide a  
> nonce
> to the AEAD algorithm, which is used for encryption (and for  
> decryption).

Right.  Making the IV an output rather than an input was a conscious  
design choice intended to trade some flexibility off for ease of use  
and security.  Here's the new rationale for this choice:

<new>
Rationale.  Proper IV generation is a crucial for security, and the  
requirements on how IVs are generated are different for different  
algorithms.  By making the IV an output of the AEAD algorithm rather  
than an input, the IV is put under the control of that algorithm.   
This use of the 'information hiding' design principle frees the user  
from needing to understand the particulars of IV generation, thus  
making the interface easier to use correctly.  Also, because IV  
generation is a security-critical operation, it makes sense to  
include it with the algorithm, which will typically be implemented in  
a crypto module.  Including IV generation in this module makes it  
more self-contained and easier to test and to validate.

Several security issues have arisen due to improper use of block  
cipher modes of operation.  Several standards have suggested  
incorrect uses of cipher block chaining (CBC) encryption (e.g. using  
a previous ciphertext block as an IV, which allows an adversary to  
predict the IV).  Modes that require distinct IVs, such as counter  
mode, are especially sensitive to misuse of IVs, which can void the  
security services that they provide.  Giving the AEAD algorithm the  
responsibility for generating its own IV helps to avoid these  
security issues.
</new>

>
> This might be more flexible, because it allows the nonce to be  
> meaningful
> to the application in some special cases.  For instance, you can use
> nonce = sector number for disk encryption (well, not actually, because
> disk encryption has to be length-preserving, but you get the idea).
> It could also fit into your framework, as a case of an AEAD algorithm
> where the IV is taken to be exactly the IV contribution, and where the
> mode documents that IV contributions must not repeat.  Perhaps this is
> what you are trying to address with your "IV contribution"?
>

The problem that the IV contribution is addressing is the need for  
CTR-based modes to be useable in a situation in which there are  
multiple devices doing encryption with a single key.  The IV  
contribution provides a place within which each encryptor can put a  
distinct value, to ensure that the IVs are distinct over all uses of  
that key.  At first I was tempted to call this input a "device ID" or  
something like that, but I went with the more generic name because  
some crypto algorithms, including CCM and GCM as used in ESP, form  
their IVs by prepending a value that is fixed (for the lifetime of  
the key) to a sequence number that increments once per packet.  The  
IV contribution is needed in order to support this usage as well.

My current thinking is that I'm going to put out a second draft that  
provides more detail but uses the current interface definition, and  
see if we can't improve the existing approach.  If people (especially  
potential users of the draft) have a hard time understanding it, I'll  
switch over to having the IV be an input.

> I prefer to use the term "nonce" when the only requirement is that  
> nonces
> must not repeat.  I tend to use "IV" when there are stricter  
> requirements
> (such as that IVs be uniformly random and unpredictable).
>
> You don't use the term "AEAD" consistently.  In one place, you say  
> that
> an AEAD algorithm has two operations, encryption and decryption.   
> In some
> other places, you seem to use AEAD to refer solely to the encryption
> operation, and AAD for the decryption operation.  Be consistent.

AAD = "Additional Authenticated Data"

>   One
> option is to always use AEAD vs AAD to refer to encryption vs  
> decryption.
> Alternatively, when you are referring to just the encryption  
> operation,
> use "AEAD encryption algorithm" instead of just "AEAD algorithm".
> (For instance, when you say the IV is an output of the AEAD algorithm,
> you might mean that it is an output of the AEAD encryption  
> algorithm --
> obviously, it is not an output of the decryption algorithm, but rather
> an input).
>
> By your definitions, no secure stateless AEAD algorithm can be
> deterministic, because the IV has to have some randomness in it.
> Did you perhaps mean that deterministic means the ciphertext output of
> the encryption algorithm is a deterministic function of the inputs and
> of the IV generated, or did you actually mean what you write?

The definition of "deterministic" is meant to capture the algorithms  
for which the IV is deterministic, since these algorithms have  
different requirements w.r.t. IV contribution.  The draft should make  
this clearer.

>
> I don't know why you require that the IV contribution be included
> "verbatim" in the IV.  (I don't even know what the word "verbatim"  
> means,
> precisely.)  This seems like a peculiar requirement with no purpose  
> that
> I can discern.
>

It's well motivated (by the needs mentioned above), if not well  
explained.

> Your document doesn't state any requirements on the IV contribution.
> Therefore, you should say that the mode specification must specify any
> requirements on the IV contribution (e.g., that it be non-repeating)
> that an application is required to abide by.
>
> I don't think it's wise to vary the length of the authentication tag
> separately for each packet.  The tag length should be bound to the key
> and should never change for the lifetime of the key.
>

Agreed.

> I don't think you should be saying that the IV is authenticated  
> internally
> to the algorithm.  The receiver should only be looking at the  
> decrypted
> plaintext and the authenticated data; higher layers at the receiving
> side should not be looking at the IV.

For a deterministic AEAD algorithm, the IV contribution could contain  
a field that needs to be authenticated, such as an address or some  
other identifier.

> Thus, I'm not sure in what sense one can say that the IV is  
> authenticated.
> Standard security definitions promise nothing about that.   
> Moreover, you should not be promising that
> the decryption operation will detect incorrect IV values, because  
> that is
> not necessarily guaranteed by standard security definitions

It is not always explicitly described, but it is often there.   
Consider the definition of "Authenticity of AEAD Schemes" in Section  
6 of "The EAX Mode of Operation", http://www.cs.ucdavis.edu/~rogaway/ 
papers/eax.pdf.  An adversary that succeeds in getting the  
verification oracle to return 1 by submitting a query (N, H, CT), in  
which (N, H, CT) was never submitted as query to the encryption  
oracle, is committing a forgery.  This is true even if (N', H, CT)  
was submitted as a query to the encryption oracle, as long as N' != N.

> (for instance,
> imagine if the last bit of the IV is ignored by both the encryption  
> and
> decryption operation; then an attacker who flips that last bit while
> the IV is in transit will go undetected, but no harm will be done).

It's better to use a definition of an AEAD algorithm that's  
consistent with IV authentication, since algorithms with that  
property will be easier to use, even if there are other AEAD  
definitions and algorithms that don't provide that facility.

> It is, however, accurate to say that no security failure results when
> the decryption operation is provided with an incorrect IV, as long  
> as you
> define "security failure" to mean that the decryption operation  
> returns
> some plaintext as valid (without FAILing) when that plaintext was  
> never
> processed by the encryption operation.
>
> I think you mean the IV may be transported along with the ciphertext
> (not "plaintext").  I think the sentence "The entire IV need not
> be transmitted; it is sufficient to provide the receiver with enough
> information to allow the IV to be reconstructed." is confusing.   
> You are
> describing two algorithms.  It is enough to say that the IV output by
> the encryption operation must be provided as input to the decryption
> operation.  The question of how it is provided to the decryption
> operation is up to the lower layers (or to the application, depending
> on how you look at it), but that question is 'none of your business'
> (i.e., it is irrelevant to an AEAD spec).
>
> The first paragraph of Section 3 looks like a repeat of things already
> stated earlier.  Skip it?
>
> Is there any value in defining a generic composition, like
> AEAD_AES_128_HMAC_SHA1, except that it uses AES-CMAC instead of  
> SHA1-HMAC?
> This would be for systems that have AES but don't want to implement  
> SHA1
> (e.g., embedded systems; hardware).

I personally like this idea, though there is a potential problem for  
users that want FIPS-140 conformance, in that AFAIK there is no  
FIPS-140 approved method for deriving an encryption key and a MAC key  
from a single key using AES.

Do you consider it appropriate to use EAX with random IVs?  If so,  
that might be a better solution than generic composition.  It doesn't  
address the FIPS-140 issue, of course, but it would be technically  
appealing.

David


>
> -- David
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> https://www1.ietf.org/mailman/listinfo/cfrg

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