SpaghettiVM

TeamItaly CTF 2022

Spaghetti VM (8 solves)

Spaghetti VM is a custom Javascript VM that runs very simple instructions with only a stack available (no registers).

The input comes from the first command line argument (sys.argv[2]) and is checked 4 characters at a time (after checking the length). It is possible to bruteforce the flag one char at a time and for this reason some counter-measures against dynamic analysis have been added: the program will check itself by running another VM for some instructions searching for newline characters.

Solution

Both dynamic and static analysis are feasible.

Dynamic analysis can be achieved by disabling the self check removing the VMs inside the instructions, this can be achieved by simply deleting the for loop that is the core of the VM.

At this point the program can be run nicely formatted allowing to dump all instructions being called and the stack. Note that the same is possible by editing the formatted file and then uglifying it again.

As the flag check is done char by char one can identify === instructions that fail and slowly reconstruct the flag, be careful as the chars are checked in random order in groups of four.

Static analysis is probably slower but can be performed by manually identifying the instructions called from the big instructions array (each number is an index into that array) and map out the program. The only instruction that takes an argument is the LOAD one, the argument is the index of the number to be loaded from the data array. The original source for the challenge is ~900 lines as some operations need to be repeated, for this reason writing some script to parse the program to identify repeating patterns is advised.

The flag is checked by xoring each character with a key that is generated piece by piece, the JS code for generating the keys is:

const makeKey = (
  length: number,
  magic1: number,
  magic2: number
): { key: number[]; magics1: number[]; magics2: number[] } => {
  const key = [],
    magics1 = [],
    magics2 = [];
  for (let i = 0; i < Math.ceil(length / 4); i++) {
    magics1.push(magic1);
    magics2.push(magic2);

    const base = magic1 + magic2;
    key.push(base & 255);
    key.push((base >> 8) & 255);
    key.push((base >> 16) & 255);
    key.push((base >> 24) & 255);

    magic1 = magic2 ^ magic1 ^ ((magic1 << 26) | (magic1 >> 6)) ^ ((magic2 ^ magic1) << 9);
    magic2 = ((magic2 ^ magic1) << 13) | ((magic2 ^ magic1) >> 19);
  }

  return { key, magics1, magics2 };
};

Where magic1 and magic2 are hardcoded inside the program and loaded from 4 8-bits integers. There is no JS code for the checking portion as it has been written directly in the VM "language", but here's the snippet:

const encryptFlag = (flag: string): { enc: number[]; magics1: number[]; magics2: number[] } => {
  const { key, magics1, magics2 } = makeKey(
    flag.length,
    randomInt(0xffffffff),
    randomInt(0xffffffff)
  );
  return {
    enc: key.map((x, i) => x ^ flag.charCodeAt(i)),
    magics1,
    magics2
  };
};

// Encrypt flag and compute all magics
const { enc, magics1, magics2 } = encryptFlag(flag);

// Compute order of checks
const shuffleList = (() => {
  const list = [];
  for (let i = 0; i < 4; i++) list.push(i);
  list.sort(() => 0.5 - Math.random());
  return list;
})();

const builder = new ChallengeBuilder();

// Get first argument
builder.loadFlag();

// Check we have the first argument
builder.dup().printNoIfFalse();

// Check the flag has the correct length
builder.len().load(flag.length).eeq().printNoIfFalse();

// Check flag 4 chars at a time
for (let i = 0; i < Math.ceil(flag.length / 4); i++) {
  builder.loadMagic(magics1[i]).loadMagic(magics2[i]).add();

  // Check 4 chars in pre-computed random order
  for (let j = 0; j < shuffleList.length; j++) {
    if (j < shuffleList.length - 1) builder.dup();

    switch (shuffleList[j]) {
      case 0:
        builder
          .load(255)
          .and()
          .loadFlag()
          .load(i * 4)
          .char()
          .xor()
          .load(enc[i * 4])
          .eeq()
          .printNoIfFalse();
        break;
      case 1:
        builder
          .rsh(8)
          .load(255)
          .and()
          .loadFlag()
          .load(i * 4 + 1)
          .char()
          .xor()
          .load(enc[i * 4 + 1])
          .eeq()
          .printNoIfFalse();
        break;
      case 2:
        builder
          .rsh(16)
          .load(255)
          .and()
          .loadFlag()
          .load(i * 4 + 2)
          .char()
          .xor()
          .load(enc[i * 4 + 2])
          .eeq()
          .printNoIfFalse();
        break;
      case 3:
        builder
          .rsh(24)
          .load(255)
          .and()
          .loadFlag()
          .load(i * 4 + 3)
          .char()
          .xor()
          .load(enc[i * 4 + 3])
          .eeq()
          .printNoIfFalse();
        break;
    }
  }
}

builder.loadString('ok!!').print();