Introduction
Almost all software created today has dependencies, meaning that the software created relies on other already developed software. To manage all these software dependencies many popular programming languages have package managers. Javascript has NPM, Python has PIP, Ruby has Gems, and the list goes on and on. This blog post goes over how graph theory was used to find insecure software dependencies in large projects.
Background
In June 2022, the maintainers of RubyGems (popular package manager for Ruby) made the announcement that multi-factor authentication (MFA) was going to be enabled for popular ruby packages. This meant that once a package crossed 180 million download threshold MFA would be enabled. The reasoning for this was that enabling MFA would make RubyGems ecosystem a lot more secure and would prevent against account takeover attacks.
Now suppose you were an attacker, and you wanted to penetrate a Ruby ecosystem. With MFA enabled going after a popular software packages would prove difficult. However, note that these popular software packages also have dependencies. What if some of these popular packages depended on some less popular packages? Since MFA isn’t enabled on these packages, if you were able to “hack” one of these less popular packages then you would be able to bypass MFA and still penetrate a large Ruby ecosystem.
Making a Dependency Graph
To determine if any of these insecure packages exist we can create a dependency graph. To make the graph we start with the popular popular packages with MFA enabled. We go over these packages and create a node for each one and their dependencies. To show a dependency we make an directed edge (We add a directed edge from node a to node b if package a depends on package b). Then we repeat this process for each node until there are no more dependencies (the process is recursive).
To make these insecure packages easier to spot we color popular packages gray, and insecure packages red. In the end we end up with a graph like this:
Link to full Picture: https://cdn.shopify.com/s/files/1/0779/4361/files/RubyGemsDependenciesGraph.png?v=1666203166&shpxid=f81a715e-F68D-4213-D43E-34BD208E12E8
Results
From the graph made we can determine which of the popular packages depend on insecure gems. To do that we use depth first search (a popular gem depends on a insecure gem if we can find a red node in it’s DFS tree).
Using that technique we find that out of the 112 popular gems, 24 of them depend on insecure gem. This tells us there is a small loophole to by MFA where an attacker can go after one of these less popular software packages.
Links
- https://shopify.engineering/relationships-between-ruby-top-100-packages-dependencies
- https://blog.rubygems.org/2022/06/13/making-packages-more-secure.html