Dependency confusion between internal registries and General

Seelengrab commented 3 years ago

A recent, novel supply chain attack on some package managers is also possible in certain Pkg/Registry configurations.

The gist of it is that some package managers, when given a package name, by default look in "internal" repos first, then also check the "public" repos and install whichever returns a higher version number. For this attack to be successful in Pkg, the attacker would also have to know the UUID of the internal package and register a package in General with both the same name and the same UUID, but a higher version number (e.g. 9001.0.0). Once registered, Pkg installs whichever version is higher, thereby allowing "shadowing" of the internal package with a malicious package.

A MWE can be found at https://github.com/DilumAluthge/MWE_multiple_registries_same_package_uuid.

The intention for all possible fixes is to preserve the ability to have multiple registries available to provide the same package. This should not allow attackers to intentionally register packages with the same name & UUID as another package in a different registry and mislead people into downloading their malicious package.

A non-breaking fix is for each private registry user who also uses General to use the 3 day waiting period to monitor for clashes in new package registrations to General. This should be automatable with some tooling, which comments on the PR to General and thus stops the automerge. As a precaution, private registry users may want to create new UUIDs for their internal packages and investigate how the UUID leaked in the first place.

Another non-breaking fix on a registry-per-registry basis would be to mirror & vet General manually, though this is somewhat high maintenance and thus unlikely to be useful in practice. This would also require some investigation into how the UUID leaked, should a mismatch be detected.

A possible long-term fix would involve a new shadowable entry in Package.toml, which would be opt-in and signal that the package is allowed to come from other registries as well. In this model, all installed registries that have the same combination of (name, UUID) would also need to have shadowable=true set for that package. If any registry doesn't have this set, we error.

This would be a breaking change, so our options are:

Do it in Julia 2.0.
Do it in Julia 1.x, but make a lot of Slack posts and Discourse posts informing people of the change, and make it easy for people (JC, Invenia, Beacon, etc) to make the changes needed. This would only affect local/internal registries that have shared a package with other registries (e.g. by open sourcing them to General). We should work closely with those who are known to have opensourced packages to make their transition as easy as possible.

Seelengrab commented 3 years ago

Many thanks to @ericphanson and @DilumAluthge for brain storming both short- and long-term fixes to this!

Seelengrab commented 3 years ago

Another complication is the case when two intentionally public registries (e.g. General and HolyLabRegistry) are able to shadow each other. This could be prevented by specifying which registries exactly are allowed to shadow the package (or rather, which packages are allowed to be trusted for a specific package). These lists would have to agree on all registries, otherwise we error.

I'm not 100% sure about this, because it requires all registries to be updated & maintained at roughly the same time. Kind of feels like a mismatch is bound to happen eventually here :/

ericphanson commented 3 years ago

I think they could just both put shadowable=true, and then opt-out of this safety check. I don't think that case is really an issue because both packages are controlled by the same maintainers.

I think the security issue is only when PkgX is in RegistryA but not RegistryB, and users of PkgX use both registries, and an adversary has the ability to register a package with the same name and UUID in RegistryB. I think for most practical purposes the only possible RegistryB is General, since it has publicly-available automerge and is installed by default on all Julia installations.

Therefore, if PkgX is already in General, there isn't really a security issue and one can just use the opt-out.

edit: deleted paragraph saying exactly the same thing as you @seelengrab about using a list of registries :). I don't think that's really needed at this point and adds to the burden like you said.

GunnarFarneback commented 3 years ago

The issue of shadowing packages from other public registries with a new package in General could also be mitigated by having auto-merge block registration of UUIDs that exist in public registries it has been configured to know about.

GunnarFarneback commented 3 years ago

A possible long-term fix would involve a new shadowable entry in Package.toml, which would be opt-in and signal that the package is allowed to come from other registries as well. In this model, all installed registries that have the same combination of (name, UUID) would also need to have shadowable=true set for that package. If any registry doesn't have this set, we error.

A non-breaking variation of this would be to only disallow merging if Registry.toml contains a field with that meaning, and have an option to allow merging on a package basis by a mergable entry in Package.toml. Possibly this could also specify exactly which registries to allow merging with. Thus General would not make use of this feature and be completely unaffected but you could set it in your private registry to make sure that your packages cannot be shadowed by General. And in case you do make some of your packages public, there's an override mechanism to allow those to be merged with General.

StefanKarpinski commented 3 years ago

I had thought through letting private registries publish a salted, hashed list of UUIDs that could be checked for collisions, but there's a bit of a problem with that: how do you distinguish the original author taking their own package open source from someone else trying to hijack their private package UUID? One answer could be that we examine the situation manually and make a judgement. Otherwise it seems like there needs to be a way of proving that you where the party that submitted the original salted and hashed entry, which gets into tricky crypto territory. Not impossible, but not simple.

