Server Model and Update Races with Threshold Signing

[ecordell]

Although TUF necessarily uses a client-server model, it leaves the mechanism by which server-side metadata is updated largely unspecified. By this I mean things like adding the targets that clients will download, or revoking and rotating root role keys.

I imagine this was intentional: metadata is just data, so you can serve it with whatever software you like and control access to it with whatever method you like. PyPI can use OAuth and RubyGems can use HTTP Basic Auth and that has little bearing on TUF; controlling who has access to updating metadata should be a concern of the specific applications of TUF (which, after all, should have the concepts of users and access control already).

But there are some problems with the basics of "updating metadata" that I think need to be considered within TUF.

TUF implicitly has principals and access control because it uses asymmetric keys: if you have a particular private key then you can sign data with it, and if you don't, you can't.

I think the race is best described with an example: Suppose you have TUF metadata on a server, and a delegated target targets/django. targets/django has a threshold of 2 and lists 3 public keys: A, B, and C, which are held by Alice, Bob, and Carol respectively.

A new version of django (v2) is ready for publishing and needs new metadata signed for it. In the normal case, Alice signs metadata and sends it to the server - it doesn't meet the threshold of keys so this metadata is technically invalid. Bob fetches the partially signed metadata from the server and signs it as well, and pushes it back up. Now there is valid metadata for v2 of django.

Suppose instead Alice and Bob are working on competing visions of what v2 is - that is, the target file referenced in targets/django has a different hash. When Alice pushes up her partially signed metadata, the server accepts it because she is part of the django project and allowed to update the metadata, and because she signed it with a valid key (A). When Bob pushes up his alternate version of django v2, the server has a problem: he is also allowed to update the metadata and has a valid key (B) but the hashes don't match between metadata. Alice and Bob are in a race to publish metadata for v2 in this scenario.

The server could decide to accept the first valid metadata it sees, or it could decide to accept the most recent valid metadata it sees.

If it accepts the first metadata it sees, we have a problem: consider the case where Carol's key (C) is compromised - an attacker can continually upload valid, partially signed metadata so that Alice and Bob can never update django properly.

If it accepts the most recent metadata it sees, we have a similar problem if a key is compromised: an attacker can overwrite attempted valid updates.

In both cases there's a race, but the attacker always wins in a threshold scenario because Alice and Bob can't both sign the metadata faster than Carol's compromised key can (without some out-of-band communication).

The model that TUF seems to implicitly take, based on the reference implementation, is that there is some (human) gatekeeper for the metadata that will be able to resolve these issues. They can even handle collecting signatures out-of-band if necessary.

But this doesn't seem to align with the model of public package repositories where TUF has been applied, like PyPI, RubyGems, Hackage, or Docker. In these cases there are individual contributors uploading packages, with little to no intervention.

A couple of questions come from this:

• Should TUF include a model of the server to some degree to address this?
• Should TUF have a first-class concept of staged metadata (e.g. targets.staged.json) so that a compromised key/account can't partially sign and overwrite the canonical metadata?
• Is there a good solution to the race? (I think rate limiting would solve it, but interested if there are other solutions)

Interested to hear your thoughts! Thanks!

[JustinCappos]

One solution is to have the server accept partially signed metadata from
both Alice and Bob. Assuming a threshold of 2, Carol's choice of which one
to sign effectively resolves the issue. (The server can discard the
'losing' V2 at that point too.)

We can give an example to explain how to handle this, but we have hesitated
to mandate it in the spec. We are trying to leave it up to the repository
implementer how they handle these cases.

Does this make sense?

On Thu, Jul 14, 2016 at 10:49 AM, Evan Cordell notifications@github.com
wrote:

Although TUF necessarily uses a client-server model, it leaves the
mechanism by which server-side metadata is updated largely unspecified. By
this I mean things like adding the targets that clients will download, or
revoking and rotating root role keys.

I imagine this was intentional: metadata is just data, so you can serve it
with whatever software you like and control access to it with whatever
method you like. PyPI can use OAuth and RubyGems can use HTTP Basic Auth
and that has little bearing on TUF; controlling who has access to updating
metadata should be a concern of the specific applications of TUF (which,
after all, should have the concepts of users and access control already).

But there are some problems with the basics of "updating metadata" that I
think need to be considered within TUF.

TUF implicitly has principles and access control because it uses
asymmetric keys: if you have a particular private key then you can sign
data with it, and if you don't, you can't.

I think the race is best described with an example: Suppose you have TUF
metadata on a server, and a delegated target targets/django.
targets/django has a threshold of 2 and lists 3 public keys: A, B, and C.
Alice has the private key for A and Bob has the private key for B. Carol
has the private key for C.

A new version of django (v2) is ready for publishing and needs new
metadata signed for it. In the normal case, Alice signs metadata and sends
it to the server - it doesn't meet the threshold of keys so this metadata
is technically invalid. Bob fetches the partially signed metadata from the
server and signs it as well, and pushes it back up. Now there is valid
metadata for v2 of django.

