Subject: [jose] Issue #23 - Make crypto indepenent of binary encoding

From: "Jim Schaad" <[email-masked]>
Date: Tue, 11 Jun 2013 11:12:02 -0700

<not chair>

Richard,

I do not currently believe that this is a doable item.  In order for me to
believe otherwise you will need to give a concrete proposal about how to
solve the problem of things drifting back and forth.  Given the text

{xxx}\r\r\rThis is the body

How does one know where the dividing line between the JSON header and the
body begins?  Until this is completely solved what you propose is not doable
and the current method of base64 encoding will be required.

Jim

---

From: Richard Barnes <[email-masked]>
Date: Tue, 11 Jun 2013 14:43:16 -0400

I don't know what you mean by "the problem of things drifting back and
forth".  Let me try to be more concrete.

Consider the following JWE:

{
    "header": { "alg": "dir" }
    "protect":
"eyJlbmMiOiAiQTEyOEdDTSIsICJraWQiOiAiY2VsdWkKDcOnYQoNCWzDoC1iYXMifQ"
    ...
}

The "protect" here is the encoding of the header '{"enc": "A128GCM", "kid":
"celui\r\nça\r\n\tlà-bas"}'  (hex=63 65 6C 75 69 0A 0D C3 A7 61 0A 0D 09 6C
C3 A0 2D 62 61 73).

In the current draft, the AAD for the AEAD is the base64-encoded version.
 The proposal here is just to make it the UTF-8 version, before
base64-encoding instead of after:

OLD:
AAD = eyJlbmMiOiAiQTEyOEdDTSIsICJraWQiOiAiY2VsdWkKDcOnYQoNCWzDoC1iYXMifQ
(== 65 79 4a 6c 62 6d 4d 69 4f 69 41 69 51 54 45 79 4f 45 64 44 54 53 49 73
49 43 4a 72 61 57 51 69 4f 69 41 69 59 32 56 73 64 57 6b 4b 44 63 4f 6e 59
51 6f 4e 43 57 7a 44 6f 43 31 69 59 58 4d 69 66 51)

NEW:
AAD = '{"enc": "A128GCM", "kid": "celui\r\nça\r\n\tlà-bas"}'
(== 7B 22 65 6E 63 22 3A 20 22 41 31 32 38 47 43 4D 22 2C 20 22 6B 69 64 22
3A 20 22 63 65 6C 75 69 0A 0D C3 A7 61 0A 0D 09 6C C3 A0 2D 62 61 73 22 7D)

On Tue, Jun 11, 2013 at 2:12 PM, Jim Schaad <[email-masked]> wrote:

> <not chair>****
> ** **
> Richard,****
> ** **
> solve the problem of things drifting back and forth.  Given the text****
>
> ** **
>
> {xxx}\r\r\rThis is the body****
>
> ** **
>
> body begins?  Until this is completely solved what you propose is not
> doable and the current method of base64 encoding will be required.****
>
> ** **
>
> Jim****
>
> ** **
>

---

From: "Jim Schaad" <[email-masked]>
Date: Tue, 11 Jun 2013 12:16:08 -0700

Yes, it is not a problem for JWE, however consider the case of JWS where
there is no distinction between how the protected data and the content are
processed.

Jim

From: Richard Barnes [mailto:[email-masked]] 
Sent: Tuesday, June 11, 2013 11:43 AM
To: Jim Schaad
Cc: [email-masked]
Subject: Re: Issue #23 - Make crypto indepenent of binary encoding

{

    "protect":

    ...

}

OLD:

NEW: 

 

 

<not chair>

Richard,

Jim

---

From: Richard Barnes <[email-masked]>
Date: Tue, 11 Jun 2013 15:50:45 -0400

Still not understanding the problem.  Things are still clearly separated in
JWS:

{
    "protected_header": "eyJhbGciOiJSUzI1NiIsImtpZCI6ImppbSJ9"
    "payload": "AQIDBA"
}

Here the protected_header is base64('{"alg":"RS256","kid":"jim"}') and the
payload is base64(0x01020304).

OLD:
Signature is
over: eyJhbGciOiJSUzI1NiIsImtpZCI6ImppbSJ9.eyJhbGciOiJSUzI1NiIsImtpZCI6ImppbSJ9
== 65 79 4a 68 62 47 63 69 4f 69 4a 53 55 7a 49 31 4e 69 49 73 49 6d 74 70
5a 43 49 36 49 6d 70 70 62 53 4a 39 2e 65 79 4a 68 62 47 63 69 4f 69 4a 53
55 7a 49 31 4e 69 49 73 49 6d 74 70 5a 43 49 36 49 6d 70 70 62 53 4a 39

