New, simpler cryptographic scheme

[Geal]

The current design based on aggregated signatures is working fine, but is too complex to implement, and hard to audit properly in every implementation.

We should move to a new scheme that can still guarantee Biscuit's basic properties:

• we can append a new block to a token, and get a valid token
• we cannot modify existing block and get a valid token
• we cannot remove an existing block and get a valid token
• verifying a token only requires one piece of public information (no secret shared between all verifiers that could allow them to mint a new token)

Proposal

The idea of this scheme is that each block has a corresponding keypair signing it, and the signature covers the public key of the next block. The token ships with the secret key of the next block. Holding that token, it is then possible to sign the next block (and generate the next keypair). We can seal a token (forbid attenuation) by using the last secret key to sign the entire token, and replace the last secret key with that signature.

That scheme can be done with simple building blocks (cryptographic hash and public key crypto, like Ed25519) and will be much easier to implement and audit than aggregated signatures.

• we have a root Ed25519 key pair, sk0, pk0
• creating a token from block0:
  • generate ephemeral keypair sk1, pk1
  • sig0 = sign(sk0, block0+pk1)
  • token0 = block0, pk1, sig0, sk1
• creating token j=i+1 from existing token i and new block i:
  • generate ephemeral keypair sk_j, pk_j
  • sig_i = sign(sk_i, block_i + pk_j)
  • token_j = block_i, pk_j, sig_i, sk_j
• verifying a token i:
  • the verifier knows pk0
  • token i contains: block0, pk1, block1, pk2, ... block_i-1, pk_i, sig_i-1, sk_i
  • verify signatures:
    • verify(pk0, sig0, block0+pk1)
    • ...
    • verify(pk_i-1, sig_i-1, block_i-1, pk_i)
• seal a token i (forbid further attenuation):
  • token i contains: block0, pk1, block1, pk2, ... block_i-1, pk_i, sig_i-1, sk_i
  • sig_j = sign(sk_i, block0 + pk1 + block1 + pk2 + ... + block_i-1 + pk_i + sig_i-1)
  • token_j contains: block0, pk1, block1, pk2, ... block_i-1, pk_i, sig_i-1, sig_i

TODO: benchmarks, measure token size, audit scheme

cc @divarvel

[divarvel]

Here's a toy implementation in Haskell (creation, attenuation, verification for extensible and sealed tokens): https://gist.github.com/divarvel/73d17e92e72e0a00b8666d971e27c060

For the token size, a back-of-the-envelope calculation of (a lower bound) the overhead (the size added to the payload) of this scheme gives
32 bytes (the final secret key) + 96 bytes (1 pub key + 1 signature) per block.

For a sealed token, it would be 64 bytes (the final signature) + 96 bytes per block

[Geal]

additional note: the new format might not integrate the root key in the token, and instead have a key id field, letting the verifier side decide which key to use.
This will imply changes to the APIs: the key id must be extracted before verifying the signature (if there is only one key the verifier can ignore the key id)

[clementd-fretlink]

Here's a proposition for the new wrapper format (eg where block contents are opaque bytestrings).

There are a few design differences compared to the current one:

• payloads, signatures and public keys are bundled in the same list (instead of being in 3 lists that have to have the same length)
• authority is required, on its own since it's always defined
• Biscuit and SealedBiscuit are modeled with a oneof in the same message (alternate schemas can be defined to only suport Biscuit or SealedBiscuit while staying compatible with the common format)

syntax = "proto2";

package biscuit.format.schema;

message Biscuit {
  optional uint32 rootKeyId = 1;
  required SignedBlock authority = 2;
  repeated SignedBlock blocks = 3;
  required Proof proof = 4;
}

message SignedBlock {
  required bytes block = 1;
  required bytes nextKey = 2;
  required bytes signature = 3;
}

message Proof {
  oneof Content {
    bytes nextSecret = 1;
    bytes finalSignature = 2;
  }
}

For the block payloads, the existing format can be used (with the V0 fields removed and the V1 fields renamed as V2, and with new datalog features such as deferred checks or signature operations)

[zarutian]

We can seal a token (forbid attenuation) by using the last secret key to sign the entire token, and replace the last secret key with that signature.

@Geal What is this functionality for exactly?

See this explanation for why this is a bad idea.

SPKI made the same mistake with its 'do not delegate' bit.

I highly recommend dropping SealedBiscuit altogether. Why? further attenuation should always be possible. Even though it might result in impotent biscuit. For the cases of flaunting to someone else that you have a particular biscuit I recommend using a neutering block with a 'chalange' fact containing a string given by the aforesaid someone.

[Geal]

@zarutian sealed tokens were introduced first as a way to exchange an attenuable token for a short term non attenuable one, because the signatures were still costly to verify. So it is not strictly necessary anymore.
I think we should still keep it for now, while evaluating other applications of the token. If there are no other uses it will be safe to remove.

[Geal]

closing this because v2 has shipped