Add support for a Macaroon-like, symmetric contruction about biscuit HOT 10 CLOSED

Something I am somewhat concerned about is that it might not be possible to provide the semantically-secure encryption and offline attenuation.

Imagine a Macaroon-like construction, using AE instead of HMAC; for a token s, if I observe s.append(a).append(b) and s.append(a).append(c) (but not s itself), I can tell that those two share a caveat prefix (and I can tell its size, rounded to block sizes).

from biscuit.

I have a lot of thoughts on both of these things:

• In my as-yet-unwritten "Madeleines" extension to Macaroons, where I ultimately netted out was using them as a way to establish a symmetric Macaroon with a target service. A client would hand over their certificate-like credential, signed by a central service, but containing a public D-H key identifying that client. The target service can then verify that credential and mint a Macaroon with the same claims/caveats, but containing a third party caveat that can only be discharged by the client itself. The client performs a key exchange (possibly incorporating ephemeral D-H keys in a Noise-like key exchange pattern), can now decrypt the caveat key, and apply their own set of service-specific caveats. The result is a Macaroon-like split credential which can be verified entirely symmetrically by the target service, while also incorporating a set of client-imposed caveats.
• For Macaroon encryption, what I had in mind was a chained/vectorized EtM construction. Roughly this might look like:
  • Assuming a secure PRF (P), use it in CTR mode with an initial key k0: Ek1 = P(k0, 0); Mk1 = P(k0, 1) to derive the first-level encryption and MAC key
  • Encrypt the first segment using an unauthenticated stream cipher (e.g. AES-CTR) under Ek1: ct1 = Encrypt(Ek1, 0, pt1)
  • MAC the first segment ciphertext: mac1 = P(Mk1, ct1)

This can be chained for multiple message segments, where P is applied to mac1 as the key instead of (k0), and used to encrypt the next message segment.

To verify, MAC all of the segments with P, and ensure the tag matches. If it does, then decrypt the caveats using the derived per-caveat keys.

In this model, we're deriving encryption keys using attacker controlled PRF inputs, but in a hierarchy which is rooted in a key unknown to the attacker. My personal inclination is if P is a secure PRF, this should still be secure (and if it weren't, any security problems would apply to the original Macaroons construction as well!), but I certainly can't prove that.

One part that is particularly weird is any holder of a credential which is a strict superset of another can decrypt any caveats which have been added to a Macaroon, possibly by another party. This seems like it could be either useful or have unintended security consequences.

from biscuit.

I'm a bit concerned about having a token that cannot be checked by the holder, and moreover this brings us back to a system where all of the verifiers need to share the original secret key, right?
It's very useful to have verifiers that can only verify, not mint new top level tokens.

from biscuit.

moreover this brings us back to a system where all of the verifiers need to share the original secret key

No, that's what "Madeleines" were intended to solve, although the more I think about it, what I really want is more of a workflow for going from a certificate/"biscuit" to a symmetric token/Macaroon. In that case you'd start with a cert/"biscuit" signed by a central authority, but each target service would have its own symmetric key, and to "log into" a service a client would present the certificate/"biscuit", the target service can return a Macaroon-ish symmetric credential with a third party caveat that needs to be discharged by the client, and then the client can mint the discharge Macaroon which makes the Macaroon minted by the target service valid (i.e. completes the proof).

The latter bit is the important magic: it means that one target service can't simply steal the certificate/"biscuit" and present it to another service. The client needs to confirm they actually want to log in (and potentially add their own caveats) by creating a discharge Macaroon unique to that particular target service. The basic idea is when the client originally gets a "biscuit" from the central authority, they provide a static D-H public key, and that key would get signed into the "biscuit". To generate the third party caveat, the target service would extend existing Macaroon keywrap into an ECIES (this is actually described in the Macaroons paper!), which would allow them to decrypt a randomly generated third party caveat key the target service keywrapped.

