Subject: [Cfrg] new authenticated encryption draft

From: "David A. McGrew" <[email-masked]>
Date: Fri, 18 Aug 2006 11:56:44 -0700

Hello,

I've recently submitted a new Internet Draft pertinent to this group,  
and I'd like to ask for your review.  The pre-publication draft is  
online at http://www.mindspring.com/~dmcgrew/draft-mcgrew-auth- 
enc-00.txt

Authenticated Encryption (draft-mcgrew-auth-enc-00.txt)

Abstract.  This draft defines algorithms for authenticated encryption  
with additional authenticated data (AEAD), and defines a uniform  
interface and a registry for such algorithms. The interface and  
registry can be used as an application independent set of  
cryptoalgorithm suites. This approach provides advantages in  
efficiency and security, and promotes the reuse of crypto  
implementations.

Comments welcome.  FYI, I'll be in Santa Barbara next week.

Best regards,

David

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

---

From: "Hal Finney" <[email-masked]>
Date: Sun, 20 Aug 2006 11:47:45 -0700

> efficiency and security, and promotes the reuse of crypto

Hi, David - That looks very interesting, but I have a few comments.

As a general philosophical point, I am not sure that the name
"authenticated encryption" accurately defines the security properties
for the lay reader. He may think it means that there is authenticity
that the message came from a particular sender, for example. Recently
I have been involved with some disk encryption work which uses
authenticated encryption. In this context, it only means that the
authenticated data was written to the sector at some time in the past.
It doesn't guarantee that what you read from the disk is what was
written there, when you are reading multiple sectors at once (each of
which has its own tag, and each of which might have been rolled back
differently by an attacker). So I think you might want to say
something in more detail about the security properties this encryption
aims to meet, and perhaps mention some caveats about attacks that are
still possible even with AEAD.

In a lot of ways, I think that AEAD is better thought of simply as
providing confidentiality, and nothing more. The purpose of the
"authentication" is to improve the confidentiality guarantee, by
preventing active attacks like chosen ciphertext. Without it, many of
our encryption modes do not provide confidentiality against a
sufficiently powerful attacker.

Another point is that you say that deterministic AEAD algorithms MUST
take an input which goes into the IV. I am not sure I fully understand
the reason for this requirement, but more to the point, I don't think
it is going to be clear to the layman what he should put into this
input. What security properties must his input meet, in order to use
the underlying abstraction safely? Without this guidance, providing
such an input may even be dangerous.

It is outside the scope of your document, but I have found from my
disk experience that the approach in these algorithms of letting the
AEAD algorithm manage uniqueness of IVs at the "micro scale" while the
caller manages uniqueness at the "macro scale" can actually lead to
very inefficient allocation of IV space. For example, with GCM taking
an external IV contribution of 64 bits, if the caller is encrypting a
lot of short messages in a context where it must be stateless and pass
in a random IV contribution, it can only encrypt 2^32 such messages
under a given key. The seemingly vast IV space is eroded to a very
significant limitation similar to what we had in the old days of DES.

One final comment is regarding your proposal AEAD_AES_128_HMAC_SHA1,
for CBC encryption with HMAC authentication. Basically it looks OK,
but when you do the HMAC you "apply it" to the AAD, IV and ciphertext.
This is ambiguous but it sounds like you might mean to concatenate
these fields and HMAC them. If so, that would be unsafe, because it
could be vulnerable to an attack where the boundaries between these
fields are changed by an attacker. For example, he could create AAD'
as AAD||IV, IV' as the first 16 bytes of ciphertext, and ciphertext'
as the remainder of the ciphertext. This would authenticate OK at the
decryption end but would not produce correct plaintext. So you should
be sure to include some length fields inside the HMAC here to assure
unambiguous parsing.

> Comments welcome.  FYI, I'll be in Santa Barbara next week.

Hey, while you're there you should stop in at the Crypto conference... ;-)

Hal

---

From: Greg Rose <[email-masked]>
Date: Sun, 20 Aug 2006 16:00:10 -0700

>significant limitation similar to what we had in the old days of DES.

This "erosion" only happens if the requirement is that the IV be 
random and unpredictable to an attacker. Most AEAD systems don't 
require this strong guarantee, and any form of Nonce will usually do; 
the only requirement being uniqueness. So the 64 bit input, provided 
in the form of a counter, is good to the same order-of-magnitude 
limit as the block cipher itself.

(Note: I haven't looked at the new mode to verify that this is the 
case, but I think it probably is.)

I've been lightly pushing for a terminology change in this area for some time:
Use "IV" when randomness and/or unpredictability are requirements
Use "Nonce" when uniqueness is the only requirement.

Greg.

---

From: "David A. McGrew" <[email-masked]>
Date: Mon, 21 Aug 2006 16:37:12 -0700

