Public key signature constraint

[Geal]

To implement use cases such as third party caveats, or using a biscuit token as attestation accumulating acknowledgement from multiple parties, caveats should be able to verify a public key signature.

A few questions here:

• do we fix the allowed algorithms, and if yes, which one(s)? If no, how?
• should I add a new data type for this? Could we just fit it into strings? Or make a more general byte array type?

Signature verification would work well as a constraint affecting 3 elements (message, key, signature) that could be filled in various ways:

• verify(message, key, sig?): a signature from a specific key must be provided
• verify(message, key?, sig?): a signature must be provided, from any key, but we could have other constraints on that key here (like the key must be in a certain set)
• verify(message?, key, sig?): specify we must have a valid signature from a key, with other constraints on the message

[Geal]

thinking a bit more about it now, it might be smarter to let the verifier's side handle that, ie patterns like this:

• we have a biscuit token that accompany some data
• the token has a fact with the hash of that data
• the token has a caveat that requires a fact from the verifier describing a valid signature for that hash with a specific key
• the verifier looks at the data and the accompanying signatures, and generates a list of facts for them
• the verifier checks the caveats

[titanous]

Currently the algorithms I'd like support for are:

• P-256 ECDSA
• Ed25519
• 2048-bit RSASSA-PKCS1-V1_5 (this one is unfortunate, but the only algorithm supported by keys generated via the ChromeOS Verified Access API)

It would also be neat to support U2F/WebAuthN assertions (a P-256 ECDSA signature over a specific data structure).

[Geal]

with https://github.com/CleverCloud/biscuit/issues/40 there will be a way to represent keys, so now we can think more about how to represent it. A key point in implementing it is that a verifier can do queries before checking the caveats. So the idea would be to have the verifier query for any signatures to check, then we create facts to represent a valid signature, and the token has caveats to check those signatures. I think it's better to provide the pattern as a kind of "cookbook" instead of integrated inside Biscuit's basic API, since it is unlikely to match all use cases.

Facts needed for the query:

• should_sign(data_index: int, algorithm: symbol, public_key: bytes) with data index that would either match a fact data(data_index, content:bytes) or some additional data that will accompany the token. The algorithm can be a symbol since it will probably be repeated
• signature(data_index: int, algorithm: symbol, public_key: bytes, content: bytes). I thought about having the public key be an index to match a public_key(key_index: int, content: bytes), but someone could try to add any key for this, so it's better to just repeat it
• should_hash(data_index: int, algorithm: symbol, digest: bytes). I'm not sure that one is needed, but it would be easy enough to add

Queries from the verifier:

• request all the should_sign facts
• request all data facts with matching index (or get them from data coming with the token). If there are multiple facts with the same index, fail
• request all signature facts
• for each matching data, should_sign and signature, check the signature, and add a fact valid_signature(#ambient, data_index: int, algorithm: symbol, public_key: bytes)

Caveats in the token:

• we can have the simple case, just requesting one signature: *valid(0?)<- should_sign(0?, 1?, 2?), valid_signature(#ambient, $0, $1, $2)
• but we can also have more general cases like requesting a signature from any of a set of public keys: *valid(0?)<- should_sign(0?, 1?, 2?), valid_signature(#ambient, $0, $1, $2) @ $2 in [ hex:01020304, hex:04050607 ]`
• by stretching things a bit, we could even represent a PKI, but it would be better to make a special scheme for it
• I'd like to support patterns like M out of N signatures, but it would require the introduction of operators (#38)

The verifier will then check the caveats and the token will succeed if the required signatures are here.

@titanous what do you think?

[titanous]

This all makes a lot of sense! The main thing I'm thinking about is how the data to be signed will be formatted. I'm going to drop some notes below.

• In the case of a basic proof of possession (PoP), we want to bind the signature to the specific biscuit and allow for replay prevention, so a reasonable construction would be a signature over ["biscuit-pop-v0", biscuit_challenge, signer_nonce, signer_timestamp].
  • "biscuit-pop-v0" - static context bytes to prevent key misuse
  • biscuit_challenge - a random nonce taken from the block to bind the signature to it
  • signer_nonce - a random nonce generated by the signer, to allow replay prevention
  • signer_timestamp - the current timestamp, added by the signer, to allow windowing the replay prevention lookup (the server should reject timestamps outside of the current window)
• In a more advanced case, we'd want to extend the above PoP scheme and add additional attributes that allow us to bind to the request context. Depending on the client, some of these attributes may not be available, so we need to allow some PoP attributes to be optional. Additionally, these fields should have a delimiter (newline or length prefixing are common) to prevent unexpected collisions. Here are the most common attributes that I can think of:
  • HTTP method/URI
  • Headers
  • Message hash
  • TLS channel binding (this is one that would not be available in the browser, but would be in a native app)
  • The AWS v4 scheme is probably the most widely deployed request signing scheme.
• I think we could have data facts with multiple arguments that define the expected template for the data.
• Macaroons include an additional step, M.PrepareForRequest(M), which binds the first party macaroon together with all of the discharge macaroons, to ensure that any discharges cannot be reused outside of the expected context. It seems like we should allow a construction that enables this, though I'm not sure what the best way to do it is.
• The proliferation of WebAuthN authenticators provides a great opportunity to allow the easy use of hardware-backed keys. Due to the way the CTAP1/2 and WebAuthN protocols work, we don't have complete control over the data that is signed.
  • The request for a WebAuthN authentication contains the following parameters:
  • challenge - this is where the hash of the data we want signed goes, in most cases this would be a version of the above PoP scheme.
  • rpId - usually the domain name of the relying party, limited control when going through the JS/browser interface, complete control when talking to the hardware directly.
  • allowCredentials - this is the list of credential IDs (and their associated transport) that are valid, this would likely be provided in the biscuit, listing authenticators that have been enrolled.
  • userVerification - whether to require a test of user presence, one of required, preferred, discouraged, defaults to preferred.
  • extensions - we can ignore this for now
  • After requesting the signature, we get the data that has been signed back, which contains fields that map to the above parameters, as well as some other fields (which can be ignored). This data should be verified to make sure it is signed correctly and that it is well-formed and contains all of the provided parameters.
  • Technically WebAuthN supports multiple signing algorithms, but everyone currently uses P-256 ECDSA.
  • Given how specific this flow is, it probably makes sense to have a separate fact that looks something like: should_webauthn_auth(data_index: int, credential: bytes, rp_id: string, user_verification: symbol) and a corresponding fact added by the verifier: valid_webauthn_auth(#ambient, data_index: int, credential: bytes, rp_id: string, user_verified: symbol)

[titanous]

@daeMOn63 has implemented an experimental proof of possession scheme here: https://github.com/flynn/biscuit-go/blob/master/experiments/pop_test.go

[divarvel]

Are these use-cases covered by the third-party blocks? They allow to handle signatures / verifications outside of datalog, avoiding a lot of issues related to exposing crypto primitives from within datalog.