Tags: misc

Rating: 5.0

# Hitcon Quals 2016 - RegExpert
### Misc - 200 pts

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

"Simple" challenge in appearance, we need to give a regex to match a fixed pattern. We have 5 regex to find.
The three main things to take care of are :
- Ruby language is used. Therefore Regex are sometimes different in their syntax compared to what I was used to
- We don't have access to options, so no "insensitive" option possible
- Asked Regex are not usual

### 1st Regex :

================= [SQL] =================
Please match string that contains "select" as a case insensitive subsequence.


Here we need to find every subsequence. Meaning SXeLEcT should match.

First try :
[sS].*[eE].*[lL].*[eE].*[cC].*[tT] should be ok. And yes it works until the last test :
Almost there...But the length limit is 21...
So here the workaround is a (?i) for the insensitive case.

And the solution is (?i)s.*e.*l.*e.*c.*t

### 2nd Regex :

=============== [a^nb^n] ================
Yes, we know it is a classical example of context free grammer.

The "Contenxt free grammer" helps us in our research. Here the goal is to create a pattern aXb where X is the same pattern in recursion and optionnal. This is possible in Ruby with the syntax \g<1>? which creates recursion on the 1 capturing group.
So we try the regex ^(a\g<1>?b)$ and it works ! 2nd Solution : ^(a\g<1>?b)$

### 3rd Regex :


================= [x^p] =================
A prime is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Here I don't have much to say.
To force all elements to be x and avoid empty regex we put ^xx+$ at the end. (xx+)\1+ matches non-prime length strings. So we invert it and get the 3rd solution 3rd Solution : (?!(xx+)\1+$)^xx+$ ### 4th Regex :  ============= [Palindrome] ============== Both "QQ" and "TAT" are palindromes, but "PPAP" is not.  Here we need to first match a single character, or create a recursive pattern matching the pattern aXa where a is a random character and X the recursion being on the whole pattern. (Because we need the recursion to have a stopping condition which here will be the single character) So first we match a single character with this ^(\w)$
Then we add to **OR** pattern with the recursion and it works !

4th Solution : ^(\w?|(\w)\g<1>\k<2>)$ ### 5th Regex :  ============== [a^nb^nc^n] ============== Is CFG too easy for you? How about some context SENSITIVE grammer?  Here context SENSITIVE grammer helps us to find informations on Google. We first found this Regex : /\A(?<AB>a\g<AB>b|){0}(?=\g<AB>c)a*(?<BC>b\g<BC>c|){1}\Z/ which we reduced to ^(a\g<1>b|)(?=\g<1>c)a*(b\g<2>c|)$

This regex works but the length limit is 29. After testings, we didn't find a way to reduce this regex. So we searched for another method. We found the regex ^(?=(a(?-1)?b)c)a+(b(?-1)?c)$ and after a little adaptation to Ruby Language we have the solution 5th Solution : ^(?=(a\g<1>?b)c)a+(b\g<2>?c)$

**Here we are !**
With all this, we get the well deserved flag : hitcon{The pumping lemma is a lie, just like the cake}`

Original writeup (https://github.com/JulesDT/ctfWriteUps/tree/master/Hitcon%20Quals%202016/RegExpert%20-%20Misc%20-%20200%20pts).