Epic “cnot” Writeup (highest value level from PlaidCTF)

When I was at Shmoocon, I saw a talk about how to write an effective capture-the-flag contest. One of their suggestions was to have a tar-pit challenge that would waste all the time of the best player, by giving him a complicated challenge he won’t be able to resist. In my opinion, in PlaidCTF, I suspected that “cnot” was that challenge. And I was the sucker, even though I knew it all the way…

(It turns out, after reviewing writeups of other challenges, that most of the challenges were like this; even so, I’m proud to have been sucked in!)

If you want a writeup where you can learn something, I plan to post a writeup for “Ropasaurus” in the next day or two. If you want a writeup about me being tortured as I fought through inconceivable horrors to finish a level and capture the bloody flag, read on! This level wasn’t a lot of learning, just brute-force persistence. It’s worthwhile to note that I’m not going to cover every piece or every line—maybe I’ll do that as a novel in the future—this is mostly going to be a summary. Even so, this is going to be a long writeup. I’m trying to make it interesting and fun to read, and to break it into shorter sections. But heed this warning!

Also, I may switch between “I” and “we” throughout the writeup. This indicates when I was being helped by somebody, when I was alone, and when I was simply going insane. I’m pretty sure the voices in my head helping with a solution are a good enough reason to say “we” instead of “I”, right?

Now that the contest is over, the source has been released. Here’s the command they used for compiling it, directly from that source:

1 // compile with:
2 // isildur cnot.c0 -l l4rt.h0 -o test.s --obfuscate --anti-debug --confuse
3 // gcc test.s obf.c -o cnot
4 // strip cnot

–obfuscate, –anti-debug, and –confuse? Awww, you shouldn’t have! But, I digress. I didn’t have this info back then…

Being that I fancy myself a reverse engineer, this level appealed to me right away. In fact, it’s the first one I looked at, despite it being the highest point value. Go big or go home!

I spent about fifteen minutes poking around. I determined that the binary was ugly as sin, that the debugger didn’t work, and that it was 64-bit Intel assembly. Well fuck, I don’t even know x64 (well, I didn’t when I started this CTF, at least). So I gave up and moved onto another level, Ropasaurus (which will have its own writeup).

After solving a some other levels with the help of HikingPete (Ropasaurus, Cyrpto, and charsheet), I came back to cnot late Friday night. Mak and Nate had put several hours into it and had given up. It was all up to me.

Let’s start by summarizing the weekend…

Work on it till 6am. Wake up at 9am. Work on another problem for a couple hours, return to cnot by noon. Work solid—besides a meal—till 6am again. Getting so close, but totally stuck.

Wake up early again, go straight to it. 9am I think? Stuck, so stuck. Came up with ideas, failed, more ideas, failed failed failed. Finally, thought of something. Can it work…? IT DID! FLAG OBTAINED!! Hardest binary I’ve ever reversed, and I was suddenly an expert on x64! Done by 2pm, too! That means I only spent.. thirty hours? Is that right? Dear lord…

And you know what the kicker is? Even without the obfuscation, without the anti-debugging, and without the… confusion? This still would have been a goddamn hard binary! Hell, take a look at the C version. Even that would have been a huge pain!

But now I’m definitely getting ahead of myself. The rest of this document will be about what worked, I don’t explore too many of the ‘wrong paths’ I took, except where it’s pedagogical to do so.

The setup

Basically, we had a 64-bit Linux executable file, and no hints of any kind. I fired up a Debian 6.0.7 machine with basically default everything, except that I installed my favourite dev/reversing tools that you’ll see throughout this writeup. I also had a Windows machine with a modern version of IDA Pro. If you plan to do any reversing, you need IDA Pro. The free version works for most stuff, but modern versions are way faster and handle a lot more madness.

You run the program, it simply asks for a password. You type in something, and it generally says “Wrong!” and ends:

1 ron@debian-x86 ~/cnot $ ./cnot
2 Please enter your password: hello
3 Wrong!

The goal was to figure out the password for this executable, which was the flag.

And that’s our starting point. So far so good!

At this point, I had a lot of ideas. Sometimes, you start with the error message, work your way back to a comparison, and look at what’s being compared to what. Sometimes, you start with the input and look at how it’s being mangled. Or sometimes, you quietly sob in the corner. I tried the first two approaches at the start, and then steadily moved on to the last.

Wasted effort

Mak and Nate had started working on the project without me, and Mak had started writing a timing-attack tool. Sometimes, if one letter is compared at a time, you can derive each letter individually by timing the comparisons and looking at which one is the fastest. That could save a ton of reversing time!

If I’d known then what I know now, I wouldn’t have bothered. This had no hope of working. But it was worth a shot!

I helped Mak finish a program that would:

  • Choose a letter
  • Write it to a file
  • Start a high resolution timer (using rdtsc, which counts the number of cycles since reset)
  • Run the process
  • Read the timer state
  • Repeat for each letter, choose the best
  • Go back to the top and choose another letter

This works exceptionally well, in some cases. This was not one of the cases. It turns out that the letters were validated with a checksum first, which instantly breaks it. Then they were validated out of order, and in various other ways, all of which would break this. So, long story short, it was a waste of our time.

Luckily, after an hour or two, I said “this isn’t working” and we moved on without ever looking back.


Our first step was anti-debugging, because this:

1 $ gdb ./cnot
2 Reading symbols from /home/ron/cnot/cnot...(no debugging symbols found)...done.
3 (gdb) run hello
4 Starting program: /home/ron/cnot/cnot hello
6 Program received signal SIGSEGV, Segmentation fault.
7 0x00400b86 in ?? ()

You assholes! If you run it with strace, you’ll see this:

1 trace ./cnot 2>&1 | tail -n4
2   munmap(0x7f5cc9159000, 63692)           = 0
3   ptrace(PTRACE_TRACEME, 0, 0, 0)         = -1 EPERM (Operation not permitted)
4   --- SIGSEGV (Segmentation fault) @ 0 (0) ---
5   +++ killed by SIGSEGV (core dumped) +++

