verifyRepoCar() accepts invalid repository paths and noncanonical MSTs

Author: olix0rCreated Aug 19, 2026Updated Aug 20, 2026

Describe the bug

Reported by: OpenAI Sol 5.6

verifyRepoCar() returns a VerifiedRepo for complete, CID-consistent, validly signed repository CARs that violate four mandatory repository invariants:

A repository path contains an unnormalized collection NSID.
A child key is on the wrong MST layer.
A right-subtree key sorts below its parent bound.
A node entry does not use the longest shared-prefix encoding.

Each fixture changes only the named structural rule. All commit, node, and record CIDs match their bytes, and each commit has a valid signature.

The repository specification requires a valid normalized NSID in every repository path, key depth and subtree ranges to be verified when parsing, and canonical prefix compression. Accepting these states lets implementations disagree about whether the same signed repository is valid. The prefix case also permits more than one MST encoding for the same key/value mapping.

This reproduces with @atproto/repo 0.10.11 and 0.10.6.

To Reproduce

Save the script below as reproduce.mjs.
Install the tested package versions:

bash

npm install @atproto/[email protected] @atproto/[email protected] @atproto/[email protected] @atproto/[email protected]

Run node reproduce.mjs.

Standalone reproducer and output

The fixed private scalar is public test material for a fictional did:example identity. It protects no account.

javascript

import { createHash } from 'node:crypto'

import { Secp256k1Keypair } from '@atproto/crypto'
import { encode } from '@atproto/lex-cbor'
import { cidForCbor } from '@atproto/lex-data'
import {
  BlockMap,
  MemoryBlockstore,
  concatBytesAsync,
  getFullRepo,
  signCommit,
  verifyRepoCar,
} from '@atproto/repo'

const did = 'did:example:repo-verifier'
const keypair = await Secp256k1Keypair.import(
  '0000000000000000000000000000000000000000000000000000000000000001',
  { exportable: true },
)
const recordKey = 'com.example.fixture1/main'
const recordBytes = encode({ $type: 'com.example.fixture1', value: 'record' })
const recordCid = await cidForCbor(recordBytes)
const markerBytes = encode({ $type: 'com.example.marker', value: 'marker' })
const markerCid = await cidForCbor(markerBytes)
const parentLayer = mstLayer(recordKey)

const wrongLayerKey = findKey(
  'com.example.wrongLayer',
  (key) => key > recordKey && mstLayer(key) !== parentLayer - 1,
)
const outOfRangeKey = findKey(
  'com.example.aaaRange',
  (key) => key < recordKey && mstLayer(key) === parentLayer - 1,
)
const [prefixLeft, prefixRight] = findSameLayerKeys('com.example.prefix')

const cases = [
  {
    name: 'unnormalized repository-path NSID',
    graph: async () => ({
      root: await mstNode([mstEntry('COM.example.fixture1/main', recordCid)]),
      children: [],
      records: [[recordCid, recordBytes]],
    }),
  },
  {
    name: 'key on the wrong MST layer',
    graph: async () => {
      const child = await mstNode([mstEntry(wrongLayerKey, markerCid)])
      return {
        root: await mstNode([mstEntry(recordKey, recordCid, child.cid)]),
        children: [child],
        records: [
          [recordCid, recordBytes],
          [markerCid, markerBytes],
        ],
      }
    },
  },
  {
    name: 'key outside its subtree range',
    graph: async () => {
      const child = await mstNode([mstEntry(outOfRangeKey, markerCid)])
      return {
        root: await mstNode([mstEntry(recordKey, recordCid, child.cid)]),
        children: [child],
        records: [
          [recordCid, recordBytes],
          [markerCid, markerBytes],
        ],
      }
    },
  },
  {
    name: 'noncanonical prefix compression',
    graph: async () => ({
      root: await mstNode([
        mstEntry(prefixLeft, markerCid),
        mstEntry(prefixRight, markerCid, null, 0, prefixRight),
      ]),
      children: [],
      records: [[markerCid, markerBytes]],
    }),
  },
]

