# Subleq64 - zer0pts CTF 2021
###### tags: `zer0pts CTF 2021` `misc`

## 概要
なんかOISCのesolangコードが渡される。
実行するとだんだん出力が遅くなり、36hで終わるか不明。

$ ./a.out test.sq 
GO
zer0pts{OISC_1s_

## 解析
出力時に対象となるメモリアドレスを調べると、6170であると分かる。
まずはここに書き込みしているやつを調べる。
書き込みはBレジスタを使うので、その参照を見る。

print(pc, a, b, hex(memory[a]), hex(memory[b]))

こんな感じ

609 6170 6170 0x0 0x0
627 6168 6170 -0x17d9 0x0
654 6170 6170 0x17d9 0x17d9
660 6174 6170 -0x22 0x0
675 6174 6170 0x0 0x22
747 6170 6170 0x22 0x22
765 6169 6170 0x0 0x0
1757 6170 6170 0x0 0x0
1775 6168 6170 -0x5851f42d4c957f2d 0x0
2006 6170 6170 0x5851f42d4c957f2d 0x5851f42d4c957f2d
...
...
...

0x5851f42d4c957f2dってのはコード先頭の方にある6364136223846793005から来ているはず。
見ると最後に6168から6170にデータが移ってる。

3240 6168 6170 -0x1454568c2ff9bb7a 0x0

ので今度は6168を見る。同様に6189, 6174, 6169と追う。ここで始めてmov以外の操作がある。

1085 6174 6169 -0x22 0x0
1091 6171 6169 -0x1454568c2ff9bb58 0x22

まずは0x22の出処を追う。
最初にこの値が現れる箇所を調べる。

        if memory[b] == 0x22 or memory[b] == -0x22:
            print(pc, a, b, memory[b], memory[a])

すると6105からやってきたと分かる。固定データかを調べるためこの周辺を見る。

print(memory[6105:6105+10])
>> [34, 70, 194, 23, 42, 149, 207, 118, 189, 238]

これは明らかにメモリアドレスっぽくないので、たぶんこれの配列$\delta_i$が次のように使われているんだと想像が付く。
0以上の整数$x$を受け取る関数$F(x)$が存在し、

$$\mathit{flag}_i = F(i) - \delta_i$$

によりフラグが作られるんじゃないかな。

次に-0x1454568c2ff9bb58の出処を追う。なんとなく上に辿ると

237 6 6169 0x14057b7ef767814f 0x2859d20b27613ca7

ってのがあり、このsubで-0x1454568c2ff9bb58が作られている。
0x14057b7ef767814fは6番目にある固定データ。

ところでこの固定データでぐぐると、こいつがヒットする。
https://en.wikipedia.org/wiki/Linear_congruential_generator

もう一個の1442695040888963407からしてMMIXってのがそれっぽい。そして-802458212630453242はシードと思われる。
試しに回す。

#include <stdio.h>

int main() {
  long a = 6364136223846793005;
  long b = 1442695040888963407;
  long x = -802458212630453242;
  x = a * x + b;
  printf("%ld\n", x);
  x = a * x + b;
  printf("%ld\n", x);
  x = a * x + b;
  printf("%ld\n", x);
  return 0;
}

$ ./a.out 
-7904187076687966115
-1464890938902559576
-5755922903835546921

hex(-1464890938902559576)
'-0x1454568c2ff9bb58'

2つ目のやつはどこかで見覚えがある。
ということで、単純な乱数と差分の配列を使っているらしい。あとは何回乱数を回しているか。だんだん遅くなる挙動からして、乱数の生成回数が徐々に増えていってそう。
LCG自体は一般項の公式が求まるので、生成回数さえ分かればO(1)で計算が終わる。

最初の方の`zer0pts{OISC_1s`あたりまでは知っているので、それを元に生成回数を逆算する。

#include <stdio.h>

int delta[] = {34, 70, 194, 23, 42, 149, 207, 118, 189, 238, 163, 162, 97, 218, 119, 98, 74, 85, 43, 70, 80, 230, 160, 128, 176, 104, 30, 159, 74, 155, 201, 140, 10, 173, 175, 42, 219, 49, 244, 125, 63, 57, 83, 175, 211, 55, 200, 153, 185, 94, 239, 55, 190, 255, 18, 129, 9, 172, 186, 12};

int main() {
  const char *known = "zer0pts{OISC_1s";
  for (int i = 0; i < 14; i++) {
    long a = 6364136223846793005;
    long b = 1442695040888963407;
    long x = -802458212630453242;
    for (int j = 0; j < 0x10000; j++) {
      x = a * x + b;
      if (((delta[i] - x) & 0xff) == known[i]) {
        printf("%c: %i\n", known[i], j);
        break;
      }
    }
  }
  return 0;
}

ふーん

z: 1
e: 4
r: 9
0: 18
p: 35
t: 68
s: 133
{: 6
O: 7
I: 8
S: 9
C: 10
_: 11
1: 12

最初のは1, 2, 4, 8, 16, ...とも取れる。そのあとなぜ6,7,8になってるかはよく分からん。

#include <stdio.h>

int delta[] = {34, 70, 194, 23, 42, 149, 207, 118, 189, 238, 163, 162, 97, 218, 119, 98, 74, 85, 43, 70, 80, 230, 160, 128, 176, 104, 30, 159, 74, 155, 201, 140, 10, 173, 175, 42, 219, 49, 244, 125, 63, 57, 83, 175, 211, 55, 200, 153, 185, 94, 239, 55, 190, 255, 18, 129, 9, 172, 186, 12};

int main() {
  const char *known = "zer0pts{OISC_1s";
  int lp[] = {1, 4, 9, 18, 35, 68, 133, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58};
  for (int i = 0; i < sizeof(lp)/4; i++) {
    long a = 6364136223846793005;
    long b = 1442695040888963407;
    long x = -802458212630453242;
    for (int j = 0; j < lp[i] + 1; j++) {
      x = a * x + b;
    }
    printf("%c", (delta[i] - x) & 0xff);
  }
  putchar('\n');
  return 0;
}

おわり

zer0pts{OISC_1s_th3_futur3~0xbuyd0g3!0xb1tc01n$vCQW04nFV+Wz}