Subject: [Cfrg] New Version Notification for draft-mcgrew-aead-aes-cbc-hmac-sha2-03.txt

From: David McGrew <[email-masked]>
Date: Thu, 13 Feb 2014 19:49:25 -0500

Hi,

the latest version of this draft is out.  Thanks are due to Jim Schaad 
and Rob Napier for their feedback on version 02.

The goals of this draft are to provide an authenticated encryption 
scheme suitable for use in those cases where CBC and HMAC are available, 
but no dedicated AE schemes are available.   Also, it doesn't require 
deterministic nonces, which itself is useful in some situations.

It might be nice to add a description of how IVs can be pseudorandomly 
generated.   It would be especially useful to generate the IV using the 
same key as used for encryption, with an unpredictable counter, or 
something like that.   Is anyone aware of a security proof that could be 
cited for that sort of technique?   I think that some systems would have 
a much easier time maintaining a counter than they would generating 
truly random IVs, which is reasonable motivation in my opinion.   Glad 
to hear other thoughts on this subject.

David

--

A new version of I-D, draft-mcgrew-aead-aes-cbc-hmac-sha2-03.txt
has been successfully submitted by David McGrew and posted to the
IETF repository.

Name:		draft-mcgrew-aead-aes-cbc-hmac-sha2
Revision:	03
Title:		Authenticated Encryption with AES-CBC and HMAC-SHA
Document date:	2014-02-13
Group:		Individual Submission
Pages:		29
URL:            http://www.ietf.org/internet-drafts/draft-mcgrew-aead-aes-cbc-hmac-sha2-03.txt
Status:         https://datatracker.ietf.org/doc/draft-mcgrew-aead-aes-cbc-hmac-sha2/
Htmlized:       http://tools.ietf.org/html/draft-mcgrew-aead-aes-cbc-hmac-sha2-03
Diff:           http://www.ietf.org/rfcdiff?url2=draft-mcgrew-aead-aes-cbc-hmac-sha2-03

Abstract:
    This document specifies algorithms for authenticated encryption with
    associated data (AEAD) that are based on the composition of the
    Advanced Encryption Standard (AES) in the Cipher Block Chaining (CBC)
    mode of operation for encryption, and the HMAC-SHA message
    authentication code (MAC).

    These are randomized encryption algorithms, and thus are suitable for
    use with applications that cannot provide distinct nonces to each
    invocation of the AEAD encrypt operation.

	

Please note that it may take a couple of minutes from the time of submission
until the htmlized version and diff are available at tools.ietf.org.

The IETF Secretariat

.

---

From: Watson Ladd <[email-masked]>
Date: Thu, 13 Feb 2014 17:44:05 -0800

On Thu, Feb 13, 2014 at 4:49 PM, David McGrew <[email-masked]> wrote:

>  Hi,
>
> the latest version of this draft is out.  Thanks are due to Jim Schaad and
> Rob Napier for their feedback on version 02.
>
> The goals of this draft are to provide an authenticated encryption scheme
> suitable for use in those cases where CBC and HMAC are available, but no
> dedicated AE schemes are available.   Also, it doesn't require
> cited for that sort of technique?   I think that some systems would have a
> much easier time maintaining a counter than they would generating truly
> random IVs, which is reasonable motivation in my opinion.   Glad to hear
> other thoughts on this subject.
>

Doesn't the usual PRF definition give you exactly this?

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg
>
>

-- 
"Those who would give up Essential Liberty to purchase a little Temporary
Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: "Manger, James" <[email-masked]>
Date: Fri, 14 Feb 2014 13:44:38 +1100

> Htmlized:       http://tools.ietf.org/html/draft-mcgrew-aead-aes-cbc-hmac-sha2-03

Section 2.1. "Encryption" adds:

  "The key MUST MUST be generated in a way that is uniformly random or pseudorandom"

This must be a doubly important requirement ;-)

Section 2.2 "Decryption" step 5 talks about removing the padding (1 byte of 0x01 to 16 bytes of 0x10). It requires an implementation to partially check the padding, but not completely. For instance, if the last byte is 0x22 then the operation fails and data is zeroized. Whereas if the last 2 bytes are 0x22 0x02 then decryption will probably succeed, removing those 2 bytes as padding. A better implementation is probably to infer the padding length from the last 4 bits. That can never fail.

Section 2.4 AEAD_AES_128_CBC_HMAC_SHA_256 has the wrong key length. The key length is mentioned twice. Both should be 32 octets. One was wrong in the previous draft, but now both are wrong! I guess a fixed was applied at the wrong point.

