Biscuit 2.0

[Geal]

Version 1.0 was released in March 2021 245ab9e. Since then, we got more experience using it, and there are still some rough edges. I discussed it a lot with @divarvel and we feel it could be improved, but that would require breaking changes, hence a 2.0 version.

Proposals

New cryptographic scheme

We're currently using aggregated signatures (pairings and VRF designs were abandoned early) over Ristretto to ensure Biscuit's security properties. The scheme is working fine, but is complex to implement, even when copying the libsodium calls list. Auditing it, for every implementation, will be a pain.

Proposal: we move to a new scheme, similar to the "challenge tokens" idea described in the design document, but simplified

It boils down to having each block signing the next block's public key, and shipping the last secret key with the token (so it can add another level). It's basically a chain of signatures like a PKI, can be done with a serie of ed25519 keys (easy to find good implementations), and it is easy to seal a token (sign the entire token with the last secret key, remove the secret key, send the token with the signature).

breaking change: the entire protobuf format changes

cf issue #73

Aggregation operations

As mentioned in #38: it would be useful to support aggregation operation in Datalog, like count, sum, min, max, average, and set operations like union and intersection.

Potential problem: in biscuit implementations, Datalog uses the bottom up, naïve approach, which could result in infinite execution through rules like this one: fact($i) <- fact($j), $i = $j + 1

This could be fixed by moving to different implementations, like the top down approach. We could also restrict the kinds of operations available, but I'm worried we would spend a lot of time finding all possible cases. Fixing it once in the engine might be better.

TODO: write issue

Symbol table

Manipulating the symbol table is messy, and it use in both the format and the datalog engine do not help in understanding it. It was introduced both to reduce the token's size (because some names and strings might be repeated) and for faster datalog execution (by interning strings, we can unify them through comparing integers instead of comparing entire strings).
Unfortunately, the separation between "symbols" and "strings" is not clear, and providing custom symbol tables is error prone.

Proposal: remove the symbol type, except for some special symbols like authority and ambient, have every string be stored in the symbol table, add more elements to the default symbol table

It would probably reduce the token size a bit, and simplify the Datalog implementation (and make it slightly faster)

breaking change: this changes the Datalog serialization, and removes the symbol type

TODO: write issue, test implementationthis changes the Datalog execution

Revocation identifiers

We currently have two kinds of revocation identifiers, unique and not unique, because unique revocation identifiers were added afterwards. We should return to unique revocation identifiers only

breaking change: older revocation identifiers will not be used anymore

Ternary and n-ary operations

Currently expressions only support unary and binary operations, we'll probably need to support larger types of operations

Scoped rules

Currently we have a concept of "privileged rules" that can generate facts with #authority and #ambient symbols. Those symbols are used in facts describing the basic rights of the token (from the root block) and the current variables from the request (date, which resource is accessed, IP address, etc).
These symbols are confusing, and currently facts and rules in blocks other than block 0 can easily mess with each other (like, block N+1 generating facts to pass checks from block N).

Proposal: rules and checks should only be able to use facts from earlier and current blocks, not future ones, and generate facts scoped to the current block. The verifier generates facts at the scope of the first block but can check facts from all scopes

Potential problems:

• this will be surprising compared to other Datalog implementations

breaking change: this changes the Datalog execution

cf issue #75

[divarvel]

I can elaborate on scoped rules if needed. IMO, the main work would be nice tooling and error reporting, to help understand what rules are available. Putting block numbers in the syntax seems very error prone (more than the current system with #ambient and #authority, with the extra complexity of having to count block before creating the datalog statements).

[Geal]

new cryptographic scheme #73:

• spec: d91e055
• Rust: biscuit-auth/biscuit-rust@6aba600

writing the crypto part is rather quick, but updating the serialization takes some time (since there's a breaking change in the format)

[Geal]

scoped rules #75:

• spec: 0175a4e
• Rust: biscuit-auth/biscuit-rust@f750e2b and biscuit-auth/biscuit-rust@42b4bec

scoped rules are relatively painless to implement, the trick is in removing rules between each block so that they are not reused on later facts

[Geal]

removing the symbol type:

• samples: a195fb4
• spec: 6092bd1
• Rust: biscuit-auth/biscuit-rust@1decc95

[Geal]

use the block signature as revocation id:

• samples: deb45ac
• spec: 040c204
• Rust: biscuit-auth/biscuit-rust@d2de2c3

[Geal]

so with these changes biscuit 2.0 is nearly done. Aggregation, ternary operations can come as future, smoother updates

[Geal]

rename ID to Term (this has always been confusing):

• spec: 6c9f12d
• Rust: biscuit-auth/biscuit-rust@a32425a

[Geal]

Still missing for this release:

• adding a separating character in fact names to help in namespacing things (cc @meh), like module::fact("data"). The character would have no real meaning for datalog execution, it's mainly for the UX
• specifying the accepted characters in strings: authorize tabs, unicode characters (with escapes)

[Geal]

sealed token sample: bc3a34b

[Geal]

add an enum indicating the key's algorithm, sign it with the key:

• spec: f38c856 and 1ced350

[Geal]

rename verifier to authorizer:

• spec: 16357ce

[Geal]

this is in a good place now, only missing the character spec from upper comment #72 (comment)

I'd like to release a 2.0 very soon. @titanous @daeMOn63 do you see any big issue that could appear when upgrading the Go version?

[divarvel]

As for #72, the spec does not provide a grammar for string literals and identifiers, afaik (for the haskell impl, I followed what was done in biscuit-rust).

I guess providing a grammar for datalog (or at least, literals and identifiers) would be good.

For string literals, idk if there is a standard way to parse them (eg with a complete list of authorized escapes). We could at least mandate utf8, no BOM, stuff like that.

[Geal]

alright, there's a test now for character uses: a450938

mabe I could add a few more tests, for integer values, testing for overfows, etc

[Geal]

add an EBNF grammar: cbc7aac #82

[Geal]

v2 has shipped 🥳