So it’s calling ptrace right before dying, eh? Well, I know how to deal with that! Mak wrote a quick library:

1   ron@debian-x64 ~/cnot $ echo 'long ptrace(int a, int b, int c){return 0;}' > override.c
2   ron@debian-x64 ~/cnot $ gcc -shared -fPIC -o override.so ./override.c

Add it to our gdbinit file:

1 $ cat gdbinit
2 # Set up the environment
3 set disassembly-flavor intel
4 set confirm off
6 # Disable the anti-debugging
7 set environment LD_PRELOAD ./overload.so

And run the program with that gdbinit file:

1 $ gdb -x ./gdbinit ./cnot
2 Reading symbols from /home/ron/cnot/cnot...(no debugging symbols found)...done.
3 (gdb) run
4 Please enter your password: hello
5 Wrong!
7 Program exited normally.

Thankfully, that was the only anti-debugging measure taken. gdbinit files are actually something I learned from Mak while working on the IO Wargame, and are one of the most valuable tools in your debugging arsenal!

First steps

First of all, let’s take a look at the imports; this can be done more easily in IDA, but to avoid filling this writeup with screenshots, I’ll use objdump to get the equivalent information:

 1 ron@debian-x86 ~/cnot $ objdump -R cnot
 3 cnot:     file format elf64-x86-64
 6 OFFSET           TYPE              VALUE
 7 006101b8 R_X86_64_GLOB_DAT   __gmon_start__
 8 00610240 R_X86_64_COPY       stdin
 9 00610250 R_X86_64_COPY       stdout
10 006101d8 R_X86_64_JUMP_SLOT  __isoc99_fscanf
11 006101e0 R_X86_64_JUMP_SLOT  exit
12 006101e8 R_X86_64_JUMP_SLOT  __libc_start_main
13 006101f0 R_X86_64_JUMP_SLOT  ungetc
14 006101f8 R_X86_64_JUMP_SLOT  fputc
15 00610200 R_X86_64_JUMP_SLOT  fgetc
16 00610208 R_X86_64_JUMP_SLOT  ptrace
17 00610210 R_X86_64_JUMP_SLOT  raise
18 00610218 R_X86_64_JUMP_SLOT  calloc
19 00610220 R_X86_64_JUMP_SLOT  feof
20 00610228 R_X86_64_JUMP_SLOT  fprintf

fputc() and fgetc() were the ones I was most interested in. To make a long story short, we put a breakpoint on fputc() to see when it was called. It was called twice for each character. Once—at offset 0x40F63B—it was in a function that checked for EOF (end of file) then used ungetc() to put it back. It was never actually returned. The other time—at offset 0x40F723—it was called then the function returned the character. That’s where I focused.

I used a breakpoint to confirm that it was actually calling each of those functions for every character I entered. It was.

At that point, I tried to follow the logic onward from where the value was read. Me and Mak, together, followed the path that was then taken through the code. Essentially, checks were done for EOF, for NULL being returned from fgetc(), and for a newline. If it was any of those, it would jump to a label that I called found_newline or something like that. We pushed our way through the obfuscated code, though, which IDA did a poor job of figuring out.

Eventually, we managed to get back to the fgetc() calls through the biiiig loop. When I tried to follow the other code path, to see how the program handles the completed string, I quickly became lost.

I then tried the other approach—starting from the “Wrong!” label and working backwards. I found all the calls to fputc() in gdb by doing the following:

Run the program until it requests password (recalling that “-x ./gdbinit” loads my init script, which loads override.so to fix the anti-debugging), then break by using ctrl-c:

 1 $ gdb -x ./gdbinit ./cnot
 2 Reading symbols from /home/ron/cnot/cnot...(no debugging symbols found)...done.
 3 (gdb) run
 4 Please enter your password: ^C
 5 Program received signal SIGINT, Interrupt.
 6 0x00007ffff793f870 in read () from /lib/libc.so.6

Add a breakpoint at fputc(), then continue and enter “hello” for my password:

 9 (gdb) b fputc
10 Breakpoint 1 at 0x7ffff78e26d0
11 (gdb) cont
12 hello

Once it breaks, run the “finish” command twice to exit two layers of function:

15 Breakpoint 1, 0x00007ffff78e26d0 in fputc () from /lib/libc.so.6
16 (gdb) finish
17 0x0040f6c6 in ?? ()
18 (gdb) finish
19 0x00400840 in ?? ()

Now we’re at 0x400840. If you look at the function it’s in, you’ll see that it ends like this:

1 .text:00400851     pop     rdi
2 .text:00400852     jmp     rdi

As a result, gdb won’t be able to “finish” properly since it never (technically) returns! Instead, we set a breakpoint on the last line then use the “stepi” command to step out:

1 (gdb) break *0x400852
2 Breakpoint 2 at 0x400852
3 (gdb) cont
5 Breakpoint 2, 0x00400852 in ?? ()
6 (gdb) stepi
7 0x0040f149 in ?? ()

0x40f149! If you’re following along in IDA, you’ll see a ton of undefined code there. D’oh! You can use ‘c’ to define the code in IDA, just keep moving up and down and pressing ‘c’ (and occasionally ‘u’ when you see SSE instructions) in various places till stuff looks right. Eventually, you’ll see:

 1 .text:0040F10F     mov     qword ptr [rbp-68h], 0
 2 .text:0040F117     mov     dword ptr [rbp-68h], 'W'
 3 .text:0040F11E     push    r8
 4 .text:0040F120     push    r9
 5 .text:0040F122     push    rcx
 6 .text:0040F123     xor     rcx, rcx
 7 .text:0040F126     jz      short near ptr loc_40F128+1
 8 .text:0040F128
 9 .text:0040F128 loc_40F128:
10 .text:0040F128     mulps   xmm2, xmmword ptr [rcx+53h]
11 .text:0040F12C     push    rdx
12 .text:0040F12D     call    $+5
13 .text:0040F132     pop     rdx
14 .text:0040F133     add     rdx, 8
15 .text:0040F137     push    rdx
16 .text:0040F138     retn
17 .text:0040F138                ; -------------
18 .text:0040F139    db  0Fh
19 .text:0040F13A                ; -------------
20 .text:0040F13A     pop     rdx
21 .text:0040F13B     pop     rbx
22 .text:0040F13C     pop     rcx
23 .text:0040F13D     mov     rdi, [rbp-68h]
24 .text:0040F141     mov     r15, rax
25 .text:0040F144     call    sub_400824