Moreover, once package authors need to have proof that they "own" a UUID — in the above scenario, just to be able to take it public at some point — then why bother with the rest? If authors have a private key, they can just sign each release's hash and those signatures can be checked with the private key that's in the registry. If the public keys in different registries don't match, then the client can refuse to install.

You would want a way for authorities that you trust to sign versions with other keys so that your local admins can publish hotfix versions of public packages, but that can also be arranged.

GunnarFarneback commented 3 years ago

In the public version of this that is implemented in AutoMerge, the rule is to allow registration of a protected UUID if name and repo matches, on the assumption that you can't effectively hijack a package if you still have to point it to the original author's repo.

Wasn't the design for the hashed version similar in that respect?

StefanKarpinski commented 3 years ago

Right, but what if you need to change the URL? It's all nice in theory to think that URLs are forever but we know that in reality they are not. If a new hashed record is submitted, how do we decide whether it's ok to let it replace the old one?

GunnarFarneback commented 3 years ago

Fundamentally we have the same problem with repo changes of packages that have already been registered in General, except of course that there is more data to make a judgement call from. The easy way out, with its own problems, is to require someone who has protected a UUID in this way and want to open source the package, to do that with a new UUID.

StefanKarpinski commented 3 years ago

That's a bitter pill to swallow given that the current system has made it so smooth and easy for people to open source their private packages and keep using them without issues. And that's something we really want to encourage.

StefanKarpinski commented 3 years ago

We don't have to do something mechanical and rigid here: if an organization has previously published a hashed list of UUIDs, is taking something open source and wants to change the URL, we can always evaluated it using human judgement — the only thing that needs to be automatic is the rejection of attack attempts. But that approach does mean that we need to be able to identify what's going on with the hash lists in order to be able to make judgements about whether a URL change should be allowed or not.

Unrelated, but here's my high-level thinking about this problem. Fundamentally this is about who each person trusts to publish new versions of various packages. One generally trusts the original author, so when they make a new release, we're happy to upgrade to it. We also sometimes want to trust some other entity like our own organization's sysadmins to publish new versions of packages they don't maintain for hotfixes and the like. But that should be a conscious choice on the part of the user or a preconfigured policy on corporate machines.

cossio commented 2 years ago

A non-breaking fix is for each private registry user who also uses General to use the 3 day waiting period to monitor for clashes in new package registrations to General. This should be automatable with some tooling, which comments on the PR to General and thus stops the automerge.

Are there any tools available for automating these monitoring checks?

GunnarFarneback commented 2 years ago

Not that I've heard of. A simpler but less proactive approach is to periodically (e.g. with a scheduled job) check for UUID collisions between General and your own registry and raise an internal alarm if one is found.

If your registry is public you can make a PR to add your registry to https://github.com/JuliaRegistries/General/blob/736de1456b8ce65a24ed0003835d370f06451f13/.github/workflows/automerge.yml#L84 so that collisions are stopped by AutoMerge. I'm not sure if that's documented somewhere.

cossio commented 2 years ago

What if we have a list of "trusted" / "untrusted" registries for each package?

When a package is installed for the first time, it's registry of origin (call it registry A) is added as trusted and updates coming from this registry can proceed automatically.

If a new version of this package shows up in another registry (B), Pkg prompts the user what to do. If the user selects to upgrade from B, then registry B is also added as trusted for this package. After that the behavior of Pkg can be the current one regarding the rules for when two registries contain the same package. However, if the user selects not to "trust" the new version in B, then Pkg adds B as untrusted for this package, and does not consider updates coming from B for this package anymore, only updating the package if new versions appear in A.

Could something like this work?

ericphanson commented 2 years ago

I think a package “should” have only one trusted group allowed to issue versions (org/committer/company/whatever), so if there’s any “untrusted” versions showing up in a registry that’s a big security issue that should be resolved at the registry level, by yanking those versions and investigating, not by someone’s client just ignoring them. I think some kind of alerting thing is good but I think the way we act on that alert shouldn’t be “ok for this particular user, they don’t want these versions”.

StefanKarpinski commented 2 years ago

I think there's two things you need here:

Allow a package to declare that certain registries are trusted for it.
Allow a user to declare that certain registries are trusted for them.

Why do you need both of these? The first is what has already been suggested, and it prevents someone injecting an untrusted version of a package in some other registry, e.g. a malicious version of a private package in the general public registry.

So why do you need the other? Because it's useful for private registries to be able to release hot-fixes or modified versions of packages in other registries, but they need to trust those registries to do this for them.

