Version number scalability

[mnm678]

dstufft

Does this have to be an incrementing integer? My concern here is simply that an ever increasing integer can run into scalability problems, particularly if people don't take into account it's ever increasing nature (example, needing a different integer size in a database).

My second question is, do we have to guarantee these are never reused, or can they be reused after some time has passed?

My gut tells me we'd be better off using a uuid for a version number, or generating a random string of characters. The biggest downside I see to that is the extremely remote chance of generating the same version number twice-- but that can be solved by recording all possible versions ever used (which might be good to do anyways to return a 410 instead oof a 404).

[lukpueh]

Some thoughts:

I think for root metadata there is not much choice. It must have a deterministically incrementing version number, in order for the clients to re-trace the chain of root updates (see spec#61). The good news is, the root version is unlikely to increase fast. It only bumps on root expiration (we recommend once a year) and on key compromise.

For all other metadata, version numbers technically are not required. Snapshot can (collisions aside) unambiguously refer to targets or delegated targets by their hashes, same goes for timestamp when referring to snapshot. Timestamp actually already does this, and so does snapshot, albeit optionally (see spec:L718-L719 and spec:L996-L998). The hashes can also be used as metadata filename prefixes in consistent snapshots. And freshliness is provided by timestamp's expiration date and not by version numbers.

What was the original reasoning behind version numbers instead of hashes (or uuids)? To eliminate the chance of collisions? And/or because version numbers are less costly in terms of computation and size? If we generate hashes of the versioned metadata anyway, then the cost-argument does not hold true. And are collisions really a concern here?

It might work to re-use version numbers for non-root metadata, because we also allow to retire old non-root metadata. But we'd have to make sure the we only re-use version numbers from metadata that has been retired, which seems risky. And even then, we should cross-check with the metadata hash.

Related issues: theupdateframework/specification#28 theupdateframework/specification#40.

[trishankatdatadog]

I talked about this with @dstufft, and he said using strictly increasing version numbers is OK, as long as we have a plan for: (1) integer overflow, when necessary, and (2) super-old clients to update w/o running into accidental DoS "attacks"

[mnm678]

As far as the issues @trishankatdatadog mentioned, I think that the current system will work as long as non-root metadata is retired before the integer overflow occurs.

For root metadata, as long as the integer is sufficiently large and only updated once a year, an overflow will not occur for a long time.

For non-root metadata, we can suggest that the metadata is retired before integer reuse becomes a problem. As long as metadata is retired fairly regularly, the integer looping back to 0 should not be a problem. To ensure that this will happen, we can specify that less than 1/2 MAX_INT (for example) versions should exist at any time.

[lukpueh]

As pointed out in #72 (comment) re-using version numbers requires us to go against the spec, which doesn't seem desirable.

But do we really need to define an integer overflow strategy? Can't we just recommend to use a common unsigned 8-Byte BigInt, which is available in Postgres, which IIUC is used by warehouse.

With an upper bound of 2^63-1 we could create a new snapshot (i.e. bump the version) once per millisecond and still last for ~300 million years.

cc @trishankatdatadog, @dstufft, @mnm678, @JustinCappos

[JustinCappos]

Perhaps the issue is more if someone breaks in and generates a file with a MAXINT version number. How do you recover from this? I think using revocation of the snapshot key to reset the version number is one sensible way.

…

On Thu, Nov 21, 2019 at 10:07 AM lukpueh ***@***.***> wrote: As pointed out in #72 (comment) <#72 (comment)> re-using version numbers requires us to go against the spec, which doesn't seem desirable. But do we really need to define an integer overflow strategy? Can't we just recommend to use a common unsigned 8-Byte BigInt, which is available in Postgres, which IIUC is used by warehouse. With an upper bound of 2^63-1 we could create a new snapshot (i.e. bump the version) once per millisecond and still last for ~300 million years. cc @trishankatdatadog <https://github.com/trishankatdatadog>, @dstufft <https://github.com/dstufft>, @mnm678 <https://github.com/mnm678>, @JustinCappos <https://github.com/JustinCappos> — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#69?email_source=notifications&email_token=AAGROD47RDU7SREQC4KV64TQU2P4ZA5CNFSM4JNPMLF2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEE2RFFA#issuecomment-557126292>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAGROD5T24VJ7TWRHZB4RBDQU2P4ZANCNFSM4JNPMLFQ> .

[lukpueh]

What about all the parts of the spec that say a user must not update to a metadata file with a version number less than the one currently trusted (as I pointed out in #72 (comment))?

If we strictly adhere to that we won't be able to update to a reset number, e.g. after revoking a compromised key.

[lukpueh]

Oh. I just saw that the specification has a solution for exactly that. It prescribes to un-trust the previous snapshot and/or timestamp after their keys get rotated.

This means if an attacker bumps from say version 42 to MAXINT, and then the key gets rotated and published with metadata version 43, the client will still be able to update, because the metadata with version MAXINT no longer counts as previously trusted, and the update will be legitimately from 42 to 43.

Is that what you meant by resetting, @JustinCappos?

[JustinCappos]

Yes, that's what I was referring to.

…

On Thu, Nov 21, 2019 at 11:04 AM lukpueh ***@***.***> wrote: Oh. I just saw that the specification has a solution for exactly that <https://github.com/theupdateframework/specification/blame/4b82990afdc6c6d77aa9d43e0632f01bb9e7752c/tuf-spec.md#L1112-L1120>. It prescribes to un-trust the previous snapshot and/or timestamp after their keys get rotated. This means if an attacker bumps from say version 42 to MAXINT, and then the key gets rotated and published with metadata version 43, the client will still be able to update, because the metadata with version MAXINT no longer counts as previously trusted, and the update will be legitimately from 42 to 43. Is that what you meant by resetting, @JustinCappos <https://github.com/JustinCappos>? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#69?email_source=notifications&email_token=AAGROD6OHAVCAA62BZN6ORTQU2WPDA5CNFSM4JNPMLF2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEE2XRXI#issuecomment-557152477>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAGRODYTSWA3VVOMAUPD653QU2WPDANCNFSM4JNPMLFQ> .

[mnm678]

The solution in the specification linked by @lukpueh solves this issue for snapshot and timestamp. Can the same method be used for targets (bins and bin-n roles)?

[lukpueh]

If the version number increment of targets and delegated targets is only checked in snapshot (see 3.3.3 of the client workflow), then un-trusting snapshot will be enough to recover from a fast-forward attack on (delegated) targets.

However, 4.3 of the client workflow prescribes that new targets must have a higher version number than previous trusted targets. In that case, recovery from fast-forward is only possible, if old targets are also untrusted after a key rotation, like timestamp and snapshot (see 1.9 of the client workflow).

I think we should update either 4.3 or 1.9 in the spec.

[lukpueh]

At any rate, given that without a compromise versions are not likely to ever reach MAXINT, and even with a compromise tuf can update from MAXINT by discarding the compromised metadata, I don't think we need to re-use version numbers as is described in #72. Does everyone agree?

[JustinCappos]

Yes, I agree. We could require a key change at that point.

…

On Fri, Nov 22, 2019 at 8:09 AM lukpueh ***@***.***> wrote: At any rate, given that without a compromise versions are not likely to ever reach MAXINT, and even with a compromise tuf can update from MAXINT by discarding the compromised metadata, I don't think we need to re-use version numbers as is described in #72 <#72>. Does everyone agree? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#69?email_source=notifications&email_token=AAGRODY2RN3HT4I63FDMF5TQU7KYXA5CNFSM4JNPMLF2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEE5SSOI#issuecomment-557525305>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAGRODY3Q6B7SA7N246TMJDQU7KYXANCNFSM4JNPMLFQ> .

[lukpueh]

Good. I can submit a patch to the spec. @mnm678, can you update #72 with the gist of what we discussed here?

[mnm678]

Yes, I will update the pr later today.

[lukpueh]

Thanks for the update @mnm678. I left a few comments. I hope they are fair :)

Here's a PR to fix the issue I pointed out above:
--> theupdateframework/specification#65

Feel free to throw rocks at it.

[lukpueh]

Closing this issue via merged #72. Related discussion is continued in theupdateframework/specification#65.