Diary of a reverse-engineer

Because we like to play with weird things.

Regular Expressions Obfuscation Under the Microscope

Introduction

Some months ago I came across a strange couple of functions that was kind of playing with a finite-state automaton to validate an input. At first glance, I didn’t really notice it was in fact a regex being processed, that’s exactly why I spent quite some time to understand those routines. You are right to ask yourself: “Hmm but the regex string representation should be in the binary shouldn’t it?”, the thing is it wasn’t. The purpose of this post is to focus on those kind of “compiled” regex, like when the author transform somehow the regex in a FSM directly usable in its program (for the sake of efficiency I guess). And to extract that handy string representation, you have to study the automaton.

In this short post, we are going to see how a regular expression looks like in assembly/C, and how you can hide/obfuscate it. I hope you will enjoy the read, and you will both be able to recognize a regular expression compiled in your future reverse-engineering tasks and to obfuscate heavily your regex!

Bring out the FSM

Manually

Before automating things, let’s see how we can implement a simple regex in C. It’s always easier to reverse-engineer something you have, at least once in your life, implemented. Even if the actual implementation is slightly different from the one you did. Let’s say we want to have an automaton that matches “Hi-[0-9]{4}”.

NOTE: I just had the chance to have a conversation with Michal, and he is totally right saying that automata ins’t really the regex we said it was. Here is an example of what the regex should match: ‘Hi-GARBAGEGARBAGE_Hi-1234’. We don’t allow our regex to like rewind the state to zero if the input doesn’t match the regex. To do so, we could replace the return statements by a “state = 0” statement :). Thank you to Michal for the remark.

Now, if from that string representation we extract an FSM, we can have that one:

Here is this automaton implemented in C:

(fsm_example.c) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <stdio.h>
#include <string.h>

unsigned char checkinput(char* s)
{
    unsigned int state = 0, i = 0;
    do
    {
        switch(state)
        {
            case 0:
            {
                if(*s == 'H')
                    state = 1;

                break;
            }

            case 1:
            {
                if(*s == 'i')
                    state = 2;
                else
                    return 0;

                break;
            }

            case 2:
            {
                if(*s == '-')
                    state = 3;
                else
                    return 0;

                break;
            }

            case 3 ... 6:
            {
                if(*s >= '0' && *s <= '9')
                    state++;
                else
                    return 0;

                break;
            }

            case 7:
                return 1;
        }
    } while(*s++);

    return 0;
}

int main(int argc, char *argv[])
{
    if(argc != 2)
    {
        printf("./fsm <string>\n");
        return 0;
    }

    if(checkinput(argv[1]))
        printf("Good boy.\n");
    else
        printf("Bad boy.\n");

    return 1;
}

If we try to execute the program:

1
2
3
4
5
6
7
8
9
10
11
> fsm_example.exe garbage-Hi-1337-garbage
Good boy.

> fsm_example.exe garbage-Hi-1337
Good boy.

> fsm_example.exe Hi-1337-garbage
Good boy.

> fsm_example.exe Hi-dudies
Bad boy.

The purpose of that trivial example was just to show you how a regex string representation can be compiled into something harder to analyze but also more efficient (it doesn’t need a compilation step, that’s the reason why you may encounter that kind of thing in real (?) softwares). Even if the code seems trivial at the first sight, when you look at it at the assembly level, it takes a bit of time to figure out it’s a simple “Hi-[0-9]{4}” regex.

In that kind of analysis, it’s really important to find the “state” variable that allows the program to pass through the different nodes of the FSM. Then, you have also to figure out how you can reach a specific node, and all the nodes reachable from a specific one. To make it short, at the end of your analysis you really want to have a clean FSM like the one we did earlier. And once you have it, you want to eliminate unreachable nodes, and to minimize it in order to remove some potential automaton obfuscation.

(fsm_example.c) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <stdio.h>
#include <string.h>