Suppose instead Alice and Bob are working on competing visions of what v2
is - that is, the target file referenced in targets/django has a
different hash. When Alice pushes up her partially signed metadata, the
server accepts it because she is part of the django project and allowed to
update the metadata, and because she signed it with a valid key (A). When
Bob pushes up his alternate version of django v2, the server has a problem:
he is also allowed to update the metadata and has a valid key (B) but the
hashes don't match between metadata. Alice and Bob are in a race to publish
metadata for v2 in this scenario.

The server could decide to accept the first valid metadata it sees, or it
could decide to accept the most recent valid metadata it sees.

If it accepts the first metadata it sees, we have a problem: consider the
case where Carol's key (C) is compromised - an attacker can continually
upload valid, partially signed metadata so that Alice and Bob can never
update django properly.

If it accepts the most recent metadata it sees, we have a similar problem
if a key is compromised: an attacker can overwrite attempted valid updates.

In both cases there's a race, but the attacker always wins in a threshold
scenario because Alice and Bob can't both sign the metadata faster than
Carol's compromised key can (without some out-of-band communication).

The model that TUF seems to implicitly take, based on the reference
implementation, is that there is some (human) gatekeeper for the metadata
that will be able to resolve these issues. They can even handle collecting
signatures out-of-band if necessary.

But this doesn't seem to align with the model of public package
repositories where TUF has been applied, like PyPI, RubyGems, Hackage, or
Docker. In these cases there are individual contributors uploading
packages, with little to no intervention.

A couple of questions come from this:

• Should TUF include a model of the server to some degree to address
  this?
• Is there a good solution to the race? (I think rate limiting would
  solve it, but interested if there are other solutions)

Interested to hear your thoughts! Thanks!

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
https://github.com/theupdateframework/tuf/issues/339, or mute the thread
https://github.com/notifications/unsubscribe/AA0XD43-bQ0TbUWEchLQ3A10sL3ul3Cvks5qVkyTgaJpZM4JMg4b
.

[ecordell]

One solution is to have the server accept partially signed metadata from
both Alice and Bob. Assuming a threshold of 2, Carol's choice of which one
to sign effectively resolves the issue. (The server can discard the
'losing' V2 at that point too.)

Wouldn't a scheme such as this allow the holder of a single compromised key to flood the server with partially signed data? How would Carol decide between 100 alternate v2s signed by Alice's compromised key?

[JustinCappos]

The way I see it, with Alice's key, you would only need to keep one. Alice
could replace her old versions...

Thanks,
Justin

On Thu, Jul 14, 2016 at 1:26 PM, Evan Cordell notifications@github.com
wrote:

One solution is to have the server accept partially signed metadata from
both Alice and Bob. Assuming a threshold of 2, Carol's choice of which one
to sign effectively resolves the issue. (The server can discard the
'losing' V2 at that point too.)

Wouldn't a scheme such as this allow the holder of a single compromised
key to flood the server with partially signed data? How would Carol decide
between 100 alternate v2s signed by Alice's compromised key?

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
https://github.com/theupdateframework/tuf/issues/339#issuecomment-232733791,
or mute the thread
https://github.com/notifications/unsubscribe/AA0XDyqsGROFBozjeb4aohKwGGFC7mxgks5qVnEogaJpZM4JMg4b
.

[ecordell]

That would work - I'm happy leaving it as an implementation detail, but since this is an issue anyone allowing public contributions would run into, should there at least be a note about this somewhere?

[JustinCappos]

I completely agree. We will include this as an example of how one might
implement this.

Let's do this before closing this issue...

On Thu, Jul 14, 2016 at 3:41 PM, Evan Cordell notifications@github.com
wrote:

That would work - I'm happy leaving it as an implementation detail, but
since this is an issue anyone allowing public contributions would run into,
should there at least be a note about this somewhere?

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
https://github.com/theupdateframework/tuf/issues/339#issuecomment-232770530,
or mute the thread
https://github.com/notifications/unsubscribe/AA0XD9_sTWC2s239wKoDj5yF9POY_I5Uks5qVpDtgaJpZM4JMg4b
.

[lukpueh]

The main tutorial describes how metadata is moved from the staging area to a live repository out-of-band see TUTORIAL.md#L551-L5570. We can revise together with #808.

[jku]

The issues described here are very real: the serverside "workflow" is not well defined (maybe it can't be) and there are many details that an implementation must handle to be a) compliant b) safe.

• Should TUF include a model of the server to some degree to address this?

Yes. The Repository Operations section is now a lot better than it was 6 years ago but it seems to still miss solid workflows for e.g. the developer upload case you talk about.

• Is there a good solution to the race?

I think in the end this is a repository implementation decision. TUF spec or some implementation manual could present a working model but different repositories might make different choices.

Finally, I think there's no actionable python-tuf issue here: we do plan to work on repository tooling in the near future but there's nothing available yet. Let's continue the spec discussion in the linked spec issue