There's a question of how to bootstrap these. The first registry that someone gets a package appears in can be implicitly trusted for it—otherwise we'd need to manually start the trust list somewhere. If a new trust declaration appears in a trusted registry, that can be trusted as well. That would allow transferring a package from one registry to another by adding the destination registry to the trust list and then doing the transfer. I think that not having an explicit trust list for a package in a registry should probably be equivalent to a trust list containing only that registry. So you could do a package transfer like this:

Initially RegistryA has an entry for PkgX with no explicit trust list, which means only RegistryA is trusted. RegistryB has no entry for PkgX.
Add an explicit trust = [RegistryA, RegistryB] entry in the Package.toml file for RegistryA (these are registry UUIDs).
Copy the PkgX directory from RegistryA to RegistryB. Now new versions from either registry will be trusted.
Delete the PkgX directory from RegistryA.
Delete the trust = [RegistryA, RegistryB] entry in PkgX/Package.toml from RegistryB, leaving only RegistryA in the implicit trust list for PkgX.

If you want two registries to both be allowed to publish versions of a package, you can just leave both packages in the middle state (step 3) indefinitely. This could be expanded to any number of registries.

Allowing users to declare that they trust certain registries to release versions of packages is the other design question here. We could potentially prompt for that if a new version of a package appears in a registry that isn't in the official trust list for a package. This could look like this:

PrivateRegistry has a new version of PkgX but isn't an officially trusted registry for PkgX. This could be an attack. Do you want to trust releases of versions from PrivateRegistry?
 [N] No: I do not trust PrivateRegistry to make unofficial releases
 [y] Yes: trust releases of PkgX from PrivateRegistry
 [a] All: trust releases of all packages from PrivateRegistry

This information could be saved in the PrivateRegistry.toml file in ~/.julia/registries as something like this:

git-tree-sha1 = "666dd7dc07e7949324d20591cde13de3b45ee1a8"
uuid = "20e4b06f-4c3f-4406-9bab-e758a9cb7e70"
path = "PrivateRegistry"
trust = true

Or for a specific list of packages for which the registry is trusted:

git-tree-sha1 = "666dd7dc07e7949324d20591cde13de3b45ee1a8"
uuid = "20e4b06f-4c3f-4406-9bab-e758a9cb7e70"
path = "PrivateRegistry"

[trust]
87703c6c-5a47-4a8b-8c61-6f07ed343807 = "PkgX"

The only other feature I can think of here would be allowing some registries to be trusted but only to provide new releases of packages from some other specific registries. But I'm not sure that's actually a useful feature: trust is pretty much all or nothing here. When you have trust = true in a registry's file, there's no reason not to trust it with everything. I'm not even entirely convinced that have a trust list for specific packages is useful. Why would you trust a registry to make unofficial releases of some packages but not others?

StefanKarpinski commented 2 years ago

Some care needs to be taken about the situation where different registries disagree about the set of trusted registries for a package is. For example, what happens when two already-trusted registries list different sets of trusted registries for a package? My gut says that we should take the intersection. But scenarios like the registry transfer one need to be thought through carefully to make sure they're possible. There's also the case where a trusted registry says another registry is trusted for a package, but the other registry doesn't yet have any versions of that package.

StefanKarpinski commented 2 years ago

It occurs to me that we need to keep a "trust database" somewhere anyway, and we could record the flag for "trust this registry to make unofficial releases" flag there as well instead of in the TOML file for the registry (which gets rewritten regularly).

Seelengrab commented 2 years ago

It feels like this discussion is starting to circle back to code signing, trust graphs (PGP/GPG?), CAs and all that entails. We should be careful not to reinvent a bad wheel here and maybe consult someone with professional expertise in establishing trust, signatures and so on. Especially your comment about a "trust database" makes me think of lots of prior art that already does that in various domains.

It may also be beneficial to tie this in with (possibly future) binary julia artifacts, to link them reproducibly to a given commit/version that artifact got built from.

cossio commented 2 years ago

Why not just ask the user whenever a package is present in more than one registry, which one to use? That is, for each package detected to be present in more than two registries, Pkg will maintain locally a list of the registries it trusts for that package, which are manually approved by the user.

StefanKarpinski commented 2 years ago

@Seelengrab, it's not really—I didn't mention signatures or CAs at all 🙂. The "trust database" is literally just a place where you record which package UUIDs have been seen in which registries previously. There's no "trust graph" involved, it's strictly local information.

@cossio: Consider the package transfer scenario—how is the user supposed to know if this situation is safe or it's an attack? They're not actually in a position to know that.

Seelengrab commented 2 years ago

