SECCON Quals 2022 - Noiseccon

Last modification on

Challenge

Noise! Noise! Noise!

Challenge Files | Solution Files

index.js
const { noise } = require("./perlin.js");
const sharp = require("sharp");
const crypto = require("node:crypto");
const readline = require("node:readline").promises;

const FLAG = process.env.FLAG ?? console.log("No flag") ?? process.exit(1);
const WIDTH = 256;
const HEIGHT = 256;

console.log(
  `   _   _       _             ____                           _
  | \\ | | ___ (_)___  ___   / ___| ___ _ __   ___ _ __ __ _| |_ ___  _ __
  |  \\| |/ _ \\| / __|/ _ \\ | |  _ / _ \\ '_ \\ / _ \\ '__/ _\` | __/ _ \\| '__|
  | |\\  | (_) | \\__ \\  __/ | |_| |  __/ | | |  __/ | | (_| | || (_) | |
  |_| \\_|\\___/|_|___/\\___|  \\____|\\___|_| |_|\\___|_|  \\__,_|\\__\\___/|_|
  `
);

console.log(`Flag length: ${FLAG.length}`);
console.log(`Image width: ${WIDTH}`);
console.log(`Image height: ${HEIGHT}`);

const paddedFlag = [
  ...crypto.randomBytes(8), // random prefix
  ...Buffer.from(FLAG),
  ...crypto.randomBytes(8), // random suffix
];

// bytes_to_long
let flagInt = 0n;
for (const b of Buffer.from(paddedFlag)) {
  flagInt = (flagInt << 8n) | BigInt(b);
}

const generateNoise = async (scaleX, scaleY) => {
  const div = (x, y) => {
    const p = 4;
    return Number(BigInt.asUintN(32 + p, (x * BigInt(1 << p)) / y)) / (1 << p);
  };

  const offsetX = div(flagInt, scaleX);
  const offsetY = div(flagInt, scaleY);

  noise.seed(crypto.randomInt(65536));
  const colors = [];
  for (let y = 0; y < HEIGHT; y++) {
    for (let x = 0; x < WIDTH; x++) {
      let v = noise.perlin2(offsetX + x * 0.05, offsetY + y * 0.05);
      v = (v + 1.0) * 0.5; // [-1, 1] -> [0, 1]
      colors.push((v * 256) | 0);
    }
  }

  const image = await sharp(Uint8Array.from(colors), {
    raw: {
      width: WIDTH,
      height: HEIGHT,
      channels: 1,
    },
  })
    .webp({ lossless: true })
    .toBuffer();
  return image;
};

const main = async () => {
  const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
    terminal: false,
  });

  const toBigInt = (value) => {
    if (value.length > 100) {
      console.log(`Invalid value: ${value}`);
      process.exit(1);
    }
    const result = BigInt(value);
    if (result <= 0n) {
      console.log(`Invalid value: ${value}`);
      process.exit(1);
    }
    return result;
  };

  const query = async () => {
    const scaleX = toBigInt(await rl.question("Scale x: "));
    const scaleY = toBigInt(await rl.question("Scale y: "));

    const image = await generateNoise(scaleX, scaleY);
    console.log(image.toString("base64"));
  };
  await query();

  rl.close();
};

main();

Overview

We are presented with source code of a NodeJS applet that returns a portion of a seeded noise field dependent on the flag contents and user input. The goal is to choose the user input in such a way that the flag may be recovered by determining the offset of the values returned by the service inside the noise field.

Analysis

On every request, the service returns a 256x256 webp 8-bit grayscale image containing values from a randomly seeded perlin noise field.

const FLAG = process.env.FLAG ?? console.log("No flag") ?? process.exit(1);
const WIDTH = 256;
const HEIGHT = 256;

const paddedFlag = [
  ...crypto.randomBytes(8), // random prefix
  ...Buffer.from(FLAG),
  ...crypto.randomBytes(8), // random suffix
];

let flagInt = 0n;
for (const b of Buffer.from(paddedFlag)) {
  flagInt = (flagInt << 8n) | BigInt(b);
}