for (const [index, testCase] of cases.entries()) {
  const graph = await testCase.graph()
  const car = await signedCar(graph, `3mugtest0000${index}`)
  const result = await verifyRepoCar(car, did, keypair.did())
  console.log(`ACCEPTED: ${testCase.name} (${result.creates.length} records)`)
}

async function mstNode(entries) {
  const bytes = encode({ l: null, e: entries })
  return { bytes, cid: await cidForCbor(bytes) }
}

function mstEntry(key, value, right = null, prefix = 0, suffix = key) {
  return {
    p: prefix,
    k: Buffer.from(suffix, 'ascii'),
    v: value,
    t: right,
  }
}

async function signedCar({ root, children, records }, rev) {
  const commit = await signCommit(
    { did, version: 3, rev, prev: null, data: root.cid },
    keypair,
  )
  const blocks = new BlockMap()
  for (const node of [root, ...children]) blocks.set(node.cid, node.bytes)
  for (const [cid, bytes] of records) blocks.set(cid, bytes)
  const commitCid = await blocks.add(commit)
  return concatBytesAsync(getFullRepo(new MemoryBlockstore(blocks), commitCid))
}

function mstLayer(key) {
  const hash = createHash('sha256').update(Buffer.from(key, 'ascii')).digest()
  let layer = 0
  for (const byte of hash) {
    for (const shift of [6, 4, 2, 0]) {
      if (((byte >> shift) & 3) !== 0) return layer
      layer += 1
    }
  }
  return layer
}

function findKey(collection, predicate) {
  for (let index = 0; index < 100_000; index += 1) {
    const key = `${collection}/k${index}`
    if (predicate(key)) return key
  }
  throw new Error(`no key satisfies ${collection}`)
}

function findSameLayerKeys(collection) {
  const byLayer = new Map()
  for (let index = 0; index < 100_000; index += 1) {
    const key = `${collection}/k${index}`
    const layer = mstLayer(key)
    const previous = byLayer.get(layer)
    if (previous) return [previous, key]
    byLayer.set(layer, key)
  }
  throw new Error(`no two keys share a layer under ${collection}`)
}

Observed output:

ACCEPTED: unnormalized repository-path NSID (1 records)
ACCEPTED: key on the wrong MST layer (2 records)
ACCEPTED: key outside its subtree range (2 records)
ACCEPTED: noncanonical prefix compression (2 records)

The generated cases use these exact violations:

COM.example.fixture1/main is accepted as a repository path.
The layer-1 root links to com.example.wrongLayer/k0, whose derived layer is 2 instead of 0.
The right subtree of com.example.fixture1/main contains com.example.aaaRange/k0, which sorts below its parent bound.
com.example.prefix/k1 is encoded with p: 0 and its full key after com.example.prefix/k0, instead of the longest shared prefix of 20 bytes.

Expected behavior

verifyRepoCar() should reject each CAR before returning a VerifiedRepo. Verification of untrusted repository bytes should enforce the canonical structure required by the repository specification.

Details

Operating system: macOS 26.5.1
Node version: v26.3.0
@atproto/repo: 0.10.11
Also reproduced with: 0.10.6

Additional context

Likely common validation gap

At current main, verifyRepoCar() verifies the commit and derives a diff from the loaded MST.

deserializeNodeData() reconstructs each key from p and k, then calls ensureValidMstKey(). That path does not verify that:

p is the longest possible shared prefix;
each key's derived layer matches its node;
each child is exactly one layer below its parent;
each subtree key falls within the link's ordering bounds; or
the collection segment is a normalized NSID.

The serializer produces canonical nodes, but the untrusted decoder accepts noncanonical nodes.

Source: bluesky-social/atproto

View original on GitHub View discussion on GitHub