I know you didn't, it just feels like moving in that direction without actually taking the final leap of signing releases & managing which kinds of signatures are ok :) From what I can tell, the "trust database" approach has TOFU (Trust On First Use) problems just like connecting to an SSH server for the first time or receiving a PGP encrypted email from an unknown sender. Just that it's about "well should I trust this Registry with this new UUID I haven't seen from it before?" instead of public key encryption, which is how I got to "why not have admins install a CA whose signatures are allowed from this registry" and hence code signing.

I am aware that it's not backwards compatible, but versions that don't support this can't participate anyway, as mentioned in the OP about whether it's breaking or not. :thinking:

StefanKarpinski commented 2 years ago

Implementing our own PKI is a bad idea, we're definitely not doing that.

StefanKarpinski commented 2 years ago

To elaborate on that: if you need a PKI, you're basically always better off leveraging an existing PKI that's actively maintained—the bigger and more active, the better. Which means you should, instead of building your own, use HTTPS. Which, in our case, means downloading things over HTTPS and trusting that the content of what you downloaded is valid. Rubbing signatures and public key encryption on things is fun and all, but you still need to find out which signatures to trust from somewhere.

Seelengrab commented 2 years ago

So you could do a package transfer like this

How would this work with versions that were published before the transfer? Can I still install them after RegistryA got removed (I presume not)?

Another thought - what's preventing me as a package author to have some malicious code running during __init__ or during precompilation that changes the trust entry for some package, install my custom malicious registry and publish package versions that way? I think as soon as we have a trust entry there, we need to ensure the integrity of that information. I just don't see how we can guarantee that without some form of PKI - the most famous form of "local only verification" is in the form of videogame tamper proofing or mobile phones, which is extremely often broken by having the private key for decryption/signature checking stored next to the stuff that's encrypted/signed (storing the keys in hardware like a TPM is what e.g. Apple is doing for their integrity checking on iPhones, but even that is broken into every few months).

StefanKarpinski commented 2 years ago

How would this work with versions that were published before the transfer?

If they're transferred to the other repository, then you can install them. The same version info can be published in multiple registries, it's all just unioned together.

Another thought - what's preventing me as a package author to have some malicious code running during __init__ or during precompilation that changes the trust entry for some package, install my custom malicious registry and publish package versions that way?

If the attacker is already running arbitrary code on your system, why do they need to do any of the other stuff?

GunnarFarneback commented 2 years ago

But I'm not sure that's actually a useful feature: trust is pretty much all or nothing here. When you have trust = true in a registry's file, there's no reason not to trust it with everything. I'm not even entirely convinced that have a trust list for specific packages is useful. Why would you trust a registry to make unofficial releases of some packages but not others?

I'm not sure I'm following here. The scenario that is of primary interest to me is having General plus a company internal registry. I want to merge the registry information in exactly two cases:

Private packages have been open sourced and new versions are registered in General.
Private versions of packages from General are published in the internal registry.

In both cases I want the company registry to dictate whether it is allowed, on a package per package basis, to merge versions with General and not leave that to the individual users, who in a majority of cases won't have any idea. If any UUID appears in both the company registry and in General, which hasn't been explicitly whitelisted, I want Pkg to refuse merging and preferably be noisy enough that the situation is escalated within the company.

StefanKarpinski commented 2 years ago

You're describing a situation where you trust your company registry, so it would be a trusted registry.

If any UUID appears in both the company registry and in General, which hasn't been explicitly whitelisted, I want Pkg to refuse merging and preferably be noisy enough that the situation is escalated within the company.

Whitelisted where? How to do the whitelisting is exactly the question. Let's say there are two registries: Internal and General; Internal is a trusted registry, General is not. If a package appears in General first and then a version is published in Internal, that version will be trusted because Internal is a trusted registry. If a package appears in Internal first and then a version of it appears in General, the question is whether that is an attack or an intentional publication of a previously internal package. How does one distinguish the two situations? Some indication that it's ok for the General registry to publish versions of the package has to appear in the Internal registry. That's what I'm proposing: you indicate that it's ok by putting trust = "23338594-aafe-5451-b93e-139f81909106" (the General UUID) or something like that in the Package.toml file for the package in question—in the Internal registry.

StefanKarpinski commented 2 years ago

In essence, what I'm saying is that you need two things:

A way to indicate that a registry (like Internal) is trusted and you can use any version it publishes.
A way for a registry that you trust for some package to delegate its ability to other registries.

The first one is pretty simple: it's a registry-level boolean flag. Details of the trust delegation feature remain a bit fuzzy, but that's what we need work out.

Consider transitive delegation, for example. If Internal delegates the ability to publish new versions of a package to General and General delegates to Other, is that allowed? As a rule of thumb, conservatism suggests no, but on the other hand, if someone doesn't know about Internal, then the delegation from General to Other would be fine, so it's a little weird if knowing about Internal prevents General from delegating to Other when it would work for people who don't know about Internal. So that suggests that transitive delegation should work.

