Sign previous timestamp hash into current timestamp

[endophage]

Submitting this on behalf of @cyli and the rest of the notary team to get it written down.

We should sign the previous timestamp into the current timestamp as an entry in the meta map. This provides 2 properties:

1. A crypto-verifiable history. A client can walk the linked list of timestamp files to traverse the published history of the repository. This is useful for auditing a repository and in the situation where old keys are compromised (even through brute force), makes it drastically more difficult to rewrite parts of history, as each version of a repository no longer exists in isolation to the versions on either side of it.
2. The need to only sign the immediate next root.json with both the old and new root keys. A client that is significantly out of date now has the ability to use the timestamp chain to walk backwards in history until the root.json (specifically, the root key, it does not need to be the exact same version of root.json) it holds comes back into view, then verify forwards. Bringing an old client up to date will be significantly slower, but this drastically reduces the key management problems of holding on to old root keys.

cc @mtrmac - we would greatly appreciate your input and thoughts on this, particularly item 2.

[mtrmac]

@endophage

1. This does not actually provide crypto-verifiable history: if the timestamp key, or the Notary server with the ability to sign data using the timestamp key, is compromised, the attacker can create an alternate timeline for an arbitrary timespan in the past, with no cryptographic way to tell whether the server-served or client-recorded timeline is the legitimate one. One could, usually, reasonably proceed under the assumption that the server’s timeline is the legitimate one, but then there is little benefit from having the server cryptographically sign it.

   That is not to say that such a link within the timestamp files would not be useful; but if you truly want a cryptographical assurance, the keys used to make a link in the past must no longer be available to an attacker in the future, e.g. the way https://www.schneier.com/cryptography/paperfiles/paper-auditlogs.pdf is creating single-use MAC keys.

   Secondarily, in some situations (e.g. the public Docker Hub) the Notary server is not necessarily 100% trusted (not under the control of the image author, no contractual relationship = no basis to sue for negligence), so it would be useful to have snapshot.json create similar history chain (signed using the client's snapshot key not available to the server) in addition to the timestamp chain (then two separate entities would have to be compromised to fake the timeline).

   OTOH it can very reasonably be argued that the server-managed timestamp keys are already a second-party trusted timestamping service and having a MAC system as a trusted timestamping mechanism for verifying the trusted timestamping service is a ridiculous overkill 😄; in that case we should probably just have a snapshot.json chain created client-side and keep using the existing server, signing timestamps and recording history as a second party attesting to the client-created chain.

   (Unfortunately with server-managed snapshot keys and the target delegation design, creating a client-managed event chain would be more difficult, AFAICS there is no single file on which we could hang the chain if the client is not managing snapshots.)

2. There are actually more options:

   1. Current implied: each root.json signed with all past keys. Time to rollover to latest O(1), storage space O((root.json updates)*(root key changes)).
   2. timestamp.json chain. Time to rollover to latest O(time since old key last used), storage space O((root.json updates)+O(time repository exists).
   3. snapshot.json chain. Time to rollover to latest O(target or root updates since old key last used), storage space O(target or root updates since old key last used).
   4. root.json chain, similar, but for root.json files only. Time to rollover to latest O(root.json updates), storage space O(root.json updates).

   The last option seems in theory much more attractive, although it would be extra code just to optimize root key rollover instead of reausing the timestamp chain which exists primarily for other reasons. Still, I imagine that eventually the storage of all past timestamps may become a burden and it will become desirable to start deleting old timestamp versions; if root key rollover relied on the timestamp chain, deleting even very old timestamps would not be possible.

(I haven’t done a deep or formal analysis, I may be missing something.)

[diogomonica]

@mtrmac, a few quick notes:

Our main objective is to have a non-malicious client be able to have the exact same view of the history of another non-malicious client. If we assume, for now, that the timestamp key hasn't been compromised, then this timestamp chain achieves that.

In particular, if we think of the situation where TUF data is being served via a malicious mirror, or HTTP mirror, or even the HTTPS connection to notary-server being MiTMed by an attacker, the timestamp key wouldn't have been compromised, and we're thus providing guarantees around the validity of the history (guarantees which we currently do not provide).

Additionally, I would also argue that we can have protections against timestamp key compromise. The definition of a secure log is in essence: "entries generated prior to the logging machine's compromise are impossible to undetectably modify or destroy". If we make the notary-clients always verify timestamps chains to the last known version on disk, this hash chain will provide that guarantee.

Now, obviously an attacker can continue moving the version numbers forward, and sign arbitrary new timestamps. However, as soon as the legitimate owner of the root key rotates the timestamp key, and republishes the repository, we're back in a known-good state, and all of the histories of all non-malicious clients will eventually converge to the exact same chain.

Obviously there is a pretty big change here: having clients download all the timestamps between the one on disk and the latest one being served, but if we wanted to do it, we could.

[endophage]

On the rewriting history aspect, I should have been more verbose. It protects against an old (timestamp) key that has been rotated out being used to rewrite parts of history for which that key was originally used. Currently, history is not protected from old keys that have been compromised and rotated out. Audits often need to take years of data into account (6 years max for an IRS audit) which means brute force key compromise may become a viable attack if the goal is to tamper with history, particularly as the signing algorithm being used a few years ago may be vulnerable to newly discovered attacks.

We considered the snapshot chain you mentioned, but determined that ultimately a snapshot does not represent a published version of a TUF repo, only a timestamp does that. As such, to list all versions, listing snapshots is insufficient because we would need back links to the timestamps to confirm a given snapshot was actually published, and adding those back links in a trusted way would require something additional to or outside of TUF.

Additionally, as of docker 1.10 and notary 0.2 we will also be supporting online snapshotting so users may choose to trust notary server for that too (it can be enabled by performing a key rotation with a new flag that indicates which roles should be signed by the server, currently only the snapshot is supported). This is so that users can easily make use of the delegation features of TUF without having to share the snapshot key with an arbitrary group of collaborators, or come online to manually snapshot their repo when collaborators push updates.

[mtrmac]

(Agreed re: protection against mirrors and the like. Again, timestamping the timestamp service seems a bit ridiculous to worry about.)

(On mitigating timestamp key compromise:)

The definition of a secure log is in essence: "entries generated prior to the logging machine's compromise are impossible to undetectably modify or destroy". If we make the notary-clients always verify timestamps chains to the last known version on disk, this hash chain will provide that guarantee.

No, that allows undetectable modification and destruction of entries prior to compromise (between the previous clients' download and the moment of compromise). For a popular repo with many thousands of clients the “total sum of state of all clients” will probably be able to detect when the compromise happened, but an individual user or an auditor trying to retrospectively figure out the state wouldn’t.

Now, obviously an attacker can continue moving the version numbers forward, and sign arbitrary new timestamps. However, as soon as the legitimate owner of the root key rotates the timestamp key, and republishes the repository, we're back in a known-good state, and all of the histories of all non-malicious clients will eventually converge to the exact same chain.

(BTW it is not obvious that this is always possible. The attacker can keep publishing new timestamps with increasing version numbers to keep the legitimate authors’ timestamps pointing to root.json updates seem obsolete, expired and therefore invalid. But then we always knew that the Notary server can DoS the author and all clients…)

[mtrmac]

It protects against an old (timestamp) key that has been rotated out being used to rewrite parts of history for which that key was originally used.

… assuming that the key has been rotated. Certainly useful, at least as long as it doesn’t introduce user-visible UI complexity.

We considered the snapshot chain you mentioned, but determined that ultimately a snapshot does not represent a published version of a TUF repo, only a timestamp does that.

Can we have both easily enough? That would prevent the timestamp server from pretending an update never happened, and the author from retroactively adding a never-published version.