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();