読者です 読者をやめる 読者になる 読者になる

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.