This isn’t quite right, because of the jz and the call/push/ret in the middle, but we’ll deal with that shortly. For now, look at 0x0040F117—push ‘W’—and 0x40F144—call the function that calls fputc()! If you follow it down, you’ll find the ‘r’, ‘o’, ‘n’, ‘g’, ‘!’, newline, and then ‘C’, ‘o’, ‘r’, ‘r’, ‘e’, ‘c’, ‘t’, ‘!’. That’s great news! We found where it prints the two cases!

The problem is, it’s ugly as sin. I can’t even count the number of times I used ‘u’ to undefine bad instructions and ‘c’ to define better ones before I finally gave up and edited the binary…


The best thing I ever did—and I wish I did it earlier!—was to fix the anti-reversing nonsense. There are long strings of the same thing that make analysis hard. In the previous example, everything from the push at 0x40F122 to the mov at 0x40F13D is totally worthless, and just confuses the disassembler, so let’s get rid of it!

I loaded up the file in xvi32.exe—my favourite Windows hex editor—and did a find/replace on the sequence of bytes:

 51 48 31 C9 74 01 0F 59 51 53 52 E8 00 00 00 00 5A 48 83 C2 08 52 C3 0F 5A 5B 59

with NOPs:

 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90

936 occurrences replaced! Awesome! But there was still some obfuscation left that looked like this:

1 .text:0040F123      xor     rcx, rcx
2 .text:0040F126      jz      short near ptr loc_40F128+1
3 .text:0040F128
4 .text:0040F128 loc_40F128:
5 .text:0040F128      mulps   xmm2, xmmword ptr [rcx+53h]
6 .text:0040F12C      push    rdx

Note the jz—it actually jumps one byte, which means the instruction immediately following—the mulps—is an invalid instruction. The 0x0f is unused! This one is simple to fix—just replace 74 01 FF—the jump and the fake instruction—with NOPs:

  74 01 0F => 90 90 90

This fixes 290 more occurrences of code that confuses IDA!

And then there’s this:

1 .text:00400C44     call    $+5
2 .text:00400C49     pop     rdx
3 .text:00400C4A     add     rdx, 8
4 .text:00400C4E     push    rdx
5 .text:00400C4F     retn
6 .text:00400C4F sub_400BD1      endp ; sp-analysis failed
7 .text:00400C4F
8 .text:00400C50     cvtps2pd xmm3, qword ptr [rbx+59h]

Which can be removed with this pattern:

  e8 00 00 00 00 5a 48 83 c2 08 52 c3 0f

74 of which were removed.

After all that, I loaded the executable back in IDA, and it was much nicer! I realized later that there was probably more code I could have removed—such as the pop edi / jmp edi that’s used instead of returning—but I got too invested in my IDA database that I didn’t want to mess it up.

Tracking down the compare

All righty, now that we’ve cleaned up the code, we’re starting to make some progress! By the time I got here, it was about 2am on Friday night, and I was still going strong (despite Mak being asleep behind me on a table). [Editor’s Note: I needed my beauty sleep, dammit!]

Let’s start by finding the ‘Wrong’ and ‘Correct’ strings again. You can breakpoint on fputc(), or you can just go to the definition of fputc() and keep jumping to cross references. Whatever you do, I want you to eventually wind up at the line that pushes the ‘W’ from ‘Wrong!’, which is here:

1 .text:0040F117                 mov     dword ptr [rbp-68h], 'W'

Two lines above it, you’ll see a conditional jump:

1 .text:0040F109                 jz      loc_40F359

If you follow that jump, you’ll see that if it jumps, it prints out ‘Correct’; otherwise, it prints ‘Wrong’. We can confirm this by forcing the jump, but first let’s update our gdbinit file to break at the ‘start’ function:

 1 ron@debian-x64 ~/cnot $ cat gdbinit
 2 # Set up the environment
 3 set disassembly-flavor intel
 4 set confirm off
 6 # Disable the anti-debugging
 7 set environment LD_PRELOAD ./overload.so
 9 # Put a breakpoint at the 'start' function
10 break *0x00400710
12 # Run the program up to the breakpoint
13 run

Now we run the program, and change the jz at line 0x0040f109 to a jmp:

 1 $ gdb -x ./gdbinit ./cnot
 2 Reading symbols from /home/ron/cnot/cnot...(no debugging symbols found)...done.
 3 Breakpoint 1 at 0x400710
 5 Breakpoint 1, 0x00400710 in ?? ()
 6 (gdb) set {char}0x0040f109 = 0x90
 7 (gdb) set {char}0x0040f10a = 0xE9
 8 (gdb) x/2i 0x0040f109
 9 0x40f109:       nop
10 0x40f10a:       jmp    0x40f359
11 (gdb) cont
12 Please enter your password: hello
13 Correct!

So, we change 0x401109 to 0x90 (nop) and 0x0040f10a to 0xe9 (jmp long), verify the instructions, and run the program. Sure enough, my password now produces ‘hello’. Success! Now I just have to backstep a little bit and find the comparison, and we’re done! Simple! Haha!

13 steps to success

So, every variable is set in an ass-backwards way. You get pretty accustomed to seeing it in this level, and kind of just mentally pattern-match it. I’m sure there’s a better way, but eh? I got pretty fast at it as time went on.

The decision whether or not to make the important jump comes from [rbp-78h], which comes from [rbp-58h] (via like ten other variables). The only way to get that variable set properly is right here:

1 .text:0040F08E                mov     qword ptr [rbp-58h], 0
2 .text:0040F096                mov     dword ptr [rbp-58h], 1

