HITCON CTF 2016 RegExpert and moRE writeup

RegExpert

RegExpert
59 Teams solved.
Description
Do you remember "hard to say" last year?
I think this one is harder to say...
nc 52.69.125.71 2171
Hint
None
% cat regexp
(?i)s.*e.*l.*e.*c.*t
^(a\g<1>?b)$
^(?!(xx+)\1+$)xx+$
^((.)\g<1>\2|.?)$
(?=^(a\g<1>?b)c)a+(b\g<2>?c)$
% cat regexp - | 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.
Running on test #885...Accepted :)

=============== [a^nb^n] ================
Yes, we know it is a classical example of context free grammer.
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.
Running on test #304...Accepted :)

============= [Palindrome] ==============
Both "QQ" and "TAT" are palindromes, but "PPAP" is not.
Running on test #799...Accepted :)

============== [a^nb^nc^n] ==============
Is CFG too easy for you? How about some context SENSITIVE grammer?
Running on test #504...Accepted :)

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

moRE

We were not able to solve this challenge in time (20 minutes delay). However, we answered all of the “questions.” So, I wrote this writeup.

11 Teams solved.
Description
Hi, our RegExpert, I know you want moRE.
nc 52.69.125.71 2172
Hint
None

First and Last of this challenge were solved by @satos___jp

% cat moRE
^(0|[1-9]\d*0000|(4|8|(([1-9]\d*|)([13579][26]|[2468][048])|[1-9]\d*0[48]))(00|))$
(xx\k<1+0>|^x)+$
(?=^-?([0369]|[147][0369]*[258]|(([258]|[147][0369]*[147])([0369]|[258][0369]*[147])*([147]|[258][0369]*[258])))+$)(?=^-?.*[02468]$)(?=^-?(?!$)(?>(|(?<B>4\g<A>|5\g<B>|6\g<C>|[07]\g<D>|[18]\g<E>|[29]\g<F>|3\g<G>))(|(?<C>[18]\g<A>|[29]\g<B>|3\g<C>|4\g<D>|5\g<E>|6\g<F>|[07]\g<G>))(|(?<D>5\g<A>|6\g<B>|[07]\g<C>|[18]\g<D>|[29]\g<E>|3\g<F>|4\g<G>))(|(?<E>[29]\g<A>|3\g<B>|4\g<C>|5\g<D>|6\g<E>|[07]\g<F>|[18]\g<G>))(|(?<F>6\g<A>|[07]\g<B>|[18]\g<C>|[29]\g<D>|3\g<E>|4\g<F>|5\g<G>))(|(?<G>3\g<A>|4\g<B>|5\g<C>|6\g<D>|[07]\g<E>|[18]\g<F>|[29]\g<G>)))(?<A>$|[07]\g<A>|[18]\g<B>|[29]\g<C>|3\g<D>|4\g<E>|5\g<F>|6\g<G>)+$)(^((?!-?0).+|0)$)
(?!,)(?=^(.\g<1>.|,)$)(|((0|1))\g<2>),(|(?!\k<3+0>)[01]\g<5>)$
% cat moRE - | 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 🐱
Running on test #6845...Accepted :)

=============== [x^(n^2)] ===============
We like squares: ■ □ ▢ ▣ ▤ ▥ ▦ ▧ ▨ ▩ ▪▫
Running on test #517...Accepted :)

=========== [Multiple of 42] ============
The answer to life the universe and everything.
Running on test #1601...Accepted :)

============= [Complement] ==============
Please match x,~x where x is a binary string. Like "0,1" or "1001,0110".
Running on test #1870...Accepted :)

Congratz! You are now our CRO (Chief Regular Officer).
ATTENTION! HUGE GIFT IS COMING!
3...2...1...

(...sorry I cut the last part)

The last [Complement] is a little tricky. The essense of the answer is

^(|((0|1))\g<2>),(|(?!\k<3+0>)[01]\g<5>)$
(when extracted, ^(|((0|1))\g<2>),(|(?!\k<2+0>)[01]\g<4>)$ is correct)

First (|((0|1))\g<2>) matches the sequence of 0,1 and each value has own nest by the recursion. Because there is ‘,’ after this part, as a whole, this part matches x of “x,~x”.

Next (|(?!\k<3+0>)[01]\g<5>) is a little tricky(and this is the point of this question). In order to make the regexp easier, I want to show another equivalent regex.

^(?<first>|((?<value>0|1))\g<first>),(?<second>|(?!\k<value+0>)[01]\g<second>)$

