Subject: Re: [Unbearable] What Gets Signed (was: Dumb idea: add Ed25519 support?)

From: Brian Campbell <[email-masked]>
Date: Thu, 1 Sep 2016 10:18:36 -0600

Okay, here's my proposal with sections 3.2 & 3.3 modified somewhat to
reflect what I believe we've now agreed to in principle. I'm happy to put
in a PR with this but thought it'd be better to first put the full text in
front of folks on the list.

3.2. TokenBinding.tokenbindingid

The ID of the Token Binding established as a result of Token Binding
message processing contains the identifier of the key parameters negotiated
via [I-D.ietf-tokbind-negotiation], the length (in bytes) of the Token
Binding public key, and the Token Binding public key itself. Token Binding
ID can be obtained from the TokenBinding structure by discarding the Token
Binding type, signature and extensions.
When rsa2048_pkcs1.5 or rsa2048_pss is used, RSAPublicKey.modulus and
RSAPublicKey.publicexponent contain the modulus and exponent of the 2048
bit RSA public key represented in big-endian format, with leading zero
bytes omitted.
When ecdsap256 is used, ECPoint.point contains the X coordinate followed by
the Y coordinate of the Curve P-256 key. The X and Y coordinates are
unsigned 32-byte integers encoded in big-endian format, preserving any
leading zero bytes. Future specifications may define Token Binding keys
using other elliptic curves with their corresponding signature and point
formats.
Token Binding protocol implementations SHOULD make Token Binding IDs
available to the application as opaque byte sequences. E.g. server
applications will use Token Binding IDs when generating and verifying bound
tokens.

3.3. TokenBinding.signature

When rsa2048_pkcs1.5 is used, the TokenBinding.signature contains the
signature generated using the RSASSA-PKCS1-v1_5 signature scheme defined in
[RFC3447] with SHA256 as the hash function.
When rsa2048_pss is used, the TokenBinding.signature contains the signature
generated RSASSA-PSS signature scheme defined in [RFC3447] with SHA256 as
the hash function. MGF1 with SHA256 MUST be used as the mask generation
function, and the salt length MUST equal 32 bytes.
When ecdsap256 is used, the TokenBinding.signature contains a pair of
32-byte integers, R followed by S, generated with ECDSA using P-256 and
SHA256 as defined in [ANSI.X9-62.2005] and [FIPS.186-4.2013]. R and S are
encoded in big-endian format, preserving any leading zero bytes.

The signature is computed over the byte string representing the
concatenation of:
    •    TokenBindingType value contained in the
TokenBinding.tokenbinding_type field;
    •    TokenBindingKeyParameters value contained in the
TokenBindingID.key_parameters field;
    •    Exported keying material (EKM) value obtained from the current TLS
connection.

The EKM is obtained using the Keying Material Exporters for TLS defined in
[RFC5705], by supplying the following input values:
    •    Label: The ASCII string "EXPORTER-Token-Binding" with no
terminating NUL.
    •    Context value: NULL (no application context supplied).
    •    Length: 32 bytes.

On Wed, Aug 31, 2016 at 6:18 PM, Andrei Popov <[email-masked]>
wrote:

> Please propose the text, it will help a lot.
>
>
>
> *From:* Brian Campbell [mailto:[email-masked]]
> *Sent:* Wednesday, August 31, 2016 5:17 PM
> *To:* Andrei Popov <[email-masked]>
> *Cc:* Mike Jones <[email-masked]>; Bill Cox <
> [email-masked]>; Nick Harper <[email-masked]>; Leif Johansson
> <[email-masked]>; Tokbind WG <[email-masked]>
> *Subject:* RE: [Unbearable] What Gets Signed (was: Dumb idea: add Ed25519
> support?)
>
>
>
> I'll propose some specific text, if that's okay. Tomorrow though. I'm on
> family duty for the rest of the evening.
>
>
>
> On Aug 31, 2016 5:58 PM, "Andrei Popov" <[email-masked]>
> wrote:
>
> Sure, this sounds good to me.
>
>
>
> *From:* Nick Harper [mailto:[email-masked]]
> *Sent:* Wednesday, August 31, 2016 4:54 PM
> *To:* Andrei Popov <[email-masked]>
> *Cc:* Mike Jones <[email-masked]>; Brian Campbell <
> [email-masked]>; Tokbind WG <[email-masked]>; Leif
> Johansson <[email-masked]>; Bill Cox <[email-masked]>
> *Subject:* Re: [Unbearable] What Gets Signed (was: Dumb idea: add Ed25519
> support?)
>
>
>
>
>
>
>
> On Wed, Aug 31, 2016 at 4:37 PM, Andrei Popov <[email-masked]>
> wrote:
>
> Ø  I think we should go back to the signature algorithm including a hash
> algorithm (if relevant - an EdDSA algorithm doesn't need a hash function).
>
> Here’s my attempt at doing this: “When an rsa2048_pkcs1.5, rsa2048_pss or
> ecdsap256 key is used, the signature is computed over the SHA256 hash of
> the byte string representing the concatenation of…”.
>
>
>
> I think this wording should be split up, so something defines "the message
> to be signed is the concatenation of ...", and then the existing signature
> algorithms can specify to hash with sha256 that message (it could be one
> statement, like "When an rsa2048_pkcs1.5, rsa2048_pss, or ecdsap256 key is
> used, the signature is computed over the SHA256 hash of the message to be
> signed", or split into multiple statements, like how we describe rsa and
> p256 separately).
>
>

---

From: Brian Campbell <[email-masked]>
Date: Thu, 1 Sep 2016 10:21:32 -0600

On Wed, Aug 31, 2016 at 4:54 PM, Nick Harper <[email-masked]> wrote:

> My understanding is that P-256 can only sign a 32-byte message
>

Sigh. Yeah, that's right. My confusion has come full circle on this one.
That was my understanding too but then I found that the API I'm using would
accept up to 64 bytes. That followed by some poor math on my part led me
astray. Turns out that API will accept up to 64 bytes but with p-256 it
only signs the first 32 of them. Apologies for subjecting the list to my
confusion.

---

From: Andrei Popov <[email-masked]>
Date: Thu, 1 Sep 2016 17:34:56 +0000

I think this does not convey the important point that SHA256 must be used as part of the PSS and PKCS padding, and separately to hash the concatenated byte string before signing, e.g.:

Ø  When rsa2048_pkcs1.5 is used, the TokenBinding.signature contains the signature generated using the RSASSA-PKCS1-v1_5 signature scheme defined in [RFC3447] with SHA256 as the hash function.

Ø  The signature is computed over the byte string representing the concatenation of: …
This seems to suggest that we sign an unhashed byte string.

Ø  When ecdsap256 is used, the TokenBinding.signature contains a pair of 32-byte integers, R followed by S, generated with ECDSA using P-256 and SHA256 as defined in [ANSI.X9-62.2005] and [FIPS.186-4.2013].
AFAIK, the ECDSA signature operation itself does not involve hashing (but it is advisable/necessary to hash before signing). In fact, I could not find any references to SHA256 in ANSI.X9-62.2005.

Cheers,

Andrei

From: Brian Campbell [mailto:[email-masked]]
Sent: Thursday, September 1, 2016 9:19 AM
To: Andrei Popov <[email-masked]>
Cc: Mike Jones <[email-masked]>; Bill Cox <[email-masked]>; Nick Harper <[email-masked]>; Leif Johansson <[email-masked]>; Tokbind WG <[email-masked]>
Subject: Re: [Unbearable] What Gets Signed (was: Dumb idea: add Ed25519 support?)

Okay, here's my proposal with sections 3.2 & 3.3 modified somewhat to reflect what I believe we've now agreed to in principle. I'm happy to put in a PR with this but thought it'd be better to first put the full text in front of folks on the list.

The ID of the Token Binding established as a result of Token Binding message processing contains the identifier of the key parameters negotiated via [I-D.ietf-tokbind-negotiation], the length (in bytes) of the Token Binding public key, and the Token Binding public key itself. Token Binding ID can be obtained from the TokenBinding structure by discarding the Token Binding type, signature and extensions.
When rsa2048_pkcs1.5 or rsa2048_pss is used, RSAPublicKey.modulus and RSAPublicKey.publicexponent contain the modulus and exponent of the 2048 bit RSA public key represented in big-endian format, with leading zero bytes omitted.
When ecdsap256 is used, ECPoint.point contains the X coordinate followed by the Y coordinate of the Curve P-256 key. The X and Y coordinates are unsigned 32-byte integers encoded in big-endian format, preserving any leading zero bytes. Future specifications may define Token Binding keys using other elliptic curves with their corresponding signature and point formats.
Token Binding protocol implementations SHOULD make Token Binding IDs available to the application as opaque byte sequences. E.g. server applications will use Token Binding IDs when generating and verifying bound tokens.

When rsa2048_pkcs1.5 is used, the TokenBinding.signature contains the signature generated using the RSASSA-PKCS1-v1_5 signature scheme defined in [RFC3447] with SHA256 as the hash function.
When rsa2048_pss is used, the TokenBinding.signature contains the signature generated RSASSA-PSS signature scheme defined in [RFC3447] with SHA256 as the hash function. MGF1 with SHA256 MUST be used as the mask generation function, and the salt length MUST equal 32 bytes.
When ecdsap256 is used, the TokenBinding.signature contains a pair of 32-byte integers, R followed by S, generated with ECDSA using P-256 and SHA256 as defined in [ANSI.X9-62.2005] and [FIPS.186-4.2013]. R and S are encoded in big-endian format, preserving any leading zero bytes.

The signature is computed over the byte string representing the concatenation of:
    •    TokenBindingType value contained in the TokenBinding.tokenbinding_type field;
    •    TokenBindingKeyParameters value contained in the TokenBindingID.key_parameters field;
    •    Exported keying material (EKM) value obtained from the current TLS connection.

The EKM is obtained using the Keying Material Exporters for TLS defined in [RFC5705], by supplying the following input values:
    •    Label: The ASCII string "EXPORTER-Token-Binding" with no terminating NUL.
    •    Context value: NULL (no application context supplied).
    •    Length: 32 bytes.

On Wed, Aug 31, 2016 at 6:18 PM, Andrei Popov <[email-masked]<mailto:[email-masked]>> wrote:
Please propose the text, it will help a lot.

From: Brian Campbell [mailto:[email-masked]<mailto:[email-masked]>]
Sent: Wednesday, August 31, 2016 5:17 PM
To: Andrei Popov <[email-masked]<mailto:[email-masked]>>
Cc: Mike Jones <[email-masked]<mailto:[email-masked]>>; Bill Cox <[email-masked]<mailto:[email-masked]>>; Nick Harper <[email-masked]<mailto:[email-masked]>>; Leif Johansson <[email-masked]<mailto:[email-masked]>>; Tokbind WG <[email-masked]<mailto:[email-masked]>>
Subject: RE: [Unbearable] What Gets Signed (was: Dumb idea: add Ed25519 support?)

I'll propose some specific text, if that's okay. Tomorrow though. I'm on family duty for the rest of the evening.

On Aug 31, 2016 5:58 PM, "Andrei Popov" <[email-masked]<mailto:[email-masked]>> wrote:
Sure, this sounds good to me.

From: Nick Harper [mailto:[email-masked]<mailto:[email-masked]>]
Sent: Wednesday, August 31, 2016 4:54 PM
To: Andrei Popov <[email-masked]<mailto:[email-masked]>>
Cc: Mike Jones <[email-masked]<mailto:[email-masked]>>; Brian Campbell <[email-masked]<mailto:[email-masked]>>; Tokbind WG <[email-masked]<mailto:[email-masked]>>; Leif Johansson <[email-masked]<mailto:[email-masked]>>; Bill Cox <[email-masked]<mailto:[email-masked]>>
Subject: Re: [Unbearable] What Gets Signed (was: Dumb idea: add Ed25519 support?)

On Wed, Aug 31, 2016 at 4:37 PM, Andrei Popov <[email-masked]<mailto:[email-masked]>> wrote:

>  I think we should go back to the signature algorithm including a hash algorithm (if relevant - an EdDSA algorithm doesn't need a hash function).
Here’s my attempt at doing this: “When an rsa2048_pkcs1.5, rsa2048_pss or ecdsap256 key is used, the signature is computed over the SHA256 hash of the byte string representing the concatenation of…”.

I think this wording should be split up, so something defines "the message to be signed is the concatenation of ...", and then the existing signature algorithms can specify to hash with sha256 that message (it could be one statement, like "When an rsa2048_pkcs1.5, rsa2048_pss, or ecdsap256 key is used, the signature is computed over the SHA256 hash of the message to be signed", or split into multiple statements, like how we describe rsa and p256 separately).

---

From: Brian Campbell <[email-masked]>
Date: Thu, 1 Sep 2016 14:06:00 -0600

Yes, we sign an unhashed byte string.  Each of RSASSA-PKCS1-v1_5 using
SHA256, RSASSA-PSS using SHA256 and MGF1 with SHA256, and ECDSA using P-256
and SHA256 can all sign arbitrary length byte sequences. So there is no
need to separately hash the concatenated byte string before signing. The
concatenated byte string is used directly as the message to be signed (or
verified).

FIPS.186-4.2013 <http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf>,
in sec 6.4 'ECDSA Digital Signature Generation and Verification', describes
ECDSA digital signatures as being generated with a hash function.

On Thu, Sep 1, 2016 at 11:34 AM, Andrei Popov <[email-masked]>
wrote:

> I think this does not convey the important point that SHA256 must be used
> as part of the PSS and PKCS padding, and separately to hash the
> concatenated byte string before signing, e.g.:
>
>
>
> Ø  When rsa2048_pkcs1.5 is used, the TokenBinding.signature contains the
> Ø  When ecdsap256 is used, the TokenBinding.signature contains a pair of
> SHA256 as defined in [ANSI.X9-62.2005] and [FIPS.186-4.2013].
>
> AFAIK, the ECDSA signature operation itself does not involve hashing (but
> it is advisable/necessary to hash before signing). In fact, I could not
> find any references to SHA256 in ANSI.X9-62.2005.
>
>
>
> Cheers,
>
>
>
> Andrei
>
>
>
> *Sent:* Thursday, September 1, 2016 9:19 AM
> When ecdsap256 is used, ECPoint.point contains the X coordinate followed
> by the Y coordinate of the Curve P-256 key. The X and Y coordinates are
> When rsa2048_pss is used, the TokenBinding.signature contains the
> signature generated RSASSA-PSS signature scheme defined in [RFC3447] with
> SHA256 as the hash function. MGF1 with SHA256 MUST be used as the mask
> generation function, and the salt length MUST equal 32 bytes.

---

From: Andrei Popov <[email-masked]>
Date: Thu, 1 Sep 2016 21:30:49 +0000

Signing unhashed byte strings is a bad idea for several reasons:

a)       Hashing before signing eliminates any structure within the byte string being signed, preventing certain types of attacks. Particularly in our case, we have a structured input with fixed elements.

b)      Generally, we want to sign fewer bytes, because signature is expensive.