unsigned char checkinput(char* s)
{
    unsigned int state = 0, i = 0;
    do
    {
        switch(state)
        {
            case 0:
            {
                if(*s == 'H')
                    state = 1;

                break;
            }

            case 1:
            {
                if(*s == 'i')
                    state = 2;
                else
                    return 0;

                break;
            }

            case 2:
            {
                if(*s == '-')
                    state = 3;
                else
                    return 0;

                break;
            }

            case 3 ... 6:
            {
                if(*s >= '0' && *s <= '9')
                    state++;
                else
                    return 0;

                break;
            }

            case 7:
                return 1;
        }
    } while(*s++);

    return 0;
}

int main(int argc, char *argv[])
{
    if(argc != 2)
    {
        printf("./fsm <string>\n");
        return 0;
    }

    if(checkinput(argv[1]))
        printf("Good boy.\n");
    else
        printf("Bad boy.\n");

    return 1;
}

Automatically

But what if our regex was totally more complex ? It would be a hell to implement manually the FSM. That’s why I wanted to find some ways to generate your own FSM from a regex string manipulation.

With re2c

re2c is a cool and simple tool that allows you to describe your regex in a C comment, then it will generate the code of the scanner. As an example, here is the source code to generate the scanner for the previous regex:

(fsm_re2c_example.c) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/* re2c -i fsm_re2c_example.c */
#include <stdio.h>
#include <string.h>

unsigned char checkinput(char* s)
{
    char *q;
/*!re2c
    re2c:define:YYCTYPE = "char";
    re2c:define:YYCURSOR = s;
    re2c:define:YYMARKER = q;
    re2c:yyfill:enable   = 0;

   "Hi-"[0-9]{4}  { return 1; }
   [^]            { return 0; }
*/
}

int main(int argc, char *argv[])
{
    if(argc != 2)
    {
        printf("./fsm <string>\n");
        return 0;
    }

    if(checkinput(argv[1]))
        printf("Good boy.\n");
    else
        printf("Bad boy.\n");

    return 1;
}

Once you feed that source to re2c, it gives you that scanner ready to be compiled:

(fsm_re2c_generated_non_optimized.c) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
/* Generated by re2c 0.13.5 on Sun Aug 25 00:27:48 2013 */
#include <stdio.h>
#include <string.h>

unsigned char checkinput(char* s)
{
    char *q;

{
        char yych;

        yych = *s;
        switch (yych) {
        case 'H':       goto yy2;
        default:        goto yy4;
        }
yy2:
        yych = *(q = ++s);
        switch (yych) {
        case 'i':       goto yy5;
        default:        goto yy3;
        }
yy3:
        { return 0; }
yy4:
        yych = *++s;
        goto yy3;
yy5:
        yych = *++s;
        switch (yych) {
        case '-':       goto yy7;
        default:        goto yy6;
        }
yy6:
        s = q;
        goto yy3;
yy7:
        yych = *++s;
        switch (yych) {
        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9':       goto yy8;
        default:        goto yy6;
        }
yy8:
        yych = *++s;
        switch (yych) {
        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9':       goto yy9;
        default:        goto yy6;
        }
yy9:
        yych = *++s;
        switch (yych) {
        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9':       goto yy10;
        default:        goto yy6;
        }
yy10:
        yych = *++s;
        switch (yych) {
        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9':       goto yy11;
        default:        goto yy6;
        }
yy11:
        ++s;
        { return 1; }
}

}

int main(int argc, char *argv[])
{
    if(argc != 2)
    {
        printf("./fsm <string>\n");
        return 0;
    }

    if(checkinput(argv[1]))
        printf("Good boy.\n");
    else
        printf("Bad boy.\n");

    return 1;
}

Cool isn’t it ? But in fact, if you try to compile and Hexrays it (even with optimizations disabled) you will be completely disappointed: it gets simplified like really ; not cool for us (cool for the reverse-engineer though!).