Typo: missing ) in section 2.4
   makes use of a random value (the IV described in Appendix A.

Typo: section 2.4
WRONG   ...(AES) [FIPS197] block cipher defined in CBC mode.
RIGHT   ...(AES) [FIPS197] block cipher in CBC mode.

Otherwise it looks great.

--
James Manger

---

From: "Manger, James" <[email-masked]>
Date: Fri, 14 Feb 2014 16:12:19 +1100

> Htmlized:       http://tools.ietf.org/html/draft-mcgrew-aead-aes-cbc-

Appendix B "Alternative Interface for Legacy Encoding" isn't quite clear that "the ciphertext C, as described in Appendix A" is only C_1 || ... || C_n. It excludes C_0 (which is the IV) as the IV is a separate field.

Suggested change (in two places):
FROM
      the initialization vector IV as defined in Appendix A,
      the ciphertext C, as defined in Appendix A, and
      the message authentication tag T, as defined in Section 2.1.
TO
      the initialization vector IV as defined in Appendix A,
      the ciphertext excluding the IV (C_1 || ... || C_n), as defined in Appendix A, and
      the message authentication tag T, as defined in Section 2.1.

K and A are not mentioned as inputs to the decryption operation.
Suggested change:
FROM
   The inputs to the decryption operation are:
      ... IV ... C ... T
TO
   The inputs to the decryption operation (in addition
   to the secret key K and associated data A) are:
      ... IV ... C ... T

Typo: appendix B (missing "are")
  The inputs to the encryption operation *are* the same

--
James Manger

---

From: David Jacobson <[email-masked]>
Date: Thu, 13 Feb 2014 22:34:28 -0800

On 2/13/14 4:49 PM, David McGrew wrote:
> scheme suitable for use in those cases where CBC and HMAC are 
> available, but no dedicated AE schemes are available.   Also, it 
> doesn't require deterministic nonces, which itself is useful in some 
> situations.
>
> generated.   It would be especially useful to generate the IV using 
> the same key as used for encryption, with an unpredictable counter, or 
> something like that.   Is anyone aware of a security proof that could 
> be cited for that sort of technique?   I think that some systems would 
> have a much easier time maintaining a counter than they would 
> generating truly random IVs, which is reasonable motivation in my 
> opinion.   Glad to hear other thoughts on this subject.
>
> David
>
> --
There is a mismatched parenthesis in the first sentence of Section 2.4.

It seems that your intent is to truncate the MAC to the length of the 
MAC_KEY.  Also these two seem to be half the size of the hash function 
output block size.  However, that is not explicitly stated.  I suggest 
you mention that somewhere.

Above you mention generating the IV with the same key as is used for 
encryption.  Note that this is in conflict with Section 3, which says 
"However, if a pseudorandom method is used, that method MUST NOT make 
use of ENC_KEY or MAC_KEY."  Maybe you are thinking the we CFRG people 
can come up with a safe way to use the encryption key, but you don't 
trust users to do that.

Above you mention an unpredictable counter.  I suspect you mean a 
counter that begins at a secret value, and wraps in the obvious way.  
Therefore it has be generated at random and stored in secure 
non-volatile storage.  So it seems strictly harder than just 
randomness.  So I don't know what is gained by using an unpredictable 
counter.

You have chosen to avoid nonces, but instead to require randomness.   It 
is debatable whether this is a good tradeoff.  I suspect it would be 
better to have a system that requires a nonce, where the only 
requirement is that it is doesn't repeat (or is sufficiently unlikely to 
repeat, to allow for random nonces if the user finds that convenient).  
Examples of suitable nonces are a counter, time, or random.  You could 
compute the IV  as SHA256(E_ek(nonce)) and use only the first 128 bits.  
E_ek means encrypt with the encryption key.  This doesn't leak an ECB 
mode plaintext-ciphertext pair to an attacker, even if he knows or can 
easily guess the nonce (e.g. when the nonce is time or when he knows the 
number of messages that have been sent).  Since the attacker doesn't 
know the encryption key, he can't predict the nonce.

You have a key that is the concatenation of the MAC_KEY and the 
ENC_KEY.  This might tempt lazy or incompetent implementers  do 
something stupid.  You might consider deriving the MAC_KEY and ENC_KEY 
from a single key.  If you did that, you could generate the MAC_KEY, 
ENC_KEY, and IV like this.  Use HMAC(key, 0x1 || counter) to generate 
enough bits for MAC_KEY and ENC_KEY.  Use HMAC(key, 0x2 || nonce) to 
compute the IV.  (This is a different proposal for the IV than the last 
paragraph.)  Even if the  attacker can predict the nonce, he cannot 
predict the IV because he doesn't know the key.