c)       Signature algorithms have limits on the amount of bytes they can sign.

d)      In addition, some crypto APIs require that the length of the input to the signature algorithm equal the length of the output of the matching hash function.

I have to ask: what problem are you trying to solve by signing an unhashed byte string?

Cheers,

Andrei

Sent: Thursday, September 1, 2016 1:06 PM

Yes, we sign an unhashed byte string.  Each of RSASSA-PKCS1-v1_5 using SHA256, RSASSA-PSS using SHA256 and MGF1 with SHA256, and ECDSA using P-256 and SHA256 can all sign arbitrary length byte sequences. So there is no need to separately hash the concatenated byte string before signing. The concatenated byte string is used directly as the message to be signed (or verified).
FIPS.186-4.2013<http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf>, in sec 6.4 'ECDSA Digital Signature Generation and Verification', describes ECDSA digital signatures as being generated with a hash function.

On Thu, Sep 1, 2016 at 11:34 AM, Andrei Popov <[email-masked]<mailto:[email-masked]>> wrote:

>  The signature is computed over the byte string representing the concatenation of: …

>  When ecdsap256 is used, the TokenBinding.signature contains a pair of 32-byte integers, R followed by S, generated with ECDSA using P-256 and SHA256 as defined in [ANSI.X9-62.2005] and [FIPS.186-4.2013].

