Subject: Re: [jose] FW: GCM nonce reuse question

From: Vijay Bharadwaj <[email-masked]>
Date: Tue, 2 Apr 2013 08:21:09 +0000

I was reading the JWE draft today for different reasons, and came here to point out exactly this issue. It was not clear to me why there were multiple headers and integrity values.

Also, it seems to me the header in JWE is defined in a way that is suboptimal for the multiple recipient case. It mixes parameters related to the encryption of payload with CMK (of which you only need one) with parameters related to the encryption of the CMK with the recipient's key (of which you need one per encrypted key). Why not refactor these to look more like CMS? In other words:

Array of recipients, where each is: {alg: <alg>, <recipient identifier such as jwk>, <encrypted CMK>}
Header: <parameters related to compression and CMK encryption, including IV>
Ciphertext: <encoded ciphertext>
Integrity_value: <encoded authentication tag with recipients and header as AAD>

Putting the integrity check at the end reduces the amount of buffering in the implementation that produces the message.

Thoughts?

From: [email-masked] [mailto:[email-masked]] On Behalf Of Richard Barnes
Sent: Thursday, March 28, 2013 7:54 PM
To: Mike Jones
Cc: Jim Schaad; [email-masked]; [email-masked]
Subject: Re: [jose] FW: GCM nonce reuse question

[trimmed CFRG, since we're talking about JOSE now]

Out of curiosity, what text are you planning to add?

As I read David's response, he is saying that GCM is unusable with multiple recipients, because multiple header values are fed into GCM with the same nonce.

Outlawing GCM is not an acceptable outcome.

Instead, we should fix the underlying issue.  Namely, we should make the header value the same for all recipients.  Or, even better, remove the header from the AAD field.

Imagine a world in which the JOSE header is not input as AAD to GCM (i.e., it receives no integrity protection).  Instead, we provide an actual "AAD field" that contains the value for that field in the AEAD computation:

OLD: header.key.iv.ciphertext.mac
NEW: header.key.iv.aad.ciphertext.mac

That world is simpler to write code for (since you don't have to keep the encoded header around), supports more applications (since you can actually use the AAD field), and the problems with GCM do not exist.  Let's create that world!

--Richard

On Thu, Mar 28, 2013 at 10:06 PM, Mike Jones <[email-masked]<mailto:[email-masked]>> wrote:
I'll plan to add text to the GCM section of JWA during the current round of edits pointing this out.  David McGrew was also going to get me some text about constraints on GCM initialization vector values.

                                                            -- Mike

From: [email-masked]<mailto:[email-masked]> [mailto:[email-masked]<mailto:[email-masked]>] On Behalf Of Jim Schaad
Sent: Thursday, March 28, 2013 7:02 PM
To: [email-masked]<mailto:[email-masked]>
Subject: [jose] FW: GCM nonce reuse question

For those people not on the CFRG list -

Jim

From: David McGrew (mcgrew) [mailto:[email-masked]]
Sent: Thursday, March 28, 2013 4:15 AM
To: Jim Schaad
Cc: [email-masked]<mailto:[email-masked]>
Subject: Re: 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

_______________________________________________
jose mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/jose

---

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

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

On Apr 2, 2013, at 11:59 AM, John Bradley <[email-masked]> wrote:

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

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

> 
> 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
>> 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:
>>  
>> (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)
>> Cc: [email-masked]
>> Subject: Re: [Cfrg] GCM nonce reuse question
>>  
>> Hi Jim,
>>  
>> From: Jim Schaad <[email-masked]>
>> To: David McGrew <[email-masked]>
>> Cc: "[email-masked]" <[email-masked]>
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

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

> ----------
> 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: Matt Miller <[email-masked]>
Date: Mon, 15 Apr 2013 09:50:57 -0600

> individual message key, so you wouldn't want to limit the key to a single

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.

---

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

> Matt Miller < [email-masked] >

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