Graph theory to assess Active Directory : Smartest vs. Shortest Control Paths

This article introduces a more efficient way of leveraging graph theory within Bloodhound, to reveal control paths that pose the highest level of risks in Microsoft Active Directory environments. For this purpose, we propose to apply weights to edges using the Graph Data Science (GDS) library within Neo4j.

Bonus: all of this is already implemented in the latest release of AD Miner.

The general idea being that the shortest path is not necessarily the easiest one, much like when you have to drive from point A to B, as illustrated below :

Thinking in graphs when assessing Active Directory security

For those interested in Windows Active Directory security assessments, leveraging graph theory turns out to be a game changer. Indeed, this concept can reveal hidden control paths that may likely be missed out using more traditional techniques. Furthermore, this concept provides a unique opportunity to demonstrate, in a highly instructive and straightforward manner, how a flawed configuration can enable, e.g., unprivileged users to attain, domain administration privileges.

This concept was initially presented at the 2014 SSTIC conference but gained significant attention following the 2016 release of Bloodhound at Black Hat Arsenal.

The benefits of leveraging graph theory in risk management is best illustrated by this famous from John Lambert, VP Security at Microsoft:

Defenders think in lists. Attackers think in graphs. As long as this is true, attackers will win.

How Bloodhound computes paths

Basically, the Bloodhound interface, whether utilizing the legacy BH OSS or the current BH Community Edition, almost solely serves as a graph visualizer where the output of cypher queries are displayed.

Cypher queries (much like SQL queries) is the language used in graph databases to determine paths between nodes (e.g., Computers, Users, Groups, etc.) through a series of relations (e.g., "Member of", "Admin to", etc.).

Graph database engines like Neo4j feature built-in functions that can find the shortest path (i.e., the path with the fewest hops), among all conceivable combinations of possible paths.

As an example, the following cypher will query the shortest path from user Joe to Domain Admin user Admin-Jane, using a series of possible relations ("MemberOf", "AdminTo", etc.):

MATCH p=shortestPath((u:User{name:"Joe@DOM"})-[r:MemberOf|AdminTo|AddKeyCredentialLink|WriteProperty|GenericAll|GenericWrite|Owns|WriteDacl*1..]->(m:User{name:"Admin-Jane@DOM"})) 
return p        

As a result, Bloodhound will display a graph showing, if any actually exists, the shortest path - or, in fact, one of the shortest path - going from Joe to Admin-Jane.

This shortest control path does not turn out to guaranty access to Admin-Jane. Indeed, the ExecuteDCOM edge does not provide local admin privileges which are necessary to leverage the session of Bob on SRQ-SQL01. So, a local privilege escalation will be needed.

The very same same problem occurs at the next step when exploiting the SQLAdmin edge.

Shortest path but not necessarily the smartest

As mentioned earlier in the map going from Paris to the SSTIC conference in Rennes, the shortest path is not always the smartest option.

Further down the road, in an attempt to find lower hanging fruits, we could try to compute all possible paths with this slightly different query where the ShortestPath function is no longer used :

MATCH p=(u:User{name:"Joe@DOM"})-[r:MemberOf|AdminTo|AddKeyCredentialLink|WriteProperty|GenericAll|GenericWrite|Owns|WriteDacl*1..]->(m:User{name:"Admin-Jane@DOM"}) 
return p        

In our example, this would reveal the following combinations as a graph :

Finally, using our eyes and our advanced expertise, we immediately spot the path at the very bottom which, despite being a bit longer, proves to be way more trivial when it comes to exploiting it.

Indeed, Joe is member of nested groups that can add a public key to Admin-Jane. As such, Joe can perform a shadow credential attack and impersonate Admin-Jane.

This example demonstrates that seeking the shortest path can sometimes (often ?) be misleading.

Graphing all possible paths is time consuming and often results in graphs that are very difficult to navigate through. So, how can we solve that issue, preferably in an automated fashion ?

Graph Data Science (GDS) to the rescue

Neo4j allows for external plugins to be installed. APOC and GDS are a few examples of those. GDS notably brings a variant of the shortest path algorithm that can compute paths with the lowest cost, assuming that edges contain an attribute that sets said cost. This technique has been introduced notably by Riccardo Ancarani in this blog post.

In that fashion, we could define costs such as :

• MemberOf = 0
• CanRDP = 50
• ExecuteDCOM = 80

All this meaning that the number of hops no longer matter as we aim at finding the path with lower cost.

Before being able to use GDS, it must be added to your neo4j container. This can be easily achieved by adding the following environement variable to the neo4j section of you docker-compose.yaml file :

??? NEO4J_PLUGINS=["graph-data-science"]        

Another way of accomplishing this consist in using the Bloodhound-Automation project by Tanguy Boisset which will create a BHCE environment with GDS support. NB: you can also use this wonderful project to automate data ingestion.

Once GDS support has been added, you are required to create a graph projection (note that the very lenghty list of candidate edges has been replaced with $properties$ to make the query easier to read) :

CALL gds.graph.project.cypher('graph_objects_to_domain_admin', 'MATCH (n) RETURN id(n) AS id', 'MATCH (n)-[r:$properties$]->(m) RETURN id(m) as source, id(n) AS target, r.cost as cost', {validateRelationships: false})        

Finally, the following cypher will query paths with the lower cost:

MATCH (target:User{name:"Admin-jane@DOM"}) CALL gds.allShortestPaths.dijkstra.stream('graph_objects_to_domain_admin', {sourceNode: target, relationshipWeightProperty: 'cost', logProgress: false}) YIELD path WITH nodes(path)[-1] AS starting_node, path WHERE starting_node.name = "Joe@DOM" 
RETURN path as p        

Wrapping up

This method introduces a more efficient way of uncovering most risky attack paths.

If you want to see the benefits of the "smartest paths" technique without the hassle of setting up GDS and figuring the right cypher queries, I strongly recommend trying it directly in AD Miner where it has recently been implemented by Clément Teytaud .