Subject: Re: [jose] Signing and Encryption algorithm

From: "Manger, James H" <[email-masked]>
Date: Mon, 7 May 2012 22:56:58 +1000

MAC( TEXT( header ) || body || LENGTH( body ) )

Including the length of the body as the last input to the MAC calculation (or starting with the length of the header) would prevent any header/body boundary changes, without adding any constraints on how the header ends (eg with or without a trailing new line).

--
James Manger

----- Reply message -----
From: "Manger, James H" <[email-masked]>
Date: Mon, May 7, 2012 6:38 pm
Subject: [jose] Signing and Encryption algorithm
To: "Jim Schaad" <[email-masked]>, "[email-masked]" <[email-masked]>

> The current code computes the signature hash as
>
> HASH( BASE64( TEXT( header )) || "." || BASE64 ( body ))
>
> From what I know and can guess, there are three reasons for doing it this
> way.
>
> 1.  We need to make sure that nothing can move the body to the headers and
> vice versa
> 2.  There is a strong desire to avoid canonicalization of the inputs and
> base64 is the method chosen to do this
> 3.  We already have the base64 values - so it makes sense to use them.
>
> I would propose to change the hash computation to be
>
> HASH( TEXT( header ) || body )
>
> 1.  There are no issues with the migration of data across the concatenation
> operator.  Since the header is required to be a well-defined JSON object, it
> is always possible to find the exact end of the JSON object in order to
> separate the header and the body fields.  The only requirement would be that
> the creation code would need to state that there are no trailing characters
> following the closing curly brace.

I agree that it would be better to do the base64url-encoding outside of the MAC calculation.

Only issue 1 seems relevant. Requiring nothing after the closing "}" of the header might be the answer. That should be easy enough for signers to meet. However, it might be harder for verifiers to check (or they might "forget" to check).

I am sure many/most JSON decoders will (sensibly) ignore whitespace after the closing "}" -- it is allowed by the JSON spec. I wouldn't be surprised if some allowed C-style comments. Others might even allow arbitrary junk.

Base64url-encoding the header, but not the body, might satisfy more parties.

HASH( BASE64( TEXT( header )) || "." || body )

P.S. HMAC is not the only form of MAC. I hope the spec drops the unnecessary restriction to "Hash-based MACs".

--
James Manger
_______________________________________________
jose mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/jose

---

From: John Bradley <[email-masked]>
Date: Mon, 7 May 2012 11:16:19 -0400

Yes all true if you are in a C/C++ type environment.   

Manipulating these signed objects easily in Scripting environments is a concern for adoption.

Google and Facebook both backed the hash over the base64 encoded parts as the simplest for developers in those environments.

I am not keen to change that without significant feedback.

John B.

---

From: "Jim Schaad" <[email-masked]>
Date: Mon, 7 May 2012 12:58:57 -0700

I don't think doing this would get around the need to do the check that
there are no trailing characters following the JSON object encoding.  This
would still allow for an attacker to be able to place data into the message
in two places which would never be seen by the consumer of the message (the
end of the header and the end of the body if JSON encoded).  

Specifically this would allow for a prefix attack where one would try and
make the following the same

HASH'( TEXT(ATTACKER HEADER) || ATTACKER DATA) = HASH'( TEXT(HEADER))

Where Hash' does not do the closing steps (such as adding the length).  One
would just output the internal state of the hash function at the end of
processing a block of data.  (One can actually use any prefix of the
original header as the remainder of the original header can just be tacked
onto the end of the attacker data field.)

