ログイン
編集不可のページディスカッション情報添付ファイル
CTF/Writeup/SECCON 2014 Quals Online Winter/The Golden Gate

MMA

The Golden Gate (Programming 400pts)

ユニバーサル基板上にゲートICを10個と,スイッチとLEDを8個ずつ配置して実際に製作されたエンコーダーの写真が与えられた。

ゲートICは調べてみるとNANDゲートが4つ入っていることがわかる。 裏表の写真を行き来しながら接続を確認して回路図に落とした。 スイッチは押すと0になるものと1になる物両方存在している。

circuit.jpg

この回路図を元にプログラムを作成して動作をシミュレーションした。 結論から言えば,依存関係順に並べれば一度に計算を終わらせることも可能であったが, フリップフロップが含まれていて順序回路になっている可能性もあったため結果が安定するまで繰り返し計算するように実装した。 どちらが上位ビットなのかわからなかったため,切り替えられるようにしてある。 また,与えられたのはエンコーダであるから,結果を逆引きして平文を求めている。

   1 #include <stdio.h>
   2 
   3 #define UPPER 0
   4 
   5 int nand(int x, int y) {
   6     return !(x && y);
   7 }
   8 
   9 int gate[10][5];
  10 unsigned char f(unsigned char x) {
  11     int i;
  12     int plus = 1;
  13 #if UPPER
  14     int sw1 =  !(x & 0x80);
  15     int sw2 =  !(x & 0x40);
  16     int sw3 = !!(x & 0x20);
  17     int sw4 = !!(x & 0x10);
  18     int sw5 =  !(x & 0x08);
  19     int sw6 = !!(x & 0x04);
  20     int sw7 =  !(x & 0x02);
  21     int sw8 = !!(x & 0x01);
  22 #else
  23     int sw1 =  !(x & 0x01);
  24     int sw2 =  !(x & 0x02);
  25     int sw3 = !!(x & 0x04);
  26     int sw4 = !!(x & 0x08);
  27     int sw5 =  !(x & 0x10);
  28     int sw6 = !!(x & 0x20);
  29     int sw7 =  !(x & 0x40);
  30     int sw8 = !!(x & 0x80);
  31 #endif
  32     for (i = 0; i < 100; i++) {
  33     gate[1][1] = nand(sw1, gate[8][2]);
  34     gate[1][2] = nand(gate[1][1], gate[8][2]);
  35     gate[1][3] = nand(gate[1][1], sw1);
  36     gate[1][4] = nand(gate[1][2], gate[1][3]);
  37     gate[2][1] = nand(plus, gate[3][1]);
  38     gate[2][2] = nand(gate[2][1], gate[3][2]);
  39     gate[2][3] = nand(gate[2][2], gate[3][3]);
  40     gate[2][4] = nand(gate[2][3], gate[3][4]);
  41     gate[3][1] = nand(plus, sw3);
  42     gate[3][2] = nand(sw3, gate[3][1]);
  43     gate[3][3] = nand(gate[2][2], gate[6][2]);
  44     gate[3][4] = nand(gate[3][3], gate[6][2]);
  45     gate[4][1] = nand(sw2, gate[5][1]);
  46     gate[4][2] = nand(gate[4][1], gate[5][2]);
  47     gate[4][3] = nand(gate[8][2], gate[5][3]);
  48     gate[4][4] = nand(gate[4][3], gate[5][4]);
  49     gate[5][1] = nand(sw2, sw4);
  50     gate[5][2] = nand(gate[5][1], sw4);
  51     gate[5][3] = nand(gate[8][2], gate[6][2]);
  52     gate[5][4] = nand(gate[5][3], gate[6][2]);
  53     gate[6][1] = nand(sw2, gate[7][1]);
  54     gate[6][2] = nand(gate[6][1], gate[7][2]);
  55     gate[6][3] = nand(gate[4][2], gate[7][3]);
  56     gate[6][4] = nand(gate[6][3], gate[7][4]);
  57     gate[7][1] = nand(sw2, sw3);
  58     gate[7][2] = nand(gate[7][1], sw3);
  59     gate[7][3] = nand(sw6, gate[4][2]);
  60     gate[7][4] = nand(gate[7][3], sw6);
  61     gate[8][1] = nand(sw6, gate[9][1]);
  62     gate[8][2] = nand(gate[8][1], gate[9][2]);
  63     gate[8][3] = nand(gate[6][2], gate[9][3]);
  64     gate[8][4] = nand(gate[8][3], gate[9][4]);
  65     gate[9][1] = nand(sw6, sw8);
  66     gate[9][2] = nand(gate[9][1], sw8);
  67     gate[9][3] = nand(gate[6][2], sw5);
  68     gate[9][4] = nand(gate[9][3], sw5);
  69     gate[0][1] = nand(sw7, sw2);
  70     gate[0][2] = nand(gate[0][1], sw2);
  71     gate[0][3] = nand(sw7, gate[0][1]);
  72     gate[0][4] = nand(gate[0][2], gate[0][3]);
  73     }
  74     int out1 = gate[1][4];
  75     int out2 = gate[2][4];
  76     int out3 = gate[2][2];
  77     int out4 = gate[4][4];
  78     int out5 = gate[0][4];
  79     int out6 = gate[6][4];
  80     int out7 = gate[4][2];
  81     int out8 = gate[8][4];
  82     x = 0;
  83 #if UPPER
  84     x |= out1 << 7;
  85     x |= out2 << 6;
  86     x |= out3 << 5;
  87     x |= out4 << 4;
  88     x |= out5 << 3;
  89     x |= out6 << 2;
  90     x |= out7 << 1;
  91     x |= out8 << 0;
  92 #else
  93     x |= out1 << 0;
  94     x |= out2 << 1;
  95     x |= out3 << 2;
  96     x |= out4 << 3;
  97     x |= out5 << 4;
  98     x |= out6 << 5;
  99     x |= out7 << 6;
 100     x |= out8 << 7;
 101 #endif
 102         x ^= 0xff;
 103     return x;
 104 }
 105 
 106 
 107 unsigned char table[256];
 108 void maketable() {
 109     int c;
 110     for (c = 0; c < 256; c++) {
 111         int c2 = f(c);
 112         table[c2] = c;
 113     }
 114 /*
 115     for (c = 0; c < 256; c++) {
 116         fprintf(stderr, "%02x ", table[c]);
 117         if (c % 16 == 15) 
 118             fprintf(stderr, "\n");
 119     }
 120     fprintf(stderr, "\n");
 121 //*/
 122 }
 123 
 124 int main(int argc, char **argv) {
 125     int i, j;
 126     for (i = 0; i < 10; i++) {
 127         for (j = 0; j < 5; j++) {
 128             gate[i][j] = 0;
 129         }
 130     }
 131     maketable();
 132     while (1) {
 133         int c = getchar();
 134         if (c == -1) break;
 135         if (*argv[1] == 'd')
 136             putchar(table[c]);
 137         else
 138             putchar(f(c));
 139     }
 140 }

これによりgzip圧縮されたフラグが得られた。

% make solve && ./solve d < ct | file -
cc     solve.c   -o solve
/dev/stdin: gzip compressed data, from Unix, last modified: Tue Nov 25 00:13:06 2014

% ./solve d < ct > result.gz 

% gzip -dc result.gz 
The flag is SECCON{Hlvd0toiXgloBhTM}

LEDが点灯するのは回路の出力が0になった時であることになかなか気づけなかった。

CTF/Writeup/SECCON 2014 Quals Online Winter/The Golden Gate (最終更新日時 2014-12-07 21:24:04 更新者 ytoku)