HITCON CTF 2016 の write-up (RegExpert, ROP, moRE)

今回の [HITCON CTF 2016](https://ctf2016.hitcon.org/) は（も？）、あまりセキュリティっぽい問題は解けず、変な問題にはまってしまっていた。 とりあえず解けた問題RegExpertとROP、それからmoREについても解けたところまで、簡単なメモを書いておく。

## RegExpert

> Do you remember "hard to say" last year?
> I think this one is harder to say...
> nc 52.69.125.71 2171

指定のポートに接続すると、（拡張）正規表現のお題が５題出題され、送信するとサーバ側でテストされ、全部パスすればフラグがゲットできる。 割と普通のプログラミングコンテストっぽい。 セキュリティっぽい問題は他のメンバーがやるだろうから、とりあえず他のメンバーがやらなそうな問題をと思って挑戦してみる。

まず、最終的に全部解けたときのサーバ側とのやり取りを以下に示したうえで、その後各問題を解いた課程について書いていく。

```
$ nc 52.69.125.71 2171
Hi! We want to hire some TRUE regular expression hackers to write firewall rules.
So here are five interview questions for you, good luck!
Note: After CVE-2015-4410, we reject everything contains newline, so you can just safely use ^ and $ here.

================= [SQL] =================
Please match string that contains "select" as a case insensitive subsequence.
(?i:s.*e.*l.*e.*c.*t)
Running on test #885...Accepted :)

=============== [a^nb^n] ================
Yes, we know it is a classical example of context free grammer.
^(a\g<1>?b)$
Running on test #370...Accepted :)

================= [x^p] =================
A prime is a natural number greater than 1 that has no positive divisors other than 1 and itself.
^(?!(xx+)\1+$)xx+$
Running on test #304...Accepted :)

============= [Palindrome] ==============
Both "QQ" and "TAT" are palindromes, but "PPAP" is not.
^(.?|(.)\g<1>?\2)$
Running on test #799...Accepted :)

============== [a^nb^nc^n] ==============
Is CFG too easy for you? How about some context SENSITIVE grammer?
^(?=(a\g<1>?b)c)a*(b\g<2>?c)$
Running on test #504...Accepted :)

Congratz! Here is your singing bonus:
hitcon{The pumping lemma is a lie, just like the cake}
```

### (1) select

`[sS][eE][lL][eE][cC][tT]` としたら、「Running on test #7...Wrong Answer -- should match "GSVElEcT"」とエラーになってしまい、 `[sS].*[eE].*[lL].*[eE].*[cC].*[tT]` としたら今度は「Running on test #885...Almost there...But the length limit is 21」という結果に。 

`[sS].*[eE].*[lL].*[eE].*[cC].*[tT]`で34文字なので13文字削らないといけないけど、こんなのどうやって削るのだろう……と悩んでいたら、 `(?i:`と`)`で囲むことで`i`オプションを有効化するという方法をチームメイトが知っていて解決。 「`(?i:s.*e.*l.*e.*c.*t)`」でいけた。 21文字ジャスト。 これが想定解？

真面目な正規表現の問題ではなく、そういうテクを問う問題なのね。 でも、そうすると、どの言語でサポートされてる正規表現なのかが重要になりそう……

### (2) a^nb^n

適当にググって見つけた [How can we match a^n b^n with Java regex? - Stack Overflow](http://stackoverflow.com/questions/3644266/how-can-we-match-an-bn-with-java-regex) にPCREの`^(a(?1)?b)$`という正規表現があったので、これを試してみたところ、「Exception: RegexpError」というエラーに。

RegexpErrorという例外名を使うのは自分の知る限りRubyだけで、ググってみても他に見つからなかったので、Rubyの正規表現だろうとアタリをつけ、 [正規表現 (Ruby 2.3.0)](https://docs.ruby-lang.org/ja/2.3.0/doc/spec=2fregexp.html)を見てみると、 Rubyの正規表現にも部分式呼び出しの構文があるじゃん。

というわけで、`^(?<r>a\g<r>?b)$` (16文字) としたら、「Running on test #370...Almost there...But the length limit is 12」というエラーに。パターンを名前ではなく番号で参照するようにして、`^(a\g<1>?b)$` (12文字) で正解。

この問題でRubyと分かって、手元で試してから投稿できるようになり、その後の問題を解くのにだいぶ助かった。

### (3) x^p

ググって [正規表現で素数判定 - NO!と言えるようになりたい](http://d.hatena.ne.jp/ytakano/20100721/1279736214) を見つけたので、「おおー、面白い」と思いつつ、これを参考に `^(?!x?$|^(xx+?)\1+$)x*$` (23文字) でテストは通るけど文字数制限が上限18文字で文字数オーバー。 

ちょっと書き換えて `^(?!(xx+?)\1+$)x{2,}$` で20文字。 もうちょっと書き換えて `^(?!(xx+?)\1+$)xx+$` で19文字。 `?` が余計なことに気づいて、 `^(?!(xx+)\1+$)xx+$` で18文字。

（拡張）正規表現の先読みの機能って、使ったことなかったけれど、こんな感じに使うものなのか。

### (4) Palindrome

ここまでくれば特に難しいことは何もなく、 `^(.?|(.)\g<1>?\2)$` で解けた。

### (5) a^nb^nc^n

結構悩んだ結果、 `^(?=((?<r>a\g<r>?b)(?=c)))a*(?
b\g
?c)$` (43文字) という回答を思いつくも、文字数制限が上限29文字。 そういえば、PEGでa^nb^nc^nをパースするときもこんな感じで書くのだっけか。

ちょっと書き換えて、`^(?=((a\g<-1>?b)(?=c)))a*(b\g<-1>?c)$` で37文字。 もうちょっと書き換えて、`^(?=((a\g<2>?b)c))a*(b\g<3>?c)$` で31文字。 あと2文字をどうやって削るのかが分からなかったけれど、チームメンバーに見せたら、余計なカッコに気づいてくれて、 `^(?=(a\g<1>?b)c)a*(b\g<2>?c)$` (29文字) で解けた。

## moRE

> Hi, our RegExpert, I know you want moRE.
> nc 52.69.125.71 2172

ということで RegExpert の難しい版らしい。 こちらは最初の1問だけしか解けない状態で、コンテスト期間が終わってしまった……

```
$ nc 52.69.125.71 2172
Hi, our RegExpert, do you want one moRE flag? Solve these four :P

============== [Leap Year] ==============
Even my cat can code this 🐱
^(?=(0|[1-9]\d*)$)((?<r>(\d*[02468])?[048]|\d*[13579][26])00|(?!\d*00$)\g<r>)$
Running on test #6845...Accepted :)

=============== [x^(n^2)] ===============
We like squares: ■ □ ▢ ▣ ▤ ▥ ▦ ▧ ▨ ▩ ▪▫
Timeout ._./
$
```

### (1) Leap Year

猫まで使って、煽ってくるスタイルかよ。ぐぬぬ。

以下のような部品の正規表現を書いたうえで、それを先読みを使って組み合わた感じ。

* 数: `(0|[1-9]\d*)`
* 4の倍数: `(\d*[02468])?[048]|\d*[13579][26]`
* 400の倍数: `((\d*[02468])?[048]|\d*[13579][26])00`
* 100の倍数: `\d*00`

それだと文字数がオーバーしたので、「400の倍数」から「部分式呼び出し」で「4の倍数」のパターンを呼び出すようにして、長さを削減。

## ROP

> Who doesn't like ROP?
> Let's try some new features introduced in 2.3.
> 
> [rop.iseq](https://s3-ap-northeast-1.amazonaws.com/hitcon2016qual/rop.iseq_a9ac4b7a1669257d0914ca556a6aa6d14b4a2092)

rop.iseqのファイルの先頭が「YARB」で始まり、かつ自分的には「2.3 といえばRuby」という連想だったので、「えっ? またRuby?」と思って適当にググってみると、[Bytecode cache is experimentally released in Ruby2.3 | 48JIGEN *Reloaded*](http://rimuru.lunanet.gr.jp/blog/cruby-bytecode-cache-is-experimentally-released) というページが見つかった。 Rubyのバイトコードをダンプしたファイルっぽい。 そこからリンクされていた [Feature #11788: New ISeq serialize binary format - Ruby trunk - Ruby Issue Tracking System](https://bugs.ruby-lang.org/issues/11788) を読んで使い方をだいたい把握。

それで、ROP(Return-oriented Programming)要素がどこにあるのかは分からないけれど、とりあえずディスアセンブルしてみようと以下のようにしてみるも、「in `load_from_binary': unmatched platform (RuntimeError)」 でエラーに……

```ruby
binary = File.open("rop.iseq_a9ac4b7a1669257d0914ca556a6aa6d14b4a2092","rb"){|f| f.read }
s = RubyVM::InstructionSequence.load_from_binary(binary)
puts s.disasm
```

iseqファイル内には「x86_64-linux」とあったので、適当に Digital Occean で Ubuntu な droplet を作って試してみるも、やはり同じエラー。 この環境では `RUBY_PLATFORM` が「x86_64-linux-gnu」 だった……ぐぬぬ……

仕方ないので、Ruby-2.3.1 の compile.c で RUBY_PLATFORM と比較している部分をコメントアウトしてビルドして試す。 で、やっと読める命令列が得られた。

```
== disasm: #<ISeq:<compiled>@<compiled>>================================
== catch table
| catch type: break  st: 0096 ed: 0102 sp: 0000 cont: 0102
| catch type: break  st: 0239 ed: 0245 sp: 0000 cont: 0245
|------------------------------------------------------------------------
local table (size: 3, argc: 0 [opts: 0, rest: -1, post: 0, block: -1, kw: -1@-1, kwrest: -1])
[ 3] k          [ 2] xs         
0000 trace            1                                               (   1)
0002 putself          
0003 putstring        "digest"
0005 opt_send_without_block <callinfo!mid:require, argc:1, FCALL|ARGS_SIMPLE>, <callcache>
0008 pop              
0009 trace            1                                               (   2)
0011 putself          
0012 putstring        "prime"
0014 opt_send_without_block <callinfo!mid:require, argc:1, FCALL|ARGS_SIMPLE>, <callcache>
0017 pop              
0018 trace            1                                               (   4)
0020 putspecialobject 3
0022 putnil           
0023 defineclass      :String, <class:String>, 0
0027 pop              
0028 trace            1                                               (  22)
0030 putspecialobject 1
0032 putobject        :gg
0034 putiseq          gg
0036 opt_send_without_block <callinfo!mid:core#define_method, argc:2, ARGS_SIMPLE>, <callcache>
0039 pop              
0040 trace            1                                               (  27)
0042 putspecialobject 1
0044 putobject        :f
0046 putiseq          f
0048 opt_send_without_block <callinfo!mid:core#define_method, argc:2, ARGS_SIMPLE>, <callcache>
0051 pop              
0052 trace            1                                               (  38)
0054 getglobal        $stdin
0056 opt_send_without_block <callinfo!mid:gets, argc:0, ARGS_SIMPLE>, <callcache>
0059 opt_send_without_block <callinfo!mid:chomp, argc:0, ARGS_SIMPLE>, <callcache>
0062 setlocal_OP__WC__0 3
0064 trace            1                                               (  39)
0066 getlocal_OP__WC__0 3
0068 putstring        "-"
0070 opt_send_without_block <callinfo!mid:split, argc:1, ARGS_SIMPLE>, <callcache>
0073 setlocal_OP__WC__0 2
0075 trace            1                                               (  40)
0077 getlocal_OP__WC__0 2
0079 opt_size         <callinfo!mid:size, argc:0, ARGS_SIMPLE>, <callcache>
0082 putobject        5
0084 opt_eq           <callinfo!mid:==, argc:1, ARGS_SIMPLE>, <callcache>
0087 branchif         94
0089 putself          
0090 opt_send_without_block <callinfo!mid:gg, argc:0, FCALL|VCALL|ARGS_SIMPLE>, <callcache>
0093 pop              
0094 trace            1                                               (  41)
0096 getlocal_OP__WC__0 2
0098 send             <callinfo!mid:all?, argc:0>, <callcache>, block in <compiled>
0102 branchif         109
0104 putself          
0105 opt_send_without_block <callinfo!mid:gg, argc:0, FCALL|VCALL|ARGS_SIMPLE>, <callcache>
0108 pop              
0109 trace            1                                               (  42)
0111 getlocal_OP__WC__0 2
0113 putobject_OP_INT2FIX_O_0_C_ 
0114 opt_aref         <callinfo!mid:[], argc:1, ARGS_SIMPLE>, <callcache>
0117 putobject        16
0119 opt_send_without_block <callinfo!mid:to_i, argc:1, ARGS_SIMPLE>, <callcache>
0122 putobject        31337
0124 opt_eq           <callinfo!mid:==, argc:1, ARGS_SIMPLE>, <callcache>
0127 branchif         134
0129 putself          
0130 opt_send_without_block <callinfo!mid:gg, argc:0, FCALL|VCALL|ARGS_SIMPLE>, <callcache>
0133 pop              
0134 trace            1                                               (  43)
0136 getlocal_OP__WC__0 2
0138 putobject_OP_INT2FIX_O_1_C_ 
0139 opt_aref         <callinfo!mid:[], argc:1, ARGS_SIMPLE>, <callcache>
0142 opt_send_without_block <callinfo!mid:reverse, argc:0, ARGS_SIMPLE>, <callcache>
0145 putstring        "FACE"
0147 opt_eq           <callinfo!mid:==, argc:1, ARGS_SIMPLE>, <callcache>
0150 branchif         157
0152 putself          
0153 opt_send_without_block <callinfo!mid:gg, argc:0, FCALL|VCALL|ARGS_SIMPLE>, <callcache>
0156 pop              
0157 trace            1                                               (  44)
0159 putself          
0160 putobject        217
0162 getlocal_OP__WC__0 2
0164 putobject        2
0166 opt_aref         <callinfo!mid:[], argc:1, ARGS_SIMPLE>, <callcache>
0169 putobject        16
0171 opt_send_without_block <callinfo!mid:to_i, argc:1, ARGS_SIMPLE>, <callcache>
0174 putobject        314159
0176 opt_send_without_block <callinfo!mid:f, argc:3, FCALL|ARGS_SIMPLE>, <callcache>
0179 putobject        28
0181 opt_send_without_block <callinfo!mid:to_s, argc:1, ARGS_SIMPLE>, <callcache>
0184 opt_send_without_block <callinfo!mid:upcase, argc:0, ARGS_SIMPLE>, <callcache>
0187 putstring        "48D5"
0189 opt_eq           <callinfo!mid:==, argc:1, ARGS_SIMPLE>, <callcache>
0192 branchif         199
0194 putself          
0195 opt_send_without_block <callinfo!mid:gg, argc:0, FCALL|VCALL|ARGS_SIMPLE>, <callcache>
0198 pop              
0199 trace            1                                               (  45)
0201 getlocal_OP__WC__0 2
0203 putobject        3
0205 opt_aref         <callinfo!mid:[], argc:1, ARGS_SIMPLE>, <callcache>
0208 putobject        10
0210 opt_send_without_block <callinfo!mid:to_i, argc:1, ARGS_SIMPLE>, <callcache>
0213 opt_send_without_block <callinfo!mid:prime_division, argc:0, ARGS_SIMPLE>, <callcache>
0216 putobject        :first
0218 send             <callinfo!mid:map, argc:0, ARGS_BLOCKARG>, <callcache>, nil
0222 opt_send_without_block <callinfo!mid:sort, argc:0, ARGS_SIMPLE>, <callcache>
0225 duparray         [53, 97]
0227 opt_eq           <callinfo!mid:==, argc:1, ARGS_SIMPLE>, <callcache>
0230 branchif         237
0232 putself          
0233 opt_send_without_block <callinfo!mid:gg, argc:0, FCALL|VCALL|ARGS_SIMPLE>, <callcache>
0236 pop              
0237 trace            1                                               (  46)
0239 getlocal_OP__WC__0 2
0241 send             <callinfo!mid:map, argc:0>, <callcache>, block in <compiled>#
0245 putobject        :^
0247 opt_send_without_block <callinfo!mid:inject, argc:1, ARGS_SIMPLE>, <callcache>
0250 opt_send_without_block <callinfo!mid:to_s, argc:0, ARGS_SIMPLE>, <callcache>
0253 opt_send_without_block <callinfo!mid:sha1, argc:0, ARGS_SIMPLE>, <callcache>
0256 putstring        "947d46f8060d9d7025cc5807ab9bf1b3b9143304"
0258 opt_eq           <callinfo!mid:==, argc:1, ARGS_SIMPLE>, <callcache>
0261 branchif         268
0263 putself          
0264 opt_send_without_block <callinfo!mid:gg, argc:0, FCALL|VCALL|ARGS_SIMPLE>, <callcache>
0267 pop              
0268 trace            1                                               (  48)
0270 putself          
0271 putobject        "Congratz! flag is "
0273 putstring        "bce410e85433ba94f0d832d99556f9764b220eeda7e807fe4938a5e6effa7d83c765e1795b6c26af8ad258f6"
0275 opt_send_without_block <callinfo!mid:dehex, argc:0, ARGS_SIMPLE>, <callcache>
0278 getlocal_OP__WC__0 3
0280 opt_send_without_block <callinfo!mid:sha1, argc:0, ARGS_SIMPLE>, <callcache>
0283 opt_send_without_block <callinfo!mid:dehex, argc:0, ARGS_SIMPLE>, <callcache>
0286 opt_send_without_block <callinfo!mid:^, argc:1, ARGS_SIMPLE>, <callcache>
0289 tostring         
0290 concatstrings    2
0292 opt_send_without_block <callinfo!mid:puts, argc:1, FCALL|ARGS_SIMPLE>, <callcache>
0295 leave            
== disasm: #<ISeq:<class:String>@<compiled>>============================
0000 trace            2                                               (   4)
0002 trace            1                                               (   5)
0004 putspecialobject 1
0006 putobject        :^
0008 putiseq          ^
0010 opt_send_without_block <callinfo!mid:core#define_method, argc:2, ARGS_SIMPLE>, <callcache>
0013 pop              
0014 trace            1                                               (   9)
0016 putspecialobject 1
0018 putobject        :sha1
0020 putiseq          sha1
0022 opt_send_without_block <callinfo!mid:core#define_method, argc:2, ARGS_SIMPLE>, <callcache>
0025 pop              
0026 trace            1                                               (  13)
0028 putspecialobject 1
0030 putobject        :enhex
0032 putiseq          enhex
0034 opt_send_without_block <callinfo!mid:core#define_method, argc:2, ARGS_SIMPLE>, <callcache>
0037 pop              
0038 trace            1                                               (  17)
0040 putspecialobject 1
0042 putobject        :dehex
0044 putiseq          dehex
0046 opt_send_without_block <callinfo!mid:core#define_method, argc:2, ARGS_SIMPLE>, <callcache>
0049 trace            4                                               (  20)
0051 leave                                                            (  17)
== disasm: #<ISeq:^@<compiled>>=========================================
== catch table
| catch type: break  st: 0004 ed: 0015 sp: 0000 cont: 0015
|------------------------------------------------------------------------
local table (size: 2, argc: 1 [opts: 0, rest: -1, post: 0, block: -1, kw: -1@-1, kwrest: -1])
[ 2] other<Arg> 
0000 trace            8                                               (   5)
0002 trace            1                                               (   6)
0004 putself          
0005 opt_send_without_block <callinfo!mid:bytes, argc:0, ARGS_SIMPLE>, <callcache>
0008 opt_send_without_block <callinfo!mid:map, argc:0, ARGS_SIMPLE>, <callcache>
0011 send             <callinfo!mid:with_index, argc:0>, <callcache>, block in ^
0015 putstring        "C*"
0017 opt_send_without_block <callinfo!mid:pack, argc:1, ARGS_SIMPLE>, <callcache>
0020 trace            16                                              (   7)
0022 leave                                                            (   6)
== disasm: #<ISeq:block in ^@<compiled>>================================
== catch table
| catch type: redo   st: 0002 ed: 0027 sp: 0000 cont: 0002
| catch type: next   st: 0002 ed: 0027 sp: 0000 cont: 0027
|------------------------------------------------------------------------
local table (size: 3, argc: 2 [opts: 0, rest: -1, post: 0, block: -1, kw: -1@-1, kwrest: -1])
[ 3] x<Arg>     [ 2] i<Arg>     
0000 trace            256                                             (   6)
0002 trace            1
0004 getlocal_OP__WC__0 3
0006 getlocal_OP__WC__1 2
0008 getlocal_OP__WC__0 2
0010 getlocal_OP__WC__1 2
0012 opt_size         <callinfo!mid:size, argc:0, ARGS_SIMPLE>, <callcache>
0015 opt_mod          <callinfo!mid:%, argc:1, ARGS_SIMPLE>, <callcache>
0018 opt_aref         <callinfo!mid:[], argc:1, ARGS_SIMPLE>, <callcache>
0021 opt_send_without_block <callinfo!mid:ord, argc:0, ARGS_SIMPLE>, <callcache>
0024 opt_send_without_block <callinfo!mid:^, argc:1, ARGS_SIMPLE>, <callcache>
0027 trace            512
0029 leave            
== disasm: #<ISeq:sha1@<compiled>>======================================
0000 trace            8                                               (   9)
0002 trace            1                                               (  10)
0004 getinlinecache   13, <is:0>
0007 getconstant      :Digest
0009 getconstant      :SHA1
0011 setinlinecache   <is:0>
0013 putself          
0014 opt_send_without_block <callinfo!mid:hexdigest, argc:1, ARGS_SIMPLE>, <callcache>
0017 trace            16                                              (  11)
0019 leave                                                            (  10)
== disasm: #<ISeq:enhex@<compiled>>=====================================
0000 trace            8                                               (  13)
0002 trace            1                                               (  14)
0004 putself          
0005 putstring        "H*"
0007 opt_send_without_block <callinfo!mid:unpack, argc:1, ARGS_SIMPLE>, <callcache>
0010 putobject_OP_INT2FIX_O_0_C_ 
0011 opt_aref         <callinfo!mid:[], argc:1, ARGS_SIMPLE>, <callcache>
0014 trace            16                                              (  15)
0016 leave                                                            (  14)
== disasm: #<ISeq:dehex@<compiled>>=====================================
0000 trace            8                                               (  17)
0002 trace            1                                               (  18)
0004 putself          
0005 newarray         1
0007 putstring        "H*"
0009 opt_send_without_block <callinfo!mid:pack, argc:1, ARGS_SIMPLE>, <callcache>
0012 trace            16                                              (  19)
0014 leave                                                            (  18)
== disasm: #<ISeq:gg@<compiled>>========================================
0000 trace            8                                               (  22)
0002 trace            1                                               (  23)
0004 putself          
0005 putstring        "Invalid Key @_@"
0007 opt_send_without_block <callinfo!mid:puts, argc:1, FCALL|ARGS_SIMPLE>, <callcache>
0010 pop              
0011 trace            1                                               (  24)
0013 putself          
0014 putobject_OP_INT2FIX_O_1_C_ 
0015 opt_send_without_block <callinfo!mid:exit, argc:1, FCALL|ARGS_SIMPLE>, <callcache>
0018 trace            16                                              (  25)
0020 leave                                                            (  24)
== disasm: #<ISeq:f@<compiled>>=========================================
== catch table
| catch type: break  st: 0021 ed: 0086 sp: 0000 cont: 0086
| catch type: next   st: 0021 ed: 0086 sp: 0000 cont: 0018
| catch type: redo   st: 0021 ed: 0086 sp: 0000 cont: 0021
|------------------------------------------------------------------------
local table (size: 6, argc: 3 [opts: 0, rest: -1, post: 0, block: -1, kw: -1@-1, kwrest: -1])
[ 6] a<Arg>     [ 5] b<Arg>     [ 4] m<Arg>     [ 3] s          [ 2] r          
0000 trace            8                                               (  27)
0002 trace            1                                               (  28)
0004 putobject_OP_INT2FIX_O_1_C_ 
0005 setlocal_OP__WC__0 3
0007 trace            1                                               (  29)
0009 getlocal_OP__WC__0 6
0011 setlocal_OP__WC__0 2
0013 trace            1                                               (  30)
0015 jump             75
0017 putnil           
0018 pop              
0019 jump             75
0021 trace            1                                               (  31)
0023 getlocal_OP__WC__0 5
0025 putobject_OP_INT2FIX_O_0_C_ 
0026 opt_aref         <callinfo!mid:[], argc:1, ARGS_SIMPLE>, <callcache>
0029 putobject_OP_INT2FIX_O_1_C_ 
0030 opt_eq           <callinfo!mid:==, argc:1, ARGS_SIMPLE>, <callcache>
0033 branchunless     49
0035 getlocal_OP__WC__0 3
0037 getlocal_OP__WC__0 2
0039 opt_mult         <callinfo!mid:*, argc:1, ARGS_SIMPLE>, <callcache>
0042 getlocal_OP__WC__0 4
0044 opt_mod          <callinfo!mid:%, argc:1, ARGS_SIMPLE>, <callcache>
0047 setlocal_OP__WC__0 3
0049 trace            1                                               (  32)
0051 getlocal_OP__WC__0 5
0053 putobject_OP_INT2FIX_O_1_C_ 
0054 opt_send_without_block <callinfo!mid:>>, argc:1, ARGS_SIMPLE>, <callcache>
0057 setlocal_OP__WC__0 5
0059 trace            1                                               (  33)
0061 getlocal_OP__WC__0 2
0063 getlocal_OP__WC__0 2
0065 opt_mult         <callinfo!mid:*, argc:1, ARGS_SIMPLE>, <callcache>
0068 getlocal_OP__WC__0 4
0070 opt_mod          <callinfo!mid:%, argc:1, ARGS_SIMPLE>, <callcache>
0073 setlocal_OP__WC__0 2
0075 getlocal_OP__WC__0 5                                             (  30)
0077 putobject_OP_INT2FIX_O_0_C_ 
0078 opt_neq          <callinfo!mid:!=, argc:1, ARGS_SIMPLE>, <callcache>, <callinfo!mid:==, argc:1, ARGS_SIMPLE>, <callcache>
0083 branchif         21
0085 putnil           
0086 pop              
0087 trace            1                                               (  35)
0089 getlocal_OP__WC__0 3
0091 trace            16                                              (  36)
0093 leave                                                            (  35)
== disasm: #<ISeq:block in <compiled>@<compiled>>=======================
== catch table
| catch type: redo   st: 0002 ed: 0011 sp: 0000 cont: 0002
| catch type: next   st: 0002 ed: 0011 sp: 0000 cont: 0011
|------------------------------------------------------------------------
local table (size: 2, argc: 1 [opts: 0, rest: -1, post: 0, block: -1, kw: -1@-1, kwrest: -1])
[ 2] x<Arg>     
0000 trace            256                                             (  41)
0002 trace            1
0004 getlocal_OP__WC__0 2
0006 putobject        /^[0-9A-F]{4}$/
0008 opt_regexpmatch2 <callinfo!mid:=~, argc:1, ARGS_SIMPLE>, <callcache>
0011 trace            512
0013 leave            
== disasm: #<ISeq:block in <compiled>@<compiled>>=======================
== catch table
| catch type: redo   st: 0002 ed: 0011 sp: 0000 cont: 0002
| catch type: next   st: 0002 ed: 0011 sp: 0000 cont: 0011
|------------------------------------------------------------------------
local table (size: 2, argc: 1 [opts: 0, rest: -1, post: 0, block: -1, kw: -1@-1, kwrest: -1])
[ 2] x<Arg>     
0000 trace            256                                             (  46)
0002 trace            1
0004 getlocal_OP__WC__0 2
0006 putobject        16
0008 opt_send_without_block <callinfo!mid:to_i, argc:1, ARGS_SIMPLE>, <callcache>
0011 trace            512
0013 leave            
```

10年前くらいにYARVのバイトコードをいじってたころと比べると、命令融合とか色々入って、複雑になってるなぁ。 とりあえず、厳密な読み方の確認は置いておいて、フィーリングで頑張ってデコンパイルっぽいことをしてみた結果が以下。 （疲れた……）

```ruby
require 'digest'
require 'prime'

class String
  def sha1
    Digest::SHA1.hexdigest(self)
  end

  def enhex
    unpack("H*")
  end
  
  def dehex
    pack("H*")
  end
end

def gg
  puts "Invalid Key @_@"
  exit
end

def f(local6, local5, local4)
  # local6 a
  # local5 b
  # local4 m
  # local3 s
  # local2 r
  
  # 04
  local3 = 1
  # 09
  local2 = local6

  # jump 75

  # 75
  while local5 != 0    
    # 21-33
    unless local5[0] == 1
      # 49
    else
      # 35-47
      local3 = (local3 * local2) % local4
    end
    # 49-57
    local5 = local5 >> 1
    # 59-73
    local2 = (local2 * local2) % local4
  end
  # 85
  nil
  local3
end

local3 = $stdin.gets.chomp
local2 = local3.split("-")
if local2.size == 5 then
  if local2.all?{|x| /^[0-9A-F]{4}$/ =~ x }
    if local2[0].to_i(16) == 31337
      if local2[1].reverse == "FACE"
        if f(217, local2[2].to_i(16), 314159).to_s(28).upcase == "48D5"
          if local2[3].to_i(10).prime_division.map(:first).sort == [53,97]
            if local2.map{|x| x.to_i(16) }.inject(:^).to_s.sha1 == "947d46f8060d9d7025cc5807ab9bf1b3b9143304"
              puts("Congratz! flag is " + ("bce410e85433ba94f0d832d99556f9764b220eeda7e807fe4938a5e6effa7d83c765e1795b6c26af8ad258f6".dehex ^ local3.sha1.dehex).to_s)
            else
              gg
            end
          else
            gg
          end
        else
          gg
        end
      else
        gg
      end
    else
      gg
    end
  else
    gg
  end  
else
  gg
end
```

「Congratz!」と出力されるパスにいたる入力を求めれば良いという、ありがちなパターンの問題。

入力は4桁の16進数を4つハイフンでつないだものであり、ここではそのそれぞれをlocal2という配列にいれている。その要素の値のそれぞれ以下で求めていく。

### local2[0]

`local2[0].to_i(16) == 31337` から `local2[0]` は `"7A69"` であることが分かる。

### local2[1]

`local2[1].reverse == "FACE"` から `local2[1]` は `"ECAF"` であることが分かる。

### local2[2]

`f(217, local2[2].to_i(16), 314159).to_s(28).upcase == "48D5"` から、`f(217, local2[2].to_i(16), 314159) == 94449` であり、以下のように探索すれば、`local2[2]` は `"1BD2"` であることが分かる。

```ruby
(0..0xFFFF).each{|x|
  printf("%04X\n", x) if f(217, x, 314159) == 94449
  # => 1BD2
}
```

### local2[3]

`local2[3].to_i(10).prime_division.map(:first).sort == [53,97]` から `local2[3].to_i(10)` の素因数が53と97であることが分かり、`local2[3].to_i(10)`は 53*97=5141 の倍数であることが分かるが、`local2[3]`は4文字なので`"5141"`で確定。

### local2[4]

`local2[4]`は以下のように探索して、`"CA72"` であることがわかった。

```ruby
(0..0xFFFF).each{|x|
  local2 = format("7A69-ECAF-1BD2-5141-%04X", x).split("-")
  if local2.map{|x| x.to_i(16) }.inject(:^).to_s.sha1 == "947d46f8060d9d7025cc5807ab9bf1b3b9143304"
    printf("%04X\n", x) #=> CA72
  end
}
```

### フラグの取得

以上から入力が「7A69-ECAF-1BD2-5141-CA72」であるときに、「Congratz!」と出力されるパスが実行されることがわかった。 そこで irb 上で実際にこの入力を与えてみると、フラグがゲットできた。

```
> binary = File.open("rop.iseq_a9ac4b7a1669257d0914ca556a6aa6d14b4a2092","rb"){|f| f.read }
> s = RubyVM::InstructionSequence.load_from_binary(binary)
> s.eval
7A69-ECAF-1BD2-5141-CA72
Congratz! flag is hitcon{ROP = Ruby Obsecured Programming ^_<}
```

ディスアセンブル結果の読み方をちゃんと確認せずに、デコンパイルをすごくいい加減にしかやってなかったので、どこかにミスがあって上手くいかないのではと心配だったけれど、細かいミスでちょっと詰まったりはしたものの、ちゃんと解けてちょっとビックリ。 

しかし、ROPってそういうことかよ……

ちなみに、この問題を解いた2番目のチームだったっぽい。 最終的には29チームも解いてるけれど。