Subject: Re: [Cfrg] GCM nonce reuse question

From: Mike Jones <[email-masked]>
Date: Tue, 2 Apr 2013 00:54:57 +0000

Hi David,

In reading this thread and http://tools.ietf.org/html/draft-mcgrew-iv-gen-02, I believe that it's OK, however if the usage is:

(Recipient #1 ciphertext, Recipient #1 authentication tag) = GCM(Key, Recipient #1 data, nonce #1, plain text)
(Recipient #2 ciphertext, Recipient #2 authentication tag) = GCM(Key, Recipient #2 data, nonce #2, plain text)

where nonce #1 and nonce #2 are guaranteed to be distinct?  Am I reading things correctly in that regard?

                                                                Thanks,
                                                                -- Mike

From: [email-masked] [mailto:[email-masked]] On Behalf Of David McGrew (mcgrew)
Sent: Thursday, March 28, 2013 4:15 AM
To: Jim Schaad
Cc: [email-masked]
Subject: Re: [Cfrg] GCM nonce reuse question

Hi Jim,

From: Jim Schaad <[email-masked]<mailto:[email-masked]>>
Date: Wednesday, March 27, 2013 6:43 PM
To: David McGrew <[email-masked]<mailto:[email-masked]>>
Cc: "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>
Subject: GCM nonce reuse question

David,

In doing a write up I became worried about a security property of the GCM encryption mode in the way that the JOSE group is currently using it.

There are known problems with not having a unique set of values for IVs and Key pairings.  Do these problems apply to having a different set of auxiliary data as well as the plain text?

Yes.  The security issues are summarized in http://tools.ietf.org/html/rfc5116#section-5.1.1  but apparently they are not described generally enough.   They should read "plaintext or associated data values".

Specifically the current way that GCM mode is being used in JOSE is

Recipient #1 authentication tag = GCM(Key, Recipient #1 data, nonce, plain text)
Recipient #2 authentication tag = GCM(Key, Recipient #2 data, nonce, plain text)

As the key, nonce and plain text are fixed it would produce the same encrypted text value but different authentication tags.

Can't do that.   Each invocation of the encryption operation needs a distinct nonce, unless all of the encryption operation inputs are identical.

Many thanks for calling this out, Jim.

David

Jim

---

From: "David McGrew (mcgrew)" <[email-masked]>
Date: Tue, 2 Apr 2013 13:32:15 +0000

Hi Mike,

From: Mike Jones <[email-masked]<mailto:[email-masked]>>
Date: Monday, April 1, 2013 8:54 PM
To: David McGrew <[email-masked]<mailto:[email-masked]>>, Jim Schaad <[email-masked]<mailto:[email-masked]>>
Cc: "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>, John Bradley <[email-masked]<mailto:[email-masked]>>
Subject: RE: GCM nonce reuse question

Hi David,

In reading this thread and http://tools.ietf.org/html/draft-mcgrew-iv-gen-02, I believe that it’s OK, however if the usage is:

Yes, that looks good.

David

                                                                Thanks,
                                                                -- Mike

From: [email-masked]<mailto:[email-masked]> [mailto:[email-masked]] On Behalf Of David McGrew (mcgrew)
Sent: Thursday, March 28, 2013 4:15 AM
To: Jim Schaad
Cc: [email-masked]<mailto:[email-masked]>
Subject: Re: [Cfrg] GCM nonce reuse question

Hi Jim,

David,

David

Jim

---

From: John Bradley <[email-masked]>
Date: Tue, 2 Apr 2013 11:41:21 -0300

David,

For draft-mcgrew-aead-aes-cbc-hmac-sha2 is the issue the same for using the same MAC_KEY, ENC_KEY  , IV  and plaintext with different AEAD.

I am guessing no good can come of that, but is it a known problem?

The other question is if doing the same thing but making the MAC_KEY different, while keeping the same ENC_KEY  for each AEAD avoids the problem?

The question comes up when trying to use encryption to multiple recipients where you are trying to use the same IV and ENC_KEY but allow for integrity protecting the algorithm identifier and other data that may be different for each recipient.

I expect that the simple solution of not integrity protecting the algorithm and key_id for the key wrapping and allowing RSA-OAEP to be replaced with RSA1_5 or other alg substitution attacks is no longer a recommended practice.   

Perhaps using the AEAD to integrity protect the envelope information is something that only really works in the single recipient case, and some other method is needed for multiple recipients.

Thanks 
John B.

On 2013-04-02, at 10:32 AM, "David McGrew (mcgrew)" <[email-masked]> wrote:

> Hi Mike,
> 
> From: Mike Jones <[email-masked]>
> To: David McGrew <[email-masked]>, Jim Schaad <[email-masked]>
> Cc: "[email-masked]" <[email-masked]>, John Bradley <[email-masked]>
>> From: Jim Schaad <[email-masked]>
>> To: David McGrew <[email-masked]>
>> Cc: "[email-masked]" <[email-masked]>

---

From: Mike Jones <[email-masked]>
Date: Tue, 2 Apr 2013 15:00:23 +0000

Actually, I was about to ask a similar question.  It's actually my assumption that it likely OK to perform multiple draft-mcgrew-aead-aes-cbc-hmac-sha2 operations where the Plaintext, Initialization Vector, and Key inputs are constant and the Additional Associated Data varies.  My reasoning is as follows...

The Authentication Tag outputs are the result of HMAC-SHA-2 operations over a combination of the AAD and Ciphertext using the HMAC Key.  For there to be a problem with the above, there would have to be a problem with using the same HMAC key on multiple distinct inputs.  But for there to be a problem with using the same HMAC key on multiple distinct inputs, I believe that effectively rests on whether there's a problem using the underlying hash function on multiple inputs.  Which if true, would mean that the cryptographic hash function doesn't have the desired cryptographic properties in the first place.

I'll readily admit that there could easily be a flaw in my chain of logic.  But on the surface of it, it seems like draft-mcgrew-aead-aes-cbc-hmac-sha2 operations should be OK in the multiple recipients case in a way that GCM isn't.

Thoughts?

                                                            -- Mike

From: John Bradley [mailto:[email-masked]]
Sent: Tuesday, April 02, 2013 7:41 AM
To: David McGrew (mcgrew)
Cc: Mike Jones; Jim Schaad; [email-masked]
Subject: Re: GCM nonce reuse question

David,

Thanks
John B.

On 2013-04-02, at 10:32 AM, "David McGrew (mcgrew)" <[email-masked]<mailto:[email-masked]>> wrote:

Hi Mike,

Hi David,

Yes, that looks good.

David

                                                                Thanks,
                                                                -- Mike

Hi Jim,

David,

David

Jim

---

From: John Bradley <[email-masked]>
Date: Tue, 2 Apr 2013 12:59:07 -0300

Jim,

I don't think Mike was proposing that as a solution, but rather an attempt to characterize the issue.

Yes changing the nonce per recipient would cause the cypher text produced by GCM to change per recipient and need to be repeated, making it an array of JWE effectively, and not really anyones idea of encrypting to multiple recipients.

In a later email I asked David if we have the same or similar issue with his AES-CBC+HMAC. 

Perhaps and I think it is too early to go there, perhaps not all encryption algorithms are equally well suited to using with multiple recipients.

John B.

On 2013-04-02, at 12:48 PM, "Jim Schaad" <[email-masked]> wrote:

> Mike,
>  
> I will note that this is not going to be considered an acceptable solution for the JOSE group.  You don’t really want to increase the size of the message by n*base64 encoding where in is the number of recipients.
>  
> Jim
>  
>  
> From: Mike Jones [mailto:[email-masked]] 
> Sent: Monday, April 01, 2013 5:55 PM
> To: David McGrew (mcgrew); Jim Schaad
> Cc: [email-masked]; John Bradley

---

From: Russ Housley <[email-masked]>
Date: Tue, 2 Apr 2013 12:12:02 -0400

Jim:

RFC 5084 and RFC 6476 both show approaches to the use of authenticated encryption with CMS.  Is there some reason that JOSE is not following one of these approaches?

Russ

On Apr 2, 2013, at 11:59 AM, John Bradley wrote:

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

---

From: Richard Barnes <[email-masked]>
Date: Tue, 2 Apr 2013 13:55:24 -0400

[re-added JOSE, since we're talking design now]

> Perhaps and I think it is too early to go there, perhaps not all encryption algorithms are equally well suited to using with multiple recipients.

This is the wrong conclusion.  GCM is suited just fine to multiple recipients, as it's use with CMS (AuthEnvelopedData) shows. 

The problem here is JWE, specifically the fact that the header (with per-recipient data) is covered by the integrity check.  If you remove the per-recipient data from the integrity check, then this problem goes away.  In that case, there is only one invocation of GCM (not one per recipient), so there's no problem.

So the choice that JOSE faces is from the following options:

Option 0. Outlaw GCM for multiple recipients.
  COST: GCM

Option 1. Keep per-recipient info under integrity check, and require a fresh nonce for each recipient
  COST: Removes all savings in the multiple recipient case 
  BENEFIT: Doesn't break backward compatibility with current, single-recipient JWE

Option 2. Remove per-recipient info from integrity check
  COST: Breaks backward compatibility with current, single-recipient JWE
  BENEFIT: Increases savings in multiple-recipient case (since no per-recipient integrity check value)

Option 0 is clearly not acceptable.  So basically, this is a choice about how much we want to let deployed code keep us from sensible architecture.

To me, the choice is clear.  Changing code is minor, short-term pain.  Getting architecture wrong is major, long-term pain.  Let's do option (2).

--Richard

---

From: John Bradley <[email-masked]>
Date: Tue, 2 Apr 2013 14:59:51 -0300

Russ,

We are close to those approaches.  However nether of those address using the Additional Authenticated Data(AAD).  They mention that it exists as an input but nothing more.

A difference between JOSE and CMS is that CMS allows non AEAD block ciphers, where JOSE requires all block cyphers to be AEAD.

That in theory allows us to use the AAD to integrity protect the envelope information including the identifier for the key wrap or key agreement.

In CMS the recipient-info values are not normally integrity protected.   

This tends to lead to a long discussion about if there is a real requirement to integrity protect them.  

In JOSE we decided to integrity protect the recipient-info values to prevent things like backwards computability attacks.  

This works just fine for one recipient but presents a problem using GCM for multiple recipients if the AAD is used to protect the recipient-info values.

That is the readers digest explanation on why those RFC are not sufficient on there own to answer the question of multiple recipients with integrity protected recipient-info.

I expect some people to chime in that we don't need to integrity protect recipient-info.

Regards
John B.

---

From: Richard Barnes <[email-masked]>
Date: Tue, 2 Apr 2013 15:05:35 -0400

John,

I don't think you've really answered Russ's question.  You've provided a *historical* reason, but not a *technical* reason why JOSE doesn't follow the same approach as CMS.

> That in theory allows us to use the AAD to integrity protect the envelope information including the identifier for the key wrap or key agreement.

The only reason JOSE has this requirement is because the header has to be integrity-protected.  So this is circular reasoning.

> In JOSE we decided to integrity protect the recipient-info values to prevent things like backwards computability attacks.  

The author of the backward-compatibility attack paper himself has said on the JOSE list that header integrity protection does not prevent BC attacks.
"""
... it does not matter, if he modifies an existing
secure object or creates a totally new object encrypted with an insecure
algorithm and appends it to the document.
"""
<http://www.ietf.org/mail-archive/web/jose/current/msg01881.html>

Do you have some other reason for integrity-protecting the recipient-info?  

> I expect some people to chime in that we don't need to integrity protect recipient-info.

<chime/>

--Richard

---

From: Russ Housley <[email-masked]>
Date: Tue, 2 Apr 2013 15:53:04 -0400

> In CMS the recipient-info values are not normally integrity protected.

Indeed.  If the things that are carried here are altered, then one of two things happens: (1) a value needed to compute the proper key is altered, which prevents the decrypt from working at all; or (2) a value for the recipient to locate their portion of the recipient information is altered, which prevents the intended recipient from decrypting the content.  In either case, the recipient is not fooled into accepting anything that is surprising to the sender.

Russ

---

From: John Bradley <[email-masked]>
Date: Tue, 2 Apr 2013 16:57:13 -0300

Richard,

The integrity check of the header is effective if as mentioned in the subsequent message in that thread http://www.ietf.org/mail-archive/web/jose/current/msg01909.html you implement the counter measure 
recommended for  RSA1_5  in https://tools.ietf.org/rfc/rfc3218.txt  continuing with a random CMK will cause the integrity check to fail and stop the oracle.

Richard is correct that there are two views on this, one where integrity protecting the envelope is good security and prevents against some known and perhaps unknown attacks (harder to prove), and others who see multiple recipients of the same encrypted body as a more important use case than the integrity protection.

Some of us are trying to find a way to accommodate both. 

The opinion of the CFRG on the value or non-value of integrity protecting the envelope information might be informative, though I think the last time we tried that the recommendation was for integrity protection, though at the time the trade off wasn't as clear.

Regards
John B.

---

From: John Bradley <[email-masked]>
Date: Tue, 2 Apr 2013 17:09:20 -0300

Russ,

The concern is not that the client will accept the token but that altering the algorithms gives an attacker additional ways to use the client as an oracle.
In JOSE JWE the envelope is also extensible so may contain other information that if changed might confuse the client.   I seem to recall that additional envelope information is possible in CMS but uncommon in practice.

Locking down the envelope is a possibility, however the work group just decided to allow additional elements to be ignored by default going in the other direction.

I expect Richard to plug a two envelope solution at this point:)

Regards
John B.

---

From: Richard Barnes <[email-masked]>
Date: Tue, 2 Apr 2013 16:22:38 -0400

The countermeasure you mention is for timing attacks in general against PKCS#1 v1.5.  It doesn't have anything to do with integrity protection of the header.

The hunt for a concrete security benefit continues...

--Richard

---

From: Richard Barnes <[email-masked]>
Date: Tue, 2 Apr 2013 16:39:47 -0400

Without having done any real analysis, I think that your conclusion is correct, i.e., that IV re-use in draft-mcgrew-aead-aes-cbc-hmac-sha2 is similar to IV re-use in CBC.

However, I'm not sure what good that information is.  JOSE still has to support GCM.

--Richard

On Apr 2, 2013, at 11:00 AM, Mike Jones <[email-masked]> wrote:

> Actually, I was about to ask a similar question.  It’s actually my assumption that it likely OK to perform multiple draft-mcgrew-aead-aes-cbc-hmac-sha2 operations where the Plaintext, Initialization Vector, and Key inputs are constant and the Additional Associated Data varies.  My reasoning is as follows…
>  
> The Authentication Tag outputs are the result of HMAC-SHA-2 operations over a combination of the AAD and Ciphertext using the HMAC Key.  For there to be a problem with the above, there would have to be a problem with using the same HMAC key on multiple distinct inputs.  But for there to be a problem with using the same HMAC key on multiple distinct inputs, I believe that effectively rests on whether there’s a problem using the underlying hash function on multiple inputs.  Which if true, would mean that the cryptographic hash function doesn’t have the desired cryptographic properties in the first place.
>  
> I’ll readily admit that there could easily be a flaw in my chain of logic.  But on the surface of it, it seems like draft-mcgrew-aead-aes-cbc-hmac-sha2 operations should be OK in the multiple recipients case in a way that GCM isn’t.
>  
> Thoughts?
>  
>                                                             -- Mike
>

---

From: "Manger, James H" <[email-masked]>
Date: Mon, 15 Apr 2013 11:55:34 +1000

I think there are more options for handling multiple recipients of AEAD-secured content:

Option 3: Put all per-recipient info into one header; keep this header under the AEAD integrity check; have one nonce.
  COST: All recipients need to be known (and their key exchange info created) before the AEAD algorithm is applied.
  COST: The JWE JSON header structure needs to be adjusted (eg to have an array of recipient info) so it is not backward compatible with current drafts.
  COST: Doesn't help use cases where one recipient forwards an AEAD-secured message on to a new recipient (eg an XMPP system receives a message secured for a user and re-secures it for a specific device of that user). Changing recipients requires reapplying the AEAD operations.
  COST: Each recipient needs to see key exchange info of all recipients (privacy impact?).
  POSSIBLE-BENEFIT: Recipients, key exchanges, parameters, and content is secured as a complete unit.

Option 2b: Remove per-recipient info from AEAD integrity check; but add AEAD details to each key exchange. For instance, info about an AEAD operation (alg id, key id etc) potentially even including the whole ciphertext is used as the "label" for the RSAES-OAEP-ENCRYPT operation that encrypts the AEAD secret key for a recipient.
  BENEFIT: The key exchange is tied to a specific AEAD operation.
  COST: Crypto is not typically done like this; uncertain as to what exact security properties you are getting. Perhaps there are some similarities to NIST Concat KDF that adds "context" to key derivation: this adds "context" about an AEAD operation to the key exchange.

I agree with Richard Barnes that the per-recipient key exchange details should be outside the AEAD operation (not covered by the AEAD integrity check). Go with option 2 or 2b.
Then, separately, we can decide which details of the AEAD operation should be bound to each key exchange: none? AEAD key length? AEAD alg id? whole AEAD header? AEAD ciphertext? other context?

--
James Manger

> ----------
> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> Richard Barnes
> Sent: Wednesday, 3 April 2013 4:55 AM
> … 
> The problem here is JWE, specifically the fact that the header (with
> per-recipient data) is covered by the integrity check.  If you remove
> the per-recipient data from the integrity check, then this problem goes
> away.  In that case, there is only one invocation of GCM (not one per
> recipient), so there's no problem.
> 
> Option 0 is clearly not acceptable.  So basically, this is a choice
> about how much we want to let deployed code keep us from sensible
> architecture.
> 
> To me, the choice is clear.  Changing code is minor, short-term pain.
> Getting architecture wrong is major, long-term pain.  Let's do option
> (2).

---

From: Richard Barnes <[email-masked]>
Date: Mon, 15 Apr 2013 11:25:56 -0400

On Sun, Apr 14, 2013 at 9:55 PM, Manger, James H <
[email-masked]> wrote:

> Option 3: Put all per-recipient info into one header; keep this header
> under the AEAD integrity check; have one nonce.
>   COST: All recipients need to be known (and their key exchange info
> created) before the AEAD algorithm is applied.
>   COST: The JWE JSON header structure needs to be adjusted (eg to have an
> array of recipient info) so it is not backward compatible with current
> drafts.
>   COST: Doesn't help use cases where one recipient forwards an
> AEAD-secured message on to a new recipient (eg an XMPP system receives a
> message secured for a user and re-secures it for a specific device of that
> user). Changing recipients requires reapplying the AEAD operations.
> Option 2b: Remove per-recipient info from AEAD integrity check; but add
> AEAD details to each key exchange. For instance, info about an AEAD
> operation (alg id, key id etc) potentially even including the whole
> ciphertext is used as the "label" for the RSAES-OAEP-ENCRYPT operation that
> encrypts the AEAD secret key for a recipient.
>   COST: Crypto is not typically done like this; uncertain as to what exact
> security properties you are getting. Perhaps there are some similarities to
> NIST Concat KDF that adds "context" to key derivation: this adds "context"
> about an AEAD operation to the key exchange.
>
>
> I agree with Richard Barnes that the per-recipient key exchange details
> should be outside the AEAD operation (not covered by the AEAD integrity
> check). Go with option 2 or 2b.
> Then, separately, we can decide which details of the AEAD operation should
> be bound to each key exchange: none? AEAD key length? AEAD alg id? whole
> AEAD header? AEAD ciphertext? other context?
>
>
> --
> James Manger
>
>

Hey James,

Thanks for this.  I agree that Option 3 is a valid possibility, but not a
desirable one.

Option 2b is an interesting possibility.  Effectively, you would be
including a hash of the JWE (sans key) under the key wrap integrity check,
binding the key to the JWE.   I would note that we're already talking about
adding the ability to bind attributes to wrapped keys (for WebCrypto).  In
light of that, the "JWE digest" could just be included as one of those
attributes.

At the same time, this attribute should be optional, since I think there
are use cases where the CMK is not entirely ephemeral.  For example, I
think the current XMPP e2e document uses it as a session key rather than an
individual message key, so you wouldn't want to limit the key to a single
JWE.

So I think that lands us back at Option 2, with one more reason to make JWE
key wrapping the same as general key wrapping
[draft-barnes-jose-key-wrapping].

--Richard

---

From: Richard Barnes <[email-masked]>
Date: Mon, 15 Apr 2013 13:39:03 -0400

On Mon, Apr 15, 2013 at 11:50 AM, Matt Miller <[email-masked]> wrote:

>
> On Apr 15, 2013, at 9:25 AM, Richard Barnes <[email-masked]>
>  wrote:
>
> XMPP e2e has both a session key and a per-message key. The per-message key
> is protected by the session key.
>
> That said, I also think Option 2 or 2b makes the most sense.
>
>
> - m&m
>
> Matt Miller < [email-masked] >
> Cisco Systems, Inc.
>

Thanks for the clarification.  I think the point stands, however, that the
"JWE-digest" attribute can be added as a protected attribute to the wrapped
key -- if we do wrapped keys right!

--Richard