Another question is whether delegated trust is persistent or not. If Internal delegates to General and then removes that delegation, do we keep trusting it or stop? What if the Internal registry is deleted or the package in question is deleted from Internal, which would leave the package only in General. In the former case where a delegation is removed, it should not persist. In the latter case, where the package is deleted from Internal entirely (say you want to transfer it to General fully), then that trust should persist. You could, in that situation ask the user to muck around with deleting registries or clearing their trust database, but it seems better if it works automatically.

I'll work on writing up a proposal.

GunnarFarneback commented 2 years ago

I guess we somewhat agree, cf https://github.com/JuliaLang/Pkg.jl/issues/2393#issuecomment-777286926. The way I see it, General should say that it is fine with any merges (at the registry level) and the company registry should say on a registry level that merges are not allowed, unless respective package specifies that they may be be merged with specified registries. Pkg should require that all involved registries allow the merge.

I'm not really seeing the point or value of the temporal ordering. Possibly because I'm not understanding this delegation stuff in the first place.

GunnarFarneback commented 2 years ago

If a package appears in Internal first and then a version of it appears in General

How do you determine the ordering of these events? If you do it client side, would an old installation (which can see the new version arrive) handle it differently from a new installation (which can only see that there are some existing versions)? Alternatively, if you add time stamps in the registries, what would stop a malignant registry from forging its time stamps?

Update: I realize that I might have misunderstood and that the ordering strictly refers to the version numbers.

StefanKarpinski commented 2 years ago

Yes, what I was thinking was that the client would remember where it saw each UUID first. However, that does require a client-side database, which it would be better to avoid. If I'm understanding where you're coming from, you'd prefer to avoid that and base everything on what's in registries, which I agree would be better if it can cover all the use cases.

StefanKarpinski commented 2 years ago

My first observation about the "stateless" approach is this: just marking a package as "mergeable" isn't sufficient since it opens up any package that's marked that way to confusion attacks from another registry. Example: you need to share a package between two private registries so you mark it as "mergeable"; now that package is susceptible to dependency confusion attacks from General.

So let's consider the variation of the stateless approach where you explicitly list the UUIDs of registries that you want to allow merging with. Here are some of the scenarios we want to allow:

Package transfer between registries.
Publishing all versions of a package that was originally private.
Publishing some versions of a package that was originally private.
Hot-patching of a public package in a trusted registry.
Mirroring a package between multiple registries.

Initially, we can assume that registry updates happen instantaneously so that we can be sure that changes to two different registries appear on clients at the same time. With that assumption wholesale transfer becomes trivial: just move all the versions of a package from one registry to the other. Because of the instantaneous update assumption, there's never a point where it looks both registries have versions for the package.

Unfortunately instantaneous publishing isn't real: it takes a varying and significant amount of time for changes to registries to propagate to package servers. However, this observation helps us deal with that issue: if two registries publish the same set of versions for a package, then there's no danger of dependency confusion. This allows the following procedure for package transfer:

Stop publishing new versions of the package
Add all versions to the new registry
Let that propagate to pkg servers
Delete all versions from the old registry
Let that propagate to pkg servers
Resume publishing new versions of the package

That way the only states a client can see, assuming they pull both registries from servers at the same time, are all versions in one or both registries, which presents no danger. This same observation also allows us to mirror a package between multiple registries so long as all versions are mirrored.

The main problem that remains is situations where some versions of a package appear in multiple registriest and one registry includes a version of a package that does not appear in the others. For simplicity, let's just consider two registries. This is a situation that one needs to support for some of the scenarios, like "publishing some versions of a package that was originally private" and "hot-patching of a public package in a trusted registry". Depending on interpretation, these are the only two, and they represent the coordinated and uncoordinated versions of the problem.

The coordinated version is where you can modify both registries. This is the case where the "mergeable" approach works: each registry indicates that the package can be merged with the other registry, by putting something like mergeable = "7680a4ac-0009-40d6-ac35-827cc6355475" in the Package.toml file for the package.

The uncoordinate version is where you cannot modify one of the registries, but the one you can modify is a trusted registry. This is the scenario where you want to hot-patch a public package in a trusted (typically private) registry. In this case you will have hotfix versions in the private registry that don't appear in the public registry but the public registry doesn't know about your private registry and cannot be modified to have a mergeable entry. However, the private registry can be marked as trusted, e.g. by putting trust = true in the Private.toml file for the registry. We won't raise the alarm when a trusted registry has versions of a package that don't appear in other registries that include that package.