so, we can see \k\<value+0> of (?!\k<value+0) references at (?\0|1) of the same nest. As you know, (?! means NOT and as a whole, (?!\k<value+0) means the same order of ~x value (because the next part [01] limits that there are only 0 or 1). So, this will pass the 1870 tests.

Last part of this challenge(decoding given “huge gift”) is explained there.

今年の総括

もうすぐ今年も終わりらしいので、一応今年を振り返りたいなと思います。

1月から2月にかけて、絶対JOI春合宿行こうな!っていう気分で、蟻本を読みつつ、競プロなどをしていました。死んでからは、競技プログラミングという分野が見えなくなりました。

でしたが、なんか科オリというものに未練が残ったので、物理チャレンジ予選に出ました。封筒が送られてきたので、通ったのかなと思ったら通っていました。本戦は計10時間小さな箱の中に佇んでいましたが、結果銅賞(19~30位)でした。銅が、JOIとJPhOで定義が違いすぎるなと思いました。


f:id:moratorium08:20151231210459p:plain
↑去年よりたくさん書けたので、来年はもう少し色々かける一年でありますようにといった感じです。来年も頑張りたいと思います。

あけましておめでとうございます

今年は昨年以上に忙しくなる一年だと思うので、頑張りたいと思います。

年賀状情報です。
f:id:moratorium08:20150101004726p:plain

今年もよろしくおねがいします。目標として、昨年はここで足し算を目標としたので、今年は引き算の習得を目指して行こうと思います。

定期試験とはナップザック問題のようなもの

以下試験からの逃避文章です。

定期試験とはナップザック問題のようなものだと思います。時間という有限の制限以下で、評価を最大化するためにどの勉強をするかを選ぶからそんな感じが。夏休みという時間を何一つ定期試験のために過ごしてこなかったから、あと数日でうわあぁって感じで、感覚で計画をしていくわけだから、ヤバいなという感じです。期末があるととてもソシャゲが捗りますね。最近は日本語の書き方も分からないのでとりあえず理数系科目だけでも拾って行けたらなって思いますよね・・・

Raspberry PiでL-03FでdocomoのXiを使ってネットをしてみる

かなり色々と試行したので、無駄な処理が入っている可能性があるのですが、とりあえず、やっとことをまとめてみます。一応、Linuxdocomoのサポート外なので、以下も自己責任でお願いします(主にパケ死などに)。

参考にさせてもらったのは、

Qaplaの覚書・メモ・備忘録・独言 Raspberry Pi をUSBモデムでインターネット接続
OBDNマガジン: [.tested] docomo L-03D [AX3][A6]
ubuntu 9.04 で docomo L-02A を使う | azkの日記 | スラッシュドット・ジャパン
あたりだとおもいます。

まず、他の記事でもたくさんかかれているように、windows/mac上でのゼロインストールのために、CD/DVDとして、/dev/sr0でlinuxが反応してしまうので、とりあえず、usbに認識させるという動作を行います。usb_modeswtichを使うということを試行しましたが、うまく動かなかったので、sudo apt-get install ejectでejectを入れて、3つ目にあげたところでも書かれているように、

pi@raspberrypi ~ $ cat /etc/udev/rules.d/99-foma_l-02a.rules
KERNEL=="sr[0-9]*", ENV{ID_VENDOR_ID}=="1004", ENV{ID_MODEL_ID}=="6367", RUN+="/usr/bin/eject /dev/$kernel"

ACTION=="add" SUBSYSTEM=="usb", ATTR{idVendor}=="1004", ATTR{idProduct}=="6366", RUN+="/sbin/modprobe usbserial vendor=0x$attr{idVendor} product=0x$attr{idProduct}"

こういう感じで設定します。やってることとしては、usbにつながれたときにeject /dev/sr0を行なって(sr0以外も動くようになってますが)、usbserialをロードしています。これで、適当にさしなおしたり、リブートすると、こいつが動きます。すると、/dev/にttyUSB0,1,2が現れますが、たぶんl-03Fが新しいので、linuxがまだこのProdctIDが分からないのだと思う(というか、モデムモードに切り替えが必要なのだと思う)ので、ググると、optionをロードして、new_idにvendorid:productidをechoするみたいなのなどを試してみましたが、うまく動かないので、最終的に、

pi@raspberrypi ~ $ sudo usb_modeswitch -v 0x1004 -p 0x6366 -M "5553424308e02186000000000000061b000000020000000000000000000000"

Looking for default devices ...
   found matching product ID
   adding device
 Found device in default mode, class or configuration (1)
Accessing device 005 on bus 001 ...
Getting the current device configuration ...
 OK, got current device configuration (1)
Using first interface: 0x00
Using endpoints 0x01 (out) and 0x81 (in)
Not a storage device, skipping SCSI inquiry

USB description data (for identification)
-------------------------
Manufacturer: NTT DOCOMO, INC.
     Product: docomo L03F
  Serial No.: not provided
-------------------------
Looking for active driver ...
 OK, driver found ("usbserial_generic")
 OK, driver "usbserial_generic" detached
Setting up communication with interface 0
Using endpoint 0x01 for message sending ...
Trying to send message 1 to endpoint 0x01 ...
 OK, message successfully sent
Resetting response endpoint 0x81
Resetting message endpoint 0x01
-> Run lsusb to note any changes. Bye.

と実行するとなんか知らないけど動きました(minicomで反応が見られるようになりました)。

pi@raspberrypi ~ $ sudo minicom -D /dev/ttyUSB1

Welcome to minicom 2.6.1

OPTIONS: I18n
Compiled on Apr 28 2012, 19:24:31.
Port /dev/ttyUSB1

Press CTRL-A Z for help on special keys

ati
NTT DOCOMO, INC.

OK

おそらく、うまくusb_modeswitchが出来ていれば、それで一発だと思うのですが、色々やりすぎて、Raspberry Piが闇化してしまったのが敗因だと思います。とりあえず、メモがてら書いてみました。