jim

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> Manger, James H
> Sent: Monday, May 07, 2012 5:57 AM
> To: [email-masked]; [email-masked]
> Subject: Re: [jose] Signing and Encryption algorithm
> 
> Including the length of the body as the last input to the MAC calculation
(or
> starting with the length of the header) would prevent any header/body
> boundary changes, without adding any constraints on how the header ends
> (eg with or without a trailing new line).
> 
> --
> James Manger
> 
> > From what I know and can guess, there are three reasons for doing it
> > this way.
> >
> > 1.  We need to make sure that nothing can move the body to the headers
> > and vice versa 2.  There is a strong desire to avoid canonicalization
> > of the inputs and
> > base64 is the method chosen to do this 3.  We already have the base64
> > values - so it makes sense to use them.
> >
> > 1.  There are no issues with the migration of data across the
> > concatenation operator.  Since the header is required to be a
> > well-defined JSON object, it is always possible to find the exact end
> > of the JSON object in order to separate the header and the body
> > fields.  The only requirement would be that the creation code would
> > need to state that there are no trailing characters following the
closing curly
> brace.
> 
> 
> I agree that it would be better to do the base64url-encoding outside of
the
> MAC calculation.
> 
> Only issue 1 seems relevant. Requiring nothing after the closing "}" of
the
> header might be the answer. That should be easy enough for signers to
> meet. However, it might be harder for verifiers to check (or they might
> "forget" to check).
> 
> I am sure many/most JSON decoders will (sensibly) ignore whitespace after
> the closing "}" -- it is allowed by the JSON spec. I wouldn't be surprised
if
> some allowed C-style comments. Others might even allow arbitrary junk.
> 
> P.S. HMAC is not the only form of MAC. I hope the spec drops the
> unnecessary restriction to "Hash-based MACs".
> 
> --
> James Manger

---

From: "Jim Schaad" <[email-masked]>
Date: Mon, 7 May 2012 13:01:09 -0700

John,

I don't follow this.  I have done work in both a C/C++ environment and in a
scripting environment (mostly jscript) and I don't see why the difference in
environment should make any difference to this.  Can you elaborate why you
feel there is a difference?

Jim

