specification
specification copied to clipboard
theupdateframework
Rollback attacks and fast forward recovery
This is my attempted takeover of #86. Based on discussion in that pr, I decided to explicitly recommend that fast forward attack recovery for delegated targets roles requires replacement of snapshot keys. Specifically this pr:
- Removes redundant rollback protection by leaving #65 in place and removes the redundant rollback check for delegated targets.
- Adds a note about fast forward attack recovery for delegated targets.
- Includes related clarifications from #72, #74, and #85 rebased for the new specification format.
It might be worth adding an ADR/other documentation about the possible methods for fast forward attack recovery and why this one was chosen.
cc @lukpueh @joshuagl @trishankatdatadog
Thank you for working on this Marina! FYI I'm planning to review this early next week.
(I'll squash these last few commits once we finalize)
Possibly better to do it now, as squash & force push will discard any approvals.
Possibly better to do it now, as squash & force push will discard any approvals.
Fair enough, it's either discard the approvals or discard the comment history :). I'll go ahead and fix it now
The whole preorder DFS is really not defined accurately. I can help to edit the text, but this code might help in the meantime.
The whole preorder DFS is really not defined accurately. I can help to edit the text, but this code might help in the meantime.
Which part? This pr just adds the snapshot and hash checks for delegated targets
Which part? This pr just adds the snapshot and hash checks for delegated targets
Yeah, maybe best done in another PR, but if you read the whole thing, you can see it has some work to do.
Yeah, maybe best done in another PR, but if you read the whole thing, you can see it has some work to do.
I think I see what you mean. I'll move the check added in this pr to after the section about multi-role delegations, because these checks should be done for each role in the multi-role delegation. There might be some better clarifications to the section as a whole, but I'll leave that to a separate pr to avoid too much scope creep here.
Overall LGTM pending resolution of Joshua's comments. Thanks, Marina!
Thanks for the reviews @joshuagl and @trishankatdatadog! I added a couple of commits to address your comments.
This language is still vague:
If a threshold of the <ROLE> keys have been removed in the new trusted root metadata compared to the previous trusted root metadata...
Do we mean no combination of the old threshold of the old <ROLE> keys are in the new root metadata?
Cc @hosseinsia
This language is still vague:
If a threshold of the keys have been removed in the new trusted root metadata compared to the previous trusted root metadata...
Do we mean no combination of the old threshold of the old keys have been removed in the new root metadata?
Cc @hosseinsia
Yes, does "If a threshold of keys from the previous trusted root metadata have been removed in the new trusted root metadata..." make this more clear?
Yes, does "If a threshold of keys from the previous trusted root metadata have been removed in the new trusted root metadata..." make this more clear?
No, I think it means "...if any previous threshold of previous timestamp/snapshot/targets keys from the previous trusted root metadata have been removed in the new trusted root metadata..."
Anyone disagree?
let's use an example: (1) If the target role keys are [a, b, c, d] and threshold is 2 in v1 and the new keys are [b, c, d, e] then no need to remove targets.json because only one key is being revoked (for being compromised) and an attacker could not have run the fast-forward attack.
(2) If the target role keys are [a, b, c, d] and threshold is 2 in v1 and the new keys are [c, d, e] then we have to remove targets.json
The reasoning is we assume revoked keys are compromised and and attacker might have launched a fast-forward attack on targets.json because he had enough keys.
Do you agree?
So I think both of you are talking about the same thing?
Do you agree?
So I think both of you are talking about the same thing?
I agree, @trishankatdatadog is this also what you were talking about? I think the biggest problem is making this clear in the wording of the spec. Maybe an example like the one above would help.
Do you agree? So I think both of you are talking about the same thing?
I agree, @trishankatdatadog is this also what you were talking about? I think the biggest problem is making this clear in the wording of the spec. Maybe an example like the one above would help.
I think we are all in the same page now, which goes back to this interpretation.
To remove any ambiguity, I propose we write how to compute whether the keys have been rotated by this interpretation, so there is no room for error.
We might as well need to clarify our assumptions about what we believe people should do when there is a key compromise for a role. Options: (1) Revoke all the keys for that role and create new ones. (2) Only revoke the keys that we think they are being compromised.
With the first assumption, we remove the related top-level metadata when all of the keys in the previous version are revoked. This is because any other type of change does not signal key compromise.
With the second assumption, we remove the related top-level metadata when the count of revoked keys is equal or bigger than the threshold of the previous version.
Which one should we assume?
(2) Only revoke the keys that we think they are being compromised.
We should assume that this is the only option people can take because they cannot afford to switch out the other keys.
ok then. Borrowing an example notations from Trishank to formulate the problem and answer:
Question: Let file A be signed by a threshold m_t of keys in k_t at time t And A be signed by a threshold $m_{t+n}$ of keys in $k_{t+n}$ at time t+n How do you tell whether the keys for $A_{t+n}$ have been rotated (i.e., not fully verifiable by any thresholds of keys for A_t) w/o opening $A_{t+n}$?
Note: The key rotation signals the need for removing metadata for the role.
Answer: Count the number of deleted keys , if it is bigger or equal to the the $m_t$ then the keys are rotated. In other words, if $$k_t - k_{t+n} >= m_t$$ is true then the key is rotated.
WDYT?
How do you tell whether the keys for $A_{t+n}$ have been rotated (i.e., not fully verifiable by any thresholds of keys for A_t) w/o opening $A_{t+n}$?
I would change this to:
How do you tell whether any threshold $m_t$ of $k_t$ have been removed in $k_{t+n}$?
Can someone explain why there need to be these rules about which metadata needs to be deleted in which rotation cases... or have I misunderstood something?
Precisely for the latter reason ;) Not everyone who reads the text has the same idea, which is a bad thing for building consistent and correct implementations.
Can someone explain why there need to be these rules about which metadata needs to be deleted in which rotation cases... or have I misunderstood something?
Precisely for the latter reason ;) Not everyone who reads the text has the same idea, which is a bad thing for building consistent and correct implementations.
What I mean is: I believe we only care whether metadata is signed by the current threshold of keys. It it is not, it should not be used as trusted metadata.
That seems vastly simpler than:
If a threshold of targets keys have been removed in the new trusted root metadata compared to the previous trusted root metadata ...
as there's no need to do any comparisons or try to figure out which keys have been removed: the only relevant question is is it signed by the current threshold of keys.
Possibly I don't understand some case you are discussing here but I have not identified a case that could not be solved by
- repository rotating keys when it needs to (e.g. to recover from ffwd attack)
- client only trusting metadata signed by current threshold of keys
What I mean is: I believe we only care whether metadata is signed by the current threshold of keys. It it is not, it should not be used as trusted metadata.
What do you mean by current? Would you please use the definitions here so we are all on the same page?
What I mean is: I believe we only care whether metadata is signed by the current threshold of keys. It it is not, it should not be used as trusted metadata.
What do you mean by current?
Whenever we load a delegator like root we get current keys/thresholds for the delegated metadata. If delegated metadata is not signed by these keys, it should not be trusted after this point. So in practice: if a new root is loaded with new timestamp keys, the local timestamp we might have on disk (or even loaded in memory) is not signed with those keys and cannot be trusted from now on.
What I mean is: I believe we only care whether metadata is signed by the current threshold of keys. It it is not, it should not be used as trusted metadata. What do you mean by current?
Whenever we load a delegator like root we get current keys/thresholds for the delegated metadata. If delegated metadata is not signed by these keys, it should not be trusted after this point. So in practice: if a new root is loaded with new timestamp keys, the local timestamp we might have on disk (or even loaded in memory) is not signed with those keys and cannot be trusted from now on.
So IIUC you mean if no m_t of k_t exists in m_{t+n} of k_{t+n}, then delete previous timestamp/snapshots/targets metadata.
This was also my interpretation, but Hossein pointed out that it's too strong. Look at his example here.
Just because a threshold of old keys have colluded and caused fast-forward attacks, doesn't mean you have the luxury to rotate all the rest that have not provably colluded.
So, the requirement should be less strict: if any (not all) old threshold of old keys have been rotated out, then take that as a signal of possible fast-forward attack, and delete the previous metadata.
So IIUC you mean if no m_t of k_t exists in m_{t+n} of k_{t+n}, then delete previous timestamp/snapshots/targets metadata.
I have to admit I don't understand what that means... but I'll look at the examples:
(1) If the target role keys are [a, b, c, d] and threshold is 2 in v1 and the new keys are [b, c, d, e] then no need to remove targets.json because only one key is being revoked (for being compromised) and an attacker could not have run the fast-forward attack.
If we have loaded root v2 and current targets keys are [b,c,d,e], we absolutely cannot trust targets.json if it was signed by only two keys and one of them was a, because at that point it is not signed by threshold of keys.
On the other hand if targets.json was signed by more than two keys (or one of them was not a), things are just fine.
(2) If the target role keys are [a, b, c, d] and threshold is 2 in v1 and the new keys are [c, d, e] then we have to remove targets.json
If targets.json was signed by at least c & d, then we can trust it and do not have to remove it :shrug:
From the context I finally think I understand what you are getting at: you think you can use the number of removed keys in a specific delegator update in comparison to the threshold of keys as a signal... I don't think you can as the keys might have been removed one by one in multiple metadata versions -- the possibility of a ffwd attack is still there even though only one key was removed at a time.
I don't quite understand why you want to remove targets.json if you suspect a ffwd attack may have happened? the real issue is in snapshot (where the targets.json version might be too big) and the issue may have been there for multiple snapshot versions already (so you can't just go back to a previous snapshot or something). I don't think there are other solutions to this problem than snapshot key rotation, and frankly it seems like a really good solution to me...
we absolutely cannot trust targets.json if it was signed by only two keys and one of them was a, because at that point it is not signed by threshold of keys.
The key problem is that we are looking at only the previous and current roots now to decide whether to delete previous timestamp/snapshot/targets metadata without looking at the current version of the latter, you see? So you cannot check based on what the actual signatures are. You can only decide based on comparing previous/current threshold of timestamp/snapshot/targets keys.