# 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 charactersat a time (after checking the length).It is possible to bruteforce the flag one char at a time and for this reason some counter-measuresagainst dynamic analysis have been added: the program will check itself by running another VM for some instructionssearching for newline characters.
### Solution
Both dynamic and static analysis are feasible.
_Dynamic analysis_ can be achieved by disabling the self check removingthe 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 biginstructions array (each number is an index into that array) and map out the program. The only instruction that takesan 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 somescript 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 generatingthe keys is:
```tsconst 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:
```tsconst 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 magicsconst { enc, magics1, magics2 } = encryptFlag(flag);
// Compute order of checksconst 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 argumentbuilder.loadFlag();
// Check we have the first argumentbuilder.dup().printNoIfFalse();
// Check the flag has the correct lengthbuilder.len().load(flag.length).eeq().printNoIfFalse();
// Check flag 4 chars at a timefor (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();```