> John Bradley
> Sent: Monday, May 07, 2012 8:16 AM
> To: Manger, James H
> Cc: [email-masked]; [email-masked]
> Google and Facebook both backed the hash over the base64 encoded parts
> as the simplest for developers in those environments.
> 
> > Including the length of the body as the last input to the MAC
calculation (or
> >> 1.  We need to make sure that nothing can move the body to the
> >> headers and vice versa 2.  There is a strong desire to avoid
> >> canonicalization of the inputs and
closing
> curly brace.
the
the
if

---

From: Nat Sakimura <[email-masked]>
Date: Tue, 8 May 2012 01:39:47 +0200

I suppose what John is asking is:

Suppose body was binary.

Is it safe to do  TEXT( header ) || body ?

Or should we do pack("C*", str_split(header)) || body ?

What happens if the header includes UTF-8 characters?

etc.

Nat

-- 
Nat Sakimura (=nat)
Chairman, OpenID Foundation
http://nat.sakimura.org/
@_nat_en

---

From: "Jim Schaad" <[email-masked]>
Date: Mon, 7 May 2012 17:21:07 -0700

> From: Nat Sakimura [mailto:[email-masked]]
> Sent: Monday, May 07, 2012 4:40 PM
> To: Jim Schaad
> Cc: John Bradley; [email-masked]; [email-masked]

Hash functions only operate on arrays of bytes - so the real question is
what happens if the body is a string.  You need to convert it into an array
of bytes before you can hash or mac it.

> Is it safe to do  TEXT( header ) || body ?

Completely if you assume that there is no trailing data on TEXT(header)

> Or should we do pack("C*", str_split(header)) || body ?

I don't understand the question.  You are always going need to convert from
characters to bytes in order to hash.

> What happens if the header includes UTF-8 characters?

The header needs to be converted into a string and then into an array of
bytes.  You then base64 encode the array of bytes.  If you base64 encode the
string then yes there is a potential problem about how the utf8 string is
converted into a byte array for base64 encoding.  If you just pass in the
byte array then no issues.  If you decode the base64 encoded strings (in the
library) to a byte array then no problem

But again this is a question of how the library or other code is written.
Somebody needs to do this conversion, if you suggest that user code does it
then it will almost surely be done consistently but yes that is a potential
problem.  On the other hand you have the same issue if people encode it into
base64 twice (once for the signature and once for sending it).

Jim

> > I don't follow this.  I have done work in both a C/C++ environment and
> > in a scripting environment (mostly jscript) and I don't see why the
> > difference in environment should make any difference to this.  Can you
> > elaborate why you feel there is a difference?
> >
> > Jim
> >
> >
> >> From: [email-masked] [mailto:[email-masked]] On Behalf
> >> Of John Bradley
> >> Google and Facebook both backed the hash over the base64 encoded
> >> parts as the simplest for developers in those environments.
> >>
> >> boundary changes, without adding any constraints on how the header
> >> ends (eg with or without a trailing new line).
> >> >
> >> > --
> >> > James Manger
> >> >
> >> >> From what I know and can guess, there are three reasons for doing
> >> >> it this way.
> >> >>
> >> >> base64 is the method chosen to do this 3.  We already have the
> >> >> base64 values - so it makes sense to use them.
> >> >>
> >> >> well-defined JSON object, it is always possible to find the exact
> >> >> end of the JSON object in order to separate the header and the
> >> >> body fields.  The only requirement would be that the creation code
> >> >> would need to state that there are no trailing characters
> >> >> following the
> > closing
> >> curly brace.
> >> >
> >> >
> >> meet. However, it might be harder for verifiers to check (or they
> >> might "forget" to check).
> >> >

---

From: "Jim Schaad" <[email-masked]>
Date: Mon, 7 May 2012 17:25:45 -0700

After sending this message I realized that I messed up.  The UTF8 conversion
from Unicode to bytes is a deterministic one.  Thus applying to a string to
produce bytes is always going to be the same.  The only problem would be if
you re-normalized the string between the applications of the utf8 conversion
function.

Jim

> Jim Schaad
> Sent: Monday, May 07, 2012 5:21 PM
> To: 'Nat Sakimura'
> Cc: 'John Bradley'; [email-masked]
what
> happens if the body is a string.  You need to convert it into an array of
bytes
> before you can hash or mac it.
> 
> >
byte
> array then no issues.  If you decode the base64 encoded strings (in the
> > > I don't follow this.  I have done work in both a C/C++ environment
> > > and in a scripting environment (mostly jscript) and I don't see why
> > > the difference in environment should make any difference to this.
> > > Can you elaborate why you feel there is a difference?
> > >
> > > Jim
> > >
> > >
> > >> From: [email-masked] [mailto:[email-masked]] On
> > >> Behalf Of John Bradley
> > >> starting with the length of the header) would prevent any
> > >> header/body boundary changes, without adding any constraints on how
> > >> the header ends (eg with or without a trailing new line).
> > >> >
> > >> > --
> > >> > James Manger
> > >> >
> > >> >> From what I know and can guess, there are three reasons for
> > >> >> doing it this way.
> > >> >>
> > >> >> well-defined JSON object, it is always possible to find the
> > >> >> exact end of the JSON object in order to separate the header and
> > >> >> the body fields.  The only requirement would be that the
> > >> >> creation code would need to state that there are no trailing
> > >> >> characters following the
> > > closing
> > >> curly brace.
> > >> >
> > >> >
> > >> header might be the answer. That should be easy enough for signers
> > >> to meet. However, it might be harder for verifiers to check (or
> > >> they might "forget" to check).
> > >> >
> > >> > I am sure many/most JSON decoders will (sensibly) ignore
> > >> > whitespace
> > > after
> > >> > Base64url-encoding the header, but not the body, might satisfy
> > >> > more
> > >> parties.
> > >> >

---

From: "Manger, James H" <[email-masked]>
Date: Tue, 8 May 2012 13:04:20 +1000

Jim,

I think there are 2 distinct concerns here:

1. The header/body boundary must not be "movable" after signing. It must not be possible for {h1, b1} and {h2, b2} to produce the same sequence of bytes that are fed to the MAC algorithm.

2. If there is room for arbitrary "junk" in the signed data then an attacker can use that to try to find collisions.

We must prevent #1.
I think we will have to accept #2. We have to assume our choice of MAC algorithm is strong enough make finding collisions infeasible.

Preventing #2 would require JSON canonicalization rules at a minimum, which we want to avoid. Regardless of whether JSON parsers ignore junk after the closing "}", there is still ample freedom to insert whitespace in the JSON value that will be ignored. For instance, insert 128 spaces or tabs before the closing "}" to give 2^128 variants of the "same" header in a search for a collision.

The current structure MAC(BASE64(header) || "." || BASE64(body)) prevents #1 because "." cannot appear in a BASE64-encoding. Might attacks still be possible if some base64-decoders silently ignore non-base64 chars during decoding, and the order of HTML-unescaping and splitting on "." is not quite right?

MAC(header_with_nothing_after_closing_} || body) prevents #1 only if JSON decoders (or the apps calling them) enforce the "nothing after the closing }" condition, which is not realistic. Enforcing "nothing other than whitespace after the closing }" is more realistic, but maybe not certain enough.