That arrangement for hotfixes seems ok, except that this is exactly what dependency confusion attack would look like: you have a trusted private registry with some versions of a package and then you have versions of the same package in an untrusted public registry. One option would be to include all the public versions in the private registry. That means none of the public versions can be an attack since they're all included in the trusted registry. However, this has publication delay issues: when a new version appears in the public registry, it will take some time to include it in the private registry, during which gap, it will look like an attack is taking place. Instead, I'd suggest that we allow the private, trusted registry to indicate that it trusts versions from the public registry: i.e. have mergeable = "23338594-aafe-5451-b93e-139f81909106" entry in the private Package.toml file but not in the public one (since the public one doesn't know about the private one).

And now you see that we've gotten to something that looks a lot like trust delegation 🙂. You can think of mergeable = "$uuid" appearing in two registries where each one has the UUID of the other as a mutual declaration of trust... which basically means "it's ok with me if this other registry has versions that I don't know about." In other words, it might be spelled trust = "$uuid" because it really means, "I trust versions of this package declared in this other registry." However, it's been a very positive exercise because I see now that we can do this without needing to keep any trust database or do anything stateful at all—i.e. no need to remember where we saw a package first.

GunnarFarneback commented 2 years ago

If I'm understanding where you're coming from, you'd prefer to avoid that and base everything on what's in registries, which I agree would be better if it can cover all the use cases.

Yes, that is exactly what I'm after.

Instead, I'd suggest that we allow the private, trusted registry to indicate that it trusts versions from the public registry: i.e. have mergeable = "23338594-aafe-5451-b93e-139f81909106" entry in the private Package.toml file but not in the public one (since the public one doesn't know about the private one).

This sounds like what I've been proposing so I believe we are converging.

StefanKarpinski commented 2 years ago

Here's my proposal.

Trust Records

There are three kinds of trust records:

User trusts a registry: a user can indicate that they trust all versions of all packages in a registry.
Registry trusts another registry: a registry can indicate that it trusts versions of all packages that are published in another registry.
Registry trusts another registry for a specific package: A registry can indicate that it trusts versions of a specific package that are published in another registry.

This information will be encoded in various TOML files:

In $Registry.toml as a top-level trusted = true flag;
In $Registry/Registry.toml as a top-level list of trusted registry UUIDs;
In the Package.toml file of a specific packages as a list of trusted registry UUIDs.

Trust Graph for a Package