Right below that, I noticed this code:

 1 .text:0040F09D     jmp     short $+2
 2 .text:0040F09F
 3 .text:0040F09F loc_40F09F:      ; CODE XREF: sub_40911F+5F6Dj
 4 .text:0040F09F     jmp     short $+2
 5 .text:0040F0A1
 6 .text:0040F0A1 loc_40F0A1:      ; CODE XREF: sub_40911F+59EBj
 7 .text:0040F0A1     jmp     short $+2
 8 .text:0040F0A3
 9 .text:0040F0A3 loc_40F0A3:      ; CODE XREF: sub_40911F+53BAj
10 .text:0040F0A3     jmp     short $+2
11 .text:0040F0A5
12 .text:0040F0A5 loc_40F0A5:      ; CODE XREF: sub_40911F+47DAj
13 .text:0040F0A5     jmp     short $+2
14 .text:0040F0A7
15 .text:0040F0A7 loc_40F0A7:      ; CODE XREF: sub_40911F+3AB1j
16 .text:0040F0A7     jmp     short $+2
17 .text:0040F0A9
18 .text:0040F0A9 loc_40F0A9:      ; CODE XREF: sub_40911F+2D88j
19 .text:0040F0A9     jmp     short $+2
20 .text:0040F0AB
21 .text:0040F0AB loc_40F0AB:      ; CODE XREF: sub_40911F+21A8j
22 .text:0040F0AB     jmp     short $+2
23 .text:0040F0AD
24 .text:0040F0AD loc_40F0AD:      ; CODE XREF: sub_40911F+2141j
25 .text:0040F0AD     jmp     short $+2
26 .text:0040F0AF
27 .text:0040F0AF loc_40F0AF:      ; CODE XREF: sub_40911F+1DE9j
28 .text:0040F0AF     jmp     short $+2
29 .text:0040F0B1
30 .text:0040F0B1 loc_40F0B1:      ; CODE XREF: sub_40911F+1D82j
31 .text:0040F0B1     jmp     short $+2
32 .text:0040F0B3
33 .text:0040F0B3 loc_40F0B3:      ; CODE XREF: sub_40911F+1CB4j
34 .text:0040F0B3     jmp     short $+2
35 .text:0040F0B5
36 .text:0040F0B5 loc_40F0B5:      ; CODE XREF: sub_40911F+1C04j
37 .text:0040F0B5     jmp     short $+2
38 .text:0040F0B7
39 .text:0040F0B7 loc_40F0B7:      ; CODE XREF: sub_40911F+1B9Dj

Each of those lines bypasses the ‘set the good value’ line, and each of them is referred to earlier in this function. I immediately surmised that each of those locations were “bad” jumps—that is, there were thirteen or so checks that were happening, and that each one that failed would lead us back here. A thirteen character string seemed possible, where each letter was checked individually, so I started looking into it. Mak—awake once again—was not convinced.

The easy start

The final thing I did Friday night was look at the first check (the last one on that list), which is located at this line:

1 .text:0040ACBC                 jz      loc_40F0B7

What causes that jump to fail? Long story short, it’s this:

1 .text:0040AC8E                 cmp     r15d, [rbp-78h]

…where r15d is an unknown value, and [rbp-78h] is 0x18 (24). Let’s break and see what r15 is:

 1   ron@debian-x64 ~/cnot $ gdb -x ./gdbinit ./cnot
 2   Reading symbols from /home/ron/cnot/cnot...(no debugging symbols found)...done.
 3   Breakpoint 1 at 0x400710
 5   Breakpoint 1, 0x00400710 in ?? ()
 6   (gdb) b *0x0040ac8e
 7   Breakpoint 2 at 0x40ac8e
 8   (gdb) cont
 9   Please enter your password: hello
11   Breakpoint 2, 0x0040ac8e in ?? ()
12   (gdb) print/d $r15
13   $1 = 5
14   (gdb) run
16   Breakpoint 1, 0x00400710 in ?? ()
17   (gdb) cont
18   Please enter your password: moo
20   Breakpoint 2, 0x0040ac8e in ?? ()
21   (gdb) print/d $r15
22   $2 = 3

When I enter ‘hello’, it’s 5, and when I enter ‘moo’, it’s 3. It compares that value to 0x18 (24), and fails if it’s anything else. We just found out the password length! And it was kind of easy!

By now it was about 5am on Friday night, and time for bed.

Not as dumb as I look

First thing Saturday morning—after three hours of sleep—I started and finished another flag—securereader. Don’t get me started on securereader. I fucked up badly, and it took wayyyyyy longer than it should have.

Anyway, by early afternoon, I was back to working on cnot. I was pretty sure those jumps were all the ‘bad’ jumps, so—in what I consider my #1 decision on this entire flag, at least tied with finding/replacing the ‘bad code’—I added a bunch of nop-outs to my gdbinit file:

 1 ron@debian-x64 ~/cnot $ cat ./gdbinit
 2 # Set up the environment
 3 set disassembly-flavor intel
 4 set confirm off
 6 # Disable the anti-debugging
 7 set environment LD_PRELOAD ./overload.so
 9 # Put a breakpoint at the 'start' function
10 break *0x00400710
12 # Run the program up to the breakpoint
13 run
15 # Verify length
16 set {int}0x040ACBC = 0x90909090
17 set {short}0x040ACC0 = 0x9090
19 set {int}0x040AD23 = 0x90909090
20 set {short}0x040AD27 = 0x9090
22 set {int}0x040ADD3 = 0x90909090
23 set {short}0x040ADD7 = 0x9090
25 set {int}0x040AEA1 = 0x90909090
26 set {short}0x040AEA5 = 0x9090
28 set {int}0x040AF08 = 0x90909090
29 set {short}0x040AF0C = 0x9090
31 set {int}0x040B260 = 0x90909090
32 set {short}0x040B264 = 0x9090
34 set {int}0x040B2C7 = 0x90909090
35 set {short}0x040B2CB = 0x9090
37 set {int}0x040BEA7 = 0x90909090
38 set {short}0x040BEAB = 0x9090
40 set {int}0x040CBD0 = 0x90909090
41 set {short}0x040CBD4 = 0x9090
43 set {int}0x040D8F9 = 0x90909090
44 set {short}0x040D8FD = 0x9090
46 set {int}0x040E4D9 = 0x90909090
47 set {short}0x040E4DD = 0x9090
49 set {int}0x040EB0A = 0x90909090
50 set {short}0x040EB0E = 0x9090
52 set {short}0x040F08C = 0x9090
54 cont