NEW:
Signature is over: {"alg":"RS256","kid":"jim"}
== 01 02 03 04 7b 22 61 6c 67 22 3a 22 52 53 32 35 36 22 2c 22 6b 69 64 22
3a 22 6a 69 6d 22 7d 01 02 03 04

That is, just decode the two octet strings, convert the protected_header to
UTF-8, and concatenate them.  (This extends the proposal to also get rid of
the "." in the middle, since it's not necessary.  I updated the issue.)

No ambiguity.

--Richard

On Tue, Jun 11, 2013 at 3:16 PM, Jim Schaad <[email-masked]> wrote:

> processed.****
> *From:* Richard Barnes [mailto:[email-masked]]
> *Sent:* Tuesday, June 11, 2013 11:43 AM
> *To:* Jim Schaad
> *Cc:* [email-masked]
> *Subject:* Re: Issue #23 - Make crypto indepenent of binary encoding****
>
> ** **
>
> forth".  Let me try to be more concrete.****
>
> ** **
>
> Consider the following JWE:****
>
> ** **
>
> {****
>
>     "header": { "alg": "dir" }****
>
>     "protect":
> "eyJlbmMiOiAiQTEyOEdDTSIsICJraWQiOiAiY2VsdWkKDcOnYQoNCWzDoC1iYXMifQ"****
>
>     ...****
>
> }****
>
> ** **
>
> The "protect" here is the encoding of the header '{"enc": "A128GCM",
> "kid": "celui\r\nça\r\n\tlà-bas"}'  (hex=63 65 6C 75 69 0A 0D C3 A7 61 0A
> 0D 09 6C C3 A0 2D 62 61 73).****
>
> ** **
>
> base64-encoding instead of after:****
>
> ** **
>
> OLD:****
>
> AAD = eyJlbmMiOiAiQTEyOEdDTSIsICJraWQiOiAiY2VsdWkKDcOnYQoNCWzDoC1iYXMifQ *
> ***
>
> (== 65 79 4a 6c 62 6d 4d 69 4f 69 41 69 51 54 45 79 4f 45 64 44 54 53 49
> 73 49 43 4a 72 61 57 51 69 4f 69 41 69 59 32 56 73 64 57 6b 4b 44 63 4f 6e
> 59 51 6f 4e 43 57 7a 44 6f 43 31 69 59 58 4d 69 66 51)****
>
> ** **
>
> NEW: ****
>
> AAD = '{"enc": "A128GCM", "kid": "celui\r\nça\r\n\tlà-bas"}'****
>
> (== 7B 22 65 6E 63 22 3A 20 22 41 31 32 38 47 43 4D 22 2C 20 22 6B 69 64
> 22 3A 20 22 63 65 6C 75 69 0A 0D C3 A7 61 0A 0D 09 6C C3 A0 2D 62 61 73 22
> 7D)****
>
> ** **
>
> ** **
>
> ** **
>
> ** **
>
> ** **
>
> ** **
>
> ** **
>
> On Tue, Jun 11, 2013 at 2:12 PM, Jim Schaad <[email-masked]>
> wrote:****
>
> <not chair>****
>
>  ****
>
> Richard,****
>
>  ****
>
>  ****
>  ****
>  ****
>  ****

---

From: "Jim Schaad" <[email-masked]>
Date: Tue, 11 Jun 2013 14:02:33 -0700

Yes – you are still not understanding the problem.

There is an interesting issue that comes up in computing hash values of
multiple things which are concatenated together.  This issue is that it is
possible to move items from one thing to an adjacent thing and still get the
same hash value.

Thus if field1=”aaa” and field2=”bbb” you get “aaabbb” as the value being
hashed.

If field1=”aa” and field2=”abbb” you still get the same “aaabbb” as the
value being hashed but different ideas of what the two fields are.

There are three classic ways to deal with this problem:

1.       Use  length prefix on each field – this is the ASN.1 encode it
version

2.       Use fields that are well defined in terms of delimiters

3.       Put in separation characters which are not allowed in either field.

I once tried to argue that this is what we should do and ended up with the
following:  Method one was not considered acceptable, method two was not
possible given the current state of JSON parsers, method three is what we
currently do.

JSON parsers allow for indefinite amounts of whitespace following a JSON
object so that will always be a problem.  Additionally there are JSON
parsers which believe they can stop parsing and not produce an error once it
has fully built a top level object.  Thus they consider the string
‘{“a”:“b”}FRED” to be something that can be successfully parsed.

This allows for an attacker to move items from the content to the protected
string unless there is an externally imposed rule about what happens for
trailing characters after the protected content.

Jim

