// The spaces building blocks (spec/SPACES.md, "The building blocks"), // written from that page with node's crypto alone, not from // @atproto/space: P-256 did:keys, the KEM shared secret, LtHash, record // CIDs, commit and record MACs and their headers, the HTTP Message // Signature of a space credential, // and STAR. The spaces run holds the test vectors in spec/interop/spaces to // this module and to the reference library both, so a vector both agree on // is one the page and the reference agree on. import crypto from 'node:crypto' import { blake3 } from '@noble/hashes/blake3' import { base58btc } from 'multiformats/bases/base58' import { base32 } from 'multiformats/bases/base32' import * as cborg from 'cborg' import { Token, Type } from 'cborg' export const hex = (b) => Buffer.from(b).toString('hex') export const unhex = (s) => Buffer.from(s, 'hex') const u16 = (n) => Buffer.from([n >> 8, n & 0xff]) // ---- DRISL ------------------------------------------------------------------ /// A CID link: tag 42 in DRISL, `{"$link": ""}` in JSON. export class Link { constructor(bytes) { this.bytes = Buffer.from(bytes) } toJSON() { return { $link: base32.encode(this.bytes) } } } const TAGS = [] TAGS[42] = (bytes) => { if (!(bytes instanceof Uint8Array) || bytes[0] !== 0) throw new Error('a CID link must be bytes starting 0x00') return new Link(bytes.subarray(1)) } const typeEncoders = { Object: (v) => (v instanceof Link ? [new Token(Type.tag, 42), new Token(Type.bytes, Buffer.concat([Buffer.from([0]), v.bytes]))] : null) } /// DRISL bytes as a value: CID links as `Link`, bytes as Uint8Array. export const decode = (bytes) => cborg.decode(bytes, { tags: TAGS }) /// A value as DRISL bytes: maps' keys sorted by length, then bytewise. export const encode = (v) => Buffer.from(cborg.encode(v, { typeEncoders })) // ---- P-256 keys and did:key (atproto/cryptography.md) ----------------------- const P256 = [0x80, 0x24] const K256 = [0xe7, 0x01] /// A P-256 keypair from its 32-byte private scalar. export function p256(privateKey) { const d = Buffer.concat([Buffer.alloc(Math.max(0, 32 - privateKey.length)), Buffer.from(privateKey)]) const ecdh = crypto.createECDH('prime256v1') ecdh.setPrivateKey(d) const uncompressed = ecdh.getPublicKey(undefined, 'uncompressed') const jwk = { kty: 'EC', crv: 'P-256', x: uncompressed.subarray(1, 33).toString('base64url'), y: uncompressed.subarray(33).toString('base64url'), d: d.toString('base64url') } return { ecdh, d, uncompressed, privateKey: crypto.createPrivateKey({ key: jwk, format: 'jwk' }), did: didKeyOf(uncompressed) } } /// A fresh P-256 keypair. export const newP256 = () => { const e = crypto.createECDH('prime256v1'); e.generateKeys(); return p256(e.getPrivateKey()) } /// The did:key of a P-256 public key, given as its 65-byte uncompressed point. export const didKeyOf = (uncompressed) => `did:key:${base58btc.encode(Uint8Array.from([...P256, ...crypto.ECDH.convertKey(Buffer.from(uncompressed), 'prime256v1', undefined, undefined, 'compressed')]))}` /// The uncompressed point of a P-256 did:key; throws for any other did:key, /// one that does not parse, or a point not on the curve (spec/SPACES.md, /// "P-256 did:keys"). export function p256Point(didKey) { if (typeof didKey !== 'string' || !didKey.startsWith('did:key:z')) throw new Error('not a did:key') const bytes = Buffer.from(base58btc.decode(didKey.slice('did:key:'.length))) if (bytes[0] !== P256[0] || bytes[1] !== P256[1]) throw new Error('not a P-256 did:key') if (bytes.length !== 35 || (bytes[2] !== 2 && bytes[2] !== 3)) throw new Error('not a compressed P-256 point') return crypto.ECDH.convertKey(bytes.subarray(2), 'prime256v1', undefined, undefined, 'uncompressed') } export const isK256DidKey = (s) => { try { const b = base58btc.decode(s.slice(8)); return b[0] === K256[0] && b[1] === K256[1] } catch { return false } } // ---- the KEM shared secret: HPKE secret export -------------------------------- const KEM_ID = Buffer.concat([Buffer.from('KEM'), u16(0x0010)]) const SUITE_ID = Buffer.concat([Buffer.from('HPKE'), u16(0x0010), u16(0x0001), u16(0xffff)]) const extract = (salt, ikm) => crypto.createHmac('sha256', salt).update(ikm).digest() const expand = (prk, info) => crypto.createHmac('sha256', prk).update(Buffer.concat([info, Buffer.from([1])])).digest() const labeledExtract = (id, salt, label, ikm) => extract(salt, Buffer.concat([Buffer.from('HPKE-v1'), id, Buffer.from(label), ikm])) const labeledExpand = (id, prk, label, info) => expand(prk, Buffer.concat([u16(32), Buffer.from('HPKE-v1'), id, Buffer.from(label), info])) export const MAC_INFO = Buffer.from('atproto-mac') /// DHKEM's shared secret from the 32-byte ECDH x-coordinate and the two /// uncompressed points, the key share's (`enc`) first. export const kemSecret = (dh, encPoint, authorPoint) => labeledExpand(KEM_ID, labeledExtract(KEM_ID, Buffer.alloc(0), 'eae_prk', dh), 'shared_secret', Buffer.concat([encPoint, authorPoint])) /// The exported secret: the key schedule in base mode, then the export with /// an empty exporter context. export function exportSecret(kem, info = MAC_INFO) { const empty = Buffer.alloc(0) const context = Buffer.concat([Buffer.from([0]), labeledExtract(SUITE_ID, empty, 'psk_id_hash', empty), labeledExtract(SUITE_ID, empty, 'info_hash', Buffer.from(info))]) const exporter = labeledExpand(SUITE_ID, labeledExtract(SUITE_ID, kem, 'secret', empty), 'exp', context) return labeledExpand(SUITE_ID, exporter, 'sec', empty) } /// The repo host's side: the author's private KEM key and the syncer's key /// share; `info` other than `atproto-mac` only for HPKE's own vector. export function decapsulate(authorPrivateKey, keyShare, info = MAC_INFO) { const author = p256(authorPrivateKey) const enc = p256Point(keyShare) return exportSecret(kemSecret(author.ecdh.computeSecret(enc), enc, author.uncompressed), info) } /// The syncer's side: a fresh key share and the secret it makes with the author's KEM key. export function encapsulate(authorKemDidKey, ephemeralPrivateKey = crypto.randomBytes(32)) { const eph = p256(ephemeralPrivateKey) const author = p256Point(authorKemDidKey) return { keyShare: eph.did, sharedSecret: exportSecret(kemSecret(eph.ecdh.computeSecret(author), eph.uncompressed, author)) } } // ---- LtHash and record CIDs ------------------------------------------------------ export class LtHash { state = new Uint16Array(1024) apply(element, sign) { const x = blake3(Buffer.from(element, 'utf8'), { dkLen: 2048 }) const v = new DataView(x.buffer, x.byteOffset, x.byteLength) for (let i = 0; i < 1024; i++) this.state[i] = (this.state[i] + sign * v.getUint16(i * 2, true)) & 0xffff return this } add(e) { return this.apply(e, 1) } remove(e) { return this.apply(e, -1) } bytes() { const b = Buffer.alloc(2048); for (let i = 0; i < 1024; i++) b.writeUInt16LE(this.state[i], i * 2); return b } digest() { return crypto.createHash('sha256').update(this.bytes()).digest() } } /// The binary CID of DRISL bytes: version 1, codec 0x71, sha-256. export const cidBytes = (drisl) => Buffer.concat([Buffer.from([0x01, 0x71, 0x12, 0x20]), crypto.createHash('sha256').update(drisl).digest()]) export const cidString = (bytes) => base32.encode(bytes) export const cidFromString = (s) => Buffer.from(base32.decode(s)) /// An RFC 9651 Dictionary, of the member forms these headers use: each value /// an Item (string, integer, token, byte sequence, boolean) or an Inner List /// of strings, with parameters. Throws on anything else. export function parseDictionary(text) { let i = 0 const s = text const out = new Map() const ows = () => { while (s[i] === ' ' || s[i] === '\t') i++ } const sp = () => { while (s[i] === ' ') i++ } const key = () => { const m = /^[a-z*][a-z0-9_\-.*]*/.exec(s.slice(i)) if (!m) throw new Error(`bad key at ${i}`) i += m[0].length return m[0] } const bareItem = () => { const c = s[i] if (c === '"') { let v = '' for (i++; ; i++) { if (i >= s.length) throw new Error('unterminated string') if (s[i] === '\\') { i++; if (s[i] !== '"' && s[i] !== '\\') throw new Error('bad escape'); v += s[i]; continue } if (s[i] === '"') { i++; return { type: 'string', value: v } } const code = s.charCodeAt(i) if (code < 0x20 || code > 0x7e) throw new Error('bad string char') v += s[i] } } if (c === ':') { const end = s.indexOf(':', i + 1) if (end < 0) throw new Error('unterminated byte sequence') const b64 = s.slice(i + 1, end) if (!/^[A-Za-z0-9+/]*={0,2}$/.test(b64)) throw new Error('bad base64') i = end + 1 return { type: 'bytes', value: Buffer.from(b64, 'base64') } } if (c === '?') { const v = s[i + 1]; if (v !== '0' && v !== '1') throw new Error('bad boolean'); i += 2; return { type: 'boolean', value: v === '1' } } const num = /^-?\d{1,15}(?![.\d])/.exec(s.slice(i)) if (num) { i += num[0].length; return { type: 'integer', value: Number(num[0]) } } const tok = /^[A-Za-z*][!#$%&'*+\-.^_`|~0-9A-Za-z:/]*/.exec(s.slice(i)) if (tok) { i += tok[0].length; return { type: 'token', value: tok[0] } } throw new Error(`bad item at ${i}`) } const params = () => { const p = new Map() while (s[i] === ';') { i++; sp(); const k = key(); let v = { type: 'boolean', value: true }; if (s[i] === '=') { i++; v = bareItem() } p.set(k, v) } return p } ows() if (i === s.length) return out for (;;) { const k = key() let member if (s[i] === '=') { i++ if (s[i] === '(') { i++ const items = [] for (;;) { sp() if (s[i] === ')') { i++; break } items.push({ ...bareItem(), params: params() }) if (s[i] !== ' ' && s[i] !== ')') throw new Error('bad inner list') } member = { type: 'list', items, params: params() } } else member = { ...bareItem(), params: params() } } else member = { type: 'boolean', value: true, params: params() } out.set(k, member) ows() if (i === s.length) return out if (s[i] !== ',') throw new Error(`expected , at ${i}`) i++ ows() if (i === s.length) throw new Error('trailing comma') } } const serializeItem = (it) => { if (it.type === 'string') return `"${it.value.replace(/[\\"]/g, (c) => `\\${c}`)}"` if (it.type === 'integer') return String(it.value) if (it.type === 'token') return it.value if (it.type === 'boolean') return it.value ? '?1' : '?0' if (it.type === 'bytes') return `:${Buffer.from(it.value).toString('base64')}:` throw new Error('cannot serialize') } const serializeParams = (p) => [...p].map(([k, v]) => (v.type === 'boolean' && v.value ? `;${k}` : `;${k}=${serializeItem(v)}`)).join('') /// An Inner List as RFC 9651 serializes it. export const serializeInnerList = (m) => `(${m.items.map((it) => serializeItem(it) + serializeParams(it.params)).join(' ')})${serializeParams(m.params)}` /// An RFC 9651 Dictionary as RFC 9651 serializes it, from `parseDictionary`'s form. export const serializeDictionary = (d) => [...d].map(([k, m]) => { if (m.type === 'list') return `${k}=${serializeInnerList(m)}` if (m.type === 'boolean' && m.value) return `${k}${serializeParams(m.params)}` return `${k}=${serializeItem(m)}${serializeParams(m.params)}` }).join(', ') // ---- HTTP Message Signatures (RFC 9421) --------------------------------------------- /// The members of a parsed Dictionary tagged `tag` (spec/SPACES.md, "HTTP /// Message Signatures"): `[label, Inner List]` pairs. export const tagged = (d, tag) => [...d].filter(([, m]) => m.type === 'list' && m.params.get('tag')?.type === 'string' && m.params.get('tag').value === tag) /// The signature base: one line per component, then `@signature-params`. export const httpSignatureBase = (lines, signatureParams) => [...lines, `"@signature-params": ${signatureParams}`].join('\n') // ---- MACs ------------------------------------------------------------------------------ export const COMMIT_PROFILE = 'atproto-space-commit' export const RECORD_PROFILE = 'atproto-space-record' /// The covered headers' values: a commit's fields, a record's URI and CID. export const commitHeader = ({ ver = 1, repo, space, rev, data }) => `ver=${ver}, repo=${serializeItem({ type: 'string', value: repo })}, space=${serializeItem({ type: 'string', value: space })}, rev=${serializeItem({ type: 'string', value: rev })}, data=:${Buffer.from(data).toString('base64')}:` export const recordHeader = (uri, cid) => `uri=${serializeItem({ type: 'string', value: uri })}, cid=${serializeItem({ type: 'string', value: cid })}` /// A syncer's `Accept-Signature` for `profile`. export const formatMacRequest = (profile, keyShare, { label = 'mac', alg = false } = {}) => `${label}=("${profile}";sf);keyid="${keyShare}";tag="${profile}"${alg ? ';alg="hmac-sha256"' : ''}` /// How a repo host reads `Accept-Signature` for `profile`: undefined when it /// asks for no MAC, else `{label, keyShare, signatureParams}`; throws when it /// is refused. Whether the key share is a P-256 did:key is decapsulation's /// to check. export function parseMacRequest(value, profile) { if (value === undefined || value === null) return undefined const members = tagged(parseDictionary(value), profile) if (!members.length) return undefined if (members.length > 1) throw new Error('more than one MAC asked for the profile') const [label, m] = members[0] const it = m.items[0] if (m.items.length !== 1 || it.type !== 'string' || it.value !== profile || it.params.size !== 1 || it.params.get('sf')?.type !== 'boolean' || it.params.get('sf').value !== true) throw new Error('the MAC must cover exactly the profile\'s header, with sf') for (const k of m.params.keys()) if (!['keyid', 'tag', 'alg'].includes(k)) throw new Error(`unsupported parameter ${k}`) const alg = m.params.get('alg') if (alg && (alg.type !== 'string' || alg.value !== 'hmac-sha256')) throw new Error('alg must be hmac-sha256') const kid = m.params.get('keyid') if (kid?.type !== 'string') throw new Error('no keyid') return { label, keyShare: kid.value, signatureParams: serializeInnerList(m) } } export const hmac = (key, input) => crypto.createHmac('sha256', key).update(input).digest() /// The MAC's signature base, for the covered header's value as serialized. export const macBase = (profile, headerValue, signatureParams) => httpSignatureBase([`"${profile}";sf: ${headerValue}`], signatureParams) /// A repo host's answer to a MAC request: the three headers. export function macHeaders(profile, headerValue, request, sharedSecret) { const mac = hmac(sharedSecret, Buffer.from(macBase(profile, headerValue, request.signatureParams))) return { [profile]: headerValue, 'signature-input': `${request.label}=${request.signatureParams}`, signature: `${request.label}=:${mac.toString('base64')}:` } } /// Check a response's MAC as a syncer does, `headers` with lower-case /// names; answers the covered header as a parsed Dictionary, for the caller /// to hold to what the answer holds. Throws with why on any fault. export function verifyMac(profile, headers, { keyShare, sharedSecret }) { const { 'signature-input': input, signature, [profile]: covered } = headers if (typeof input !== 'string' || typeof signature !== 'string' || typeof covered !== 'string') throw new Error('missing MAC headers') const members = tagged(parseDictionary(input), profile) if (members.length !== 1) throw new Error(`${members.length} signatures tagged ${profile}`) const [label, m] = members[0] const it = m.items[0] if (m.items.length !== 1 || it.type !== 'string' || it.value !== profile || it.params.size !== 1 || it.params.get('sf')?.value !== true) throw new Error('wrong components') const kid = m.params.get('keyid') if (kid && (kid.type !== 'string' || kid.value !== keyShare)) throw new Error('keyid is not the key share asked with') const alg = m.params.get('alg') if (alg && (alg.type !== 'string' || alg.value !== 'hmac-sha256')) throw new Error('wrong alg') const s = parseDictionary(signature).get(label) if (!s || s.type !== 'bytes' || s.params.size || s.value.length !== 32) throw new Error('no 32-byte MAC for the label') const dict = parseDictionary(covered) const want = hmac(sharedSecret, Buffer.from(macBase(profile, serializeDictionary(dict), serializeInnerList(m)))) if (!crypto.timingSafeEqual(want, s.value)) throw new Error('MAC mismatch') return dict } /// Whether a verified `Atproto-Space-Commit` names exactly this commit. export function headerNamesCommit(dict, { ver = 1, repo, space, rev, data }) { const is = (k, type, v) => { const m = dict.get(k); return m?.type === type && !m.params.size && (type === 'bytes' ? Buffer.from(m.value).equals(Buffer.from(v)) : m.value === v) } return dict.size === 5 && is('ver', 'integer', ver) && is('repo', 'string', repo) && is('space', 'string', space) && is('rev', 'string', rev) && is('data', 'bytes', data) } /// Whether a verified `Atproto-Space-Record` names exactly this record. export function headerNamesRecord(dict, uri, cid) { const is = (k, v) => { const m = dict.get(k); return m?.type === 'string' && !m.params.size && m.value === v } return dict.size === 2 && is('uri', uri) && is('cid', cid) } // ---- the HTTP Message Signature of a space credential -------------------------------- export const CREDENTIAL_TAG = 'atproto-space-credential' const COVERED = '("authorization" "atproto-space-audience")' export const signatureBase = (authorization, audience, signatureParams) => httpSignatureBase([`"authorization": ${authorization.trim()}`, `"atproto-space-audience": ${audience.trim()}`], signatureParams) /// Sign as a credential holder: the four headers. export function signCredential(key, credential, audience, { scheme = 'Atproto-Space-Credential', extra = '', label = 'sig' } = {}) { const authorization = `${scheme} ${credential}` const params = `${COVERED};tag="${CREDENTIAL_TAG}"${extra}` const sig = crypto.sign('sha256', Buffer.from(signatureBase(authorization, audience, params)), { key: key.privateKey, dsaEncoding: 'ieee-p1363' }) return { authorization, 'atproto-space-audience': audience, 'signature-input': `${label}=${params}`, signature: `${label}=:${sig.toString('base64')}:` } } /// Verify a request's signature against `keyId`, the credential's `cnf.kid`. /// Answers the signature base; throws with why on any fault. export function verifyCredential(headers, keyId) { const { authorization, 'atproto-space-audience': audience, 'signature-input': input, signature } = headers if (typeof authorization !== 'string' || !authorization) throw new Error('no authorization') if (typeof audience !== 'string' || !audience) throw new Error('no audience') if (typeof input !== 'string' || typeof signature !== 'string') throw new Error('no signature headers') const members = tagged(parseDictionary(input), CREDENTIAL_TAG) if (members.length !== 1) throw new Error(`${members.length} signatures tagged ${CREDENTIAL_TAG}`) const [label, m] = members[0] const s = parseDictionary(signature).get(label) if (!s || s.type !== 'bytes' || s.params.size) throw new Error('no signature for the label') const covered = `(${m.items.map((it) => (it.type === 'string' && !it.params.size ? `"${it.value}"` : '?')).join(' ')})` if (covered !== COVERED) throw new Error('wrong components') const alg = m.params.get('alg') if (alg && (alg.type !== 'string' || alg.value !== 'ecdsa-p256-sha256')) throw new Error('wrong alg') const kid = m.params.get('keyid') if (kid && (kid.type !== 'string' || kid.value !== keyId)) throw new Error('keyid mismatch') const point = p256Point(keyId) if (s.value.length !== 64) throw new Error('signature is not 64 bytes') const base = signatureBase(authorization, audience, serializeInnerList(m)) const pub = crypto.createPublicKey({ key: { kty: 'EC', crv: 'P-256', x: point.subarray(1, 33).toString('base64url'), y: point.subarray(33).toString('base64url') }, format: 'jwk' }) if (!crypto.verify('sha256', Buffer.from(base), { key: pub, dsaEncoding: 'ieee-p1363' }, s.value)) throw new Error('bad signature') return base } // ---- STAR (spec/spaces/star.md) --------------------------------------------------------- const varint = (n) => { const out = []; do { let b = n & 0x7f; n = Math.floor(n / 128); if (n) b |= 0x80; out.push(b) } while (n); return Buffer.from(out) } /// A STAR archive of `meta` (DRISL-encoded here) and `pairs` of byte keys and values. export function writeStar(meta, pairs) { const m = encode(meta) const parts = [Buffer.from([0x2a, 0x6c, 0x01, 0x00]), varint(m.length), m] for (const { key, value } of pairs) parts.push(Buffer.from([1]), varint(key.length), key, varint(value.length), value) parts.push(Buffer.from([0])) return Buffer.concat(parts) } /// Parse a whole STAR archive, as strictly as the spec asks; `limits` are a /// profile's `{meta, key, value}` maximum lengths. export function readStar(buf, limits = {}) { let i = 0 const vi = () => { let n = 0, mul = 1 const start = i for (;;) { if (i >= buf.length) throw new Error('unexpected end of archive') const b = buf[i++] n += (b & 0x7f) * mul if (!(b & 0x80)) break mul *= 128 if (i - start >= 9) throw new Error('varint too long') } if (i - start > 1 && buf[i - 1] === 0) throw new Error('non-minimal varint') return n } const take = (n, max, what) => { if (max !== undefined && n > max) throw new Error(`${what} over its limit`) if (i + n > buf.length) throw new Error('unexpected end of archive') const s = buf.subarray(i, i + n) i += n return Buffer.from(s) } if (!take(4).equals(Buffer.from([0x2a, 0x6c, 0x01, 0x00]))) throw new Error('bad magic') const metaBytes = take(vi(), limits.meta, 'metadata') const meta = decode(metaBytes) if (!meta || typeof meta !== 'object' || Array.isArray(meta) || meta instanceof Uint8Array || typeof meta.$type !== 'string') throw new Error('metadata must be a map with a string $type') if (!encode(meta).equals(metaBytes)) throw new Error('metadata is not canonical DRISL') const pairs = [] for (;;) { const c = take(1)[0] if (c === 0) break if (c !== 1) throw new Error(`invalid control byte ${c}`) const key = take(vi(), limits.key, 'key') const value = take(vi(), limits.value, 'value') pairs.push({ key, value }) } if (i !== buf.length) throw new Error('bytes after the end of the archive') return { meta, metaBytes, pairs } } export const REPO_LIMITS = { meta: 65536, key: 4096, value: 1048576 } /// Read an `atproto-space-repo` archive: its commit, and its records in order, /// each `{path, cid, bytes}`. With `expect` `{space, repo}`, the commit must /// name them; with `headers`, `keyShare` and `sharedSecret`, the response's /// commit MAC must check and its header name the commit. Throws with why on /// any fault, the digest too. export function readRepoStar(buf, { expect, keyShare, sharedSecret, headers } = {}) { const { meta, pairs } = readStar(buf, REPO_LIMITS) if (meta.$type !== 'atproto-space-repo') throw new Error('not an atproto-space-repo archive') if (meta.ver !== 1) throw new Error('unsupported commit version') for (const k of ['repo', 'space', 'rev']) if (typeof meta[k] !== 'string') throw new Error(`metadata ${k} is not a string`) if (!(meta.data instanceof Uint8Array) || meta.data.length !== 32) throw new Error('data is not 32 bytes') if (expect && (meta.space !== expect.space || meta.repo !== expect.repo)) throw new Error('archive names another repo') if (headers && !headerNamesCommit(verifyMac(COMMIT_PROFILE, headers, { keyShare, sharedSecret }), meta)) throw new Error('the MAC\'s header names another commit') const lt = new LtHash() let prev = null const records = [] for (const { key, value } of pairs) { const path = key.toString('utf8') if (!/^[a-zA-Z][a-zA-Z0-9.-]*\/[A-Za-z0-9._:~-]{1,512}$/.test(path) || !Buffer.from(path, 'utf8').equals(key)) throw new Error(`bad record path ${JSON.stringify(path)}`) if (prev && Buffer.compare(prev, key) >= 0) throw new Error('keys out of order or duplicated') prev = key const cid = cidString(cidBytes(value)) lt.add(`${path}/${cid}`) records.push({ path, cid, bytes: value }) } if (!lt.digest().equals(Buffer.from(meta.data))) throw new Error('digest mismatch') return { commit: meta, records } }