MAC(header || body || length(body)) prevents #1 regardless of any leniency of base64-decoders and JSON-decoders.

Jim, your "prefix attack" looks like issue #2. Is junk after "}" that is ignored any worse than whitespace before "}" that is ignored?

--
James Manger

---

From: Seetharama Rao Durbha <[email-masked]>
Date: Tue, 8 May 2012 09:05:12 -0600

Apologize for jumping in. Isn't it true that if header cannot be reliably serialized (ignoring whitespace after closing }) then it doesn't matter if we do 

a. MAC(BASE64(serializedHeader) || "." || BASE64(body))
OR
b. MAC(serializedHeader || body)

Base64(serializedHeader) is still going to be messed up if there are trailing whitespace after closing }.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Manger, James H
Sent: Monday, May 07, 2012 9:04 PM
To: Jim Schaad; [email-masked]
Subject: Re: [jose] Signing and Encryption algorithm

Jim,

We must prevent #1.

---

From: Mike Jones <[email-masked]>
Date: Tue, 8 May 2012 16:01:40 +0000

It doesn't matter to the meaning of the header whether there is trailing whitespace or not.  The period character between the base64url encoded header and the base64url encoded payload provides a simple way of ensuring that the two cannot be confused with one another.  Base64url encoding the header accurately preserves it, whether there are trailing (or leading or embedded) whitespace characters (including tabs, LFs, CRs, spaces), or not.

				-- Mike

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Seetharama Rao Durbha
Sent: Tuesday, May 08, 2012 8:05 AM
To: 'Manger, James H'; Jim Schaad; [email-masked]
Subject: Re: [jose] Signing and Encryption algorithm

a. MAC(BASE64(serializedHeader) || "." || BASE64(body)) OR b. MAC(serializedHeader || body)

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Manger, James H
Sent: Monday, May 07, 2012 9:04 PM
To: Jim Schaad; [email-masked]
Subject: Re: [jose] Signing and Encryption algorithm

Jim,

We must prevent #1.

---

From: Seetharama Rao Durbha <[email-masked]>
Date: Tue, 8 May 2012 10:13:57 -0600

If there was deserialization involved, I might agree with the confusion aspect. But since we are talking about inputs to MAC, we just need reliable serialization of header and body. Adding a period in between does not eliminate inconsistencies in serialization of header or body. What I am saying is that whoever is verifying the MAC should know whether to include or exclude any trailing whitespace, regardless.

