Subject: Re: [Cfrg] new authenticated encryption draft

From: "John Wilkinson" <[email-masked]>
Date: Fri, 1 Sep 2006 19:52:31 -0400

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?

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

-John

On 8/28/06, David McGrew <[email-masked]> 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
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: David McGrew <[email-masked]>
Date: Wed, 6 Sep 2006 14:17:47 -0700

Hi John,

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

> 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

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

---

From: "John Wilkinson" <[email-masked]>
Date: Mon, 11 Sep 2006 14:32:46 -0400

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?

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

---

From: "D. J. Bernstein" <[email-masked]>
Date: 12 Sep 2006 01:19:03 -0000

Networks often transmit packets repeated, out of order, etc. To detect
and correct these problems, we attach an increasing nonce to each
packet, such as the number of bytes transmitted previously. (The nonce
can be compressed for transport; for example, TCP's ``sequence number''
is essentially the bottom 32 bits of the nonce.)

The obvious way to prevent forgery and eavesdropping is to reuse this
nonce for a MAC and a stream cipher. It's a waste of time and bandwidth
to have a separate cryptographic layer producing its own nonce.

---D. J. Bernstein, Professor, Mathematics, Statistics,
and Computer Science, University of Illinois at Chicago

---

From: "Steven M. Bellovin" <[email-masked]>
Date: Mon, 11 Sep 2006 21:44:17 -0400

> to have a separate cryptographic layer producing its own nonce.
Many people have made similar proposals; others disagree -- there's a
layering issue here that might impact security.  In particular, if the
crypto layer requires certain properties of the sequence number -- say,
non-repeating or monotonically increasing -- the question is whether or
not it can trust the upper layer to do that correctly.  This is
particularly difficult if you're using an outboard crypto device, where
its security context (and assurance level) is really quite different than,
say, TCP's.

Let me give a slightly -- but only slightly -- contrived example.  Suppose
you had a site-to-site VPN, where the encryptor used counter mode driven
by the TCP sequence number.  All outbound traffic has to pass through this
encryptor, so there's no opportunity for anyone to talk directly to the
outside.  A corrupt insider sends packets of known content -- perhaps all
zeros, though it doesn't have to be -- but using previously-observed or
probable previously-used TCP sequence numbers.  The encryptor would
encrypt the known content with the same sequence number it had used for
real content.  The attack is then obvious; it can't even be dignified as
cryptanalysis.

The underlying flaw is that the crypto layer relied on data under control
of an enemy.

		--Steven M. Bellovin, http://www.cs.columbia.edu/~smb

---

From: "D. J. Bernstein" <[email-masked]>
Date: 12 Sep 2006 02:36:30 -0000

Steven M. Bellovin writes:
> layering issue here that might impact security.

No, there isn't. Nonces used to recognize out-of-order packets have a
security requirement, no matter what layer they're in: they _must_ be
generated in increasing order. Nonces used as MAC inputs also have a
security requirement, no matter what layer they're in: they _must_ be
unique.

In an efficient protocol, these nonces are unified. There's one piece of
security-critical code generating one nonce in increasing order. In an
inefficient protocol, these nonces are separated, and there are two
pieces of security-critical code generating the two nonces.

> by the TCP sequence number.

The TCP sequence number isn't a nonce; it repeats. The TCP sequence
number is the _bottom 32 bits_ of a nonce _for one connection_ (plus an
irrelevant offset). The nonce is, as I said before, the number of bytes
transmitted through the connection. It's safe to use this nonce to
encrypt those bytes in counter mode under a connection-specific key.

---

From: David McGrew <[email-masked]>
Date: Tue, 12 Sep 2006 12:58:50 -0700

Hi John,

thanks again for your comments.

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

> 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

---

From: "D. J. Bernstein" <[email-masked]>
Date: 14 Sep 2006 13:58:34 -0000

David McGrew writes:
> among themselves to agree on the values of the IV contribution.

Specific references, please. What are those cases? Why can't the key
generator hand out a counter along with the key? Who exactly is sharing
a single secret key among a large number of parties without having a
list of the parties? What's the name of the software or hardware? How
exactly does the promiscuous key sharing work? Is it secure? If it isn't
actually secure, why should we even consider screwing up our APIs to
support it?

---