Cheers,

Andrei

---

From: Benjamin Kaduk <[email-masked]>
Date: Thu, 1 Sep 2016 21:30:24 -0400 (EDT)

> only signs the first 32 of them. Apologies for subjecting the list to my

Care to share what API it is, so that the authors can be tracked down and
hit over the head^W^W^W^Wtaught that crypto software interfaces should be
precisely defined and fail loudly if algorithm requirements are not met?

-Ben

---

From: Brian Campbell <[email-masked]>
Date: Fri, 2 Sep 2016 06:21:21 -0600

I'm trying to avoid an unnecessary round of hashing. And avoid having a
direct usage of SHA256 in part of the TB protocol that isn't variable with
negotiation. The latter being something that's likely to be flagged during
IESG review, if we don't address it first.

On Thu, Sep 1, 2016 at 3:30 PM, Andrei Popov <[email-masked]>
wrote:

> a)       Hashing before signing eliminates any structure within the byte
> string being signed, preventing certain types of attacks. Particularly in
> our case, we have a structured input with fixed elements.
>
> d)      In addition, some crypto APIs require that the length of the
> input to the signature algorithm equal the length of the output of the
> matching hash function.
>
>
>
> *Sent:* Thursday, September 1, 2016 1:06 PM
> FIPS.186-4.2013
> <http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf>, in sec 6.4
> 'ECDSA Digital Signature Generation and Verification', describes ECDSA
> digital signatures as being generated with a hash function.
>
>
>
>
>
>
>
>
>
>
>

---

From: Brian Campbell <[email-masked]>
Date: Fri, 2 Sep 2016 06:38:54 -0600

It was the Java signature API
https://docs.oracle.com/javase/8/docs/api/java/security/Signature.html with
"NONEwithECDSA" as the algorithm name. I eventually had to find the
underlying source code to understand what it was doing
https://github.com/openjdk-mirror/jdk/blob/jdk8u/jdk8u/master/src/share/classes/sun/security/ec/ECDSASignature.java