Re: [Cfrg] new authenticated encryption draft

[David McGrew <[e-mail]>]

Hi John,

thanks again for your comments.

On Sep 11, 2006, at 11:32 AM, John Wilkinson wrote:

> David,
>
> I have read your draft more carefully now, and I see that you have
> specified both "deterministic" and "random" AEAD schemes. In the case
> of an encryption operation where the "IV" is generated randomly,
> obviously it must be returned to the user so that it can be passed
> along to the decryption operation. May I ask the purpose of specifying
> algorithms with random (non-deterministic) IVs? Are there any cases
> where this is truly necessary?
>

Yes, there are several cases where a random IV is useful because it  
is difficult to use a unique IV.  These cases should have been  
mentioned in the draft.

When a key is used over a time period that extends across multiple  
restarts of a device, a provision must be made in order to ensure  
that a deterministic IV maintains its uniqueness across all of those  
restarts.  This can be done, for instance, by periodically  
checkpointing the IV value into non-volatile memory.  However,  
checkpointing is a non-trivial process, and many encryption systems  
do not already contain facilities to support it.  There are also  
systems with limited non-volatile memory capabilities, in which it is  
difficult or undesirable to frequently write new values into memory.

When a single key is used by multiple encryptors, a unique IV needs  
to have a distinct IV contribution for each encryptor.  In some  
cases, it may not be convenient for the encryptors to coordinate  
among themselves to agree on the values of the IV contribution.   It  
is undesirable to rely on human coordination, and automated systems  
may not be available.  For example, consider the case in which there  
is a cluster of devices that share an encryption key in order to  
provide a load balancing or failover capability.  When a  
deterministic IV is used with that key, the cluster must provide  
distinct IV contributions, or it must carefully coordinate the IV  
usage in some other way.  When a random IV is used by encryption  
process, this need for additional coordination goes away.


> It seems that in the example you give in section 5.3 (generic
> composition of AES-CBC encryption and HMAC-SHA1 authentication),
> randomness isn't really required for security. It suffices to have the
> IV be unpredictable to the attacker, which could be easily
> accomplished deterministically by the following (using your notation):
>
> IV = leftmost(HMAC_SHA1(K, "IV" | IV_contribution), 128);
>
> Where the user's IV_contribution is concatenated with the string "IV"
> to form the message to be MACed. More elegant formulations of
> generating ENC_KEY, MAC_KEY, and IV are also possible.
>
> It seems to me that this method of deterministically generating IV's
> is likely to be more reliable than relying on any external source of
> randomness. As long as the IV contribution from the user is a "number
> used once" (nonce), this AEAD scheme is secure in the sense of
> IND-CCA2 (assuming that AES is IND-CPA, etc.). Is there any reason to
> prefer the random IV formulation? If not, I would recommend removing
> the non-deterministic algorithms from your specification, removing the
> requirement to return the (now deterministically generated) IV to the
> user, and removing the requirement that the IV contribution be used
> "verbatim". I too value simplicity and ease of use in crypto
> algorithms, and requiring that all AEAD algorithms conforming to this
> specification accept a nonce for both encryption and decryption, and
> dispensing with non-determinism and having to keep track of separate
> IVs and IV contributions seems simpler and more robust, at least to me
> anyway.
>
> -John
>
> P.S. If no one else has pointed it out yet, your specification for
> AEAD_AES_256_HMAC_SHA1 in section 5.3.2 isn't quite complete, since it
> fails to explain how one generates a 256-bit AES key from HMAC-SHA1.
> (One can, of course, imagine many ways of doing this, but it should be
> spelled out.) Also, if the keys and IVs were generated pseudorandomly
> using HMAC-SHA1, should that be considered to have "a cryptographic
> strength equivalent to that of AES-256"?

Thanks; some others have pointed it out as well.  Jack Lloyd  
suggested using something like IEEE 1363's KDF2, which is essentially  
SHA1 in counter mode.  It would be FIPS-140-2 compliant, which is  
appealing.

David

>
> On 9/6/06, David McGrew <[e-mail]> wrote:
>> Hi John,
>>
>> On Sep 1, 2006, at 4:52 PM, John Wilkinson wrote:
>>
>> > David (McGrew),
>> >
>> > I understand and accept your rationale for placing "IV" generation
>> > under the control of the AEAD algorithm. It was clear to me from  
>> the
>> > first draft, though your revised language is even more explicit. I
>> > think it's a good idea for precisely the reasons you state.  
>> However,
>> > two things I do not agree with are:
>> >
>> > 1) Requiring that the IV be an *output* of the encryption  
>> algorithm,
>> > rather than a value only used internally to the algorithm. What  
>> is the
>> > purpose of making it an output? Is it not simpler to require the  
>> input
>> > of a nonce to the encryption algorithm, and the input of the same
>> > nonce to the decryption algorithm? I see no need to make the  
>> internal
>> > workings of the algorithm (including the IV) visible to the  
>> user. GCM,
>> > to pick an example you are undoubtedly familiar with, does not  
>> return
>> > the IV to the user, so why require it here?
>>
>> it's returned so that the user can send the IV along with the
>> ciphertext and tag.  When it is the encryption algorithm rather than
>> the user that's generating the IV, the user needs to be told that  
>> value.
>>
>> >
>> > 2) Requiring that the "IV contribution" be included "verbatim"  
>> in the
>> > (preferably internal) IV of the algorithm. I would remove this
>> > language entirely. It is unclear what "verbatim" means in this
>> > context, and I think the requirement is counterproductive.
>>
>> Yeah, others have told me that "verbatim" is confusing too.  What I'd
>> meant was that the IV contribution must appear as part of the IV,
>> e.g. as the prefix or as the suffix, or as some other contiguous sub-
>> sequence of bits.
>>
>> > As long as
>> > the user supplies a nonce, and the algorithm creates from that  
>> nonce
>> > an internal IV, the form of that IV shouldn't be restricted. Again,
>> > GCM does not use the user-supplied "IV contribution" (nonce)  
>> directly
>> > (verbatim?) when the nonce is other than 96-bits long, so why  
>> should
>> > you be more restrictive here?
>>
>> I think that crypto modules should trade off some flexibility for
>> some usability.  The idea is that an AEAD module as defined in the
>> spec is harder to misue, and easier to test and to validate, than a
>> module that implements a set of block cipher modes or other lower
>> level primitives.
>>
>> I'll rewrite the draft and try to make the situation w.r.t. the IV
>> and IV Contribution more clear, over the next week or so.  I'll value
>> your thoughts on the new text.
>>
>> David
>>
>> >
>> > -John
>> >
>> > On 8/28/06, David McGrew <[e-mail]> wrote:
>> >> Hi John,
>> >>
>> >> On Aug 22, 2006, at 7:05 PM, John Wilkinson wrote:
>> >> >
>> >> > 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.
>> >>
>> >> 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,
>> >> > 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."
>> >>
>> >> 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.
>> >>
>> >> >
>> >> > 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.
>> >>
>> >> 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 "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.
>> >> >
>> >>
>> >> 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
>> >>
>> >
>> > _______________________________________________
>> > Cfrg mailing list
>> > [e-mail]
>> > https://www1.ietf.org/mailman/listinfo/cfrg
>>
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> https://www1.ietf.org/mailman/listinfo/cfrg

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