Given a collection of installed registries and these trust records, for each package, P, we can derive the directed trust graph for that package. The nodes of the graph are all the registries that have a Package.toml file for P (registries that don't know about P are not included in its graph—this is important) and the directed edges are the following from each registry:

To every registry that the user has marked as fully trusted;
To every registry it has marked as trusted for all packages;
To every registry it has marked as trusted specifically for P.

Checking for Attacks

To check for dependency confusion attacks, we must verify two things for each package P:

That no registries make conflicting claims about the meaning of a version number—they all have to agree on the tree hash of every version number.
That for every version of P, there is a path in the trust graph for P to from every registry to some registry in which that version appears.

The first check is fairly uncontroversial: if two registries claim different meanings for the same version of a package, there's a problem and one of them may be trying to trick you into using an incorrect, potentially malicious version of the package.

The second check is the meat of the design: it establishes a chain of trust from each registry to each version of each package that it knows about. Another way to think about this, rather than in terms of transitive trust, is that each registry virtually includes all versions from other registries that it trusts. In this perspective, the condition we want to check is that all the registries that know about a package include identical sets of versions of it. This is somewhat intutive: if all the registries that know about a package agree on what the versions of that package are, then a dependency confusion attack is not possible. Of course, actually having all registries literally include all the versions of every package makes having different registries pointless. What the trust/inclusion mechanism allows is for registries to virtually include various versions in other registries, which preserves the usefulness of multiple registies while ensuring that they all agree on what the versions exist of packages that they know about.

Scenarios

In what follows, we'll walk through some scenarios to make sure that this actually prevents attacks and that it still allows various useful use cases of registries.

Dependency confusion attack

First, let's consider the scenario we are actually trying to defend against: someone tries a dependency confusion attack. Suppose an organization has an Internal package registry which includes a package, P, which does not exist in the General public registry. An attacker learns the UUID of P and introduces a malicious fake version of P into General. There are a few variations on this that we'll cover.

Case: Internal is not trusted by a user (can’t introduce hotfixes to external packages) and General doesn't know about Internal, so there are no trust edges—the trust graph for P is disconnected. The malicious version is only in General which isn't reachable from Internal, so the malicious version is correctly detected as an attack. From the inclusion perspective, the malicious version is included in General but not in Internal, which indicates an attack.

Case: Internal is trusted (i.e. can introduce hotfixes) so there is a trust edge from General → Internal; there are no other trust edges. Again, the malicious version is only in General which isn't reachable from Internal (the edge goes the other way), so the malicious version is correctly detected as an attack again.

Case: Suppose the attacker, in addition to a malicious version of P in General, also introduces a trust edge from General to Internal (which can be a trusted registry or not—it doesn't matter for this case). This situation produces the same trust graph as last time: an edge from General to Internal again, so the attack is caught. In order to prevent detection, the attack would need to introduce a trust edge in the other direction, from Internal to General. But if the attacker could modify the Internal registry, then they could directly introduce the malicious version into the Internal registry without needing to use a dependency confusion attack.

We can conclude that this proposal does actually prevent dependency confusion attacks. In the following scenarios we'll make sure that it still allows useful use cases that aren't attacks.

Package transfer between two untrusted registries

If we want to transfer a package from one registry to another, as described in my previous comment, we can stop publishing new versions of the package, copy the entire package directory to the new registry, delete the package from the old registry, let those changes propagate to package servers, and then resume publishing new versions. In this case the trust graph is disconnected—the registries don't trust each other. However, that's not a problem because there are only two states that are ever visible to an end user:

The package only appears in one registry, so its trust graph only has one node;
The package appears in both registries, but the same set of versions appear in both registries, so every version is reachable from both registries.

From the inclusion perspective, there's agreement on the set of versions in both cases: in the former because only one of the registries include P and it agrees with itself; in the latter because they two registries have identical sets of versions.

Hot-patching of a public package in a trusted registry

Suppose you have an urgent fix to a public package, P, and can't wait until a new version is published in General (maybe the maintainer is on vacation). A useful feature of Pkg's registry system is that a new version of the package, say v1.2.3-hotfix, can be registered in an internal registry. How does this work with this proposal? Making this work requires two things:

Users have to trust the Internal registry;
The Internal registry must indicate that General is trusted for package P.

The first change causes versions of any package published in Internal to be trusted, allowing it to make hotfixes of any package. The second change prevents versions of P in General from being mistaken for a dependency confusion attack, which they otherwise would look like if Internal doesn't include them all. (Internal could explicitly include all of the versions of P that are in General, but then any time a new one is released, it would look like an attack again until Internal is updated to include the new version.)

Note that Internal should not indicate that it trusts General for all packages, as that would open it up to dependency confusion attacks for internal packages!

Publishing versions of a package that was originally private

Suppose a package, P, originally starts out in an Internal registry, but the organization decides to publish it by adding some or all versions of the package to General. In order to signal that this isn't a dependency confusion attack, they need to indicate that Internal trusts versions of P that are published in General.

If they publish all versions of the package, then it doesn't matter if the Internal registry is trusted or not. If they only publish some versions and the Internal registry is not trusted by their users (why wouldn't it be though?), then the presence of private versions that aren't in General will look like a reverse dependency confusion attack. This would be a little unusual, since internal private registries should generally be trusted, but there are some options in such a situation:

We could have Pkg not error unless it's actually considering installing a version. Since the unpublished versions would be older in this case, there wouldn't be any problem. However, if someone did try to resolve some environment that needed an older internal-only version, it would raise an error, so that's not an ideal solution.
The organization can ask for a trust entry from General to Internal for this package. There's no reason we can't do this since it's their package. That means there would some private registry UUID in the General registry, which is weird but not fundamentally wrong. However, this would introduce a risk that an attacker could make a fake registry with that UUID and then convince someone to add it, and then if they try to use P the attacker could trick them into using a malicious version from the registry they installed. In general, I think we need to train people that adding registries is an act of trust and that they should only do it with caution, but this also suggests that this option isn't ideal.
The organization can split their Internal registry into InternalTrusted and InternalUntrusted. The unpublished versions of the published package go in the InternalTrusted registry. This is probably the best solution even though it's awkward. But again, why wouldn't you trust everything in your internal registry?

Ultimately, I don't think this is a real issue—internal registries should be trusted.

DilumAluthge commented 2 years ago

This information will be encoded in various TOML files:

In $Registry.toml as a top-level trusted = true flag;

How does this work for Git registries, or for Pkg server registries in which we uncompressed and extract the tarball. IIUC, the $Registryname.toml file only exists for Pkg server registries that we leave compressed.

StefanKarpinski commented 2 years ago

We can also create the TOML file for git cloned registries. Another option is to put the trusted = true flag in the Registry.toml file and prompt the user if they trust the registry or not when they install it if it's a trusted registry. In other words, make it the registry maintainers call whether it's trusted or not, but require the user to agree to that upon installation.

StefanKarpinski commented 2 years ago

I think that might make sense: if a registry is intended to be trusted, things are likely to break if someone installs it but doesn't treat it as trusted, e.g. it might contain hotfixes of public packages, which will then be treated as dependency confusion attacks. So having the trusted = true flag in the Registry.toml file but then prompting the user if they try to add it makes sense to me. That also means we'd need to check when a registry gets updated if some tries to slip that entry into the TOML file, and either prompt them at that point and roll back to the previous registry state? Or delete the registry entirely and require them to add it again?

Basically, adding a trusted registry is an act of trust since it has license to publish hotfixes of any package. Adding an untrusted registry is safe until you add a package from it. This mechanism prevents the untrusted registr from forging versions of packages in other registries. You should only install a trusted registry if you trust everyone who can add things to it; you can safely install an untrusted registry like General that potential attackers can register things in.

GunnarFarneback commented 2 years ago

In other words, make it the registry maintainers call whether it's trusted or not, but require the user to agree to that upon installation.

I have mixed feelings about the last part. On one hand I can see the scenario where someone makes some useful packages available in their own public registry, which they have set as trusted, then at a later time starts adding malignant packages (or by ignorance allow others to do so). In that case it's not good if the trusted status does not have to be confirmed by the user.

On the other hand I see the in-organization scenario where you want things to just work. Having your users be forced to confirm that they trust the internal registry is a pointless distraction and there is a risk that they answer the question incorrectly, likely causing more trouble down the road.

One possibility would be to skip the trustedness confirmation if the registry is installed from a package server. After all, if you connect to a package server under the control of an attacker, they can add new malignant versions to any package at will, regardless of trust flags.

StefanKarpinski commented 2 years ago

That's a good point: for any registry you get via a package server, you might as well trust whatever trust flag they set on it. For example, if you're using an private package server and it includes two registries: Internal and General (mirrored from the public General), then the operator would mark the Internal registry as trusted and the General registry as untrusted, to indicate that the end user can trust anything in the former, but should be wary of the latter.

GunnarFarneback commented 2 years ago

Another minor observation:

if all the registries that know about a package agree on what the versions of that package are, then a dependency confusion attack is not possible

A weaker version of this could be "if all the registries that know about a package agree on the package repo URL" but unfortunately you can't draw very strong conclusions from this unless you verify or have guarantees that all versions' tree hashes actually exist in the repo.

StefanKarpinski commented 1 year ago

We should really implement this. There's been a real dependency confusion attack on PyTorch: https://pytorch.org/blog/compromised-nightly-dependency/, https://medium.com/checkmarx-security/py-torch-a-leading-ml-framework-was-poisoned-with-malicious-dependency-e30f88242964.

Seelengrab commented 1 year ago

I just noticed that the MWE @DilumAluthge and I came up with in the initial post 404s now - I don't think I still have a reference to that, but it would have been good as a test example :/

DilumAluthge commented 1 year ago

😬

DilumAluthge commented 1 year ago

I must have deleted the repo.

DilumAluthge commented 1 year ago

It shouldn't be too hard to create the MWE. You just need to set up two registries that have the same package (with the same package name and same package UUID).

Seelengrab commented 1 year ago

That much is true, I just dread doing it again because the one we came up with back then was super self contained, cleaned up after itself and everything :sob:

Octogonapus commented 1 year ago

I built a tool we use for monitoring for dependency confusion attacks against our private registry and against public registries. We would be up for sharing more details in a call if there is interest.

cc @IanButterworth

cadojo commented 1 year ago

In Python, and Julia, there seems to be a lot of complications to support a use case that I've not yet seen used — an identical package hosted in two different locations, which are both equally valid to the user.

Rust takes the approach of specifying each dependency's registry if and only if the registry is not the standard crates.io registry. This requires users to specify all non-crates.io dependencies explicitly, but for private organizations that may give some peace of mind to developers anyway.

If a user wants to ditch General completely in favor of their own private mirror, maybe making their own mirror the default registry in Pkg could be sufficient here. In other words, we could use Rust's approach with one modification: specify each dependency's registry if and only if the registry is not the ~~standard~~ Pkg default registry.

All the text above are just some thoughts I've had. I am not a software supply chain / security / package management expert. I am interested in how this is going to be resolved in Python, so I've been keeping an eye on reported dependency confusion attacks in PyPI.

Octogonapus commented 1 year ago

I built a tool we use for monitoring for dependency confusion attacks against our private registry and against public registries. We would be up for sharing more details in a call if there is interest.

The tool has grown quite a bit and I've been running it since I posted this earlier message. I recently made it public: https://github.com/Octogonapus/RegistryScanner If you run a private registry, I would encourage you to also run this tool and configure it with all the registries you use.

JuliaLang / Pkg.jl