SCTF The Last Honest Witness Writeup

#!/usr/bin/env node
const fs = require("fs");
const path = require("path");
const { execFileSync } = require("child_process");
const circomlibjs = require("circomlibjs");
const { solvePageA, solvePageC } = require("./solve_fixed");

const EXTERNAL_NULLIFIER = 48879n;
const LEAF_COUNT = 32;
const RECIPIENT_COMMITMENT =
  9377985761090098792458769157668700179213141594497154267610801610404565099971n;

const PAGE_B_V = "28";
const PAGE_B_R = "0xc3349965986bd706337e04fd1a6a740e1f759a5d95ec4d2854655fc414ec6402";
const PAGE_B_S = "0x432d7ce0d69b4a37abd4504c03aac315e27d666b6720d0624a2d2984cfcd346a";

function usage() {
  console.error("usage: RPC=<url> SETUP=<addr> PRIVATE_KEY=<key> node solve_remote.js");
  process.exit(2);
}

function sh(cmd, args, opts = {}) {
  const out = execFileSync(cmd, args, {
    cwd: opts.cwd || __dirname,
    encoding: "utf8",
    stdio: opts.stdio || ["ignore", "pipe", "pipe"],
    env: process.env,
  });
  return out == null ? "" : out.trim();
}

function parseHexWord(s, name) {
  const m = s.match(/0x[0-9a-fA-F]+/);
  if (!m) throw new Error(`missing hex word for${name}:${s}`);
  return BigInt(m[0]);
}

function parseAddress(s, name) {
  const words = [...s.matchAll(/0x[0-9a-fA-F]{40,64}/g)].map((m) => m[0]);
  if (words.length === 0) throw new Error(`missing address for${name}:${s}`);
  const word = words[words.length - 1];
  return "0x" + word.slice(-40);
}

function mod(a, n) {
  const r = a % n;
  return r >= 0n ? r : r + n;
}

function egcd(a, b) {
  let x0 = 1n, x1 = 0n;
  while (b !== 0n) {
    const q = a / b;
    [a, b] = [b, a - q * b];
    [x0, x1] = [x1, x0 - q * x1];
  }
  return [a, x0];
}

function inv(a, n) {
  const [g, x] = egcd(mod(a, n), n);
  if (g !== 1n) throw new Error(`inverse does not exist, gcd=${g}`);
  return mod(x, n);
}

function modPow(base, exp, n) {
  base = mod(base, n);
  let result = 1n;
  while (exp > 0n) {
    if (exp & 1n) result = (result * base) % n;
    base = (base * base) % n;
    exp >>= 1n;
  }
  return result;
}

function isqrt(n) {
  if (n < 0n) throw new Error("negative sqrt");
  if (n < 2n) return n;
  let x0 = 1n << BigInt((n.toString(2).length + 1) >> 1);
  while (true) {
    const x1 = (x0 + n / x0) >> 1n;
    if (x1 >= x0) return x0;
    x0 = x1;
  }
}

function fermatFactor(n, maxIterations = 10000000) {
  let a = isqrt(n);
  if (a * a < n) a++;
  for (let i = 0; i <= maxIterations; i++) {
    const b2 = a * a - n;
    const b = isqrt(b2);
    if (b * b === b2) {
      const p = a - b;
      const q = a + b;
      if (p > 1n && p * q === n) return p < q ? [p, q, i] : [q, p, i];
    }
    a++;
  }
  throw new Error(`Fermat factorization exceeded${maxIterations} iterations`);
}

async function buildPrimitives() {
  const poseidon = await circomlibjs.buildPoseidon();
  const field = poseidon.F;
  const hash = (values) => BigInt(field.toString(poseidon(values)));
  return {
    commitment: (plaintext) => hash([1n, plaintext]),
    identitySecret: (plaintext, p, q) => hash([2n, plaintext, p, q, EXTERNAL_NULLIFIER]),
    leaf: (identity, commitment) => hash([3n, identity, commitment]),
    node: (left, right) => hash([4n, left, right]),
    nullifierHash: (identity) => hash([5n, identity, EXTERNAL_NULLIFIER]),
    emptyLeaf: (index) => hash([6n, BigInt(index), EXTERNAL_NULLIFIER]),
  };
}

async function merkleData(p, q, plaintext) {
  const h = await buildPrimitives();
  const activeIndex = Number((plaintext + p + q) % BigInt(LEAF_COUNT));
  const commitment = h.commitment(plaintext);
  const identitySecret = h.identitySecret(plaintext, p, q);
  const nullifierHash = h.nullifierHash(identitySecret);
  const leaves = Array.from({ length: LEAF_COUNT }, (_, i) => h.emptyLeaf(i));
  leaves[activeIndex] = h.leaf(identitySecret, commitment);

  const pathElements = [];
  const pathIndices = [];
  let pos = activeIndex;
  let level = leaves;
  while (level.length > 1) {
    pathElements.push(level[pos ^ 1]);
    pathIndices.push(pos & 1);
    const next = [];
    for (let i = 0; i < level.length; i += 2) next.push(h.node(level[i], level[i + 1]));
    level = next;
    pos = Math.floor(pos / 2);
  }

  return {
    activeIndex,
    commitment,
    identitySecret,
    nullifierHash,
    merkleRoot: level[0],
    input: {
      p: p.toString(),
      q: q.toString(),
      plaintext: plaintext.toString(),
      pathElements: pathElements.map((x) => x.toString()),
      pathIndices: pathIndices.map((x) => x.toString()),
      modulus: (p * q).toString(),
      merkleRoot: level[0].toString(),
      recipientCommitment: commitment.toString(),
      nullifierHash: nullifierHash.toString(),
      externalNullifier: EXTERNAL_NULLIFIER.toString(),
    },
  };
}

