HITCON CTF 2016 RegExpert and moRE writeup


59 Teams solved.
Do you remember "hard to say" last year?
I think this one is harder to say...
nc 2171
% cat regexp
% cat regexp - | nc 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}


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.
Hi, our RegExpert, I know you want moRE.
nc 2172

First and Last of this challenge were solved by @satos___jp

% cat moRE
% cat moRE - | nc 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).

(...sorry I cut the last part)

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

(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.


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.