adhammer_graph/
lib.rs

1//! Control-path graph (the BloodHound-style layer, in-process on petgraph).
2//!
3//! Nodes are security principals; a directed edge `A -> B` means "A holds a primitive
4//! that lets it control B". We seed Tier-0 (Domain/Enterprise Admins, DC computers,
5//! the domain head) and do a reverse traversal to find every principal that can reach it.
6//! Each edge carries a weight; the cheapest path is the attacker's likely route.
7
8use adhammer_core::sid::Sid;
9use adhammer_core::snapshot::Snapshot;
10use adhammer_core::AdObject;
11use petgraph::graph::{DiGraph, NodeIndex};
12use petgraph::visit::EdgeRef;
13use std::collections::HashMap;
14use windows_sddl::{rights, AccessMask, AceType};
15
16#[derive(Clone, Copy, Debug, PartialEq, Eq)]
17pub enum EdgeKind {
18    MemberOf,
19    Owns,
20    WriteDacl,
21    WriteOwner,
22    GenericAll,
23    GenericWrite,
24    ForceChangePassword,
25    AddMember,
26    AddKeyCredential, // Shadow Credentials
27    WriteRbcd,
28    DcsyncRight,
29}
30
31impl EdgeKind {
32    /// Lower = cheaper for the attacker = more dangerous.
33    pub fn weight(self) -> u32 {
34        match self {
35            EdgeKind::MemberOf => 0,
36            EdgeKind::GenericAll | EdgeKind::Owns => 1,
37            EdgeKind::WriteDacl | EdgeKind::WriteOwner => 1,
38            EdgeKind::ForceChangePassword | EdgeKind::AddKeyCredential => 1,
39            EdgeKind::AddMember => 1,
40            EdgeKind::WriteRbcd => 2,
41            EdgeKind::GenericWrite => 2,
42            EdgeKind::DcsyncRight => 0,
43        }
44    }
45}
46
47#[derive(Clone, Debug)]
48pub struct Node {
49    pub sid: Sid,
50    pub label: String,
51    pub tier0: bool,
52}
53
54pub struct ControlGraph {
55    g: DiGraph<Node, EdgeKind>,
56    by_sid: HashMap<String, NodeIndex>,
57}
58
59impl ControlGraph {
60    pub fn build(snap: &Snapshot) -> Self {
61        let mut cg = ControlGraph {
62            g: DiGraph::new(),
63            by_sid: HashMap::new(),
64        };
65
66        // 1. one node per principal that has a SID.
67        for o in &snap.objects {
68            if let Some(sid) = o.bin1("objectSid").and_then(Sid::from_bytes) {
69                let tier0 = is_tier0(snap, &sid);
70                cg.ensure(sid, label_of(o), tier0);
71            }
72        }
73
74        // 2. edges.
75        for o in &snap.objects {
76            let Some(dst) = o.bin1("objectSid").and_then(Sid::from_bytes) else {
77                continue;
78            };
79            cg.add_membership_edges(snap, o, &dst);
80            cg.add_acl_edges(snap, o, &dst);
81            cg.add_rbcd_edge(o, &dst);
82        }
83        cg
84    }
85
86    fn ensure(&mut self, sid: Sid, label: String, tier0: bool) -> NodeIndex {
87        if let Some(&ix) = self.by_sid.get(&sid.to_string()) {
88            if tier0 {
89                self.g[ix].tier0 = true;
90            }
91            return ix;
92        }
93        let key = sid.to_string();
94        let ix = self.g.add_node(Node { sid, label, tier0 });
95        self.by_sid.insert(key, ix);
96        ix
97    }
98
99    fn node_for(&mut self, sid: Sid) -> NodeIndex {
100        self.ensure(sid.clone(), sid.to_string(), false)
101    }
102
103    fn add_membership_edges(&mut self, snap: &Snapshot, o: &AdObject, self_sid: &Sid) {
104        // memberOf: this principal -> group. Edge means "member can act as group".
105        let me = self.node_for(self_sid.clone());
106        for group_dn in o.all("memberOf") {
107            if let Some(g) = snap
108                .by_dn(group_dn)
109                .and_then(|g| g.bin1("objectSid"))
110                .and_then(Sid::from_bytes)
111            {
112                let gx = self.node_for(g);
113                self.g.add_edge(me, gx, EdgeKind::MemberOf);
114            }
115        }
116    }
117
118    fn add_rbcd_edge(&mut self, o: &AdObject, self_sid: &Sid) {
119        // msDS-AllowedToActOnBehalfOfOtherIdentity is itself an SD; anyone in it can act on `self`.
120        if let Some(raw) = o.bin1("msDS-AllowedToActOnBehalfOfOtherIdentity") {
121            if let Ok(sd) = windows_sddl::parse(raw) {
122                let target = self.node_for(self_sid.clone());
123                for ace in sd
124                    .dacl
125                    .iter()
126                    .flat_map(|d| &d.aces)
127                    .filter(|a| a.is_allow())
128                {
129                    let src = self.node_for(ace.trustee.clone());
130                    self.g.add_edge(src, target, EdgeKind::WriteRbcd);
131                }
132            }
133        }
134    }
135
136    fn add_acl_edges(&mut self, _snap: &Snapshot, o: &AdObject, self_sid: &Sid) {
137        let Some(raw) = o.bin1("nTSecurityDescriptor") else {
138            return;
139        };
140        let Ok(sd) = windows_sddl::parse(raw) else {
141            return;
142        };
143        let target = self.node_for(self_sid.clone());
144
145        if let Some(owner) = sd.owner {
146            if !owner.is_well_known() {
147                let src = self.node_for(owner);
148                self.g.add_edge(src, target, EdgeKind::Owns);
149            }
150        }
151
152        for ace in sd.dacl.iter().flat_map(|d| &d.aces) {
153            if ace.ace_type == AceType::AccessDenied || ace.ace_type == AceType::AccessDeniedObject
154            {
155                continue; // model allows only; deny-aware pathing is future work
156            }
157            if ace.trustee.is_well_known() {
158                continue;
159            }
160            let kinds = classify(ace);
161            if kinds.is_empty() {
162                continue;
163            }
164            let src = self.node_for(ace.trustee.clone());
165            for k in kinds {
166                self.g.add_edge(src, target, k);
167            }
168        }
169    }
170
171    /// Every principal that can reach any Tier-0 node, with the cheapest path cost.
172    pub fn paths_to_tier0(&self) -> Vec<AttackPath> {
173        use petgraph::algo::dijkstra;
174        // Reverse the graph: shortest path *into* a tier0 node = attacker route.
175        let rev = petgraph::visit::Reversed(&self.g);
176        let mut out = Vec::new();
177        for tix in self.g.node_indices().filter(|&i| self.g[i].tier0) {
178            let dist = dijkstra(rev, tix, None, |e| *edge_weight(e.weight()));
179            for (src, cost) in dist {
180                if src == tix || self.g[src].tier0 {
181                    continue;
182                }
183                out.push(AttackPath {
184                    principal: self.g[src].label.clone(),
185                    principal_sid: self.g[src].sid.to_string(),
186                    target: self.g[tix].label.clone(),
187                    cost,
188                });
189            }
190        }
191        out.sort_by_key(|p| p.cost);
192        out
193    }
194
195    pub fn stats(&self) -> (usize, usize) {
196        (self.g.node_count(), self.g.edge_count())
197    }
198
199    /// Direct `kind` edges from a non-Tier-0 principal into a Tier-0 node.
200    pub fn direct_edges_to_tier0(&self, kind: EdgeKind) -> Vec<(String, String)> {
201        let mut out = Vec::new();
202        for e in self.g.edge_indices() {
203            if self.g[e] != kind {
204                continue;
205            }
206            let (src, dst) = self.g.edge_endpoints(e).unwrap();
207            if self.g[dst].tier0 && !self.g[src].tier0 {
208                out.push((self.g[src].label.clone(), self.g[dst].label.clone()));
209            }
210        }
211        out.sort();
212        out.dedup();
213        out
214    }
215}
216
217fn edge_weight(k: &EdgeKind) -> &u32 {
218    // dijkstra wants &measure; cache the small set of weights.
219    match k {
220        EdgeKind::MemberOf | EdgeKind::DcsyncRight => &0,
221        EdgeKind::WriteRbcd | EdgeKind::GenericWrite => &2,
222        _ => &1,
223    }
224}
225
226#[derive(Clone, Debug, serde::Serialize)]
227pub struct AttackPath {
228    pub principal: String,
229    pub principal_sid: String,
230    pub target: String,
231    pub cost: u32,
232}
233
234/// Turn one allow-ACE into the control primitives it grants.
235fn classify(ace: &windows_sddl::Ace) -> Vec<EdgeKind> {
236    let m = ace.mask;
237    let mut v = Vec::new();
238    if m.contains(AccessMask::GENERIC_ALL) {
239        v.push(EdgeKind::GenericAll);
240    }
241    if m.contains(AccessMask::WRITE_DAC) {
242        v.push(EdgeKind::WriteDacl);
243    }
244    if m.contains(AccessMask::WRITE_OWNER) {
245        v.push(EdgeKind::WriteOwner);
246    }
247    if m.contains(AccessMask::GENERIC_WRITE) {
248        v.push(EdgeKind::GenericWrite);
249    }
250    // Object-scoped rights: only count when the GUID matches a dangerous primitive,
251    // OR when no GUID is present (applies to all properties/rights).
252    let broad = ace.object_type.is_none();
253    if m.contains(AccessMask::CONTROL_ACCESS) {
254        match &ace.object_type {
255            Some(g) if rights::FORCE_CHANGE_PASSWORD.matches(g) => {
256                v.push(EdgeKind::ForceChangePassword)
257            }
258            Some(g) if rights::is_dcsync_right(g) => v.push(EdgeKind::DcsyncRight),
259            None => v.push(EdgeKind::GenericAll), // all extended rights
260            _ => {}
261        }
262    }
263    if m.contains(AccessMask::WRITE_PROP) {
264        match &ace.object_type {
265            Some(g) if rights::MEMBER_ATTR.matches(g) => v.push(EdgeKind::AddMember),
266            Some(g) if rights::KEY_CREDENTIAL_LINK.matches(g) => v.push(EdgeKind::AddKeyCredential),
267            Some(g) if rights::RBCD_ATTR.matches(g) => v.push(EdgeKind::WriteRbcd),
268            None if broad => v.push(EdgeKind::GenericWrite),
269            _ => {}
270        }
271    }
272    v
273}
274
275fn is_tier0(snap: &Snapshot, sid: &Sid) -> bool {
276    use adhammer_core::sid::rid;
277    let Some(rid) = sid.rid() else { return false };
278    // domain-relative privileged RIDs
279    if matches!(
280        rid,
281        rid::DOMAIN_ADMINS
282            | rid::ENTERPRISE_ADMINS
283            | rid::SCHEMA_ADMINS
284            | rid::ADMINISTRATOR
285            | rid::KRBTGT
286            | rid::DOMAIN_CONTROLLERS
287    ) {
288        // ensure it belongs to this domain (or is builtin admins)
289        if let Some(dsid) = &snap.domain.domain_sid {
290            let prefix = &sid.sub_authorities[..sid.sub_authorities.len().saturating_sub(1)];
291            if prefix == &dsid.sub_authorities[..] {
292                return true;
293            }
294        }
295    }
296    // BUILTIN\Administrators  S-1-5-32-544
297    sid.identifier_authority == 5
298        && sid.sub_authorities.first() == Some(&32)
299        && sid.rid() == Some(rid::ADMINISTRATORS_BUILTIN)
300}
301
302fn label_of(o: &AdObject) -> String {
303    o.one("sAMAccountName")
304        .map(String::from)
305        .unwrap_or_else(|| o.dn.clone())
306}
adhammer_graph/lib.rs

adhammer_graph/
lib.rs