If you really don't want to accept a nonce, have the library generate 
its own nonce with something from inside the system, such processID || 
date_time || message_counter_in_this_process. (Remember, this only has 
to be unique within users of the same key. It doesn't have to be 
world-wide unique.)  The downside is that any such scheme is specific to 
a particular system.  I think most of us would rather say "compute this 
and pass it in as the nonce" than "modify the code to collect this".

As to the question you actually asked, I don't see that you can have 
randomness in the encryption if you don't have either randomness as an 
input or use a nonce.  It is completely deterministic and the same 
message will be encrypted the same every time.  However, you can do a 
bit better.  In some applications the authenticated but unencrypted part 
(called A in the draft) will contain a sequence number or timestamp.  If 
you compute MAC_KEY, ENC_KEY, and IV similar to the way in the last 
paragraph, but change the IV computation to HMAC(key, 0x2 || A).  
Absolutely identical messages will result in the same bits over the 
channel, but if the unencrypted part contains a sequence number or 
timestamp, the encrypted part will be randomized.  My final suggestion 
is to compute IV as HMAC(key, 0x2 || length(A) || A || nonce).  This 
way, users who supply non-repeating nonces get randomized encryption, 
and even if they mess up, they will get randomized encryption if the A 
part has a time stamp or sequence number.

     --David Jacobson

> URL:http://www.ietf.org/internet-drafts/draft-mcgrew-aead-aes-cbc-hmac-sha2-03.txt
> Status:https://datatracker.ietf.org/doc/draft-mcgrew-aead-aes-cbc-hmac-sha2/
> Htmlized:http://tools.ietf.org/html/draft-mcgrew-aead-aes-cbc-hmac-sha2-03
> Diff:http://www.ietf.org/rfcdiff?url2=draft-mcgrew-aead-aes-cbc-hmac-sha2-03
>
> Abstract:

---

From: David McGrew <[email-masked]>
Date: Fri, 14 Feb 2014 06:05:51 -0500

On 02/13/2014 08:44 PM, Watson Ladd wrote:
>
>
>
> On Thu, Feb 13, 2014 at 4:49 PM, David McGrew <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>     Hi,
>
>     the latest version of this draft is out.  Thanks are due to Jim
>     Schaad and Rob Napier for their feedback on version 02.
>
>     doesn't require deterministic nonces, which itself is useful in
>     some situations.
>
>     It might be nice to add a description of how IVs can be
>     pseudorandomly generated.   It would be especially useful to
>     generate the IV using the same key as used for encryption, with an
>     unpredictable counter, or something like that.   Is anyone aware
>     of a security proof that could be cited for that sort of
>     technique?   I think that some systems would have a much easier
>     time maintaining a counter than they would generating truly random
>     IVs, which is reasonable motivation in my opinion.   Glad to hear

Yes; the only tricky bit is showing that using the CBC encryption key to 
generate pseudorandom IVs doesn't affect CBC encryption security.   I'm 
sure that it can be done securely, but I don't know of a proof of 
security (for using a single key for both CBC and to generate IVs) that 
I can point to.

David

>     until the htmlized version and diff are available attools.ietf.org  <http://tools.ietf.org>.
>
>     The IETF Secretariat
>
>     .
>
>
>
>
>     [email-masked] <mailto:[email-masked]>
> "Those who would give up Essential Liberty to purchase a little 
> Temporary Safety deserve neither  Liberty nor Safety."
> -- Benjamin Franklin

---

From: David McGrew <[email-masked]>
Date: Fri, 14 Feb 2014 06:21:58 -0500

>        the message authentication tag T, as defined in Section 2.1.

good catch; I've made these changes.

>    The inputs to the encryption operation *are* the same

Fixed, along with the other typos identified in your previous email.   
Many thanks for the quick review.

David

---

From: David McGrew <[email-masked]>
Date: Fri, 14 Feb 2014 06:44:40 -0500

Hi David,

On 02/14/2014 01:34 AM, David Jacobson wrote:
>> pseudorandomly generated.   It would be especially useful to generate 
>> the IV using the same key as used for encryption, with an 
>> unpredictable counter, or something like that.   Is anyone aware of a 
>> security proof that could be cited for that sort of technique?   I 
>> think that some systems would have a much easier time maintaining a 
>> counter than they would generating truly random IVs, which is 
>> reasonable motivation in my opinion.   Glad to hear other thoughts on 
>> this subject.
>>
>> David
>>
>> --