By hand

That’s why I tried to generate myself the C code of the scanner. The first thing you need is a “regular-expression string” to FSM Python library: a sort-of regex compiler. Then, once you are able to generate a FSM from a regular expression string, you are totally free to do whatever you want with the automaton. You can obfuscate it, try to optimize it, etc. You are also free to generate the C code you want. Here is the ugly-buggy-PoC code I wrote to generate the scanner for the regex used previously:

(generate_c_fsm.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
import reCompiler
import random

c = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!"#$%&()*+,-./:;<=>?@[\\]^_`{|}~ \t\n\r\x0b\x0c'

fsm = reCompiler.compileRE('Hi-[0-9][0-9][0-9][0-9]', minimize = 1)
states = fsm.states
transitions = fsm.transitions

useless_states = [random.randint(0, 0xffffffff) for _ in range(random.randint(50, 100))]
states += useless_states

# We don't want to have dead nodes, so let's create transition
deadnodes = set(useless_states)
while len(deadnodes) != 0:
    s, d, t = random.choice(states), random.choice(states), random.choice(c)
    transitions += [(s, d, t)]
    deadnodes -= set([s])

# To obfuscate we can use random state number
dic_states = dict(
    (i, random.randint(0, 0xffffffff)) for i in states
)

random.shuffle(states)
assert(len(dic_states.values()) == len(set(dic_states.values())))

print 'unsigned char checkinput(char *p){\nunsigned int state = %d;\nwhile(*p)\n{\nswitch(state)\n{' % dic_states[fsm.initialState]

for i in states:
    if i in fsm.finalStates:
        continue

    print 'case %d:\n{' % dic_states[i]

    is_first = True
    for src, dst, t in transitions:
        if src != i:
            continue

        if is_first == False:
            print 'else',
        else:
            is_first = False

        r = str(t)
        if r.startswith('\\') == False or len(r) == 1:
            print "if(*p == %s)" % repr(r)
        elif r == '\\d':
            print "if(*p >= '0' && *p <= '9')"
        else:
            raise Exception('Not implemented!')

        print '{'

        if dst in fsm.finalStates:
            print 'return 1;'
        else:
            print 'state = %d; ++p;' % dic_states[dst]

        print '}'

    # Kind of hack to not anchor the regex (not handled by the RE->FSM)
    if i == fsm.initialState:
        print 'else ++p;'
    else:
        print 'else return 0;'
    print 'break;\n}'

print '}\n}\nreturn 0;\n}'

Now, if you open it in IDA the CFG will look like this:

Not that fun to reverse-engineer I guess. If you are enough curious to look at the complete source, here it is: fsm_generated_by_hand_example.c.

Thoughts to be more evil: one input to bind all the regex in the darkness

Keep in mind, the previous examples are really trivial to analyze, even if we had to do it at the assembly level without Hexrays (by the way Hexrays does a really nice job to simplify the assembly code, cool for us!). Even if we have slightly obfuscated the automaton with useless states/transitions, we may want to make things harder.

One interesting idea to bother the reverse-engineer is to use several regex as “input filters”. You create one first “permissive” regex that has many possible valid inputs. To reduce the valid inputs set you use another regex as a filter. And you do that until you have only one valid input: your serial. Note that you may also want to build complex regex, because you are evil.

In that case, the reverse-engineer has to analyze all the different regex. And if you focus on a specific regex, you will have too many valid inputs whereas only one gives you the good boy (the intersection of all the valid inputs set of the different regex).

If you are interested by the subject, a cool resource I’ve seen recently that does similar things was in a CTF task write-up written by Michal Kowalczyk: read it, it’s awesome.

UPDATE: You should also read the follow-up made by @fdfalconA black-box approach against obfuscated regular expressions using Pin”. Using Pin to defeat the FSM obfuscation, and to prove my obfuscation was a bit buggy: two birds, one stone :)).

Messing with automata is good for you.