Thank you for the speedy review! On Tue, Mar 14, 2023 at 2:53 PM Ilari Liusvaara <[email protected]> wrote:
> On Tue, Mar 14, 2023 at 08:36:43AM -0500, Orie Steele wrote: > > Here is the I-D, I promised: > > > > > https://datatracker.ietf.org/doc/html/draft-steele-cose-merkle-tree-proofs-00 > > > > There are a few rough edges still, I look forward to discussing with > > the group. > > Some quick comments/ideas: > > - Extra data should either be supported by every tree algorithm, or > eliminated. Otherwise it seems like a nasty footgun. > > Yes, sadly despite how simple merkle trees are, the construction of the leaf (prior to hashing or including hashing...) is observed to be a source of complexity. A verifier needs to be able to construct the payload and hash it to produce a leaf, to prove inclusion for a payload under a given tree algorithm. And a few tree algorithms include extra data, in the construction of the leaf, prior to hashing. So you simply can't verify the payload without the extra data. The verifier wants to know if "payload" is included in a signed root. The verifier wants to process the payload, and if extra metadata is mixed with it before the leaf is produced... The extra metadata needs to be retained, and processed according to the tree alg. Of course what I am saying has to do with using CBOR for "existing tree algs" that are observed in the wild, that require "extra data". If you are building a brand new tree alg, you might be able to make a CBOR representation of a leaf and its proof much more elegant. There are also cases where "payload" is already a hash / content identifier. We aim to provide clarity around how to support these various cases using CBOR representation for the data structures. - Add optional nonce in SignedMerkleTreeProof (to make some attacks > harder). The nonce must go into the leaf hash first. > Yes, there is another use case for merkle proofs, beyond just inclusion proofs, which is selective disclosure, and that also relies on nonces, to protect against brute force attacks on siblings. Nonces are an example of "extra data" in my mind. There is also the case where you want to sign over the nonce in a protected header, but not include the nonce in the proof from leaf to root. > > - UndirectionalInclusionPath should either be used or eliminated. > > There are several other tree algorithms we have been looking at, our goal is to only define proof representations that are valuable for tree algorithms. We will remove this path format, if we have no tree algorithms that benefit or require it. > - The payload could be detached like in signatures. Yes! However, it may be necessary to combine it with extra data / nonce to create the leaf to prove inclusion, for certain tree algorithms. In the case the payload is very large, you will really want to detach it, or substitute a hash of it / use a content id system. > - The structure could be flattened. Something like: > > SignedMerkleTreeProof = [ > root_protected: bstr .cbor header_map, > root_unprotected: header_map, > index: uint, > peer_hashes: [+ bstr], > nonce: bstr / nil, > extra_data: bstr / nil, > payload: bstr / nil, > root_signature: bstr, > ] > > Where root_* are the corresponding fields from COSE_Sign1 forming the > root signature. > > If root_protected does not contain tree size property, then index > contains path vector (lsb is toward leafs, 1 is right, 0 is left). > > I can see value in the flat structure for the inclusion path, I used a similar approach in my latest implementation I would prefer to be able to transport the inclusion proof in unprotected headers. Or the signed inclusion proof in unprotected headers, similar to how COSE counter signatures work. > - To prevent possible cross-protocol attacks, either this needs to > flag the tree algorithm as critical or use a new context for > signature. > > Interesting. I would like to avoid `crit` if possible. I would also like to avoid registering new `alg` values. Not sure if you are suggesting we must choose one or the other. > - The hash data could be CBOR-encoded: > > InternalNode = [ > left: bstr, > right: bstr, > ] > > LeafNode = [ > nonce: bstr / nil, > extra_data: bstr / nil, > payload: bstr, > ] > > And then the hash is either: > > HASH(CanonicalEncode(InternalNode)) > HASH(CanonicalEncode(LeafNode)) > > Where CanonicalEncode is the canonical encoding as in RFC 9052. > > These can not collide, because one is 2 elements (always starts with > 0x82) and the other is 3 (always starts with 0x83). > > This seems to be a proposal for a new tree algorithm, since it produces a leaf which is based on a CBOR structure. The root for this algorithm would be computed over CBOR structures, if I read this correctly. Most tree algorithms I have seen do not assume CBOR, and yet, we can still represent their proofs in CBOR. Thank you for the comments! > > > -Ilari > > _______________________________________________ > COSE mailing list > [email protected] > https://www.ietf.org/mailman/listinfo/cose > -- *ORIE STEELE* Chief Technical Officer www.transmute.industries <https://www.transmute.industries>
_______________________________________________ COSE mailing list [email protected] https://www.ietf.org/mailman/listinfo/cose