The result is a fully symmetric Macaroon set which skips the need to perform additional public key operations once the target service has initially verified the certificate/"biscuit" and minted a Macaroon from it.

from biscuit.

having a token that cannot be checked by the holder

That's a fair concern, @Geal. On the other hand, I'm not sure such a verification is super meaningful when interacting with a single party (and symmetric biscuits can only support that, since they require access to the minting secret):

• that party is the one which issued your credential;
• you aren't verifying that its interpretation of biscuit is the same as yours (i.e. that it uses a correct implementation).

all of the verifiers need to share the original secret key, right?
It's very useful to have verifiers that can only verify, not mint new top level tokens.

Useless TL;DR: “Yes, but no.”

Yes, verifying a symmetric biscuit requires having access (directly or not) to the minting key.
No, a service can be restricted to verifying (but not minting) by giving it a verification oracle from which the minting secret cannot be extracted (for ex. implemented by a HSM, or an SGX enclave).

Yes, having verification-only capability is exceedingly useful, and Macaroons tended to push towards undesirable designs, either due to minting key proliferation, or due to requiring the client to perform many requests to discharge 3rd-party caveats (which is a latency and availability issue).
No, I don't think symmetric biscuits would have that effect, because there are asymmetric biscuits too, and conversions between them are possible.

I think the caching usecase is a good example of that:

• the relying service needs access to an issuing secret, but it can be one that is specific to that service (or even to a single server within that service);
• cross-service interactions are still mediated by pubkey biscuits;
• we are trading a tiny bit more communication on the first request (as an equivalent, symmetric biscuit is sent back) against computation and communication in later queries:
  • replacing ECC computations with symmetric crypto that is orders-of-magnitude faster;
  • replacing a revocation check (involves I/O, either to a revocation-checking service or to a local revocation list) with a short-lived token.

from biscuit.

@tarcieri Yes, that's similar to what I had in mind (though I suspect it's possible to do it in a single pass).

What I meant specifically, when I said it doesn't provide semantic security, is that if I do not have the minting key, and observe 2 biscuits, I can tell whether they were obtained by attenuating the same biscuit, by checking whether they share a prefix.

I don't think it is necessarily a huge problem (esp. in protocols that already use a private channel), but it doesn't fit standard definitions of confidentiality., and makes the privacy model more complex.
Sadly, I doubt it's possible to avoid that while still providing offline attenuation, constant overhead, and decryption/verification in linear time and constant space.

from biscuit.

What I meant specifically, when I said it doesn't provide semantic security, is that if I do not have the minting key, and observe 2 biscuits, I can tell whether they were obtained by attenuating the same biscuit, by checking whether they share a prefix.

Most credential systems have the property that credentials are fixed and replayed per request, which violates typical notions of semantic security. Of course, in most credential systems, if the attacker can observe your credential, all is lost.

With offline attenuation we're at a somewhat curious middle ground, where we're minting unique credentials per request with the goal of passing them through "semi-trusted" systems (e.g. proxies), but as you mentioned, they share a common prefix.

I don't think it is necessarily a huge problem (esp. in protocols that already use a private channel)

I'm generally thinking of an "honest but curious" threat model where one of these proxies might want to learn about the plaintext of the token. We can imagine it contains PII the proxy wants to learn (really my main motivation here is preventing the accidental disclosure of PII, but it's a lot more fun to think about things within an adversary model).

Even if we don't have a full loss of confidentiality, they can potentially learn quite a bit by the prefix patterns they observe.

it doesn't fit standard definitions of confidentiality

It is definitely much weaker than, say, IND-CCA3.

from biscuit.

it doesn't fit standard definitions of confidentiality

It is definitely much weaker than, say, IND-CCA3.

Yes, semantic security is (much, much) weaker than IND-CCA3, so there's no way we were going to fulfill that one. ;)

from biscuit.

I added an example of a sealed token, but only using HMAC for now: 055c02b
anyone wants to try the encrypted version?

from biscuit.

closing for now, we might revisit that later

from biscuit.