LabyREnth 2016 Write-up: “Regex”

Random track #2 – Regex

This is a challenge involving regular expressions. It reads the huge expression from the file omglob_what_is_dis_crap.txt. The code that reads and evaluates this expression will only provide you with the key if you provide it with an input that doesn’t match this expression. Of course the program runs on a remote server, so you don’t have direct access to the flag.

Inspecting the expression, there’s a lot of “OR” conditions, and splitting them into lines gets you something like this:

^(
.*[^0mglo8sc1enC3].*|
.{,190}|
.{192,}|
.{97}[cgClm]|
.{135}[so1l803]|
   .
   .
   .

If this looks familiar to you, it’s because a similar challenge appeared in PlaidCTF 2015. I solved and wrote about the challenge here using Z3 (an SMT solver).

Basically the first 3 lines of expressions at the start dictate what characters can appear in the input, as well its length (191, in this case). This, however, is a watered-down challenge compared to the PlaidCTF one. You do not need to use Z3 in this case. To illustrate what I mean, if you sort each of the regex part in numeric order using sort -k 1.3n, you get this:

.{0}[eo1Cnsc0lm38]
.{1}[3]
.{1}[8l0osm]
.{1}[c1C]
.{1}[en]
.{2}[18]
.{2}[3omsglcn]
.{2}[C]
.{2}[e]
.{3}[3]
.{3}[com8negC]
   .
   .
   .

Using a script, you can easily piece together what characters should (not) go into each position, and thus, construct the correct input to feed to the server.

Because I’m lazy, I decided to re-use my solver script from last time. At that time, the character set was "plaidctf" but this time round it’s "0mglo8sc1enC3", the length of which is unable to fit exactly into N bits (not a power of 2). So I made a few modifications to make it use Z3 Ints instead of a BitVec to support arbitrary string lengths. Fortunately I did a good enough regex parser the last time, so that worked out of the box. (Never did I imagine that it would ever be re-used again.) Now all you need to do is to change the valid character set and length of the flag at the top of the solver script, and off it goes!

I said this was watered-down because Z3 took about 20 minutes the last time to solve PlaidCTF’s constraints. This, on the other hand, took less than one second.

Advertisements
This entry was posted in CTFs.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s