Implement verification by a threshold of keys

[sechkova]

Description of issue or feature request:
A verification of signed metadata by a threshold of keys is needed both for client and repository.

Metadata already has vanilla one-signature verify and could potentially be the right location for this implementation. See #1060 (comment) for thoughts about that distinction.

[joshuagl]

When computing whether the threshold of signatures has been met, we need to be sure that only a single valid signature is counted for each keyid in the signatures list.

This prevents a malicious key owner from signing metadata multiple times to meet the threshold.

For more details see: GHSA-pwqf-9h7j-7mv8 and 83ac7be

[mnm678]

Good catch @joshuagl. Depending on how keyids are computed or validated, we may also need to ensure that each actual key is only counted once (and not, for example use both the sha256 and sha512 keyids for the same key). There's some discussion about this in TAP 12

[joshuagl]

Indeed, I considered multiple keyids for the same key but decided not to mention it as the current specification requires keyids be the sha256 hash of the key's canonical form. I agree it would be worth trying to implement threshold computation in a forward-thinking way if it doesn't complicate things too much, that probably means ensuring that signatures are unique, keyids are unique, and that each keyid maps to a unique key?

FYI I filed a PR against the spec to try and describe what's required of implementations here theupdateframework/specification#154

[jku]

So the problem space is this:

• Root contains keys and thresholds for top level metadata
• delegating (targets) roles contain keys and thresholds for their delegated roles
• The "metadata controller" (client code or some repository tool) wants to verify all metadata using the correct keys and thresholds from the delegating role in a way that makes it clear what is happening
• "key uniqueness" wrt threshold needs to be upheld

Some options I see are (examples for a hypothetical client that wants to verify a timestamp file it has just downloaded):

• Root and Targets provide a function that verifies their delegates (note that this one turns the verifier/verifiee around -- root verifies timestamp instead of timestamp verifying itself with data from root):

  root.signed.verify_delegate_with_threshold("timestamp", unverified_metadata)
  

• Metadata provides a way to verify itself and the delegating roles provide an easy way to get actual securesystemlib keys for a specific role

  keys = root.signed.get_keys("timestamp") # returns list of sslib key dict
  threshold = root.signed.get_threshold("timestamp")
  unverified_metadata.verify_with_threshold(keys, threshold)
  

• Metadata provides a way to verify itself and knows how to transform keyids to sslib keys

  keyids = root.signed.roles["timestamp"]["keyids"]
  threshold = root.signed.roles["timestamp"]["threshold"]
  unverified_metadata.verify_with_threshold(keyids, threshold)
  

(editing to add a fourth option)

• Metadata verifies that delegate is signed by correct threshold of keys:

  md.verify_delegate_with_threshold("timestamp", unverified_metadata)
  

This looks nice but does mean the function will have to check that self.signed is a Root or Targets...

[sechkova]

For options 2 and 3, delegated roles need to be aware of their parent (delegating role) to retrieve the correct keys/threshold which, except for the case when the parent is root, is not trivial because it is not stored in the metadata.

[MVrachev]

For options 2 and 3, delegated roles need to be aware of their parent (delegating role) to retrieve the correct keys/threshold which, except for the case when the parent is root, is not trivial because it is not stored in the metadata.

It could be added to the metadata if we decide.
Delegations are not yet implemented and we can add info about the parent.

I feel like the first option makes the most sense to me, but I am wondering how it will look like from an implementation perspective.
Especially in the case of delegations and when then can be multiple levels deep.
It seems we would have to be able to recursively verify the delegations three.

[sechkova]

It could be added to the metadata if we decide.
Delegations are not yet implemented and we can add info about the parent.

I was referring to the specification, but yes, it can be extended in the implementation.

It seems we would have to be able to recursively verify the delegations three.

This needs to happen in all cases

[jku]

For options 2 and 3, delegated roles need to be aware of their parent (delegating role) to retrieve the correct keys/threshold which, except for the case when the parent is root, is not trivial because it is not stored in the metadata.

in the hypothetical examples I was thinking this code is in e.g. client Updater and it would handle the "delegation tree" and would know who can verify who (updated comment to explain that).

[jku]

What makes this annoying is that delegation data is just different enough in Targets and Root that sharing an implementation is a bit difficult.

I've got a prototype of option 1 jku@3cf353b

[jku]

• Root and Targets provide a function that verifies their delegates (note that this one turns the verifier/verifiee around -- root verifies timestamp instead of timestamp verifying itself with data from root):

  root.signed.verify_delegate_with_threshold("timestamp", unverified_metadata)
  

I guess this could actually be a Metadata function as well (and not a Root/Target function):

md.verify_delegate_with_threshold("timestamp", unverified_metadata)

in this case there would be code in metadata that would do one thing if self.signed._type=='root' and and another if self.signed._type=='targets' ... A bit ugly but could work: develop...jku:verify_with_threshold

[joshuagl]

(Apologies for the brevity of this drive-by comment)

I think delegator verifies the delegated is the right approach (I do not like delegated verifies itself with info from delegator, options 2 & 3 in the original breakdown).

verify_delegate_with_threshold() in develop...jku:verify_with_threshold looks like a good starting point (at first glance it's missing at least an optional Signer parameter).

[jku]

Note to self: Clarify the uniqueness of role names in delegations. The file format and spec does not enforce this (because roles in delegations is an ordered list), but I think there can only be one role with a specific role name in a delegations object: to verify the delegation with threshold of keys we need to lookup the keyids with the role name: if there were multiple roles with same name they could have different keyids...