Tuf: Targets delegations are not updated when adding a new delegation key

[sechkova]

Description of issue:

When adding a new key to a delegated role e.g.:

repository.targets('unclaimed').add_verification_key(public_new_key)

the delegating role metadata (e.g. targets.json) is not updated with the new key.

Steps to reproduce:

1) Delegate to 'unclaimed' role

repository.targets.delegate('unclaimed', [public_unclaimed_key], ['*']) 
repository.mark_dirty(['unclaimed', 'targets', 'snapshot', 'timestamp'])
repository.writeall()

Delegated role's internal metadata:

tuf.roledb.get_roleinfo('unclaimed')    
{'name': 'unclaimed',
 'keyids': ['9313d41de1204c061f09429197edbe12f71bd6dd354ebae6bd3bdbee4bffb1e1'],
 'signing_keyids': [],
 'threshold': 1,
 'version': 1,
 'expires': '2020-08-25T21:30:11Z',
 'signatures': [],
 'partial_loaded': False,
 'paths': {},
 'delegations': {'keys': {}, 'roles': []}}

targets.json:

"signed": {
  "_type": "targets",
  "delegations": {
   "keys": {
    "9313d41de1204c061f09429197edbe12f71bd6dd354ebae6bd3bdbee4bffb1e1": {
     "keyid_hash_algorithms": [
      "sha256",
      "sha512"
     ],
     "keytype": "ed25519",
     "keyval": {
      "public": "ede15f800ab11184080552a4edbfa61b0a0920243acebd536cca7d344331d21b"
     },
     "scheme": "ed25519"
    }
   },
   "roles": [
    {
     "keyids": [
      "9313d41de1204c061f09429197edbe12f71bd6dd354ebae6bd3bdbee4bffb1e1"
     ],
     "name": "unclaimed",
     "paths": [
      "*"
     ],
     "terminating": false,
     "threshold": 1
    }
   ]
  },
  "expires": "2020-08-25T21:27:11Z",
  "spec_version": "1.0.0",
  "targets": {},
  "version": 2
 }
}

2) Rotate the 'unclaimed' role key

repository.targets('unclaimed').remove_verification_key(public_unclaimed_key)
repository.targets('unclaimed').add_verification_key(public_new_key) 
repository.mark_dirty(['unclaimed', 'targets', 'snapshot', 'timestamp'])
repository.writeall()

Delegated role's metadata is updated:

tuf.roledb.get_roleinfo('unclaimed')
{'name': 'unclaimed',
 'keyids': ['10bb2defd9e01b2bbed14f1eab48c92495136675f3af2fa6dfd277a63ca45f0e'],
 'signing_keyids': [],
 'threshold': 1,
 'version': 2,
 'expires': '2020-08-25T21:30:11Z',
 'signatures': [],
 'partial_loaded': False,
 'paths': {},
 'delegations': {'keys': {}, 'roles': []},
 'previous_keyids': []}

targets.json keeps the old key:

"signed": {
  "_type": "targets",
  "delegations": {
   "keys": {
    "9313d41de1204c061f09429197edbe12f71bd6dd354ebae6bd3bdbee4bffb1e1": {
     "keyid_hash_algorithms": [
      "sha256",
      "sha512"
     ],
     "keytype": "ed25519",
     "keyval": {
      "public": "ede15f800ab11184080552a4edbfa61b0a0920243acebd536cca7d344331d21b"
     },
     "scheme": "ed25519"
    }
   },
   "roles": [
    {
     "keyids": [
      "9313d41de1204c061f09429197edbe12f71bd6dd354ebae6bd3bdbee4bffb1e1"
     ],
     "name": "unclaimed",
     "paths": [
      "*"
     ],
     "terminating": false,
     "threshold": 1
    }
   ]
  },
  "expires": "2020-08-25T21:27:11Z",
  "spec_version": "1.0.0",
  "targets": {},
  "version": 3
 }

Current behavior:
The delegating role metadata is not updated when a delegation key is updated