got it.

> you mention that somewhere.

Added this to the rationale.

<t>
The algorithms in this note truncate the HMAC output to half of the
size of the output of the underlying hash function.  This size is the
recommended minimum (see Section 5 of <xref target="RFC2104"/>), and
this parameter choice has withstood the test of time.
</t>

> can come up with a safe way to use the encryption key, but you don't 

RIght; if there is a security analysis somewhere that I can cite, I 
would like to do so.   Otherwise, I want to leave it out.

> randomness.  So I don't know what is gained by using an unpredictable 

It would enable the algorithms to be used for encryption on devices that 
lacked a random source, and it would allow other systems to avoid the 
complication of calling a random source during each encryption 
invocation.   I don't have a lot of trust in good random sources being 
done correctly and being available.   Maybe another good way to say it 
is that the requirement to tap into good randomness or pseudorandomness 
is a very significant external dependency.    For example, if a 
non-crypto-specialist downloads the source code for these ciphersuites 
off the Internet and links it to their application, it would be much 
better to have no such external dependancy, since the developer might 
not even understand the randomness requirement.

>
> You have chosen to avoid nonces, but instead to require randomness.   
> It is debatable whether this is a good tradeoff.  I suspect it would 
> be better to have a system that requires a nonce, where the only 
> requirement is that it is doesn't repeat (or is sufficiently unlikely 
> to repeat, to allow for random nonces if the user finds that convenient). 

Respectfully disagree.   The goal here is not to develop a new AEAD 
algorithm, but rather to show people how they can construct a good AEAD 
out of the CBC and HMAC components that they probably have in their 
toolkits.   The Rationale sections outlines the goals.

> compute the IV  as SHA256(E_ek(nonce)) and use only the first 128 
> bits.  E_ek means encrypt with the encryption key.  This doesn't leak 
> an ECB mode plaintext-ciphertext pair to an attacker, even if he knows 
> or can easily guess the nonce (e.g. when the nonce is time or when he 
> knows the number of messages that have been sent).  Since the attacker 
> doesn't know the encryption key, he can't predict the nonce.
>
> compute the IV.  (This is a different proposal for the IV than the 
> last paragraph.)  Even if the attacker can predict the nonce, he 
> cannot predict the IV because he doesn't know the key.

This draft consciously avoids key derivation for simplicity, and to 
avoid potential complications around validation (especially FIPS-140 key 
derivation).

> world-wide unique.)  The downside is that any such scheme is specific 
> to a particular system.  I think most of us would rather say "compute 
> this and pass it in as the nonce" than "modify the code to collect this".
>
> bit better.  In some applications the authenticated but unencrypted 
> part (called A in the draft) will contain a sequence number or 
> timestamp.  If you compute MAC_KEY, ENC_KEY, and IV similar to the way 
> in the last paragraph, but change the IV computation to HMAC(key, 0x2 
> || A). Absolutely identical messages will result in the same bits over 
> the channel, but if the unencrypted part contains a sequence number or 

Thanks for your comments and feedback.   You bring up some valid 
considerations, some of which fall outside the particular (modest) goals 
of this draft.

David

---

From: Watson Ladd <[email-masked]>
Date: Fri, 14 Feb 2014 07:55:12 -0800

On Fri, Feb 14, 2014 at 3:05 AM, David McGrew <[email-masked]> wrote:

> sure that it can be done securely, but I don't know of a proof of security
> (for using a single key for both CBC and to generate IVs) that I can point
> to.
>

Okay, I didn't realize we needed a single key. Then I think the following
proof works, but I don't know how strong the result is. Replace the PRP
with a PRF by Bernstein's lemma. Then so long as we've never encrypted a
block equal to the counter, life is good. Show this can't happen with more
than negligible probability for the ideal PRF. Conclude that an attacker
who breaks the scheme turns into one who can distinguish the PRF from an
ideal PRF with some loss.

Sincerely,
Watson Ladd

---

From: "Paterson, Kenny" <[email-masked]>
Date: Fri, 14 Feb 2014 16:04:51 +0000

Watson,

Yes, that proof idea should work out.

It’s related to the proof for AES-CCM by Jonsson (this scheme uses CBC-MAC on top of CTR mode; the same issue about avoiding colliding counters/CBC chaining variable crops up there too): http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/ccm-ad1.pdf

Cheers,

Kenny

