Subject: RE: [Cfrg] new authenticated encryption draft

From: "Santosh Chokhani" <[email-masked]>
Date: Tue, 29 Aug 2006 10:40:13 -0700

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

FIPS 140 does not specifically address derivation of keys from a single
key.  FIPS Pseudo RNG permits use of SHA-1 function and AES ECB for
pseudo randomizing.

-----Original Message-----
From: David Wagner [mailto:[email-masked]] 
Sent: Tuesday, August 29, 2006 1:22 PM
To: [email-masked]
Subject: Re: [Cfrg] new authenticated encryption draft

David McGrew  wrote:
>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.

Ok.

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

Ok, makes sense.

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

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

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

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

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

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.

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

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.

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

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?

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

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

---

From: Ken Raeburn <[email-masked]>
Date: Thu, 31 Aug 2006 00:09:02 -0400

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.

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

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.

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.

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

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.

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.

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

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

   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.

   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.

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.

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.

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

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

Ken