Expected behavior:
The delegating role metadata is kept up to date with the latest delegation keys

[lukpueh]

Wow, this is a great find. Thanks, @sechkova!!

I just dug through repo tool and repo lib to see why and how this works with root-to-top-level-role delegations, as shown in the Tutorial:

>>> repository.targets.add_verification_key(import_rsa_publickey_from_file('targets_key.pub'))
>>> repository.snapshot.add_verification_key(import_rsa_publickey_from_file('snapshot_key.pub'))
>>> repository.timestamp.add_verification_key(import_rsa_publickey_from_file('timestamp_key.pub'))

We use the same add_verification_key function there as in your breaking example above, but the keys do end up in root metadata...

The secret is that repository_lib.generate_root_metadata (which is called in the course of writeall) iterates over all top-level roles in roledb and adds the keys to the root metadata:

https://github.com/theupdateframework/tuf/blob/a4b52e7e0de6d3056f8aa7ed97f40686dd7bf2c9/tuf/repository_lib.py#L1085-L1097

As a quick-and-dirty fix we could patch repository_lib.generate_targets_metadata to do something similar.

In the course of a rewrite that enhances the representation of the delegation graph, we should come up with a less roundabout way. What do you think?

[sechkova]

Totally agree with this analysis. As for the fix, I see two possibilities:

1. Patch repository_lib.generate_targets_metadata to follow a similar logic of repository_lib.generate_root_metadata - a potential problem here is _delegated hashed bins_. If we iterate roledb to extract information about each bin this may bring back the recently fixed performance issues #1012. Correct me if I'm wrong that hashed bins may often use the same key for all bins which would mean an update of one key is an update of each bin ...
2. Update the delegating role in roledb after the delegated role's attributes (keys, threshold) are updated - this leads to the discussions in #1038 about the problems in the current implementation related to delegations hierarchy.

Maybe @lukpueh @joshuagl, you can give some hints on option 1, since you were involved in fixing the performance issue :)

[joshuagl]

Iterating roledb shouldn't cause major performance regressions, it's the many calls to deepcopy when _modifying_ roledb that cause the performance hit (see #1005). Because the proposed change here is just reading from roledb, not updating it, seems like it should be OK.

1005 includes a sample script for measuring the performance of delegate_hashed_bins(). Perhaps we could implement the proposed change in 1. and measure performance before merging?

[lukpueh]

Great observation, @sechkova! Assuming that we use the same signing key for all hashed bins and the deepcopies in "roledb" remain the bottleneck (see 1005), then I think we're better off with 1), which might look something like this:

# in generate_targets_metadata (simplified)
roleinfo = roledb.get_roleinfo(targets_role) # very expensive
for delegation in delegations_for_targets_role: # not so expensive
  if has_new_keys(delegation):
    add_keys_to_roleinfo()
roledb.update_roleinfo(roleinfo) # very expensive

# ... add fileinfo and write delegating role

OTOH, in 2) we'll have an additional read/write cycle for each hashed bin, e.g:

def add_verification_key(self, new_key): # (simplified)
  # ...
  # ...
  roleinfo = roledb.get_roleinfo(self.get_delegating_role())
  add_keys_to_role_info()
  roledb.update_roleinfo(role_info)

for hashed_bin_name in hashed_bin_names: # eg. 16k iterations (very expensive)
  repository.targets(hashed_bin_name).add_verification_key(new_key)

Does this make sense? Please let me know what you think.

[lukpueh]

Oh, didn't see that you commented before me, @joshuagl. But it seems like we came to the same conclusion. :)

[sechkova]

Now I see it, same or most likely _bigger_ overhead plus the additional complications in 2) :eyes:

Thank you both, let's go for 1) and I will share what are the performance results using the script @joshuagl pointed.

[sechkova]

It is worth mentioning that the approach we agreed upon here (collecting and updating the delegations metadata during repository_lib.generate_targets_metadata) is also affected by #574.
After loading the repository the delegated roles' 'keyids' and 'threshold' are lost.

[joshuagl]

Resolved in #1074