Hi Hal,

> sufficiently powerful attacker.

That's a great point.

> such an input may even be dangerous.

You're right, there is not a sufficient motivation for the IV  
contribution, nor advice on what to put in it.   That field is needed  
so that 1) for each fixed key, each distinct invocation of the  
authenticated encryption operation can have a distinct IV value (e.g.  
to ensure distinct counter values), and 2) some of the existing uses  
of CCM and GCM include a fixed value in the l.s.b. of their IV  
values.    I'll need to come up with some text on this.

> significant limitation similar to what we had in the old days of DES.

True; I'd expect that in practice an IV contribution could be much  
smaller though.  For RFCs 4106 and 4309, the contribution could be as  
small as 4 and 3 bytes, respectively, leaving 64 bits for the micro- 
scale IV.

> be sure to include some length fields inside the HMAC here to assure

Good catch!  I lifted the CBC+HMAC definition from an existing spec  
for which the AAD length was fixed, and introduced an error by not  
authenticating the location of the AAD/plaintext boundary.  (I think  
I violated my own advice here too :-)

David

---

From: "John Wilkinson" <[email-masked]>
Date: Tue, 22 Aug 2006 22:05:14 -0400

> limit as the block cipher itself.

Gregg, unless I'm missing something, in the _stateless_ case Hal
mentions, the IV/nonce must be random (since a counter requires
state), and the potential for nonce "collisions" becomes unacceptably
high after many fewer than 2^32 encryptions.

David, while I've only briefly skimmed your draft, Hal and Gregg's
comments make me wonder about the way you're treating IVs in your
specification. Why do you feel that IVs must be an _output_ of the
encryption algorithm, rather than a purely internal value? Further,
what, exactly, do you mean by the requirement that "A deterministic
AEAD encryption algorithm MUST accept an additional input, and that
value [the IV contribution] MUST be included _verbatim_ [emphasis
added] in the IV."

It seems to me that it would be a better abstraction of the AEAD
mechanism if the IV is used purely internally to the algorithm, so
that the only input required is a nonce, and that the same nonce is
used for encryption and decryption. Furthermore, the requirement that
the "IV contribution" must be used "verbatim" in the IV could be read
to exclude, for example, Bellare, Rogaway, and Wagner's EAX mode. EAX
uses a user-supplied nonce, which may be of any length, and computes a
MAC on this nonce to generate the initial counter for counter-mode
encryption.

-John

---

From: "Scott Fluhrer" <[email-masked]>
Date: Wed, 23 Aug 2006 22:24:38 -0400

> -----Original Message-----
> From: David A. McGrew [mailto:[email-masked]] 
> Sent: Monday, August 21, 2006 7:37 PM
> To: Hal Finney
> Cc: [email-masked]
> Subject: Re: [Cfrg] new authenticated encryption draft
> 
> Hi Hal,
> 

I don't entirely agree - AEAD does give you something more than
confidentiality; it gives the guarantee that the data was encrypted by
someone who has the key (and with that exact additional data).  Now, as Hal
has pointed out, in some scenarios, this can be less than what someone who
hears "authentication" may expect (and so perhaps "integrity" would be a
better term).  However, this is something that can be spelled out, rather
than just letting the user assume that this doesn't provide any sort of
integrity assurance.

-- 
scott

---

From: David McGrew <[email-masked]>
Date: Mon, 28 Aug 2006 14:29:23 -0700

Hi John,

On Aug 22, 2006, at 7:05 PM, John Wilkinson wrote:
> specification.

I've heard from others that the motivation for why IVs are handled in  
the document is not clear.  Thanks for your comments; I clearly have  
more explaining to do :-)

> Why do you feel that IVs must be an _output_ of the
> encryption algorithm, rather than a purely internal value?

There is a rationale given in Section 2, but I'll try to amplify it -  
here's a rewrite of that part.  Please let me know what you think.

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

> Further,

Several 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 these algorithms, and  
it is needed in order to allow CTR-based modes (like CCM, GCM, and  
EAX) 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.

> used for encryption and decryption.

Here we've gotten stuck on the terminological thicket.  What you're  
calling a nonce is what the draft calls an IV.  I should add  
definitions I guess.

> Furthermore, the requirement that

The GCM mode of operation has the same property (it will accept an IV  
of any length, though it is optimized to handle 96-bit IVs).   
However, there does not seem to be any significant use for this  
facility in practice, so I decided to use a simpler and more  
consistent interface for the AEAD algorithms.  EAX could certainly be  
added, but obviously we'd need to mandate a particular IV format.

David

---

From: David A. McGrew <[email-masked]>
Date: Mon, 28 Aug 2006 15:11:09 -0700

Hi Scott,

thanks for your comments, more inline:

On Aug 23, 2006, at 7:24 PM, Scott Fluhrer wrote:

> someone who has the key (and with that exact additional data).

In the draft I didn't make the point that authentication helps to  
achieve confidentiality goals - I should have though.  Since most  
users understand confidentiality, but many may not appreciate the  
importance of authentication/integrity, this consideration is worth  
stating.  That's what I'd meant.

> Now, as Hal

I agree, adding definitions would be the best way to go.

David

---

From: [email-masked] (David Wagner)
Date: Tue, 29 Aug 2006 08:20:52 +0000 (UTC)

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

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"?

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

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.

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.

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

-- David

---

From: David McGrew <[email-masked]>
Date: Tue, 29 Aug 2006 08:56:06 -0700

Hi David,

thanks for your detailed comments, more inline:

> to the AEAD algorithm, which is used for encryption (and for  

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>

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

> operation, and AAD for the decryption operation.  Be consistent.

AAD = "Additional Authenticated Data"

>   One

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.

> precisely.)  This seems like a peculiar requirement with no purpose  

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

> and should never change for the lifetime of the key.

Agreed.

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

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.

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

---

From: "Hal Finney" <[email-masked]>
Date: Tue, 29 Aug 2006 09:51:40 -0700

One sentence that struck me as kind of odd was this, in section 2.1:
"The strength of the authentication of P, IV and A is attenuated by
the length t of the authentication tag."

Attenuation means a weakening or reduction, so this makes it sound
like a longer tag will result in diminished security. Maybe you could
substitute "controlled by" or "determined by", or even "exponential in
the length t". A good algorithm ought to be exponential in t, I'd
think, othewise it is being wasteful.

Hal Finney

---

From: "David A. McGrew" <[email-masked]>
Date: Tue, 29 Aug 2006 09:58:43 -0700

Hi Hal,

On Aug 29, 2006, at 9:51 AM, Hal Finney wrote:

> like a longer tag will result in diminished security.

bad choice of words in the draft.  I like "determined by".

David

> Maybe you could

---

From: [email-masked] (David Wagner)
Date: Tue, 29 Aug 2006 17:22:29 +0000 (UTC)

David McGrew  wrote:
>Making the IV an output rather than an input was a conscious  
>and security.

Ok.

>multiple devices doing encryption with a single key.

Ok, makes sense.

>a field that needs to be authenticated, such as an address or some  

Alternatively, one could tell users to include that field as part of
the AAD.

>was submitted as a query to the encryption oracle, as long as N' != N.

I've been hoist by my own petard!

Yes, it's true.  Here is the distinction I was thinking of.  If the
AEAD scheme is proven to meet the INT-CTXT condition, then yes, I think
you'll be able to count on the authenticity of the IV.  However, if the
AEAD scheme is proven to meet INT-PTXT, then I don't think you'll be
able to count on this.  As you say, EAX was proven to be INT-CTXT.
I don't recall off the top of my head whether the security proofs for
the other AEAD modes in your spec prove INT-CTXT or INT-PTXT.  However,
I can easily imagine future modes being proven INT-PTXT.  INT-PTXT is
not an unreasonable criteria for a mode of operation; it appears to be
perfectly adequate so long as the application never inspects the
ciphertext directly (including the IV).  It seemed to me that your
spec would be more general if it works for any INT-PTXT scheme, but
that would mean that applications should not be examining the IV and
should not be counting on its authenticity.

Alternatively, if you want to require that AEAD modes be proven to
be INT-CTXT before they can be used within your framework, you might
want to mention that, and I think you would then need to go check
the security theorems for CCM, GCM, etc., to make sure that each of
the modes mentioned in your document have been proven to be INT-CTXT
(and not just INT-PTXT).

>definitions and algorithms that don't provide that facility.

Perhaps.  But this might prevent you from using some AEAD algorithm
that doesn't provide IV authentication (e.g., because it is INT-PTXT
but not INT-CTXT) but has other beneficial properties not shared by
its competitors.  It's a defensible choice, but I'm not sure yet
whether it is the optimal choice.

>from a single key using AES.

Well, I would use CMAC for that task.  CMAC is a NIST-approved mode.
If AES is secure, then AES-CMAC is a secure PRF.  And any secure PRF is
perfectly fine for deriving an encryption key and a MAC key.

Is SHA1-HMAC FIPS-140 approved as a method for deriving two keys from
a single key?  If FIPS-140 approves SHA1-HMAC but not AES-CMAC for this
purpose, and if FIPS-140 conformance is important, well, I'll confess I
don't have any solution to that.

>address the FIPS-140 issue, of course, but it would be technically  

Sure.  I mean, I don't see why not.  As far as I know, you can use EAX
with random IVs if you want -- you can use it with any kind of IVs,
as long as they don't repeat.  Or did I misunderstand the question?