From: Cfrg [mailto:[email-masked]] On Behalf Of Watson Ladd
Sent: 14 February 2014 15:55
To: David McGrew
Cc: [email-masked]
Subject: Re: [Cfrg] New Version Notification for draft-mcgrew-aead-aes-cbc-hmac-sha2-03.txt

On Fri, Feb 14, 2014 at 3:05 AM, David McGrew <[email-masked]<mailto:[email-masked]>> wrote:
On 02/13/2014 08:44 PM, Watson Ladd wrote:

On Thu, Feb 13, 2014 at 4:49 PM, David McGrew <[email-masked]<mailto:[email-masked]>> wrote:
Hi,

the latest version of this draft is out.  Thanks are due to Jim Schaad and Rob Napier for their feedback on version 02.

The goals of this draft are to provide an authenticated encryption scheme suitable for use in those cases where CBC and HMAC are available, but no dedicated AE schemes are available.   Also, it doesn't require deterministic nonces, which itself is useful in some situations.

It might be nice to add a description of how IVs can be pseudorandomly generated.   It would be especially useful to generate the IV using the same key as used for encryption, with an unpredictable counter, or something like that.   Is anyone aware of a security proof that could be cited for that sort of technique?   I think that some systems would have a much easier time maintaining a counter than they would generating truly random IVs, which is reasonable motivation in my opinion.   Glad to hear other thoughts on this subject.

Yes; the only tricky bit is showing that using the CBC encryption key to generate pseudorandom IVs doesn't affect CBC encryption security.   I'm sure that it can be done securely, but I don't know of a proof of security (for using a single key for both CBC and to generate IVs) that I can point to.

Okay, I didn't realize we needed a single key. Then I think the following proof works, but I don't know how strong the result is. Replace the PRP with a PRF by Bernstein's lemma. Then so long as we've never encrypted a block equal to the counter, life is good. Show this can't happen with more than negligible probability for the ideal PRF. Conclude that an attacker who breaks the scheme turns into one who can distinguish the PRF from an ideal PRF with some loss.

Sincerely,
Watson Ladd

David

David

--

IETF repository.

Revision:  03

Pages:            29

Abstract:

until the htmlized version and diff are available at tools.ietf.org<http://tools.ietf.org>.

The IETF Secretariat

.

_______________________________________________
Cfrg mailing list
[email-masked]<mailto:[email-masked]>
http://www.irtf.org/mailman/listinfo/cfrg

--
"Those who would give up Essential Liberty to purchase a little Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

--
"Those who would give up Essential Liberty to purchase a little Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: David Jacobson <[email-masked]>
Date: Fri, 14 Feb 2014 08:26:17 -0800

On 2/14/14 3:44 AM, David McGrew wrote:
>>> unpredictable counter, or something like that.   Is anyone aware of 
>>> a security proof that could be cited for that sort of technique?   I 
>>> reasonable motivation in my opinion.   Glad to hear other thoughts 
>>> on this subject.
>>>
>>> David
>>>
>>> --
>> [SNIP]
>>
> It would enable the algorithms to be used for encryption on devices 
> that lacked a random source, and it would allow other systems to avoid 
> the complication of calling a random source during each encryption 
> is that the requirement to tap into good randomness or 
> pseudorandomness is a very significant external dependency.    For 
> example, if a non-crypto-specialist downloads the source code for 
> these ciphersuites off the Internet and links it to their application, 
> it would be much better to have no such external dependancy, since the 
> developer might not even understand the randomness requirement.
>
You may have missed my point.  If  by "unpredictable counter" you mean 
one where the starting value is secret and it is incremented modulo the 
counter range once for each message, then you need randomness to get the 
initial counter value.  So you haven't eliminated the need for 
randomness.  Now maybe you were thinking of something like the TICK 
counter available in some CPUs.  It is incremented once each clock tick, 
and hence is pretty hard for the attacker to predict exactly.

[SNIP]
> avoid potential complications around validation (especially FIPS-140 
> key derivation).
>
>
Thank you for clarifying that.  Thus the key you describe may be an 
abstraction for managed keys in a hardware security module, and you 
can't get to them, and it is hard to push new ones in.  That changes a 
lot of things.

There is another concern:  replay attacks.   There is no way for the 
receiver to differentiate between a genuine fresh message sent by the 
sender and a replay of that message sent by an attacker.  I suggest that 
you mention that fact in Section 6 (Security Concerns), and say that for 
applications where replay resistance is required, the application is 
responsible for implementing replay resistance. The data used to 
implement replay resistance (say a sequence number or time stamp) can 
safely be put in the unencrypted portion.

    --David Jacobson

[SNIP]