From: David McGrew <[email-masked]>
Date: Thu, 14 Sep 2006 17:01:06 -0700

Hi Dan,

On Sep 14, 2006, at 6:58 AM, D. J. Bernstein wrote:

> Specific references, please. What are those cases?

from my earlier mail: "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."  For that matter,  
any protocol which uses a long-term shared secret key, and which is  
not explicitly designed to support a distributed implementation, but  
which ends up being implemented in a distributed manner anyway.

> Why can't the key
> generator hand out a counter along with the key?

You're assuming that there is a central entity distributing the key;  
why should we enforce that limitation on our systems?  Distributed  
systems are non-trivial, and forcing the use of unique IVs on them  
would create a need for coordination that could otherwise be  
avoided.  If a central authority coordinates all of the counters,  
this would force a single point of failure on the system.  If the  
counters are managed in a distributed manner (e.g. a VRRP like  
election), there is a chance of failure due to a network partition  
that bifurcates a cluster.

> Who exactly is sharing

Allowing random IVs is screwing up our APIs?

Your final question neglects the first rationale that I gave for  
random IVs: with deterministic IVs, a provision must be made in order  
to ensure that the IV maintains its uniqueness across reboots, and it  
is not always convenient or desirable to do so.  That reason alone is  
sufficient.

David

---

From: "John Wilkinson" <[email-masked]>
Date: Thu, 14 Sep 2006 21:37:05 -0400

David,

Can you point me to an existing randomized AEAD specification that
might have a more detailed rationale its randomness? I'm having a hard
time understanding why this is necessary. It seems to me that almost
any device on a network will have some sort of unique identifier
associated with it, e.g., a MAC or IP address. This could be used to
guarantee a unique nonce as input to the AEAD algorithm.

It seems to me that your specification allows two types of AEAD
schemes that aren't interchangeable:

1) The deterministic AEAD schemes, which accept as input a nonce, and
which have a redundant output--the IV.

2) The randomized AEAD schemes, which accept as input an "IV
contribution" (which may be reused), and which have an internal source
of randomness which is used to generate the IV, which is then returned
to the user.

I tend to think that the internal source of randomness required for
the second class of schemes will be extremely difficult to design in a
portable (between architectures) way. In fact, I can't think of any
crypto specifications at this level that assume, as part of the
specification, an internal source of randomness. Usually, the
randomness is a required input, not an output. How would GCM or EAX or
CCM be specified if the algorithms required an internal source of
randomness? They would have to reference a particular class of
certified hardware random number generators.

Personally--and this is only my opinion--I find it much cleaner to
separate the specifications of AEAD schemes and sources of randomness.
Let all AEAD schemes be specified to be deterministic, and to accept
at input a nonce. Let random number generation be handled in another
component, that may have to be more machine-specific. I'd like to hear
others' opinions on this.

-John

---

From: "Doug Whiting" <[email-masked]>
Date: Thu, 14 Sep 2006 19:17:19 -0700

David, I have heard this argument as well for years. I guess I understand it in the abstract, but I still don't fully get how/where it would really work or be needed. Do we currently have a "segmented" seqNum version of ESP? If not, I don't understand how you can make the sequence numbers work across "uncoordinated" crypto modules. That is, anti-replay will cause problems it seems to me, both on transmit and receive, if there is no coordination. If there is a coordination, why can't the IV space just be divided among them (e.g., for N modules, use log2(N) bits in the IV to distinguish among the modules). Seems like that one-time setup would be very easy to do in a multi-module system, and it avoids the need for random IVs to avoid collisions, since each module can then just use a counter.
 
So I guess that, like Dan, I'm asking for a little better explanation of how a system requiring random IVs might actually be structured. If I can't picture at least one realistic scenario, I have a hard time seeing the need for it in a standard. Hopefully somebody can turn on the light bulb for me.
 
Doug Whiting

________________________________

From: David McGrew [mailto:[email-masked]]
Sent: Thu 9/14/2006 5:01 PM
To: D. J. Bernstein
Cc: [email-masked]
Subject: Re: [Cfrg] new authenticated encryption draft

Hi Dan,

David

---

From: David McGrew <[email-masked]>
Date: Fri, 15 Sep 2006 04:47:42 -0700

Hi Doug,

On Sep 14, 2006, at 7:17 PM, Doug Whiting wrote:

> David, I have heard this argument as well for years. I guess I  
> understand it in the abstract, but I still don't fully get how/ 
> where it would really work or be needed. Do we currently have a  
> "segmented" seqNum version of ESP?
> If not, I don't understand how you can make the sequence numbers  
> work across "uncoordinated" crypto modules. That is, anti-replay  
> will cause problems it seems to me, both on transmit and receive,  
> if there is no coordination. If there is a coordination, why can't  
> the IV space just be divided among them (e.g., for N modules, use  
> log2(N) bits in the IV to distinguish among the modules). Seems  
> like that one-time setup would be very easy to do in a multi-module  
> system, and it avoids the need for random IVs to avoid collisions,  
> since each module can then just use a counter.
>
> So I guess that, like Dan, I'm asking for a little better  
> explanation of how a system requiring random IVs might actually be  
> structured. If I can't picture at least one realistic scenario, I  
> have a hard time seeing the need for it in a standard. Hopefully  
> somebody can turn on the light bulb for me.

I'm not sure that ESP does needs to have random IVs. A better example  
of an application that would benefit from their use of would be an  
one that uses long-term shared secrets, especially a challenge/ 
response protocol.  Perhaps the draft didn't make it clear that it  
was intended for use in this sort of protocol as well.

In a C/R application, in order to use a sequence number as a nonce,  
there will be a need to have those values checkpointed into non- 
volatile memory, and there will be a need for the application to  
coordinate an "IV contribution" among the devices that share the  
secret.  If we require this sort of coordination, it makes it harder  
to distribute the application across multiple nodes.  In particular,  
there are existing applications (like mirrored servers) that don't do  
this sort of coordination because they don't currently need it.  If  
we require additional coordination, we'll give those applications a  
motivation to not use our spec, even if it is theoretically possible  
to provide that coordination.

David

---

From: David McGrew <[email-masked]>
Date: Fri, 15 Sep 2006 09:14:42 -0700

Hi John,

On Sep 14, 2006, at 6:37 PM, John Wilkinson wrote:

> might have a more detailed rationale its randomness?

EAX, for one.  It was an explicit design goal for that mode.

It is an aim for the AEAD draft to be useful in scenarios in which a  
secret key is stored over a long term, including challenge/response  
applications that use random nonces rather than sequence numbers for  
anti-replay protection.  Let me turn your question around: can you  
point me to an existing C/R protocol that uses unique IVs rather than  
random IVs?

> I'm having a hard

Most network identifiers are not suitable for use in constructing  
nonces.  For example, IP addresses are not suitable because of  
network address translation (NAT) and DHCP, besides the fact that the  
address identifies an interface rather than a device.  Using a  
network identifier would also put part of the IV under the control of  
a system which may not provide high assurance about the distinctness  
of the IVs, which is not always acceptable.

> specification, an internal source of randomness.

The DSA and ECDSA signature algorithms require an internal random  
source.	

> Usually, the

Why?

David

---

From: "John Wilkinson" <[email-masked]>
Date: Sat, 30 Sep 2006 17:58:10 -0400

David,

Sorry for my delayed response. I've been on business travel lately. I
think you've got a lot of good comments from other people, and I we
understand each others' positions, so I'll wrap up here.

> EAX, for one.  It was an explicit design goal for that mode.

I believe that EAX would be classified as "deterministic" under your
terms, not as "random". EAX takes a nonce, message, and header, and
deterministically produces a ciphertext (which includes both the
unencrypted header and authentication tag). Given the same inputs
(including nonce), EAX always produces the same ciphertext. Prof.
Wagner, would you like to chime in here?

> of the IVs, which is not always acceptable.

True, IP addresses may not always be useful in constructing nonces,
but unique device serial numbers may be.

> The DSA and ECDSA signature algorithms require an internal random

Yes, but they don't specify how to obtain that randomness.  From
Appendix 3 of FIPS:

"In the algorithms in sections 3.1 and 3.2, a secret b-bit seed-key is used."

The algorithms in sections 3.1 and 3.2 then specify how to use SHA to
"stretch" an initial b-bit seed-key into infinitely many secret bits
for generating private keys and signing.

If you can guarantee a device has a unique b-bit key, I don't
understand why you can't guarantee that it has a unique serial number.

In any event, good job on writing something up for the lazier among us
to throw darts at. :)

-John