After like two hours of troubleshooting that code because I forgot that ‘long’ = 8 bytes and ‘int’ = 4 bytes (which Aemelianus had the pleasure to watch me fight with), eventually it worked:

1 $ gdb -x ./gdbinit ./cnot
2 Reading symbols from /home/ron/cnot/cnot...(no debugging symbols found)...done.
3 Breakpoint 1 at 0x400710
5 Breakpoint 1, 0x00400710 in ?? ()
6 Please enter your password: hello
7 Correct!
9 Program exited normally.

Excellent! I can easily test any of the checks without the others interfering!

From here on out, I did everything in a more or less random order, and each step took a long time. Ultimately, however, there were four main types of checks I found: character class (upper/lower/numeric), adjacent checks, shift checks (I’ll explain these later), and checksums. I solved the first three on Saturday, and the last—the hardest, the checksum—on Sunday. Let’s take each of them individually.

Character class

The character class checks happen right here:

 1 .text:0040AD00                 mov     rdi, [rbp-70h]
 2 .text:0040AD04                 mov     r15, rax        ; both = pointers to my string
 3 .text:0040AD07                 call    do_validation2  ; Validate a pattern (fully reversed)
 4 .text:0040AD0C                 mov     [rbp-68h], rax
 5 .text:0040AD10                 mov     rax, r15
 6 .text:0040AD13                 add     rsp, 0
 7 .text:0040AD17                 pop     r9
 8 .text:0040AD19                 pop     r8
 9 .text:0040AD1B                 mov     r15d, [rbp-68h]
10 .text:0040AD1F                 cmp     r15d, 0
11 .text:0040AD23                 jz      bad_place2

do_validation2() is about a million lines, and is actually a great place to get your feet wet with how the obfuscation works. By the end of it, I could move through pretty quickly. It calls three different functions, which are:

1 0x00402726 check_alphabetic(char c)
2 0x004028AC check_lowercase(char c)
3 0x0040297E check_numeric(char c)

I’m not going to dwell on how those work. Suffice to say, they’re about as simple as anything is in this binary. One line in the source, and only about 150 lines in the binary!

Essentially, throughout this function, you’ll see things like:

1 .text:00402AFD                 add     r11, rbx        ; add 0*8 to the offset
2 .text:00402B1E                 mov     rax, [rax]       ; rax = first character ("a")
3 .text:00402B40                 mov     rdi, rax
4 .text:00402B43                 call    check_alphabetic ; Returns '1' if it's upper or lower case
5 .text:00402B50                 cmp     eax, 0           ; '1' is good
6 .text:00402B53                 jz      bad

(note that I’m leaving out the extra ‘obfuscating’ lines)

This runs through every character, one by one, with similar checks. I did a ton of debugging to see what was going on, and was able to determine the ‘possible’ values of each character:

Character 1  :: Letter
Character 2  :: Letter
Character 3  :: Lowercase
Character 4  :: Lowercase
Character 5  :: Letter
Character 6  :: Symbol (not letter or number)
Character 7  :: Letter
Character 8  :: Symbol
Character 9  :: Number
Character 10 :: Lowercase
Character 11 :: Letter
Character 12 :: Letter
Character 13 :: Letter
Character 14 :: Uppercase
Character 15 :: Letter
Character 16 :: Letter
Character 17 :: Uppercase
Character 18 :: Letter
Character 19 :: Symbol
Character 20 :: Letter
Character 21 :: Letter (I originally had 'lowercase', that was wrong)
Character 22 :: Letter
Character 23 :: Uppercase
Character 24 :: Symbol

In addition to character classes, a couple properties were discovered here:

  • The fourth character had to be one higher than the tenth character
  • The twenty-first character was alphabetic, but if you subtract one it wasn't (therefore, it had to be a 'a' or 'A')

So now we have a lot of properties, and an actual letter! Progress! And we have one more check that’ll pass; two down, eleven to go!

Adjacent checks

After the character class checks, I was getting a little faster. There’s a ton of code, but eventually you learn how it indexes arrays, and that makes it much easier, since you can skip by about 95% of the code.

This section starts here:

 1 .text:0040AEE5                 mov     rdi, [rbp-70h]
 2 .text:0040AEE9                 mov     r15, rax
 3 .text:0040AEEC                 call    do_validation_5 ; Validates adjacent letters, and their relationships to each other
 4 .text:0040AEEC                                         ; rdi = pointer to string buffer
 5 .text:0040AEF1                 mov     [rbp-68h], rax  ; rax shouldn't be 0
 6 .text:0040AEF5                 mov     rax, r15
 7 .text:0040AEF8                 add     rsp, 0
 8 .text:0040AEFC                 pop     r9
 9 .text:0040AEFE                 pop     r8
10 .text:0040AF00                 mov     r15d, [rbp-68h]
11 .text:0040AF04                 cmp     r15d, 0
12 .text:0040AF08                 jz      bad_place5

Note that I’m not doing this in order; I don’t have to, since I disable the checks I’m not using!

Inside my stupidly named do_validation_5() (I didn’t know what it was going to do when I named it!), you’ll see the same pattern over and over and over; it loads a letter, then the next letter, and compares them with either jg (jump if greater) or jl (jump if less):

1 .text:00404FE2                 mov     r10, [r10]       ; first letter
2 .text:00405087                 mov     r11, [r11]       ; second letter
3 .text:0040508A                 cmp     r10d, r11d
4 .text:0040508D                 jg      short loc_405096 ; good jump
5 .text:0040508F                 mov     ebx, 0           ; bad
6 .text:00405094                 jmp     short loc_40509B

If you go through this, you’ll get the following relationships:

character[1]  > character[2]
character[2]  > character[3]
character[3]  < character[4]
character[4]  > character[5]
character[5]  > character[6]
character[6]  < character[7]
character[7]  > character[8]
character[8]  < character[9]
character[9]  < character[10]
character[10] < character[11]
character[11] > character[12]
character[12] < character[13]
character[13] > character[14]
character[14] < character[15]
character[15] < character[16]
character[16] > character[17]
character[17] < character[18]
character[18] > character[19]
character[19] < character[20]
character[20] > character[21]
character[21] < character[22]
character[22] > character[23]
character[23] > character[24]

When I got to this point, Mak started writing a Prolog and also a Python program so we could take these relationships and start deriving relationships. In the end, he started working on another flag, and I never actually used these relationships to solve anything…

On the plus side, after the first few, it was fast going! I did the first seven or eight carefully and with a debugger, and all the rest I just blew through in about a half hour!

Shift checks

So, I purposely waited to work on these ones, because they called long functions, which called other long functions, which did crazy shifty stuff. After I actually started reversing, I realized that it was actually pretty easy—most of them did the same thing! Everything in this binary looks long and complicated, though.

Let’s start with one of the innermost functions. Removing all the crap, it does this:

 1 .text:00400E75 shift10         proc near
 2 .text:00400EAA                 mov     rax, rdi        ; rax = arg
 3 .text:00400EC8                 mov     r10, rax        ; r10 = arg
 4 .text:00400ECB                 mov     r11d, 0Ah       ; r11 = 10
 5 .text:00400ED2                 mov     r15d, r10d      ; r15 = arg
 6 .text:00400ED5                 mov     ecx, r11d       ; ecx = 10
 7 .text:00400ED8                 sar     r15d, cl        ; r15 = arg >> 10
 8 .text:00400EDB                 mov     ebx, r15d       ; ebx = rdi >> 10
 9 .text:00400EDF                 mov     r10d, 1Fh       ; r10 = 0x1f
10 .text:00400F00                 and     ebx, r10d       ; ebx = (arg >> 10) & 0x1f
11 .text:00400F03                 mov     rax, rbx
12 .text:00400F1B                 pop     rdi
13 .text:00400F1C                 jmp     rdi

Which is basically:

1 return (arg >> 10) & 0x1F

Easy! There are actually a bunch of functions that do almost the same thing:

1 def shift0(c)  return (c >> 0) & 0x1F; end
2 # Oddly, there's no shift5()
3 def shift10(c) return (c >> 0) & 0x1F; end
4 def shift15(c) return (c >> 0) & 0x1F; end
5 def shift20(c) return (c >> 0) & 0x1F; end
6 def shift25(c) return (c >> 0) & 0x1F; end
7 def shift30(c) return (c >> 0) & 0x03; end

Then those functions are called from two others (actually, three, but the third is never used in the code we care about):

1 .text:00401E96 shifter()
2 .text:00402413 shifter2()

I’m not going to waste your time by reversing them. They’re kinda long, but fairly simple. Here is what they end up as:

1 def shifter(c, i = 0)
2   return i | (1 << shift10(c)) | (1 << shift5(c)) | (1 << shift0(c))
3 end
5 def shifter2(c, i = 0)
6   return i | (1 << shift25(c)) | (1 << shift20(c)) | (1 << shift10(c)) | (1 << shift0(c))
7 end

Basically, take various sequences of five bytes within the string, and set those bits in another value!

Now, how are these used? The first use is easy, and is actually the second-simplest check (after the length check). It looks like this (once again, I’ve removed obfuscating lines):

1 .text:0040B04B      mov     rsi, [rbp-80h]  ; rsi = last character
2 .text:0040B04F      mov     r15, rax
3 .text:0040B052      call    shifter
4 .text:0040B057      mov     [rbp-70h], rax
5 .text:0040B066      mov     qword ptr [rbp-78h], 0
6 .text:0040B06E      mov     dword ptr [rbp-78h], 80000003h
7 .text:0040B075      mov     r15d, [rbp-70h]
8 .text:0040B079      cmp     r15d, [rbp-78h]
9 .text:0040B07D      jz      short loc_40B093 ; Good jump

So the last line of the string is the symbol that, when put through shifter(), produces 0x80000003? That’s easy! Here’s a quick Ruby program (I actually did it in a much more complicated way originally, by literally reversing the algorithm, but that was dumb):

1 0x20.upto(0x7F) do |i|
2 if(shifter(i) == 0x80000003)
3     puts("Character: #{i.chr}")
4 end
5 end

Which prints out:

1 ron@debian-x86 ~$ ruby ./do_shift.rb
2 Character: ?

The last character is a question mark! Awesome!

After that, there are a bunch of checks (all remaining checks but two, in fact!) that all sort of look the same (and are implemented inline, not in functions). One of them you can find starting at 0x0040BEAD, and the logic is something like this:

 1 c = second_character;
 2 if(shifter(c, c) == shifter2(c, c))
 3 {
 4   if(shifter(c - 0x20, c - 0x20) != shifter2(c - 0x20, c - 0x20))
 5   {
 6     if(c < 'i' && c > 'd')
 7     {
 8       acceptable_second_character(c);
 9     }
10   }
11 }

Implementing it in Ruby (this code will only work in 1.9 because of String.ord()) will look something like this:

 1 ?A.upto(?Z) do |i|
 2   i = i.ord
 3   (set &lt;&lt; i) if(shifter(i, i) == shifter2(i, i))
 4 end
 5 ?a.ord.upto(?z.ord) do |i|
 6   i = i.ord
 7   (set &lt;&lt; i) if(shifter(i, i) == shifter2(i, i))
 8 end
10 set.each do |i|
11   if(shifter(i - 0x20, i - 0x20) != shifter2(i - 0x20, i - 0x20))
12     if(i &gt; ?d.ord &amp;&amp; i < ?i.ord)
13       puts(i.chr)
14     end
15   end
16 end

And running it:

1 $ ruby do_shift.rb
2 h

Tells us that the only possibility is ‘h’! We just solved the second letter!

There are a ton of checks like this, and I’m not going to go over the rest of them. The only other noteworthy “shift” check is the function defined here:

1 .text:00406F32 check_duplicates

