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 adhammer_sddl::{rights, AccessMask, AceType};
12use petgraph::graph::{DiGraph, NodeIndex};
13use petgraph::visit::EdgeRef;
14use std::collections::HashMap;
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 { g: DiGraph::new(), by_sid: HashMap::new() };
62
63        // 1. one node per principal that has a SID.
64        for o in &snap.objects {
65            if let Some(sid) = o.bin1("objectSid").and_then(Sid::from_bytes) {
66                let tier0 = is_tier0(snap, &sid);
67                cg.ensure(sid, label_of(o), tier0);
68            }
69        }
70
71        // 2. edges.
72        for o in &snap.objects {
73            let Some(dst) = o.bin1("objectSid").and_then(Sid::from_bytes) else { continue };
74            cg.add_membership_edges(snap, o, &dst);
75            cg.add_acl_edges(snap, o, &dst);
76            cg.add_rbcd_edge(o, &dst);
77        }
78        cg
79    }
80
81    fn ensure(&mut self, sid: Sid, label: String, tier0: bool) -> NodeIndex {
82        if let Some(&ix) = self.by_sid.get(&sid.to_string()) {
83            if tier0 {
84                self.g[ix].tier0 = true;
85            }
86            return ix;
87        }
88        let key = sid.to_string();
89        let ix = self.g.add_node(Node { sid, label, tier0 });
90        self.by_sid.insert(key, ix);
91        ix
92    }
93
94    fn node_for(&mut self, sid: Sid) -> NodeIndex {
95        self.ensure(sid.clone(), sid.to_string(), false)
96    }
97
98    fn add_membership_edges(&mut self, snap: &Snapshot, o: &AdObject, self_sid: &Sid) {
99        // memberOf: this principal -> group. Edge means "member can act as group".
100        let me = self.node_for(self_sid.clone());
101        for group_dn in o.all("memberOf") {
102            if let Some(g) = snap.by_dn(group_dn).and_then(|g| g.bin1("objectSid")).and_then(Sid::from_bytes) {
103                let gx = self.node_for(g);
104                self.g.add_edge(me, gx, EdgeKind::MemberOf);
105            }
106        }
107    }
108
109    fn add_rbcd_edge(&mut self, o: &AdObject, self_sid: &Sid) {
110        // msDS-AllowedToActOnBehalfOfOtherIdentity is itself an SD; anyone in it can act on `self`.
111        if let Some(raw) = o.bin1("msDS-AllowedToActOnBehalfOfOtherIdentity") {
112            if let Ok(sd) = adhammer_sddl::parse(raw) {
113                let target = self.node_for(self_sid.clone());
114                for ace in sd.dacl.iter().flat_map(|d| &d.aces).filter(|a| a.is_allow()) {
115                    let src = self.node_for(ace.trustee.clone());
116                    self.g.add_edge(src, target, EdgeKind::WriteRbcd);
117                }
118            }
119        }
120    }
121
122    fn add_acl_edges(&mut self, _snap: &Snapshot, o: &AdObject, self_sid: &Sid) {
123        let Some(raw) = o.bin1("nTSecurityDescriptor") else { return };
124        let Ok(sd) = adhammer_sddl::parse(raw) else { return };
125        let target = self.node_for(self_sid.clone());
126
127        if let Some(owner) = sd.owner {
128            if !owner.is_well_known() {
129                let src = self.node_for(owner);
130                self.g.add_edge(src, target, EdgeKind::Owns);
131            }
132        }
133
134        for ace in sd.dacl.iter().flat_map(|d| &d.aces) {
135            if ace.ace_type == AceType::AccessDenied || ace.ace_type == AceType::AccessDeniedObject {
136                continue; // model allows only; deny-aware pathing is future work
137            }
138            if ace.trustee.is_well_known() {
139                continue;
140            }
141            let kinds = classify(ace);
142            if kinds.is_empty() {
143                continue;
144            }
145            let src = self.node_for(ace.trustee.clone());
146            for k in kinds {
147                self.g.add_edge(src, target, k);
148            }
149        }
150    }
151
152    /// Every principal that can reach any Tier-0 node, with the cheapest path cost.
153    pub fn paths_to_tier0(&self) -> Vec<AttackPath> {
154        use petgraph::algo::dijkstra;
155        // Reverse the graph: shortest path *into* a tier0 node = attacker route.
156        let rev = petgraph::visit::Reversed(&self.g);
157        let mut out = Vec::new();
158        for tix in self.g.node_indices().filter(|&i| self.g[i].tier0) {
159            let dist = dijkstra(rev, tix, None, |e| *edge_weight(e.weight()));
160            for (src, cost) in dist {
161                if src == tix || self.g[src].tier0 {
162                    continue;
163                }
164                out.push(AttackPath {
165                    principal: self.g[src].label.clone(),
166                    principal_sid: self.g[src].sid.to_string(),
167                    target: self.g[tix].label.clone(),
168                    cost,
169                });
170            }
171        }
172        out.sort_by_key(|p| p.cost);
173        out
174    }
175
176    pub fn stats(&self) -> (usize, usize) {
177        (self.g.node_count(), self.g.edge_count())
178    }
179}
180
181fn edge_weight(k: &EdgeKind) -> &u32 {
182    // dijkstra wants &measure; cache the small set of weights.
183    match k {
184        EdgeKind::MemberOf | EdgeKind::DcsyncRight => &0,
185        EdgeKind::WriteRbcd | EdgeKind::GenericWrite => &2,
186        _ => &1,
187    }
188}
189
190#[derive(Clone, Debug, serde::Serialize)]
191pub struct AttackPath {
192    pub principal: String,
193    pub principal_sid: String,
194    pub target: String,
195    pub cost: u32,
196}
197
198/// Turn one allow-ACE into the control primitives it grants.
199fn classify(ace: &adhammer_sddl::Ace) -> Vec<EdgeKind> {
200    let m = ace.mask;
201    let mut v = Vec::new();
202    if m.contains(AccessMask::GENERIC_ALL) {
203        v.push(EdgeKind::GenericAll);
204    }
205    if m.contains(AccessMask::WRITE_DAC) {
206        v.push(EdgeKind::WriteDacl);
207    }
208    if m.contains(AccessMask::WRITE_OWNER) {
209        v.push(EdgeKind::WriteOwner);
210    }
211    if m.contains(AccessMask::GENERIC_WRITE) {
212        v.push(EdgeKind::GenericWrite);
213    }
214    // Object-scoped rights: only count when the GUID matches a dangerous primitive,
215    // OR when no GUID is present (applies to all properties/rights).
216    let broad = ace.object_type.is_none();
217    if m.contains(AccessMask::CONTROL_ACCESS) {
218        match &ace.object_type {
219            Some(g) if rights::FORCE_CHANGE_PASSWORD.matches(g) => v.push(EdgeKind::ForceChangePassword),
220            Some(g) if rights::is_dcsync_right(g) => v.push(EdgeKind::DcsyncRight),
221            None => v.push(EdgeKind::GenericAll), // all extended rights
222            _ => {}
223        }
224    }
225    if m.contains(AccessMask::WRITE_PROP) {
226        match &ace.object_type {
227            Some(g) if rights::MEMBER_ATTR.matches(g) => v.push(EdgeKind::AddMember),
228            Some(g) if rights::KEY_CREDENTIAL_LINK.matches(g) => v.push(EdgeKind::AddKeyCredential),
229            Some(g) if rights::RBCD_ATTR.matches(g) => v.push(EdgeKind::WriteRbcd),
230            None if broad => v.push(EdgeKind::GenericWrite),
231            _ => {}
232        }
233    }
234    v
235}
236
237fn is_tier0(snap: &Snapshot, sid: &Sid) -> bool {
238    use adhammer_core::sid::rid;
239    let Some(rid) = sid.rid() else { return false };
240    // domain-relative privileged RIDs
241    if matches!(rid, rid::DOMAIN_ADMINS | rid::ENTERPRISE_ADMINS | rid::SCHEMA_ADMINS | rid::ADMINISTRATOR | rid::KRBTGT | rid::DOMAIN_CONTROLLERS) {
242        // ensure it belongs to this domain (or is builtin admins)
243        if let Some(dsid) = &snap.domain.domain_sid {
244            let prefix = &sid.sub_authorities[..sid.sub_authorities.len().saturating_sub(1)];
245            if prefix == &dsid.sub_authorities[..] {
246                return true;
247            }
248        }
249    }
250    // BUILTIN\Administrators  S-1-5-32-544
251    sid.identifier_authority == 5
252        && sid.sub_authorities.first() == Some(&32)
253        && sid.rid() == Some(rid::ADMINISTRATORS_BUILTIN)
254}
255
256fn label_of(o: &AdObject) -> String {
257    o.one("sAMAccountName").map(String::from).unwrap_or_else(|| o.dn.clone())
258}
adhammer_graph/lib.rs

adhammer_graph/
lib.rs
