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 (?\
Last part of this challenge(decoding given “huge gift”) is explained there.