const generateNoise = async (scaleX, scaleY) => {
  const div = (x, y) => {
    const p = 4;
    return Number(BigInt.asUintN(32 + p, (x * BigInt(1 << p)) / y)) / (1 << p);
  };

  const offsetX = div(flagInt, scaleX);
  const offsetY = div(flagInt, scaleY);

  noise.seed(crypto.randomInt(65536));
  const colors = [];
  for (let y = 0; y < HEIGHT; y++) {
    for (let x = 0; x < WIDTH; x++) {
      let v = noise.perlin2(offsetX + x * 0.05, offsetY + y * 0.05);
      v = (v + 1.0) * 0.5; // [-1, 1] -> [0, 1]
      colors.push((v * 256) | 0);
    }
  }

  const image = await sharp(Uint8Array.from(colors), {
    raw: {
      width: WIDTH,
      height: HEIGHT,
      channels: 1,
    },
  })
    .webp({ lossless: true })
    .toBuffer();
  return image;
};

.. with the scaleX and scaleY paramters controlled by user input:

const query = async () => {
  const scaleX = toBigInt(await rl.question("Scale x: "));
  const scaleY = toBigInt(await rl.question("Scale y: "));

  const image = await generateNoise(scaleX, scaleY);
  console.log(image.toString("base64"));
};
await query();

The program uses div to perform an integer division with limited precision p on flagInt using scaleX and scaleY to generate offsetX and offsetY. These offsets are then used to sample the 256x256 field with step size 0.05.

A straight-forward approach to recover the flag is to determine either offsetX or offsetY by searching for the returned values in the seeded noise field. By repeating this for varying values of scaleX or scaleY one can retrieve all parts of the flag. A naive bruteforce would require 65536 iterations to guess the correct seed, 256 * 2^p * 256 * 2^p iterations to guess the correct offsetX and offsetY, and 256 * 256 comparisons to determine wether the returned values match.

The runtime complexity of the search may be improved by reducing the size of the subfield used to verify whether a position is correct e.g. 40 * 40 is sufficient. Next, we may set scaleY to a large value (larger than flagInt * 2^p) such that offsetY is fixed to 0, since the flag can be leaked via offsetX alone. This way, only 256 * 2^p iterations are needed to guess the correct offsetX, 65536 iterations to guess the correct seed and 40 * 40 comparisons are needed to verify that a correct offsetX and seed were found.

Exploit

The offset search is implemented in NodeJS to ensure that the noise field we compare the values returned by the service to matches the server's.

solve.py
from pwn import *
from base64 import b64decode
import subprocess

def extract_char(index):
    io = remote("noiseccon.seccon.games", 1337)

    scalex = 1 << (64 + index * 8)
    scaley = "9" * 100

    io.readuntil(b"Flag length: ")
    flaglen = int(io.readline())

    io.readuntil(b"Image width: ")
    width = int(io.readline())

    io.readuntil(b"Image height: ")
    height = int(io.readline())

    print(flaglen, width, height)

    io.readuntil(b"Scale x: ")
    io.sendline(str(scalex).encode())

    io.readuntil(b"Scale y: ")
    io.sendline(str(scaley).encode())

    data = b64decode(io.readline().strip())
    with open("tmp.webp", "wb+") as f:
        f.write(data)
    io.close()

    output = subprocess.check_output(["node", "findoff.js"])
    indexlines = [l for l in output.split(b"\n") if l.startswith(b"IDX ")]
    indexes = set([int(l.split()[1]) for l in indexlines])
    print(len(indexes), indexes)

    return chr(list(indexes)[0])

flag = ""
for i in range(40):
    if flag.startswith("SECCON"):
        break
    flag = extract_char(i) + flag
print(flag)

findoff.js
const { noise } = require("./perlin.js");
const { argv } = require("process");
const crypto = require("node:crypto");
const sharp = require("sharp");
const fs = require("fs");

const WIDTH = 256;
const HEIGHT = 256;

const main = async() => {
    var buffer = fs.readFileSync("tmp.webp")
    const image = await sharp(buffer, {
            webp: {
                width: WIDTH,
                height: HEIGHT,
                channels: 1
            }
        }).raw().toBuffer()
    var ivals = Uint8Array.from(image);
    console.log(ivals.length, 256 * 256 * 3)

    for (let seed = 0; seed < 65536; seed++) {
        noise.seed(seed);
        for (let ox = 0; ox < 256; ox++) {
            for (let p = 0; p < 16; p++) {
                let match = true;
                for (let y = 0; y < 40; y++) {
                    for (let x = 0; x < 40; x++) {
                        let v = noise.perlin2(ox + p * 0.0625 + x * 0.05, y * 0.05);
                        v = (v + 1.0) * 0.5;
                        v = (v * 256) | 0;
                        if (ivals[(y * 256 + x) * 3] != v) {
                            match = false;
                            break;
                        }
                    }
                    if (!match)
                        break;
                }
                if (match)
                    console.log("IDX", ox);
            }
        }
    }
}

main();