Seetharama

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Mike Jones
Sent: Tuesday, May 08, 2012 10:02 AM
To: Seetharama Rao Durbha; 'Manger, James H'; Jim Schaad; [email-masked]
Subject: Re: [jose] Signing and Encryption algorithm

				-- Mike

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Manger, James H
Sent: Monday, May 07, 2012 9:04 PM
To: Jim Schaad; [email-masked]
Subject: Re: [jose] Signing and Encryption algorithm

Jim,

We must prevent #1.

---

From: "Jim Schaad" <[email-masked]>
Date: Tue, 8 May 2012 14:52:52 -0700

> From: Manger, James H [mailto:[email-masked]]
> Sent: Monday, May 07, 2012 8:04 PM
> Subject: RE: [jose] Signing and Encryption algorithm
> 
> Jim,
> 
> 1. The header/body boundary must not be "movable" after signing. It must
> not be possible for {h1, b1} and {h2, b2} to produce the same sequence of
> bytes that are fed to the MAC algorithm.
> 
> 2. If there is room for arbitrary "junk" in the signed data then an
attacker can
> use that to try to find collisions.
> 
> We must prevent #1.
> I think we will have to accept #2. We have to assume our choice of MAC
> algorithm is strong enough make finding collisions infeasible.
> 
> Preventing #2 would require JSON canonicalization rules at a minimum,
which
> we want to avoid. Regardless of whether JSON parsers ignore junk after the
> closing "}", there is still ample freedom to insert whitespace in the JSON
> value that will be ignored. For instance, insert 128 spaces or tabs before
the
> closing "}" to give 2^128 variants of the "same" header in a search for a
> collision.

The restriction of the character set to those items which are just
whitespace does provide some improved security characteristics over allowing
for a complete character set to occur.  The fact that some bits in the
string need to be 0s (bits 6 and 7) and others are tightly related restricts
the full search space in the hash algorithm attack.  One of the improvements
that was considered to keep SHA1 alive longer was to double hash each
characters (thus "abc" becomes "aabbcc") which forces structure on the input
stream and therefore increases the difficulty of finding collisions.

This does imply that allowing whitespace in the string in arbitrary
locations does allow for an attack space, but not a full attack space.

> 
> 
> The current structure MAC(BASE64(header) || "." || BASE64(body))
> prevents #1 because "." cannot appear in a BASE64-encoding. Might attacks
> still be possible if some base64-decoders silently ignore non-base64 chars
> during decoding, and the order of HTML-unescaping and splitting on "." is
not
> quite right?

There are a couple of things.  First the base64 decoder would need to check
that all of the input bytes are consumed - you could have a legal base64
string followed by some arbitrary bytes (not containing a ".") and then the
"." character.  If the base64 stopped when it got to the point it had enough
characters and did not check to see if there were more then you would have
an issue.  (As an example it could stop when finding either a "=" or a "==")
This is less of an issue because of the call for the url safe version of
base64 to be used.  

Again the fact that only base64 characters can appear does make it more
difficult to attack this section if the base64 decoder does its job and
makes sure that there are no non-base64 characters present.  This is an
issue for whitespace since most base64 decoders allow for arbitrary amounts
of whitespace to occur in the string.

> 
> MAC(header_with_nothing_after_closing_} || body) prevents #1 only if
> JSON decoders (or the apps calling them) enforce the "nothing after the
> closing }" condition, which is not realistic. Enforcing "nothing other
than
> whitespace after the closing }" is more realistic, but maybe not certain
> enough.
> 
> MAC(header || body || length(body)) prevents #1 regardless of any
> leniency of base64-decoders and JSON-decoders.

But we still need to deal with MAC (header || Attack || body ||
length(body)) 

It would be possible to deal with it by including a header length as well
and checking both lengths against the total message length.  This would
allow for total lengths to be checked and ignore the JSON/Base64 parser
problems.  However putting lengths in imposes additional programmer issues
that need to be dealt with.

Jim

> 
> 
> Jim, your "prefix attack" looks like issue #2. Is junk after "}" that is
ignored
> any worse than whitespace before "}" that is ignored?
> 
> --
> James Manger