From: Richard Barnes [mailto:[email-masked]] 
Sent: Tuesday, June 11, 2013 12:51 PM
To: Jim Schaad
Cc: [email-masked]
Subject: Re: Issue #23 - Make crypto indepenent of binary encoding

{

    "payload": "AQIDBA"

}

OLD: 

Signature is over:
eyJhbGciOiJSUzI1NiIsImtpZCI6ImppbSJ9.eyJhbGciOiJSUzI1NiIsImtpZCI6ImppbSJ9

NEW:

No ambiguity.

--Richard

 

Jim

{

    "protect":

    ...

}

OLD:

NEW: 

 

 

<not chair>

Richard,

Jim

---

From: Richard Barnes <[email-masked]>
Date: Tue, 11 Jun 2013 17:43:59 -0400

Ah. I see.  Guess that's what the '.' character is for in the base64
version.  :)

In this version, you could just require that the JWS protected header have
no trailing white space.  Then, if you the attacker trims any characters,
it won't be valid.

Senders MUST NOT create a header with trailing white space. Recipient
MUST (1) check that the header is valid JSON, and (2) check that there is
no trailing white space in the header string.

I think this is a flavor of your (2).

On Tuesday, June 11, 2013, Jim Schaad wrote:

> Yes – you are still not understanding the problem.****
>
> ** **
>
> possible to move items from one thing to an adjacent thing and still get
> the same hash value.****
>
> ** **
>
> hashed.****
> value being hashed but different ideas of what the two fields are.****
>
> ** **
>
> There are three classic ways to deal with this problem:****
>
> ** **
>
> **1.       **Use  length prefix on each field – this is the ASN.1 encode
> it version****
>
> **2.       **Use fields that are well defined in terms of delimiters****
>
> **3.       **Put in separation characters which are not allowed in either
> field.****
>
> ** **
>
> currently do.****
> parsers which believe they can stop parsing and not produce an error once
> it has fully built a top level object.  Thus they consider the string
> ‘{“a”:“b”}FRED” to be something that can be successfully parsed.****
>
> ** **
>
> This allows for an attacker to move items from the content to the
> protected string unless there is an externally imposed rule about what
> happens for trailing characters after the protected content.****
>
> ** **
>
> Jim****
>
> ** **
>
> ** **
>
> *From:* Richard Barnes [mailto:[email-masked] <javascript:_e({}, 'cvml',
> [email-masked]');>]
> *Sent:* Tuesday, June 11, 2013 12:51 PM
> *To:* Jim Schaad
> *Cc:* [email-masked] <javascript:_e({}, 'cvml', [email-masked]');>
> Still not understanding the problem.  Things are still clearly separated
> in JWS:****
>
> ** **
>
> {****
>
>     "protected_header": "eyJhbGciOiJSUzI1NiIsImtpZCI6ImppbSJ9"****
>
>     "payload": "AQIDBA"****
>
> }****
>
> ** **
>
> payload is base64(0x01020304).****
>
> ** **
>
> OLD: ****
>
> Signature is
> 55 7a 49 31 4e 69 49 73 49 6d 74 70 5a 43 49 36 49 6d 70 70 62 53 4a 39***
> *
>
> ** **
>
> NEW:****
>
> Signature is over: {"alg":"RS256","kid":"jim"}****
>
> 3a 22 6a 69 6d 22 7d 01 02 03 04****
>
> ** **
>
> That is, just decode the two octet strings, convert the protected_header
> to UTF-8, and concatenate them.  (This extends the proposal to also get rid
> of the "." in the middle, since it's not necessary.  I updated the issue.)
> ****
>
> ** **
>
> No ambiguity.****
>
> ** **
>
> --Richard****
>
> ** **
>
> ** **
>
> ** **
>
> ** **
>
> ** **
>
> On Tue, Jun 11, 2013 at 3:16 PM, Jim Schaad <[email-masked]>
> wrote:****
>

---

From: Richard Barnes <[email-masked]>
Date: Tue, 11 Jun 2013 17:53:43 -0400

---

From: Richard Barnes <[email-masked]>
Date: Tue, 11 Jun 2013 18:40:52 -0400

Note: This is exactly how CMS mitigates this attack.  The SignedAttrs DER
structure is appended after the content, so DER parsing will fail if any
octets are added or removed.

---

From: "Jim Schaad" <[email-masked]>
Date: Tue, 11 Jun 2013 16:02:05 -0700

No - that is not true.

CMS mitigates this attack by doing an indirect signing on the content.  Thus
the hash of the content is part of the signed attributes.

Jim

From: Richard Barnes [mailto:[email-masked]] 
Sent: Tuesday, June 11, 2013 3:41 PM
To: Jim Schaad
Cc: [email-masked]
Subject: Re: Issue #23 - Make crypto indepenent of binary encoding

In this version, you could just require that the JWS protected header have
no trailing white space.  Then, if you the attacker trims any characters, it
won't be valid.  

Senders MUST NOT create a header with trailing white space. Recipient MUST
(1) check that the header is valid JSON, and (2) check that there is no
trailing white space in the header string. 

Yes - you are still not understanding the problem.

Thus if field1="aaa" and field2="bbb" you get "aaabbb" as the value being
hashed.

If field1="aa" and field2="abbb" you still get the same "aaabbb" as the
value being hashed but different ideas of what the two fields are.

1.       Use  length prefix on each field - this is the ASN.1 encode it
version

'{"a":"b"}FRED" to be something that can be successfully parsed.

---

From: Richard Barnes <[email-masked]>
Date: Tue, 11 Jun 2013 19:12:53 -0400

True.  You could also do that here.

But I think my scheme still works, and is a little simpler.

On Tuesday, June 11, 2013, Jim Schaad wrote:

> No – that is not true.****
>
> ** **
>
> CMS mitigates this attack by doing an indirect signing on the content.
> Thus the hash of the content is part of the signed attributes.****
>
> ** **
>
> Jim****
>
> ** **
>
> ** **
>
> *Sent:* Tuesday, June 11, 2013 3:41 PM
> *To:* Jim Schaad
> On Tuesday, June 11, 2013, Richard Barnes wrote:****
>
> version.  :)****
> it won't be valid.  ****
> no trailing white space in the header string. ****
>
> ** **
>
> I think this is a flavor of your (2). ****
>
> ** **
>
>
>
> On Tuesday, June 11, 2013, Jim Schaad wrote:****
>
> version****
> 2.       Use fields that are well defined in terms of delimiters****
>
> 3.       Put in separation characters which are not allowed in either
> field.****
>
>  ****
>

---

From: "Manger, James H" <[email-masked]>
Date: Wed, 12 Jun 2013 11:30:10 +1000

TL;DR: Removing the scaling limitation to make JOSE broadly applicable (by incurring any 33% overhead of base64url-encoding outside the crypto calculation) is a compelling reason to accept a cost of a few dozen additional lines of code in binary-unfriendly languages.

>> #23: Make crypto independent of binary encoding (base64)
>>
>> The cryptographic operations that JOSE performs should not depend on the  transfer encoding used for binary components.  The operations should work  directly on the encoded byte strings, not on the encoded form.

Thanks for adding this issue Richard.

The reason this can work for the JWE JSON serialization is that the separate segments (protected header, IV, plaintext) are passed as separate arguments to the AEAD algorithm (AAD, IV, plaintext). Each AEAD algorithm ensures there can be no confusion between the arguments.

AES_CBC_HMAC_SHA2, for instance, includes the length of the AAD in its HMAC calculation: HMAC(AAD || CIPHERTEXT || LENGTH(AAD)).

AES256GCM, for instance, calculates its authentication tag as GHASH(AAD || padding || CIPHERTEXT || padding || LENGTH(AAD) || LENGTH(CIPHERTEXT))

Signing & MAC algorithms accept a single argument for the content to be signed, whereas JWS wants to sign two fields: header & payload. So JOSE needs to specify how the header and payload are combined.

A good solution for JOSE would be to follow the example of these AEAD algorithms. For instance, specify that the bytes to be signed are HEADER || PAYLOAD || LENGTH(HEADER), where HEADER is the UTF-8 encoded header JSON object. 

> 1.       Use  length prefix on each field – this is the ASN.1 encode it version
> I once tried to argue that this is what we should do and ended up with the following:  Method one was not considered acceptable, method two was not possible given the current state of JSON parsers, method three is what we currently do.

We should reconsider a variant of option 1 (include the length of the header at the end).

Applying crypto (eg HASH or ENC/DEC) to a base64url encoding means there will always be a 33% overhead. Applying it to a concatenation of bytes plus a length field means there is a fixed overhead (eg 8 bytes). Both can be ignored for small messages. A 33% overhead will be a showstopper for large messages.

Small messages is a primary use case for JOSE today. Without being able to scale efficiently though, we are crippling its wider applicability. There would be ongoing pressure to use something other than JOSE whenever a protocol might handle messages that are medium-sized or larger.

The downside of not signing the base64url-encoding is that JOSE libraries need to handle bytes, instead of strings, in a few more places. That will add some work in some binary-unfriendly languages. My guess is that the extra work is of the order of dozens on lines of code. Removing the scaling limitation to make JOSE broadly applicable is a compelling reason to accept that extra work.

--
James Manger