Request signing extension should support cryptographic agility

[callumdmay]

The request signing extension currently only supports Ed25519 for signing requests. In the event that future research indicates this algorithm shouldn't be used, there should be a well-defined way for the UA to use different signing algorithms.

A proposed two part solution would be as follows.

The first part would be to introduce major and minor versioning to the protocol_version of the key commitment. The major version (a number) would indicate the set of algorithms the UA may use to sign requests, and the minor version (a letter) would indicate the algorithm used for the public key in the key commitment, which is a member of the set of algorithms in the major version.

Example:

Future version TrustTokenV2 supports {Ed25519, ES256} Then a key commitment with protocol_version TrustTokenV2A would indicate the key commitment key is of type Ed25519 and a key commitment with protocol_version TrustTokenV2B would indicate the key commitment key is of type ES256. Both Ed25519 or ES256 could then be used for request signing of tokens issued by either one of these key commitments.

The second part of the change is to modify the token redemption flow as follows:

During token redemption, the site would indicate that it wants the UA to sign the request by introducing a new property signRequestData:

fetch('<issuer>/.well-known/trust-token', {
  trustToken: {
    type: 'srr-token-redemption',
    issuer: <issuer>,
    refreshPolicy: {none, refresh},
    signRequestData: true | false
  }
}).then(...)

If the value is true, the UA generates a public-private keypair. The public-private keypair is double-keyed to issuer and requesting site to prevent using the public key for fingerprinting. The UA then includes the algorithm identifier and public key in the redemption request as part of the client data. The issuer is expected to return this as part of the client data in the SRR, and sign over it to attest to its validity:

{
  Redemption timestamp,
  ClientData: {
    “redemption-timestamp”: <Redemption timestamp, seconds past the Unix epoch>,
    “redeeming-origin”: <Top-level origin at the time of redemption>,
    “key-hash”: SHA256(client public key),
    “request-signing”: {
      “alg”: "ed25519" | 'ES256’
      “publicKey”: “Base 64 encoded public key” 
    }  
  },
  Metadata: {
    Trust Token Key ID
  }
  Signature of the above verifiable by well-known public key of the issuer,
  optional expiry timestamp
}

Then, as usual the site indicates it wishes for the UA to sign the request using the signRequestData property in the send-srr fetch request to the 3rd party SRR consumer, already described in the spec. We then validate that the SRR we just redeemed for the site includes the public key (the site correctly requested request signing in the srr-token-redemption in the previous step), and if so, we then provide the algorithm alg for the public key in the Sec-Signature header we send as part of the request:

Sec-Signature:
  alg=<alg>
  public-key=<pk>
  sig=<signature>
  sign-request-data=<include, headers-only>

[dvorak42]

I think this issue really splits into two different things:

1) The signing algorithm the issuer uses on redemption.

With the caveat that one change we're looking at (https://github.com/WICG/trust-token-api/pull/46) removes the SRR from the core protocol and treats it as an arbitrary blob of data, it seems reasonable for issuers/ecosystems to define their Redemption Record format such that however they distribute their signing keys, they can also indicate what sigalg they're using.

2) The signing algorithm used by the client/UA for the signing extension.

I think we need to be careful to not have too many 'options' for each Trust Token version, since every downstream consumer would have to support every option. I think as a first step doing a PR to add the alg field to the Sec-Signature and to include the sigalg in the redemption request seems reasonable. Its then a separate question/issue on how to come to consensus on what requirements need to be supported. if more than one.

[callumdmay]

@dvorak42 As an initial set we propose two algorithms: ED25519 and ES256. We can scope this to request signing for now and I will open a separate issue for key commitments supporting multiple algorithms. Do you think this is a reasonable set or should we include more? Also, do we want to do something similar with grease here to ensure consumers support all the algorithms?

[dvorak42]

Are you imagining Edge would always sign with ES256 or are there cases it would use ED25519?

I think keeping the set as small as possible to avoid consumers needing to support a ton of different suites. GREASEing here gets a little bit odd, since its not an interactive protocol, so the client doesn't have the opportunity to then switch back to its intended protocol.

[callumdmay]

Edge would always sign with ES256. What I meant with regards to GREASE was using a similar protocol where a small percentage of the time signing would be done with other algorithms from the set. This would benefit browser interoperability and ecosystem flexibility. Is this something Chrome would support?

We understand the awkwardness of this ask given we can't support ED25519, but this only applies in this specific case and we would "GREASE" supported algorithms that are added in the future.

[dvorak42]

To some extent, by virtue of some browsers only using E256 and others using Ed25519, and keeping the number of required sigalgs small, the ecosystem has to ensure compatibility with these sigalgs to be able to support all clients.

GREASE is usually used in situations where we want to make sure consumers can support other new parameters as the protocol gets extended (unknown fields for protocols that later pick up new sigalgs or extensions). If we declare that a particular TrustToken version only supports a fixed set of sigalgs, then I don't think GREASE is necessary here (though there is something to be said about doing some sort of GREASE like thing to make sure consumers don't get pinned to a particular TrustToken version and are unable to handle when the version changes).

[callumdmay]

While we wish that were true, historically we've found that not to be the case. Particularly in pre-Chromium Edge, we dealt with a number of interop bugs that could have been fixed had the site tested in Edge as well as Chrome. If there is a dominant implementation in the web ecosystem many clients tend to forego support for other implementations. Our concern is that due to the relational nature of an issuer to its downstream consumers they would know which signing algorithms their issuer/the issuers preferred browser would use, and would thus have no reason to support others. While the spec outlines that a particular consumer supporting a version should support all signing algorithms, there isn't a forcing function to ensure that is the case. We're happy to do the work to implement this change.

[dvorak42]

For this particular case the issuer doesn't have any relation to the signing algorithm used (since its purely determined by the client), so it comes down to which clients the redeeming sites are likely to see/support.

One option is just to define that the new set of algorithms is {ES256}, and then browsers just use that, and avoid the ecosystem having to implement other algorithms, until we have need to support additional algorithms for crypto agility (Chrome is fine using the versioning of Trust Token for switching algorithms when we need it, and if Edge isn't planning on supporting Ed25519, then this doesn't really provide crypto agility for your use case).

If we really do need to keep both around, then UAs doing specific fuzzing/GREASE behaviors is possible, though probably shouldn't be a requirement for Trust Token clients. For Chrome-specific changes, maybe we should open a bug on bugs.chromium.org to figure out how we'd implement it there.

[callumdmay]

Are you suggesting using ES256 as the only supported algorithm for the next version (eg. V3)? If that is the case, we are fine with this and can open up a change against the spec. Regarding future support for additional algorithms, how do you envision coming to consensus on algorithms in future versions?

[dvorak42]

Yeah, I think for V3 that makes the most sense since the benefits of reducing consumer implementation load and ecosystem complexity from running both versus losing the small performance benefits falls on the side of reducing ecosystem complexity.

For future additional algorithms, I think we'll need to analyze and balance the costs of adding it to the ecosystem and whether the benefits/security/performance is worth it, and whether clients are likely to implement the algorithms/are able to fuzz it. Once this is on a standards track/owned by a WG, if there really isn't agreement on the tradeoffs, we can use that WG's consensus building approach.

Also, we probably will need to bikeshed what the SigAlg should actually be called, AFAIK ES256 is JWT specific terminology? ecdsa_secp256r1_sha256 is the equivalent in TLS land.

[callumdmay]

That all sounds great, and leveraging the WG's consensus building in case of disagreement makes sense. Agreed on ES256 being shorthand, we can use ecdsa_secp256r1_sha256 for the spec. Will get this change up shortly