function arrayArg(value) {
  if (Array.isArray(value)) return `[${value.map(arrayArg).join(",")}]`;
  return value.toString();
}

async function main() {
  const rpc = process.env.RPC;
  const setup = process.env.SETUP;
  const privateKey = process.env.PRIVATE_KEY;
  if (!rpc || !setup || !privateKey) usage();

  const challenge = parseAddress(
    sh("cast", ["call", setup, "challenge()(address)", "--rpc-url", rpc]),
    "challenge",
  );
  const modulus = parseHexWord(sh("cast", ["storage", setup, "1", "--rpc-url", rpc]), "setup.slot1");
  const publicExponent = parseHexWord(sh("cast", ["storage", setup, "2", "--rpc-url", rpc]), "setup.slot2");
  const ciphertext = parseHexWord(sh("cast", ["storage", setup, "3", "--rpc-url", rpc]), "setup.slot3");
  const chainRoot = parseHexWord(sh("cast", ["storage", challenge, "3", "--rpc-url", rpc]), "challenge.slot3");

  console.log(`[chain] challenge=${challenge}`);
  console.log(`[chain] modulus=${modulus}`);
  console.log(`[chain] publicExponent=${publicExponent}`);
  console.log(`[chain] ciphertext=${ciphertext}`);
  console.log(`[chain] merkleRoot(slot3)=${chainRoot}`);

  const [p, q, fermatIterations] = fermatFactor(modulus);
  const phi = (p - 1n) * (q - 1n);
  const d = inv(publicExponent, phi);
  const plaintext = modPow(ciphertext, d, modulus);
  if (modPow(plaintext, publicExponent, modulus) !== ciphertext) {
    throw new Error("RSA plaintext check failed");
  }
  console.log(`[rsa] p=${p}`);
  console.log(`[rsa] q=${q}`);
  console.log(`[rsa] fermatIterations=${fermatIterations}`);
  console.log(`[rsa] plaintext=${plaintext}`);

  const data = await merkleData(p, q, plaintext);
  if (data.commitment !== RECIPIENT_COMMITMENT) {
    throw new Error(`recipient commitment mismatch:${data.commitment}`);
  }
  if (data.merkleRoot !== chainRoot) {
    throw new Error(`computed root${data.merkleRoot} != chain root${chainRoot}`);
  }
  console.log(`[merkle] activeIndex=${data.activeIndex}`);
  console.log(`[merkle] nullifierHash=${data.nullifierHash}`);

  const runDir = path.join(__dirname, "run");
  fs.mkdirSync(runDir, { recursive: true });
  const inputPath = path.join(runDir, "input.json");
  const proofPath = path.join(runDir, "proof.json");
  const publicPath = path.join(runDir, "public.json");
  fs.writeFileSync(inputPath, JSON.stringify(data.input, null, 2) + "\n");

  const snarkjs = path.join(__dirname, "node_modules", ".bin", "snarkjs");
  sh(snarkjs, [
    "groth16",
    "fullprove",
    inputPath,
    path.resolve(__dirname, "../../extracted/zk/LastHonestWitness.wasm"),
    path.resolve(__dirname, "../../extracted/zk/LastHonestWitness_final.zkey"),
    proofPath,
    publicPath,
  ], { stdio: ["ignore", "inherit", "inherit"] });
  const calldata = sh(snarkjs, ["zkey", "export", "soliditycalldata", publicPath, proofPath]);
  const [proofA, proofB, proofC, publicSignals] = JSON.parse(`[${calldata}]`);

  const pageAPlaintext = solvePageA().toString();
  const [pageCLeft, pageCRight] = solvePageC();
  const signature =
    "claim(uint256[2],uint256[2][2],uint256[2],uint256[5],uint256,uint8,bytes32,bytes32,uint256,uint256)";
  const args = [
    "send",
    challenge,
    signature,
    arrayArg(proofA),
    arrayArg(proofB),
    arrayArg(proofC),
    arrayArg(publicSignals),
    pageAPlaintext,
    PAGE_B_V,
    PAGE_B_R,
    PAGE_B_S,
    pageCLeft.toString(),
    pageCRight.toString(),
    "--rpc-url",
    rpc,
    "--private-key",
    privateKey,
  ];
  console.log("[tx] submitting claim");
  console.log(sh("cast", args));

  const solved = sh("cast", ["call", challenge, "isSolved()(bool)", "--rpc-url", rpc]);
  console.log(`[check] isSolved=${solved}`);

  if (solved === "true" && process.env.TEAM_TOKEN) {
    console.log("[flag] fetching platform flag");
    console.log(sh("python3", [path.resolve(__dirname, "../platform.py"), "flag", process.env.TEAM_TOKEN]));
  } else if (solved === "true") {
    console.log("[flag] TEAM_TOKEN is not set; run `python3 ../platform.py flag\"$TEAM_TOKEN\"` to print the flag.");
  }
}

main().catch((err) => {
  console.error(err.stack || err.message);
  process.exit(1);
});