doormile_backend/controllers/cxIdentifierScramble.go

package controllers

import (
	"crypto/hmac"
	"crypto/sha256"
	"encoding/binary"
	"os"
	"strings"

	"doormile/utils"
)

// Format-preserving scrambling for the customer-facing identifiers.
//
// THE PROBLEM. Both identifiers come off a Postgres sequence, because a
// sequence is the only generator here that can promise uniqueness — the columns
// are UNIQUE, and a random 8-digit id collides with ~43% probability by the
// ten-thousandth parcel, which would be a rider unable to complete a pickup.
// But a sequence is also readable: DMX10000042 and DMX10000043 are visibly
// adjacent, so anyone holding two numbers learns the throughput between them,
// and anyone holding one can guess its neighbours.
//
// THE FIX. Keep the sequence — keep its uniqueness guarantee — and pass the
// index through a bijection before formatting it. Same one-to-one property, so
// no two parcels can ever collide; unrelated outputs, so nothing is guessable
// from a neighbour.
//
// WHY NOT THE OBVIOUS TRICK. Multiplying by a number coprime with the domain is
// also a bijection and is one line. It is wrong here: a multi-destination
// pickup hands ONE customer three consecutive sequence values, so the
// differences between their three tracking numbers are all exactly the
// multiplier. One booking leaks the key, and the whole range becomes walkable.
// The mapping has to be non-linear.
//
// WHAT THIS IS. A 4-round balanced Feistel network keyed with HMAC-SHA256, plus
// cycle-walking to keep the result inside the digit range. A Feistel is a
// bijection for ANY round function — that is its defining property — so
// uniqueness survives regardless of the key. Cycle-walking (re-encrypt until
// the output lands in range) preserves bijectivity on the subset.
//
// WHAT THIS IS NOT. Not a security boundary. Every route that resolves a
// tracking number is already authenticated and owner-scoped, and that is what
// actually stops a stranger reading someone's parcel. This removes the
// information leak in the identifier itself, so the authorisation check is not
// the only thing standing between an outsider and your volume figures.

const (
	// Tracking numbers occupy DMX10000000..DMX99999999 — 90,000,000 values,
	// always eight digits so the format never changes width.
	cxTrackingBase   = 10_000_000
	cxTrackingDomain = 90_000_000
	// 28 bits (two 14-bit halves) is the smallest even split covering the
	// domain. Cycle-walking averages ~3 encryptions per id; each is four
	// HMACs, so this is microseconds.
	cxTrackingHalfBits = 14

	// Booking references occupy DM-100000..DM-999999 — 900,000 values, always
	// six digits.
	cxBookingBase   = 100_000
	cxBookingDomain = 900_000
	// 20 bits (two 10-bit halves). Cycle-walking averages ~1.2 encryptions.
	cxBookingHalfBits = 10

	// cxFeistelRounds. Four is the standard minimum for a Feistel to be a
	// strong pseudorandom permutation (Luby–Rackoff). More rounds cost HMACs
	// for no property this needs.
	cxFeistelRounds = 4

	// cxCycleWalkLimit bounds the walk so a pathological key can never hang a
	// request. Reaching it is astronomically unlikely — each step has a ~2/3
	// chance of landing in range for tracking numbers — and the caller falls
	// back to the plain sequence rather than failing a booking.
	cxCycleWalkLimit = 64
)

// cxScrambleKey keys the round function.
//
// Overridable via CX_ID_SCRAMBLE_KEY. Changing it changes every identifier
// minted AFTERWARDS and none already stored, so rotation is safe but leaves a
// visible discontinuity — there is no reason to rotate it, and a good reason
// not to.
//
// The built-in default is not a secret and is not pretending to be one. It
// exists so the scrambling works out of the box rather than being silently off
// on any deployment that forgot to set an env var — an identifier scheme that
// depends on configuration to be safe is one that will be unsafe somewhere.
var cxScrambleKey = func() []byte {
	if k := strings.TrimSpace(os.Getenv("CX_ID_SCRAMBLE_KEY")); k != "" {
		return []byte(k)
	}
	return []byte("doormile-cx-identifier-permutation-v1")
}()

// cxFeistelRound is the round function. It need not be invertible — a Feistel
// is a bijection whatever this returns — so any keyed mixing works, and HMAC
// gives good diffusion for four bytes of output.
func cxFeistelRound(half uint64, round int, key []byte) uint64 {
	var buf [9]byte
	binary.BigEndian.PutUint64(buf[:8], half)
	buf[8] = byte(round)

	mac := hmac.New(sha256.New, key)
	mac.Write(buf[:])
	sum := mac.Sum(nil)

	return uint64(binary.BigEndian.Uint32(sum[:4]))
}

// cxFeistelEncrypt permutes a value within 2^(2*halfBits).
//
// Bijective by construction: every round is invertible because the half that is
// mixed is carried forward untouched, so the whole network can be run
// backwards. That is the property the UNIQUE constraint depends on.
func cxFeistelEncrypt(x uint64, halfBits uint, key []byte) uint64 {
	mask := uint64(1)<<halfBits - 1
	left := (x >> halfBits) & mask
	right := x & mask

	for round := 0; round < cxFeistelRounds; round++ {
		left, right = right, left^(cxFeistelRound(right, round, key)&mask)
	}
	return (left << halfBits) | right
}

// cxPermuteIndex maps a sequence index onto a scattered index in the same
// domain, one-to-one.
//
// Cycle-walking: the Feistel operates on the whole power-of-two space, which is
// larger than the digit range, so an output that overshoots is re-encrypted
// until it lands inside. Re-encrypting a bijection is still a bijection on the
// subset, so no two indices can ever converge.
func cxPermuteIndex(index, domain uint64, halfBits uint) uint64 {
	if index >= domain {
		// Past the end of the fixed-width range. The caller handles this;
		// returning the index unchanged keeps the function total.
		return index
	}

	x := index
	for i := 0; i < cxCycleWalkLimit; i++ {
		x = cxFeistelEncrypt(x, halfBits, cxScrambleKey)
		if x < domain {
			return x
		}
	}

	// Unreachable in practice. Falling back to the sequential index keeps the
	// identifier unique — which is the property that must never break — and
	// loses only the scattering.
	utils.Warn("cxPermuteIndex: cycle walk did not converge, using the sequential index",
		"index", index, "domain", domain)
	return index
}

// cxScrambledTracking turns a sequence value into the eight digits after DMX.
//
// Returns ok=false once the sequence runs past the fixed-width range, so the
// caller can fall back to plain sequential formatting and let the identifier
// grow a digit rather than wrapping onto one already issued.
func cxScrambledTracking(seq int64) (uint64, bool) {
	if seq < cxTrackingBase {
		return 0, false
	}
	index := uint64(seq - cxTrackingBase)
	if index >= cxTrackingDomain {
		return 0, false
	}
	return cxTrackingBase + cxPermuteIndex(index, cxTrackingDomain, cxTrackingHalfBits), true
}

// cxScrambledBooking is the same for the six digits after DM-.
func cxScrambledBooking(seq int64) (uint64, bool) {
	if seq < cxBookingBase {
		return 0, false
	}
	index := uint64(seq - cxBookingBase)
	if index >= cxBookingDomain {
		return 0, false
	}
	return cxBookingBase + cxPermuteIndex(index, cxBookingDomain, cxBookingHalfBits), true
}