Which goes through a bunch of fields, and requires them to be equal to one another (eg, the sixth, eighth, and nineteenth characters are the same; the fourteenth and seventeenth letter are the same; etc).

When all’s said and done, at the end of the ‘shift’ stuff, and including the character class checks, we have the following properties:

  Character 1  :: 'w'
  Character 2  :: 'h'
  Character 3  :: 'e'
  Character 4  :: Lowercase letter = the 10th character + 1
  Character 5  :: 'e'
  Character 6  :: Symbol, same as 8th and 19th characters
  Character 7  :: 'u', 'v', or 'w'
  Character 8  :: Symbol, same as 6th and 19th characters
  Character 9  :: Number
  Character 10 :: Lowercase
  Character 11 :: Letter
  Character 12 :: 'e'
  Character 13 :: 'n'
  Character 14 :: Uppercase, same as 17th
  Character 15 :: 'h', 'i', 'j', or 'k'
  Character 16 :: Letter, same as 18th
  Character 17 :: Uppercase, same as 14th
  Character 18 :: Letter, same as 16th
  Character 19 :: Symbol, same as 6th and 8th
  Character 20 :: 'n'
  Character 21 :: 'a' or 'A'
  Character 22 :: Letter
  Character 23 :: Uppercase
  Character 24 :: '?'

To put it another way:


I reached this point… maybe 5am on Saturday night? The next hour me and Rylaan and others spent trying to make guesses. We were reasonably sure that the fourth letter was ‘r’, making the first word ‘where’. That would make the tenth character a ‘q’ and the eleventh a ‘u’. That worked out pretty well. And putting a ‘u’ in the seventh character (since it’s much more likely than ‘v’ or ‘w’) and making the symbols into spaces made sense. That gave us:

  where u #quen_____ na__?

We also surmised that the last word was ‘namE’ or ‘nAME’ or something, but that turned out to be wrong so I won’t show that part off. :)

Here is what I had scribbled down at this point.

Before bed, I wrote a quick Ruby script that would bruteforce guess all unknown characters, hoping to guess it by morning. That was also a failure. It barely got anywhere in the three hours I slept.


I went to sleep on the hackerspace couch at 6am Saturday night, and woke up at 9am with the idea: “quantum”! “where u quantum name” or something. So I jumped up, ran to the computer, and realized that that made no sense. Crap! But I was already up, may as well work on it more. I spent the next little while updating Mak on my progress and thinking through the next step.

I spent a few hours working on these four checksum values:

1 .text:0040AD41                 mov     dword ptr [rbp-78h], 0FAF7F5FFh ; checksum1
2 .text:0040AD81                 mov     dword ptr [rbp-90h], 0A40121Fh  ; checksum2
3 .text:0040AE00                 mov     dword ptr [rbp-78h], 0FF77F7F6h ; checksum3
4 .text:0040AE4F                 mov     dword ptr [rbp-90h], 0FD9E7F5Fh ; checksum4

I spent hours trying to reverse how those were calculated before finally giving up. I was running out of ideas. I had eleven of the thirteen checks passing, with only the four checksums (in two checks) to go! Gah!

I noticed an interesting property in the checksums, though: the values I was generating were actually quite close to the real ones, compared to what they’d originally been! If I changed a known “good” character to a bad one, it got worse. All I had to do was figure out a way to either generate the checksums myself or pull them from memory! At this point in the game, generating them myself was pretty much outta the question, so I had to find a way to extract them, and quickly!

I won’t bore you with the failed attempts, only the successful attempt. It’s a Ruby program, and it looks something like this (check out the sweet syntax highlighting, I even highlighted the gdbinit file properly; that wasn’t easy!):

  1 def count_bits(i)
  2   bits = 0
  4   while(i != 0) do
  5     if((i & 1) == 1)
  6       bits += 1
  7     end
  9     i >>= 1
 10   end
 12   return bits
 13 end
 15 def go(str)
 16   puts(" String: '#{str}'")
 18   # Write the current test string to a file called 'stdin'
 19   File.open("./stdin", "w") do |f|
 20     f.write(str)
 21   end
 23   File.open("./gdb", "w") do |f|
 24   f.write <<EOF
 25 # Set up the environment
 26 set disassembly-flavor intel
 27 set confirm off
 29 # Disable the anti-debugging
 30 set environment LD_PRELOAD ./overload.so
 32 # Read from the "stdin" file, which is where we're writing the data
 33 set args < ./stdin
 35 # Break at the first check (the length)
 36 b *0x040AC83
 37 run
 39 # Make all 4 checksums run by forcing jumps to happen
 40 set {char}0x40AD50 = 0xeb
 41 set {char}0x40AE0F  = 0xeb
 43 # Checksum 1 and 2
 44 set {int}0x040ADD3 = 0x90909090
 45 set {short}0x040ADD7 = 0x9090
 47 # Checksum 3 and 4
 48 set {int}0x040AEA1 = 0x90909090
 49 set {short}0x040AEA5 = 0x9090
 51 # TODO: Test once mak finishes the python tool
 52 # Check adjacent characters
 53 set {int}0x040AF08 = 0x90909090
 54 set {short}0x040AF0C = 0x9090
 56 # Checksum1
 57 b *0x000000000040AD4C
 59 # Checksum2
 60 b *0x000000000040AD92
 62 # Checksum3
 63 b *0x000000000040AE0F
 65 # Checksum4
 66 b *0x000000000040AE60
 68 cont
 70 print/x $r15
 71 cont
 73 print/x $r15
 74 cont
 76 print/x $r15
 77 cont
 79 print/x $r15
 80 cont
 82 # We continue before quitting so we can make sure 'Success!' is printed
 83 quit
 85 EOF
 86   end
 88   checksums = []
 90   # Our list of known-good checksums
 91   good_checksums = [0xFAF7F5FF, 0xA40121F, 0xFF77F7F6, 0xFD9E7F5F]
 93   # Run gdb with our new config file
 94   IO.popen("gdb -x ./gdb ./cnot") {|p|
 95     loop do
 96       line = p.gets
 97       if(line.nil?)
 98         break
 99       end
100       if(line =~ / = /)
101         checksums << line.gsub(/.* = /, '').chomp.to_i(16)
102       end
104       if(line =~ /Wrong/)
105         puts(line)
106         puts("ERROR!")
107         exit
108       end
109     end
110   }
112   puts(" Expected: %08x %08x %08x %08x" % [good_checksums[0], good_checksums[1], good_checksums[2], good_checksums[3]])
113   puts(" Received: %08x %08x %08x %08x" % [checksums[0],      checksums[1],      checksums[2],      checksums[3]])
115   # Count the different bits and print the difference
116   diff = count_bits(good_checksums[0] ^ checksums[0]) + count_bits(good_checksums[2] ^ checksums[2]) + count_bits(good_checksums[1] ^ checksums[1]) + count_bits(good_checksums[3] ^ checksums[3])
117   puts(" Difference: %d" % diff)
118   puts()
120   # Return the difference so we can save the best one
121   return diff
122 end
124 diffs = {}
126 ?0.upto(?9) do |i|
127   i = i.chr
129   str = "where u #{i}quenTisTs naME?"
130     diff = go(str)
132     diffs[diff] = diffs[diff] || []
133     diffs[diff] << "#{i} :: #{str}"
134   end
135 end
137 # Print the best option(s)
138 i = 0
139 loop do
140   if(!diffs[i].nil?)
141     puts("== #{i} ==\n#{diffs[i].join("\n")}")
142     exit
143   end
145   i += 1
146 end

