Skip to main content

keychain/
format.rs

1//! The `kych` container: file header, tables, records, attribute values.
2//!
3//! Layout per the
4//! [dtformats specification](https://github.com/libyal/dtformats/blob/main/documentation/MacOS%20keychain%20database%20file%20format.asciidoc),
5//! with the details it leaves open (`[yellow-background]*Unknown*` fields,
6//! padding, value encodings) pinned down against keychains written by macOS.
7//! Everything is big-endian.
8//!
9//! ```text
10//! file header (20 bytes)
11//! tables array: size, count, count x offset
12//!   table: header (28 bytes), slot array, records, index data
13//!     record: header (24 bytes), attribute offsets, key data, attribute values
14//! ```
15//!
16//! The model keeps every field, including the ones whose meaning is unknown and
17//! the opaque per-table index data, so that parsing and re-serializing a
18//! macOS-written keychain reproduces it byte for byte. That round trip is the
19//! test that this understanding of the layout is complete — see
20//! `tests/keychain_roundtrip.rs`.
21
22use std::collections::BTreeMap;
23
24use crate::error::{Error, Result};
25use crate::index::{IndexBlob, IndexValue};
26use crate::schema::{AttributeFormat, RecordType, Relation, Schema};
27
28pub const SIGNATURE: &[u8; 4] = b"kych";
29
30/// Combined major/minor version: major 1, minor 0.
31pub const VERSION: u32 = 0x0001_0000;
32
33/// Value of the header's size field, which is 4 less than the header itself.
34pub const HEADER_SIZE_FIELD: u32 = 16;
35
36pub const HEADER_LEN: usize = 20;
37pub const TABLE_HEADER_LEN: usize = 28;
38pub const RECORD_HEADER_LEN: usize = 24;
39
40/// Attribute offsets carry a set low bit; mask it off to get the real offset.
41const ATTRIBUTE_OFFSET_FLAG: u32 = 1;
42
43/// A record slot whose low bit is set is not a record offset: it is a link in
44/// the table's free list, which macOS uses to allocate record numbers. Reading
45/// one as an offset lands in the middle of a record — the login keychain has 231
46/// of them in its certificate table alone.
47const SLOT_FREE_FLAG: u32 = 1;
48
49/// A parsed keychain database.
50#[derive(Debug, Clone)]
51pub struct Keychain {
52    pub version: u32,
53    /// Header size field (`16` in every observed file).
54    pub header_size: u32,
55    /// Purpose unknown; `0` in every observed file.
56    pub auth_offset: u32,
57    /// Tables in file order. Order is preserved because the file's table offset
58    /// array is written in this order.
59    pub tables: Vec<Table>,
60    /// A `u32` that follows the tables array, outside its declared size. macOS
61    /// writes `1` for a fresh keychain and increments it once per committed
62    /// write, so it reads as a commit counter. Preserved, and bumped by
63    /// [`Self::bump_commit_version`] when this code modifies the database.
64    /// `None` for a file that has no such trailer.
65    pub commit_version: Option<u32>,
66}
67
68#[derive(Debug, Clone)]
69pub struct Table {
70    pub record_type: RecordType,
71    /// Head of the table's free list: a link to the highest free slot, or `0`
72    /// when every slot holds a record.
73    ///
74    /// A link is `(28 + 4 * slot) | 1` — the offset of that slot's entry in the
75    /// slot array, with the low bit set to tell it from a record offset. The
76    /// slot it points at holds a link to the next free slot down, and the lowest
77    /// one holds `0`. That is why a fresh, empty table carries `0x1d`: one slot,
78    /// free, at `28 + 0`.
79    pub free_list_head: u32,
80    /// Record slots in file order. A slot's index is the record number it holds.
81    pub slots: Vec<Slot>,
82    /// Slot indexes in the order their records are laid out in the file.
83    ///
84    /// Not the slot order: macOS appends a new record at the end of the records
85    /// region even when it reuses a low-numbered slot, so a keychain that has
86    /// been deleted from and added to has the two orders diverge. Preserving it
87    /// is what keeps a re-serialized file byte-identical to the one read.
88    pub(crate) layout: Vec<usize>,
89    /// The table's index region.
90    pub indexes: TableIndexes,
91}
92
93/// One entry of a table's record-slot array.
94#[derive(Debug, Clone, PartialEq, Eq)]
95pub enum Slot {
96    /// A live record.
97    Record(Record),
98    /// A free-list link, preserved verbatim: its low bit is set, and the rest is
99    /// macOS's bookkeeping for reusing this record number.
100    Free(u32),
101    /// Never used, written as zero.
102    Empty,
103}
104
105impl Slot {
106    pub fn record(&self) -> Option<&Record> {
107        match self {
108            Self::Record(record) => Some(record),
109            _ => None,
110        }
111    }
112
113    pub fn record_mut(&mut self) -> Option<&mut Record> {
114        match self {
115            Self::Record(record) => Some(record),
116            _ => None,
117        }
118    }
119
120    pub fn is_empty(&self) -> bool {
121        matches!(self, Self::Empty)
122    }
123}
124
125/// A table's index region: understood, or preserved as-is.
126#[derive(Debug, Clone, PartialEq, Eq)]
127pub enum TableIndexes {
128    Parsed(IndexBlob),
129    /// Kept verbatim because it did not parse. Such a table must not be
130    /// modified: its offsets are relative to the table and would go stale.
131    Raw(Vec<u8>),
132}
133
134impl TableIndexes {
135    /// Serialize, with offsets measured from `table_offset` — the position of
136    /// the region within its table.
137    pub fn to_bytes(&self, table_offset: usize) -> Vec<u8> {
138        match self {
139            Self::Parsed(blob) => blob.to_bytes(table_offset),
140            Self::Raw(bytes) => bytes.clone(),
141        }
142    }
143
144    pub fn len(&self) -> usize {
145        match self {
146            Self::Parsed(blob) => blob.encoded_len(),
147            Self::Raw(bytes) => bytes.len(),
148        }
149    }
150
151    pub fn is_empty(&self) -> bool {
152        self.len() == 0
153    }
154
155    pub fn blob(&self) -> Option<&IndexBlob> {
156        match self {
157            Self::Parsed(blob) => Some(blob),
158            Self::Raw(_) => None,
159        }
160    }
161}
162
163#[derive(Debug, Clone, PartialEq, Eq)]
164pub struct Record {
165    /// Record number, unique within the table.
166    pub number: u32,
167    /// The database's commit version at the moment the record was written.
168    /// macOS stamps both records of an added item with the same value, so the
169    /// highest record version in a file equals its
170    /// [`Keychain::commit_version`].
171    pub version: u32,
172    /// Purpose unknown. `0` in every observed record except symmetric-key
173    /// records, where macOS writes `4`.
174    pub unknown3: u32,
175    /// Purpose unknown; `0` in every observed record.
176    pub unknown5: u32,
177    /// The record's data: an SSGP blob for password items, a key blob for key
178    /// records, a `DbBlob` for the metadata record.
179    pub key_data: Vec<u8>,
180    /// Attribute values, in the relation's schema order. `None` is an absent
181    /// value, written as a zero offset.
182    pub attributes: Vec<Option<Value>>,
183}
184
185/// An attribute value, in the format the schema declares for it.
186#[derive(Debug, Clone, PartialEq, Eq)]
187pub enum Value {
188    /// Length-prefixed, NUL-terminator optional.
189    String(Vec<u8>),
190    Sint32(i32),
191    Uint32(u32),
192    /// Fixed 16 bytes, `YYYYMMDDhhmmssZ` plus a NUL. Not length-prefixed.
193    Date(Vec<u8>),
194    /// Length-prefixed bytes. Also used for `BIG_NUM`, `MULTI_UINT32`,
195    /// `COMPLEX`, and `REAL`, which are not interpreted further.
196    Blob(Vec<u8>),
197}
198
199impl Value {
200    pub fn as_bytes(&self) -> Option<&[u8]> {
201        match self {
202            Self::String(bytes) | Self::Blob(bytes) | Self::Date(bytes) => Some(bytes),
203            _ => None,
204        }
205    }
206
207    pub fn as_u32(&self) -> Option<u32> {
208        match self {
209            Self::Uint32(value) => Some(*value),
210            Self::Sint32(value) => Some(*value as u32),
211            _ => None,
212        }
213    }
214
215    /// Printable rendering: text when the bytes are valid UTF-8, else hex.
216    pub fn to_display_string(&self) -> String {
217        match self {
218            Self::Sint32(value) => value.to_string(),
219            Self::Uint32(value) => value.to_string(),
220            Self::Date(bytes) | Self::String(bytes) | Self::Blob(bytes) => {
221                let trimmed = trim_nul(bytes);
222                match std::str::from_utf8(trimmed) {
223                    Ok(text) if trimmed.iter().all(|b| !b.is_ascii_control()) => text.to_string(),
224                    _ => format!("0x{}", hex::encode(trimmed)),
225                }
226            }
227        }
228    }
229
230    fn encoded_len(&self) -> usize {
231        match self {
232            Self::Sint32(_) | Self::Uint32(_) => 4,
233            Self::Date(_) => 16,
234            Self::String(bytes) | Self::Blob(bytes) => pad4(4 + bytes.len()),
235        }
236    }
237
238    fn write(&self, out: &mut Vec<u8>) {
239        match self {
240            Self::Sint32(value) => out.extend_from_slice(&value.to_be_bytes()),
241            Self::Uint32(value) => out.extend_from_slice(&value.to_be_bytes()),
242            Self::Date(bytes) => {
243                let mut field = [0u8; 16];
244                let take = bytes.len().min(16);
245                field[..take].copy_from_slice(&bytes[..take]);
246                out.extend_from_slice(&field);
247            }
248            Self::String(bytes) | Self::Blob(bytes) => {
249                out.extend_from_slice(&(bytes.len() as u32).to_be_bytes());
250                out.extend_from_slice(bytes);
251                out.resize(pad4(out.len()), 0);
252            }
253        }
254    }
255}
256
257pub fn trim_nul(bytes: &[u8]) -> &[u8] {
258    match bytes.iter().position(|b| *b == 0) {
259        Some(end) => &bytes[..end],
260        None => bytes,
261    }
262}
263
264fn pad4(len: usize) -> usize {
265    (len + 3) & !3
266}
267
268// ---------------------------------------------------------------------------
269// Reading
270// ---------------------------------------------------------------------------
271
272/// Bounds-checked big-endian reader over the file image.
273struct Cursor<'a> {
274    data: &'a [u8],
275}
276
277impl<'a> Cursor<'a> {
278    fn u32(&self, at: usize) -> Result<u32> {
279        let end = at.checked_add(4).ok_or_else(|| Error::truncated(at, 4))?;
280        let bytes = self
281            .data
282            .get(at..end)
283            .ok_or_else(|| Error::truncated(at, 4))?;
284        Ok(u32::from_be_bytes([bytes[0], bytes[1], bytes[2], bytes[3]]))
285    }
286
287    fn bytes(&self, at: usize, len: usize) -> Result<&'a [u8]> {
288        let end = at
289            .checked_add(len)
290            .ok_or_else(|| Error::truncated(at, len))?;
291        self.data
292            .get(at..end)
293            .ok_or_else(|| Error::truncated(at, len))
294    }
295}
296
297impl Keychain {
298    /// Parse a keychain image. The schema is read from the file itself.
299    pub fn parse(data: &[u8]) -> Result<Self> {
300        let cursor = Cursor { data };
301
302        if data.len() < HEADER_LEN {
303            return Err(Error::truncated(0, HEADER_LEN));
304        }
305        if &data[..4] != SIGNATURE {
306            return Err(Error::NotAKeychain);
307        }
308
309        let version = cursor.u32(4)?;
310        let header_size = cursor.u32(8)?;
311        let tables_offset = cursor.u32(12)? as usize;
312        let auth_offset = cursor.u32(16)?;
313
314        // The declared tables-array size is not trusted for bounds: table
315        // offsets are read individually and each table is checked on its own.
316        // It does locate the commit-version trailer, which sits just past it.
317        let tables_size = cursor.u32(tables_offset)? as usize;
318        let commit_version = cursor.u32(tables_offset + tables_size).ok();
319
320        let table_count = cursor.u32(tables_offset + 4)? as usize;
321        let mut table_offsets = Vec::with_capacity(table_count);
322        for index in 0..table_count {
323            table_offsets.push(cursor.u32(tables_offset + 8 + index * 4)? as usize);
324        }
325
326        // The schema lives in the file's own tables, so read the schema tables
327        // first — with the built-in definitions for those four relations — and
328        // only then parse everything with the schema the file declares. Parsing
329        // an unknown relation would misplace its key data, so it is not attempted.
330        let bootstrap = Schema::bootstrap();
331        let mut schema_tables = Vec::new();
332        for offset in &table_offsets {
333            let at = tables_offset + offset;
334            let record_type = RecordType(cursor.u32(at + 4)?);
335            if bootstrap.relation(record_type).is_some() {
336                schema_tables.push(Table::parse(&cursor, at, &bootstrap)?);
337            }
338        }
339        let schema = Schema::from_tables(&schema_tables)?;
340
341        let mut tables = Vec::with_capacity(table_count);
342        for offset in &table_offsets {
343            tables.push(Table::parse(&cursor, tables_offset + offset, &schema)?);
344        }
345
346        Ok(Self {
347            version,
348            header_size,
349            auth_offset,
350            tables,
351            commit_version,
352        })
353    }
354
355    /// The schema this file declares.
356    pub fn schema(&self) -> Result<Schema> {
357        Schema::from_tables(&self.tables)
358    }
359
360    /// Record another committed write, the way macOS does.
361    pub fn bump_commit_version(&mut self) {
362        self.commit_version = Some(self.commit_version.unwrap_or(0) + 1);
363    }
364
365    pub fn table(&self, record_type: RecordType) -> Option<&Table> {
366        self.tables
367            .iter()
368            .find(|table| table.record_type == record_type)
369    }
370
371    pub fn table_mut(&mut self, record_type: RecordType) -> Option<&mut Table> {
372        self.tables
373            .iter_mut()
374            .find(|table| table.record_type == record_type)
375    }
376
377    /// Serialize back to a file image.
378    pub fn to_bytes(&self) -> Result<Vec<u8>> {
379        let mut tables = Vec::with_capacity(self.tables.len());
380        for table in &self.tables {
381            tables.push(table.to_bytes()?);
382        }
383
384        // Tables array: size, count, offsets, then the tables themselves.
385        let array_header = 8 + 4 * tables.len();
386        let mut offsets = Vec::with_capacity(tables.len());
387        let mut running = array_header;
388        for table in &tables {
389            offsets.push(running as u32);
390            running += table.len();
391        }
392
393        let mut out = Vec::with_capacity(HEADER_LEN + running);
394        out.extend_from_slice(SIGNATURE);
395        out.extend_from_slice(&self.version.to_be_bytes());
396        out.extend_from_slice(&self.header_size.to_be_bytes());
397        out.extend_from_slice(&(HEADER_LEN as u32).to_be_bytes());
398        out.extend_from_slice(&self.auth_offset.to_be_bytes());
399
400        out.extend_from_slice(&(running as u32).to_be_bytes());
401        out.extend_from_slice(&(tables.len() as u32).to_be_bytes());
402        for offset in offsets {
403            out.extend_from_slice(&offset.to_be_bytes());
404        }
405        for table in tables {
406            out.extend_from_slice(&table);
407        }
408        if let Some(commit_version) = self.commit_version {
409            out.extend_from_slice(&commit_version.to_be_bytes());
410        }
411        Ok(out)
412    }
413}
414
415impl Table {
416    fn parse(cursor: &Cursor<'_>, at: usize, schema: &Schema) -> Result<Self> {
417        let _size = cursor.u32(at)?;
418        let record_type = RecordType(cursor.u32(at + 4)?);
419        let _record_count = cursor.u32(at + 8)?;
420        let _records_offset = cursor.u32(at + 12)?;
421        let indexes_offset = cursor.u32(at + 16)? as usize;
422        let free_list_head = cursor.u32(at + 20)?;
423        let slot_count = cursor.u32(at + 24)? as usize;
424        if slot_count > 1 << 20 {
425            return Err(Error::format(format!(
426                "table 0x{:08x} claims {slot_count} record slots",
427                record_type.0
428            )));
429        }
430
431        let mut slots = Vec::with_capacity(slot_count);
432        let mut layout: Vec<(usize, usize)> = Vec::new();
433        for index in 0..slot_count {
434            let offset = cursor.u32(at + TABLE_HEADER_LEN + index * 4)?;
435            if offset == 0 {
436                slots.push(Slot::Empty);
437                continue;
438            }
439            if offset & SLOT_FREE_FLAG != 0 {
440                slots.push(Slot::Free(offset));
441                continue;
442            }
443            layout.push((offset as usize, index));
444            let offset = offset as usize;
445            if offset < TABLE_HEADER_LEN || offset >= indexes_offset {
446                return Err(Error::format(format!(
447                    "table 0x{:08x} slot {index} points to {offset}, outside its records",
448                    record_type.0
449                )));
450            }
451            slots.push(Slot::Record(Record::parse(
452                cursor,
453                at + offset,
454                record_type,
455                schema,
456            )?));
457        }
458
459        let size = _size as usize;
460        if indexes_offset > size {
461            return Err(Error::format(format!(
462                "table 0x{:08x} index offset {indexes_offset} is past its {size}-byte extent",
463                record_type.0
464            )));
465        }
466        let index_data = cursor.bytes(at + indexes_offset, size - indexes_offset)?;
467
468        // Parsing needs the relation, for the attribute formats the index keys
469        // are encoded in. A region that does not parse is kept verbatim.
470        let relation = schema.relation(record_type);
471        let indexes = match IndexBlob::parse(index_data, indexes_offset, relation) {
472            Ok(blob) if blob.to_bytes(indexes_offset) == index_data => TableIndexes::Parsed(blob),
473            _ => TableIndexes::Raw(index_data.to_vec()),
474        };
475
476        // Records are laid out in the file in this order, which is not
477        // necessarily slot order.
478        layout.sort_unstable();
479
480        Ok(Self {
481            record_type,
482            free_list_head,
483            slots,
484            layout: layout.into_iter().map(|(_, index)| index).collect(),
485            indexes,
486        })
487    }
488
489    /// The free-list link that points at slot `index`.
490    ///
491    /// Links are table-relative offsets into the slot array with the low bit
492    /// set, which is what distinguishes them from a record offset.
493    fn free_link(index: usize) -> u32 {
494        (TABLE_HEADER_LEN + 4 * index) as u32 | SLOT_FREE_FLAG
495    }
496
497    /// Rebuild the free list from the slots that are actually free.
498    ///
499    /// macOS threads the list through the slot array itself: the table header
500    /// holds a link to the highest free slot, that slot holds a link to the next
501    /// one down, and the lowest holds zero. The chain is a function of which
502    /// slots are free, not of the order they were freed in — two keychains that
503    /// reached the same state by opposite deletion orders are byte-identical.
504    fn rebuild_free_list(&mut self) {
505        let mut head = 0u32;
506        for index in 0..self.slots.len() {
507            if self.slots[index].record().is_some() {
508                continue;
509            }
510            self.slots[index] = if head == 0 {
511                Slot::Empty
512            } else {
513                Slot::Free(head)
514            };
515            head = Self::free_link(index);
516        }
517        self.free_list_head = head;
518    }
519
520    /// The slot the next insert should take: the head of the free list.
521    fn free_head(&self) -> Option<usize> {
522        (0..self.slots.len())
523            .rev()
524            .find(|index| self.slots[*index].record().is_none())
525    }
526
527    /// Live records, skipping free and empty slots.
528    pub fn records(&self) -> impl Iterator<Item = &Record> {
529        self.slots.iter().filter_map(Slot::record)
530    }
531
532    pub fn records_mut(&mut self) -> impl Iterator<Item = &mut Record> {
533        self.slots.iter_mut().filter_map(Slot::record_mut)
534    }
535
536    pub fn record_count(&self) -> usize {
537        self.records().count()
538    }
539
540    /// Lowest unused record number. macOS numbers records from 0 upward.
541    pub fn next_record_number(&self) -> u32 {
542        self.records()
543            .map(|record| record.number)
544            .max()
545            .map_or(0, |max| max + 1)
546    }
547
548    /// Store a record, taking the head of the free list when there is one.
549    ///
550    /// The record's number is the slot it lands in — that is what a record
551    /// number *is* here — so it is assigned rather than taken from the caller,
552    /// and returned. The record's bytes go at the end of the records region, the
553    /// way macOS appends them, however low the reused slot number is.
554    pub fn insert(&mut self, mut record: Record) -> u32 {
555        let index = match self.free_head() {
556            Some(index) => index,
557            None => {
558                self.slots.push(Slot::Empty);
559                self.slots.len() - 1
560            }
561        };
562        record.number = index as u32;
563        self.slots[index] = Slot::Record(record);
564        self.layout.push(index);
565        self.rebuild_free_list();
566        index as u32
567    }
568
569    /// Delete a record, freeing its slot the way macOS frees one.
570    ///
571    /// The slot keeps its place unless it is the last one, in which case the
572    /// array loses exactly that entry — trailing free slots below it are left
573    /// alone, and the array never shrinks below one slot. Surviving records keep
574    /// their numbers: index entries refer to records by number, and macOS never
575    /// renumbers.
576    ///
577    /// Returns whether a record was there to delete.
578    pub fn delete(&mut self, number: u32) -> bool {
579        let Some(position) = self
580            .slots
581            .iter()
582            .position(|slot| slot.record().is_some_and(|record| record.number == number))
583        else {
584            return false;
585        };
586
587        self.slots[position] = Slot::Empty;
588        self.layout.retain(|index| *index != position);
589        if position + 1 == self.slots.len() && self.slots.len() > 1 {
590            self.slots.pop();
591        }
592        self.rebuild_free_list();
593
594        if let TableIndexes::Parsed(blob) = &mut self.indexes {
595            blob.remove_record(number);
596        }
597        true
598    }
599
600    /// The attributes of the table's unique index, by id.
601    ///
602    /// `None` when this build could not parse the index region, or the table
603    /// declares no unique index.
604    pub fn unique_index_attribute_ids(&self) -> Option<&[u32]> {
605        self.indexes
606            .blob()?
607            .indexes
608            .iter()
609            .find(|index| index.kind == 1)
610            .map(|index| index.attribute_ids.as_slice())
611    }
612
613    /// True when a record already has the same key as `attributes` under the
614    /// table's unique index.
615    ///
616    /// The unique index is the one the region marks `kind == 1`; the attributes
617    /// it names are the relation's notion of identity, which is what macOS
618    /// refuses a duplicate of. A table whose index region this build could not
619    /// parse answers `false`: it cannot tell, and refusing a write macOS would
620    /// accept is worse than allowing it.
621    pub fn has_record_with_unique_key(
622        &self,
623        relation: &Relation,
624        attributes: &[Option<Value>],
625    ) -> bool {
626        let Some(blob) = self.indexes.blob() else {
627            return false;
628        };
629        let Some(unique) = blob.indexes.iter().find(|index| index.kind == 1) else {
630            return false;
631        };
632        // Attributes are stored in relation order, so an attribute id becomes a
633        // position in the record.
634        let positions: Vec<usize> = unique
635            .attribute_ids
636            .iter()
637            .filter_map(|id| {
638                relation
639                    .attributes
640                    .iter()
641                    .position(|attribute| attribute.id == *id)
642            })
643            .collect();
644        if positions.len() != unique.attribute_ids.len() {
645            return false;
646        }
647
648        let key_of = |values: &[Option<Value>]| -> Vec<Option<Value>> {
649            positions
650                .iter()
651                .map(|position| values.get(*position).cloned().flatten())
652                .collect()
653        };
654        let wanted = key_of(attributes);
655        self.records()
656            .any(|record| key_of(&record.attributes) == wanted)
657    }
658
659    /// Rebuild every index from the table's records.
660    ///
661    /// Rebuilding rather than patching keeps the indexes consistent with the
662    /// records by construction; `tests/keychain_index.rs` checks that a rebuild
663    /// reproduces the entries and the ordering macOS wrote.
664    pub fn rebuild_indexes(&mut self, relation: &Relation) -> Result<()> {
665        let TableIndexes::Parsed(blob) = &mut self.indexes else {
666            return Err(Error::format(format!(
667                "table 0x{:08x} has an index region this build cannot rewrite",
668                self.record_type.0
669            )));
670        };
671
672        // Attribute id -> (position in the record, format).
673        let positions: Vec<(u32, usize, AttributeFormat)> = relation
674            .attributes
675            .iter()
676            .enumerate()
677            .map(|(position, attribute)| (attribute.id, position, attribute.format))
678            .collect();
679
680        for index in &mut blob.indexes {
681            index.entries.clear();
682        }
683        for record in self.slots.iter().filter_map(Slot::record) {
684            let position_of = |attribute_id: u32| -> Option<usize> {
685                positions
686                    .iter()
687                    .find(|(id, _, _)| *id == attribute_id)
688                    .map(|(_, position, _)| *position)
689            };
690            let key = |attribute_id: u32| -> IndexValue {
691                match positions.iter().find(|(id, _, _)| *id == attribute_id) {
692                    Some((_, position, format)) => {
693                        IndexValue::from_value(record.attribute(*position), *format)
694                    }
695                    None => IndexValue::Bytes(Vec::new()),
696                }
697            };
698            // macOS does not index a record under an attribute it does not
699            // have: an absent value is not an empty one.
700            blob.insert_record_where(record.number, key, |attribute_ids: &[u32]| -> bool {
701                attribute_ids.iter().all(|id| {
702                    position_of(*id).is_some_and(|position| record.attribute(position).is_some())
703                })
704            });
705        }
706        Ok(())
707    }
708
709    fn to_bytes(&self) -> Result<Vec<u8>> {
710        let records_offset = TABLE_HEADER_LEN + 4 * self.slots.len();
711        let mut slot_offsets = vec![0u32; self.slots.len()];
712        for (index, slot) in self.slots.iter().enumerate() {
713            if let Slot::Free(link) = slot {
714                slot_offsets[index] = *link;
715            }
716        }
717
718        // Records go out in layout order, each slot's offset recorded as it is
719        // placed. A slot missing from the layout — one added without going
720        // through `insert` — is appended after the rest.
721        let mut order: Vec<usize> = self
722            .layout
723            .iter()
724            .copied()
725            .filter(|index| {
726                self.slots
727                    .get(*index)
728                    .is_some_and(|slot| slot.record().is_some())
729            })
730            .collect();
731        for (index, slot) in self.slots.iter().enumerate() {
732            if slot.record().is_some() && !order.contains(&index) {
733                order.push(index);
734            }
735        }
736
737        let mut bodies = Vec::with_capacity(order.len());
738        let mut running = records_offset;
739        for index in &order {
740            let Some(Slot::Record(record)) = self.slots.get(*index) else {
741                continue;
742            };
743            let bytes = record.to_bytes()?;
744            slot_offsets[*index] = running as u32;
745            running += bytes.len();
746            bodies.push(bytes);
747        }
748        let records: Vec<Option<Vec<u8>>> = bodies.into_iter().map(Some).collect();
749        let indexes_offset = running;
750        let index_data = self.indexes.to_bytes(indexes_offset);
751        let size = indexes_offset + index_data.len();
752
753        let mut out = Vec::with_capacity(size);
754        out.extend_from_slice(&(size as u32).to_be_bytes());
755        out.extend_from_slice(&self.record_type.0.to_be_bytes());
756        out.extend_from_slice(&(self.record_count() as u32).to_be_bytes());
757        out.extend_from_slice(&(records_offset as u32).to_be_bytes());
758        out.extend_from_slice(&(indexes_offset as u32).to_be_bytes());
759        out.extend_from_slice(&self.free_list_head.to_be_bytes());
760        out.extend_from_slice(&(self.slots.len() as u32).to_be_bytes());
761        for offset in slot_offsets {
762            out.extend_from_slice(&offset.to_be_bytes());
763        }
764        for record in records.into_iter().flatten() {
765            out.extend_from_slice(&record);
766        }
767        out.extend_from_slice(&index_data);
768        Ok(out)
769    }
770}
771
772impl Record {
773    fn parse(
774        cursor: &Cursor<'_>,
775        at: usize,
776        record_type: RecordType,
777        schema: &Schema,
778    ) -> Result<Self> {
779        let size = cursor.u32(at)? as usize;
780        let number = cursor.u32(at + 4)?;
781        let version = cursor.u32(at + 8)?;
782        let unknown3 = cursor.u32(at + 12)?;
783        let key_data_size = cursor.u32(at + 16)? as usize;
784        let unknown5 = cursor.u32(at + 20)?;
785
786        let formats = schema.attribute_formats(record_type);
787        let mut attributes = Vec::with_capacity(formats.len());
788        let mut offsets = Vec::with_capacity(formats.len());
789        for index in 0..formats.len() {
790            offsets.push(cursor.u32(at + RECORD_HEADER_LEN + index * 4)?);
791        }
792
793        let key_data_at = at + RECORD_HEADER_LEN + 4 * formats.len();
794        let key_data = cursor.bytes(key_data_at, key_data_size)?.to_vec();
795
796        for (offset, format) in offsets.iter().zip(&formats) {
797            if *offset == 0 {
798                attributes.push(None);
799                continue;
800            }
801            let value_at = at + (*offset & !ATTRIBUTE_OFFSET_FLAG) as usize;
802            if value_at >= at + size {
803                return Err(Error::format(format!(
804                    "record {number} in table 0x{:08x} points an attribute past its extent",
805                    record_type.0
806                )));
807            }
808            attributes.push(Some(read_value(cursor, value_at, *format)?));
809        }
810
811        Ok(Self {
812            number,
813            version,
814            unknown3,
815            unknown5,
816            key_data,
817            attributes,
818        })
819    }
820
821    pub fn attribute(&self, index: usize) -> Option<&Value> {
822        self.attributes.get(index).and_then(Option::as_ref)
823    }
824
825    /// Set or clear an attribute by its position in the relation.
826    ///
827    /// Out-of-range positions are ignored rather than panicking: a record built
828    /// against a shorter relation is a schema problem, not a caller error.
829    pub fn set_attribute(&mut self, index: usize, value: Option<Value>) {
830        if let Some(slot) = self.attributes.get_mut(index) {
831            *slot = value;
832        }
833    }
834
835    fn to_bytes(&self) -> Result<Vec<u8>> {
836        let count = self.attributes.len();
837        let header_and_offsets = RECORD_HEADER_LEN + 4 * count;
838        let key_data_len = pad4(self.key_data.len());
839
840        // Values follow the key data, in attribute order, each padded to 4.
841        let mut offsets = Vec::with_capacity(count);
842        let mut running = header_and_offsets + key_data_len;
843        for attribute in &self.attributes {
844            match attribute {
845                Some(value) => {
846                    offsets.push(running as u32 | ATTRIBUTE_OFFSET_FLAG);
847                    running += value.encoded_len();
848                }
849                None => offsets.push(0),
850            }
851        }
852        let size = running;
853
854        let mut out = Vec::with_capacity(size);
855        out.extend_from_slice(&(size as u32).to_be_bytes());
856        out.extend_from_slice(&self.number.to_be_bytes());
857        out.extend_from_slice(&self.version.to_be_bytes());
858        out.extend_from_slice(&self.unknown3.to_be_bytes());
859        out.extend_from_slice(&(self.key_data.len() as u32).to_be_bytes());
860        out.extend_from_slice(&self.unknown5.to_be_bytes());
861        for offset in offsets {
862            out.extend_from_slice(&offset.to_be_bytes());
863        }
864        out.extend_from_slice(&self.key_data);
865        out.resize(header_and_offsets + key_data_len, 0);
866        for value in self.attributes.iter().flatten() {
867            value.write(&mut out);
868        }
869
870        debug_assert_eq!(
871            out.len(),
872            size,
873            "record serialization disagreed with its own layout"
874        );
875        Ok(out)
876    }
877}
878
879fn read_value(cursor: &Cursor<'_>, at: usize, format: AttributeFormat) -> Result<Value> {
880    Ok(match format {
881        AttributeFormat::Sint32 => Value::Sint32(cursor.u32(at)? as i32),
882        AttributeFormat::Uint32 => Value::Uint32(cursor.u32(at)?),
883        AttributeFormat::TimeDate => Value::Date(cursor.bytes(at, 16)?.to_vec()),
884        AttributeFormat::String => {
885            let len = cursor.u32(at)? as usize;
886            Value::String(cursor.bytes(at + 4, len)?.to_vec())
887        }
888        // Blob, and the formats this does not interpret.
889        _ => {
890            let len = cursor.u32(at)? as usize;
891            Value::Blob(cursor.bytes(at + 4, len)?.to_vec())
892        }
893    })
894}
895
896/// Group the live records of every table by record type.
897pub fn records_by_type(keychain: &Keychain) -> BTreeMap<RecordType, Vec<&Record>> {
898    let mut out = BTreeMap::new();
899    for table in &keychain.tables {
900        out.insert(table.record_type, table.records().collect());
901    }
902    out
903}
904
905#[cfg(test)]
906mod tests {
907    use super::*;
908
909    #[test]
910    fn padding_rounds_up_to_four() {
911        assert_eq!(pad4(0), 0);
912        assert_eq!(pad4(1), 4);
913        assert_eq!(pad4(4), 4);
914        assert_eq!(pad4(13), 16);
915    }
916
917    #[test]
918    fn rejects_files_that_are_not_keychains() {
919        assert!(matches!(
920            Keychain::parse(b"not a keychain at all!!!"),
921            Err(Error::NotAKeychain)
922        ));
923        assert!(matches!(
924            Keychain::parse(b"kych"),
925            Err(Error::Truncated { .. })
926        ));
927    }
928
929    #[test]
930    fn value_encoding_lengths_match_the_layout_rules() {
931        assert_eq!(Value::Uint32(7).encoded_len(), 4);
932        assert_eq!(Value::Date(b"20260725095125Z\0".to_vec()).encoded_len(), 16);
933        // 4-byte length prefix, then the bytes padded to a 4-byte boundary.
934        assert_eq!(Value::Blob(b"alice".to_vec()).encoded_len(), 12);
935        assert_eq!(Value::Blob(b"myservice".to_vec()).encoded_len(), 16);
936        assert_eq!(Value::Blob(Vec::new()).encoded_len(), 4);
937    }
938
939    #[test]
940    fn values_serialize_with_prefix_and_padding() {
941        let mut out = Vec::new();
942        Value::Blob(b"alice".to_vec()).write(&mut out);
943        assert_eq!(out, b"\x00\x00\x00\x05alice\0\0\0");
944
945        let mut out = Vec::new();
946        Value::Date(b"20260725095125Z\0".to_vec()).write(&mut out);
947        assert_eq!(out.len(), 16);
948        assert_eq!(&out, b"20260725095125Z\0");
949
950        // A date shorter than the field is zero-filled, not length-prefixed.
951        let mut out = Vec::new();
952        Value::Date(b"2026".to_vec()).write(&mut out);
953        assert_eq!(out, b"2026\0\0\0\0\0\0\0\0\0\0\0\0");
954    }
955
956    #[test]
957    fn display_prefers_text_and_falls_back_to_hex() {
958        assert_eq!(
959            Value::Blob(b"alice\0".to_vec()).to_display_string(),
960            "alice"
961        );
962        assert_eq!(Value::Uint32(8080).to_display_string(), "8080");
963        assert_eq!(Value::Blob(vec![0xff, 0xfe]).to_display_string(), "0xfffe");
964        assert_eq!(
965            Value::Date(b"20260725095125Z\0".to_vec()).to_display_string(),
966            "20260725095125Z"
967        );
968    }
969
970    #[test]
971    fn trim_nul_stops_at_the_first_terminator() {
972        assert_eq!(trim_nul(b"abc\0def"), b"abc");
973        assert_eq!(trim_nul(b"abc"), b"abc");
974        assert_eq!(trim_nul(b"\0"), b"");
975    }
976
977    #[test]
978    fn a_freed_slot_is_the_next_one_allocated() {
979        let record = |number| Record {
980            number,
981            version: 0,
982            unknown3: 0,
983            unknown5: 0,
984            key_data: Vec::new(),
985            attributes: vec![None],
986        };
987        let mut table = Table {
988            record_type: RecordType::GENERIC_PASSWORD,
989            free_list_head: 0,
990            slots: vec![
991                Slot::Record(record(0)),
992                Slot::Empty,
993                Slot::Record(record(2)),
994            ],
995            layout: vec![0, 2],
996            indexes: TableIndexes::Parsed(IndexBlob {
997                indexes: Vec::new(),
998            }),
999        };
1000
1001        assert_eq!(table.record_count(), 2);
1002
1003        // The hole is filled, and the record takes that slot's number.
1004        assert_eq!(table.insert(record(99)), 1);
1005        assert_eq!(table.slots.len(), 3, "the hole was reused");
1006        assert_eq!(table.slots[1].record().map(|record| record.number), Some(1));
1007        assert_eq!(table.free_list_head, 0, "no free slots left");
1008
1009        // With none left, the array grows.
1010        assert_eq!(table.insert(record(99)), 3);
1011        assert_eq!(table.slots.len(), 4);
1012    }
1013
1014    #[test]
1015    fn the_free_list_is_a_chain_through_the_slot_array() {
1016        let record = |number| Record {
1017            number,
1018            version: 0,
1019            unknown3: 0,
1020            unknown5: 0,
1021            key_data: Vec::new(),
1022            attributes: vec![None],
1023        };
1024        let mut table = Table {
1025            record_type: RecordType::GENERIC_PASSWORD,
1026            free_list_head: 0,
1027            slots: (0..4).map(|number| Slot::Record(record(number))).collect(),
1028            layout: vec![0, 1, 2, 3],
1029            indexes: TableIndexes::Parsed(IndexBlob {
1030                indexes: Vec::new(),
1031            }),
1032        };
1033
1034        // Freeing two slots threads a chain: the header points at the highest
1035        // free slot, that slot points at the next one down, the lowest holds
1036        // zero. These are the values macOS writes.
1037        assert!(table.delete(2));
1038        assert!(table.delete(0));
1039        assert_eq!(table.free_list_head, (TABLE_HEADER_LEN as u32 + 8) | 1);
1040        assert_eq!(table.slots[2], Slot::Free(TABLE_HEADER_LEN as u32 | 1));
1041        assert_eq!(table.slots[0], Slot::Empty);
1042
1043        // Freeing order does not matter: the chain is a function of which slots
1044        // are free.
1045        let mut other = Table {
1046            record_type: RecordType::GENERIC_PASSWORD,
1047            free_list_head: 0,
1048            slots: (0..4).map(|number| Slot::Record(record(number))).collect(),
1049            layout: vec![0, 1, 2, 3],
1050            indexes: TableIndexes::Parsed(IndexBlob {
1051                indexes: Vec::new(),
1052            }),
1053        };
1054        assert!(other.delete(0));
1055        assert!(other.delete(2));
1056        assert_eq!(other.slots, table.slots);
1057        assert_eq!(other.free_list_head, table.free_list_head);
1058
1059        // Deleting the last slot shortens the array instead, but never past one
1060        // slot, and never trims the free slots below it.
1061        assert!(table.delete(3));
1062        assert_eq!(table.slots.len(), 3);
1063        assert_eq!(table.record_count(), 1);
1064        assert!(table.delete(1));
1065        assert_eq!(table.slots.len(), 3, "slot 1 is not the last one");
1066        assert_eq!(table.record_count(), 0);
1067    }
1068
1069    #[test]
1070    fn records_keep_their_place_in_the_file_when_a_slot_is_reused() {
1071        let record = |number, data: &[u8]| Record {
1072            number,
1073            version: 0,
1074            unknown3: 0,
1075            unknown5: 0,
1076            key_data: data.to_vec(),
1077            attributes: vec![None],
1078        };
1079        let mut table = Table {
1080            record_type: RecordType::GENERIC_PASSWORD,
1081            free_list_head: 0,
1082            slots: vec![
1083                Slot::Record(record(0, b"first")),
1084                Slot::Record(record(1, b"second")),
1085                Slot::Record(record(2, b"third")),
1086            ],
1087            layout: vec![0, 1, 2],
1088            indexes: TableIndexes::Parsed(IndexBlob {
1089                indexes: Vec::new(),
1090            }),
1091        };
1092
1093        // Free a middle slot and reuse it: the new record's bytes belong at the
1094        // END of the records region, not where the old one sat, which is what
1095        // macOS does and what makes a re-read file byte-identical.
1096        table.delete(1);
1097        table.insert(record(0, b"fourth"));
1098        assert_eq!(table.layout, vec![0, 2, 1]);
1099
1100        let bytes = table.to_bytes().unwrap();
1101        let offset = |slot: usize| {
1102            let at = TABLE_HEADER_LEN + slot * 4;
1103            u32::from_be_bytes(bytes[at..at + 4].try_into().unwrap())
1104        };
1105        assert!(
1106            offset(1) > offset(2),
1107            "the reused slot's record is last in the file"
1108        );
1109    }
1110}