Skip to main content

ms_gkdi/
gkdi.rs

1//! MS-GKDI: the Group Key Distribution structures and the L0/L1/L2 key-tree walk.
2//!
3//! A DPAPI-NG blob does not carry a key — it carries a *key identifier*: which KDS root key,
4//! and which (L0, L1, L2) node of that root's tree. A domain controller hands out a
5//! [`GroupKeyEnvelope`] for some node at or above the one you asked for; deriving downwards
6//! to the exact node is [`compute_l2_key`], and it is pure computation — no network.
7
8use crate::cursor::Cursor;
9use crate::kdf::{kdf, kds_service_label, HashAlg};
10use crate::{GkdiError, Result};
11
12/// `KDSK` — the magic in a key-identifier blob.
13pub const KEY_IDENTIFIER_MAGIC: u32 = 0x4B53_444B;
14/// `KDSK` — the magic in a group-key envelope.
15pub const ENVELOPE_MAGIC: u32 = 0x4B53_444B;
16/// The tree is 32-ary: L1 and L2 indices run 0..=31.
17pub const TREE_ARITY: i32 = 32;
18
19/// A 16-byte GUID in its on-wire (mixed-endian) form, kept as raw bytes because that is
20/// exactly what the KDF context wants.
21#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
22pub struct RootKeyId(pub [u8; 16]);
23
24impl RootKeyId {
25    pub fn from_bytes(b: &[u8]) -> Result<RootKeyId> {
26        Ok(RootKeyId(
27            b.get(..16)
28                .ok_or(GkdiError::Truncated("root key identifier"))?
29                .try_into()
30                .unwrap(),
31        ))
32    }
33}
34
35impl std::fmt::Display for RootKeyId {
36    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
37        let b = &self.0;
38        write!(
39            f,
40            "{:02x}{:02x}{:02x}{:02x}-{:02x}{:02x}-{:02x}{:02x}-{:02x}{:02x}-{}",
41            b[3],
42            b[2],
43            b[1],
44            b[0],
45            b[5],
46            b[4],
47            b[7],
48            b[6],
49            b[8],
50            b[9],
51            b[10..16]
52                .iter()
53                .map(|x| format!("{x:02x}"))
54                .collect::<String>()
55        )
56    }
57}
58
59/// `KDF_PARAMETERS` — names the hash the key tree is derived with.
60#[derive(Clone, Debug, PartialEq, Eq)]
61pub struct KdfParameters {
62    pub hash: HashAlg,
63}
64
65impl KdfParameters {
66    pub fn parse(b: &[u8]) -> Result<KdfParameters> {
67        let mut c = Cursor::new(b);
68        // Two fixed u32 headers, then the length of the NUL-terminated UTF-16LE name,
69        // then another fixed u32, then the name itself.
70        c.skip(8, "kdf parameters header")?;
71        let name_len = c.u32le("kdf hash name length")? as usize;
72        c.skip(4, "kdf parameters padding")?;
73        let raw = c.take(name_len, "kdf hash name")?;
74        Ok(KdfParameters {
75            hash: HashAlg::from_name(&utf16_lossy(raw))?,
76        })
77    }
78
79    pub fn to_bytes(&self) -> Vec<u8> {
80        let name: Vec<u8> = format!("{}\0", self.hash.name())
81            .encode_utf16()
82            .flat_map(u16::to_le_bytes)
83            .collect();
84        let mut out = Vec::with_capacity(20 + name.len());
85        out.extend_from_slice(&0u32.to_le_bytes());
86        out.extend_from_slice(&1u32.to_le_bytes());
87        out.extend_from_slice(&(name.len() as u32).to_le_bytes());
88        out.extend_from_slice(&0u32.to_le_bytes());
89        out.extend_from_slice(&name);
90        out
91    }
92}
93
94/// The `KEY_IDENTIFIER` carried in a protected blob: which root key and which tree node the
95/// content was encrypted for.
96#[derive(Clone, Debug, PartialEq, Eq)]
97pub struct KeyIdentifier {
98    pub version: u32,
99    pub flags: u32,
100    pub l0: i32,
101    pub l1: i32,
102    pub l2: i32,
103    pub root_key_id: RootKeyId,
104    pub kdf_algorithm: String,
105    pub kdf_parameters: Vec<u8>,
106    pub secret_algorithm: String,
107    pub secret_parameters: Vec<u8>,
108    pub private_key_length: u32,
109    pub public_key_length: u32,
110    pub domain_name: String,
111    pub forest_name: String,
112}
113
114impl KeyIdentifier {
115    /// `true` when the blob was protected with the public-key half of the node (the
116    /// key-agreement path) rather than the seed key directly.
117    pub fn is_public_key(&self) -> bool {
118        self.flags & 0x01 != 0
119    }
120
121    pub fn parse(b: &[u8]) -> Result<KeyIdentifier> {
122        let mut c = Cursor::new(b);
123        let version = c.u32le("version")?;
124        let magic = c.u32le("magic")?;
125        if magic != KEY_IDENTIFIER_MAGIC {
126            return Err(GkdiError::BadMagic {
127                what: "key identifier",
128                got: magic,
129            });
130        }
131        let flags = c.u32le("flags")?;
132        let l0 = c.i32le("l0 index")?;
133        let l1 = c.i32le("l1 index")?;
134        let l2 = c.i32le("l2 index")?;
135        let root_key_id = RootKeyId::from_bytes(c.take(16, "root key identifier")?)?;
136        let kdf_alg_len = c.u32le("kdf algorithm length")? as usize;
137        let kdf_param_len = c.u32le("kdf parameters length")? as usize;
138        let secret_alg_len = c.u32le("secret algorithm length")? as usize;
139        let secret_param_len = c.u32le("secret parameters length")? as usize;
140        let private_key_length = c.u32le("private key length")?;
141        let public_key_length = c.u32le("public key length")?;
142        let domain_len = c.u32le("domain name length")? as usize;
143        let forest_len = c.u32le("forest name length")? as usize;
144
145        let kdf_algorithm = utf16_lossy(c.take(kdf_alg_len, "kdf algorithm")?);
146        let kdf_parameters = c.take(kdf_param_len, "kdf parameters")?.to_vec();
147        let secret_algorithm = utf16_lossy(c.take(secret_alg_len, "secret algorithm")?);
148        let secret_parameters = c.take(secret_param_len, "secret parameters")?.to_vec();
149        let domain_name = utf16_lossy(c.take(domain_len, "domain name")?);
150        let forest_name = utf16_lossy(c.take(forest_len, "forest name")?);
151
152        Ok(KeyIdentifier {
153            version,
154            flags,
155            l0,
156            l1,
157            l2,
158            root_key_id,
159            kdf_algorithm,
160            kdf_parameters,
161            secret_algorithm,
162            secret_parameters,
163            private_key_length,
164            public_key_length,
165            domain_name,
166            forest_name,
167        })
168    }
169
170    pub fn to_bytes(&self) -> Vec<u8> {
171        let kdf_alg = utf16z(&self.kdf_algorithm);
172        let secret_alg = utf16z(&self.secret_algorithm);
173        let domain = utf16z(&self.domain_name);
174        let forest = utf16z(&self.forest_name);
175
176        let mut out = Vec::new();
177        out.extend_from_slice(&self.version.to_le_bytes());
178        out.extend_from_slice(&KEY_IDENTIFIER_MAGIC.to_le_bytes());
179        out.extend_from_slice(&self.flags.to_le_bytes());
180        out.extend_from_slice(&self.l0.to_le_bytes());
181        out.extend_from_slice(&self.l1.to_le_bytes());
182        out.extend_from_slice(&self.l2.to_le_bytes());
183        out.extend_from_slice(&self.root_key_id.0);
184        out.extend_from_slice(&(kdf_alg.len() as u32).to_le_bytes());
185        out.extend_from_slice(&(self.kdf_parameters.len() as u32).to_le_bytes());
186        out.extend_from_slice(&(secret_alg.len() as u32).to_le_bytes());
187        out.extend_from_slice(&(self.secret_parameters.len() as u32).to_le_bytes());
188        out.extend_from_slice(&self.private_key_length.to_le_bytes());
189        out.extend_from_slice(&self.public_key_length.to_le_bytes());
190        out.extend_from_slice(&(domain.len() as u32).to_le_bytes());
191        out.extend_from_slice(&(forest.len() as u32).to_le_bytes());
192        out.extend_from_slice(&kdf_alg);
193        out.extend_from_slice(&self.kdf_parameters);
194        out.extend_from_slice(&secret_alg);
195        out.extend_from_slice(&self.secret_parameters);
196        out.extend_from_slice(&domain);
197        out.extend_from_slice(&forest);
198        out
199    }
200
201    /// The hash the key tree for this blob is derived with.
202    pub fn hash(&self) -> Result<HashAlg> {
203        Ok(KdfParameters::parse(&self.kdf_parameters)?.hash)
204    }
205}
206
207/// `GROUP_KEY_ENVELOPE` — what `GetKey` returns: seed key material for one node of the tree,
208/// at or above the node you asked for.
209#[derive(Clone, Debug, PartialEq, Eq)]
210pub struct GroupKeyEnvelope {
211    pub version: u32,
212    pub flags: u32,
213    pub l0: i32,
214    pub l1: i32,
215    pub l2: i32,
216    pub root_key_id: RootKeyId,
217    pub kdf_algorithm: String,
218    pub kdf_parameters: Vec<u8>,
219    pub secret_algorithm: String,
220    pub secret_parameters: Vec<u8>,
221    pub private_key_length: u32,
222    pub public_key_length: u32,
223    pub domain_name: String,
224    pub forest_name: String,
225    pub l1_key: Vec<u8>,
226    pub l2_key: Vec<u8>,
227}
228
229impl GroupKeyEnvelope {
230    /// `true` if this envelope carries the public key rather than seed keys.
231    pub fn is_public_key(&self) -> bool {
232        self.flags & 0x02 != 0
233    }
234
235    pub fn hash(&self) -> Result<HashAlg> {
236        Ok(KdfParameters::parse(&self.kdf_parameters)?.hash)
237    }
238
239    pub fn parse(b: &[u8]) -> Result<GroupKeyEnvelope> {
240        let mut c = Cursor::new(b);
241        let version = c.u32le("version")?;
242        let magic = c.u32le("magic")?;
243        if magic != ENVELOPE_MAGIC {
244            return Err(GkdiError::BadMagic {
245                what: "group key envelope",
246                got: magic,
247            });
248        }
249        let flags = c.u32le("flags")?;
250        let l0 = c.i32le("l0 index")?;
251        let l1 = c.i32le("l1 index")?;
252        let l2 = c.i32le("l2 index")?;
253        let root_key_id = RootKeyId::from_bytes(c.take(16, "root key identifier")?)?;
254        let kdf_alg_len = c.u32le("kdf algorithm length")? as usize;
255        let kdf_param_len = c.u32le("kdf parameters length")? as usize;
256        let secret_alg_len = c.u32le("secret algorithm length")? as usize;
257        let secret_param_len = c.u32le("secret parameters length")? as usize;
258        let private_key_length = c.u32le("private key length")?;
259        let public_key_length = c.u32le("public key length")?;
260        let l1_key_len = c.u32le("l1 key length")? as usize;
261        let l2_key_len = c.u32le("l2 key length")? as usize;
262        let domain_len = c.u32le("domain name length")? as usize;
263        let forest_len = c.u32le("forest name length")? as usize;
264
265        let kdf_algorithm = utf16_lossy(c.take(kdf_alg_len, "kdf algorithm")?);
266        let kdf_parameters = c.take(kdf_param_len, "kdf parameters")?.to_vec();
267        let secret_algorithm = utf16_lossy(c.take(secret_alg_len, "secret algorithm")?);
268        let secret_parameters = c.take(secret_param_len, "secret parameters")?.to_vec();
269        let domain_name = utf16_lossy(c.take(domain_len, "domain name")?);
270        let forest_name = utf16_lossy(c.take(forest_len, "forest name")?);
271        let l1_key = c.take(l1_key_len, "l1 key")?.to_vec();
272        let l2_key = c.take(l2_key_len, "l2 key")?.to_vec();
273
274        Ok(GroupKeyEnvelope {
275            version,
276            flags,
277            l0,
278            l1,
279            l2,
280            root_key_id,
281            kdf_algorithm,
282            kdf_parameters,
283            secret_algorithm,
284            secret_parameters,
285            private_key_length,
286            public_key_length,
287            domain_name,
288            forest_name,
289            l1_key,
290            l2_key,
291        })
292    }
293}
294
295/// The KDF context for one tree node: root key GUID followed by the three indices.
296pub fn kdf_context(root: RootKeyId, l0: i32, l1: i32, l2: i32) -> Vec<u8> {
297    let mut ctx = Vec::with_capacity(28);
298    ctx.extend_from_slice(&root.0);
299    ctx.extend_from_slice(&l0.to_le_bytes());
300    ctx.extend_from_slice(&l1.to_le_bytes());
301    ctx.extend_from_slice(&l2.to_le_bytes());
302    ctx
303}
304
305/// Walk an envelope down to the exact `(l1, l2)` node the blob was encrypted for.
306///
307/// The DC returns the key for the node it is willing to hand out; every step from there to
308/// the requested node is a one-way KDF, which is what makes the tree useful — a key for a
309/// later node cannot recover an earlier one.
310pub fn compute_l2_key(env: &GroupKeyEnvelope, want_l1: i32, want_l2: i32) -> Result<Vec<u8>> {
311    if env.is_public_key() {
312        return Err(GkdiError::PublicKeyEnvelope);
313    }
314    if !(0..TREE_ARITY).contains(&want_l1) || !(0..TREE_ARITY).contains(&want_l2) {
315        return Err(GkdiError::BadTreeIndex {
316            l1: want_l1,
317            l2: want_l2,
318        });
319    }
320    let hash = env.hash()?;
321    let label = kds_service_label();
322    let key_len = 64;
323
324    let mut l1 = env.l1;
325    let mut l1_key = env.l1_key.clone();
326    let mut l2 = env.l2;
327    let mut l2_key = env.l2_key.clone();
328
329    // The L2 chain only runs downwards. A fully-seeded node (l2 == 31), a move to a different
330    // L1 branch, or a request for a *later* L2 than we hold all mean the chain has to be
331    // re-seeded from the L1 key — the tree is one-way, so a later node is not reachable from
332    // an earlier one.
333    let mut reseed_l2 = l2 == TREE_ARITY - 1 || env.l1 != want_l1 || want_l2 > l2;
334    if l2 != TREE_ARITY - 1 && env.l1 != want_l1 {
335        l1 -= 1;
336    }
337    while l1 != want_l1 {
338        if l1_key.is_empty() {
339            return Err(GkdiError::MissingSeedKey("L1"));
340        }
341        reseed_l2 = true;
342        l1 -= 1;
343        l1_key = kdf(
344            hash,
345            &l1_key,
346            &label,
347            &kdf_context(env.root_key_id, env.l0, l1, -1),
348            key_len,
349        );
350    }
351    if reseed_l2 {
352        if l1_key.is_empty() {
353            return Err(GkdiError::MissingSeedKey("L1"));
354        }
355        l2 = TREE_ARITY - 1;
356        l2_key = kdf(
357            hash,
358            &l1_key,
359            &label,
360            &kdf_context(env.root_key_id, env.l0, l1, l2),
361            key_len,
362        );
363    }
364    if l2 < want_l2 {
365        // Only reachable if the envelope carried no L1 key to re-seed from.
366        return Err(GkdiError::MissingSeedKey("L1"));
367    }
368    while l2 != want_l2 {
369        if l2_key.is_empty() {
370            return Err(GkdiError::MissingSeedKey("L2"));
371        }
372        l2 -= 1;
373        l2_key = kdf(
374            hash,
375            &l2_key,
376            &label,
377            &kdf_context(env.root_key_id, env.l0, l1, l2),
378            key_len,
379        );
380    }
381    Ok(l2_key)
382}
383
384pub(crate) fn utf16_lossy(b: &[u8]) -> String {
385    let units: Vec<u16> = b
386        .chunks_exact(2)
387        .map(|c| u16::from_le_bytes([c[0], c[1]]))
388        .collect();
389    let trimmed = match units.iter().rposition(|&u| u != 0) {
390        Some(i) => &units[..=i],
391        None => &[][..],
392    };
393    String::from_utf16_lossy(trimmed)
394}
395
396pub(crate) fn utf16z(s: &str) -> Vec<u8> {
397    let mut out: Vec<u8> = s.encode_utf16().flat_map(u16::to_le_bytes).collect();
398    out.extend_from_slice(&[0, 0]);
399    out
400}