And in that particular configuration, the program attempts every possible number for the start of the third word:

 1 $ ruby ./cs.rb
 2  String: 'where u 0quenTisTs naME?'
 3  Expected: faf7f5ff 0a40121f ff77f7f6 fd9e7f5f
 4  Received: fafff5ff 1240021f f377f5e7 fd92ff7f
 5  Difference: 13
 7  String: 'where u 1quenTisTs naME?'
 8  Expected: faf7f5ff 0a40121f ff77f7f6 fd9e7f5f
 9  Received: fafff5ff 1240021f f377fde6 fd927fff
10  Difference: 13
12  String: 'where u 2quenTisTs naME?'
13  Expected: faf7f5ff 0a40121f ff77f7f6 fd9e7f5f
14  Received: fafff5ff 1240021f f377fde6 fd927f7f
15  Difference: 12
17  String: 'where u 3quenTisTs naME?'
18  Expected: faf7f5ff 0a40121f ff77f7f6 fd9e7f5f
19  Received: fafff5ff 1240021f f777f5f6 fd967f7f
20  Difference: 8
22  String: 'where u 4quenTisTs naME?'
23  Expected: faf7f5ff 0a40121f ff77f7f6 fd9e7f5f
24  Received: fafff5ff 1240021f f377f5ee ffd27f7f
25  Difference: 14
27  String: 'where u 5quenTisTs naME?'
28  Expected: faf7f5ff 0a40121f ff77f7f6 fd9e7f5f
29  Received: fbfff5ff 1240021f f37ff5e6 fd927f7f
30  Difference: 13
32  String: 'where u 6quenTisTs naME?'
33  Expected: faf7f5ff 0a40121f ff77f7f6 fd9e7f5f
34  Received: fafff5ff 1240021f f377fde6 fd927f7f
35  Difference: 12
37  String: 'where u 7quenTisTs naME?'
38  Expected: faf7f5ff 0a40121f ff77f7f6 fd9e7f5f
39  Received: fefff5ff 1240021f f377f5e6 fd927f7f
40  Difference: 12
42  String: 'where u 8quenTisTs naME?'
43  Expected: faf7f5ff 0a40121f ff77f7f6 fd9e7f5f
44  Received: fafff5ff 1240021f f3f7f5e6 fdd27f7f
45  Difference: 13
47  String: 'where u 9quenTisTs naME?'
48  Expected: faf7f5ff 0a40121f ff77f7f6 fd9e7f5f
49  Received: fafff5ff 1240021f f377f5e6 fd927f7f
50  Difference: 11
52 == 8 ==
53 3 :: where u 3quenTisTs naME?

As you can see, the best result we got from this was eight bits different, and the number ‘3’ (which tuned out to be correct)!

We did this over and over for different letters, occasionally repeating letters if we wound up getting bad results, getting closer. I considered writing an A* search or something, I bet we could have optimized this pretty good, but that turned out to not be necessary. Eventually, I was reasonably sure everything was right except for the last two letters (in ‘naME’), so I decided to try every possible pairing:

 1 ?a.upto(?z) do |i|
 2   i = i.chr
 3   ?A.upto(?Z) do |j|
 4     j = j.chr
 5     str = "where u 3quenTisTs na#{i}#{j}?"
 6     diff = go(str)
 8     diffs[diff] = diffs[diff] || []
 9     diffs[diff] &lt;&lt; "#{i} :: #{str}"
10   end
11 end

And eventually, it printed out:

 1 $ ruby cs.rb | tail
 2 Received: 7ef7f7ff 0240221f f7f7f5f6 fd96ffff
 3 Difference: 13
 5 String: 'where u 3quenTisTs nazZ?'
 6 Expected: faf7f5ff 0a40121f ff77f7f6 fd9e7f5f
 7 Received: 7ef7f5ff 0240421f f777f5fe fd977f7f
 8 Difference: 11
10 == 0 ==
11 o :: where u 3quenTisTs naoW?

The answer! I punched it into the site, and it worked. omg!!! #bestfeelingever


I realize this was an extremely long writeup, for an extremely elaborate level. It took a long time to solve, and I was exceptionally proud. Did I mention that, at 450 points, it was the most valuable flag in the entire competition?

Just to go over what I had to overcome:

  • Anti-debugging
  • Anti-reversing (obfuscation)
  • More code obfuscation
  • A series of "letter n is between x and y" type solutions, instead of actual "this letter is z" solutions
  • Crazy checksums that, it turns out, used Fibonacci sequences (I never did reverse them)

And that’s cnot in a nutshell. Thanks for reading!


Join the conversation on this Mastodon post (replies will appear below)!

    Loading comments...