This is a writeup of the challenge rarara from the secuinside 2014 pre-qual ctf.

I participated in this challenge together with Yoav Ben Shalom, Matan Mates, and Itamar Marom. This was the probably the hardest challenge in the competition and only one team had managed to solve it a few hours before the competition ended when my team had to leave early.

We had figured out the solution but ran out of time before implementing it. Had we stayed and finished this level and another we likely would have been in the top ten teams, but oh well!

The challenge

We were given a binary. You can download it from here. Running it from the command line yields

While the easy solution might be to install 64 bit windows, examining the assembly reveals that the code is actually 32 bit binary. I’m not sure why this check is done, but it’s easy enough to patch it (a single jz -> jnz) and allow the binary to run on 32 bit systems.

Next we are presented with a prompt asking for input. Trying a few random inputs, we get the message “Wrong!”. It’s time to open up IDA and see what this program does!

Anti-reversing

Once we’ve identified the important function, we can see a few things. First, the length of the input is checked and compared to 13.

Then each of the letters is checked to make sure it is alphanumeric

And then we reach this block at which point IDA’s analysis fails us:

This block is repeated in many different locations throughout the code.

What is this block doing? When we call $+5 it puts our address on the stack. 3E+var3E is 0x3E - 0x3E = 0, so the add instruction adds 5 to the address just placed on the stack. Finally, we return to that address, or just after the retf instruction.

In other words, this whole block is just a compilicated nop that screws with IDA’s autoanalysis. By patching the binary to replace all instances of this block (plus some slight variations) with nops, we turn this:

into this:

So straight and organized! Now we can start working.

Understanding how the password is checked

After making sure that all of the characters are alphanumeric, the program places the letters into a global array in jumps of 0x14 while keeping track of the sum. The sum is later compared to 0x3E2 giving us our third constraint on the password (the other two being length and alphanumericness).

The global array is then processed in a loop. This was the third challenge in the competition involving CRC’s, so we quickly recognized the loop as calculating the crc64 of the global array (of length 0x100) with the letters of our password placed in the indexes as described above. The crc is then compared to a constant value.

If it is correct, then the value “Correct” is placed in the buffer where “Wrong” was held before so “Correct” will be printed at the end of the program.

So, to summarize we need to find a password of length 13 comprised of alphanumeric characters whose sum is 0x3E2 and whose CRC64 when placed in a set array at specific indexes is equal to 0x15AD90B88ABA1847

Breaking CRC

A previous challenge involved appending data to the end of a string in order to obtain arbitrary CRCs. That’s a less helpful ability for this challenge since we’re not changing 8 consecutive bytes in the crc (so the same algorithm doesn’t apply) and there’s no way of ensuring we will only have alphanumeric characters.

However, there is an interesting property of CRC that we can use - CRC is a linear function. This means that CRC(x) ^ CRC(y) ^ CRC(z) = CRC(x^y^z). Since CRC(0) = 0 in this implementation (usually there is a xor with 0xxffff… that prevents this), we get CRC(x^y) = CRC(x) ^ CRC(y).

Using this knowledge, we can check how each bit of input affects the final CRC. We start by filling the array with a throwaway value - we filled the array with 0x41 (‘A’) as our base value. We then change a single bit and look at the new CRC. Since CRC(x ^ y) = CRC(x) ^ CRC(y) we get CRC(array with bit changed) = CRC(array) ^ CRC(effect of changing that bit)

In other words, we can look at what happens when we change a single bit and then figure out which bits we want to change and which we want to keep the same.

We do this by building up a matrix where each column is the effect of changing a single bit. By multiplying each row with the vector of whether or not we actually change each bit we should get the corresponding bit in the final CRC.

The problem then becomes one of solving a simple linear equation. Since we have 91 input bits (13 letters * 7 unknown bits since the upper bit is always 0) and 64 rows in our matrix (since the CRC is 64 bits long) we still need to iterate over 91 - 64 = 27 bits and check if the solution is valid (alphanumeric and proper sum).

We split our solution into two parts. First we generated a ranked matrix in python. We then found all of the solutions in C++ since our original python solution was too slow. You can see the code below.

Optimizations

The original C++ code was still very slow. It took around an hour to go over all of the possible values for 27 bits. The speed was significantly boosted by checking after every 7 bits if the letter was valid. This effectively allowed us to short circuit solutions that were known to be invalid and improved the speed to around 30 seconds.

The other major optimization was moving from vector<bool> to bitsets. Because bitsets have built in operator& and count functions that work effeciently the speed of the inner function was vastly improved (see below).

Using bitsets the speed of the program was reduced to 4 seconds.

But we can do even better :)

We know that the xor of the lower bits of all of the equations is zero, because the sum of the letters is even. Therefore, we can add a row to our matrix and we have one less bit that we have to brute force. Final speed is around 2 seconds.

Update: Even better

Michael Huzman pointed out that the builtin popcnt instruction should vastly improve the speed of the inner function. By adding the flag -march=corei7 gcc will automatically use this instruction for bitset’s count function. This again halves the speed and now it runs in 1.2 seconds!

Disassembly before and after:

Before:

0000000000401e80 <_Z5innerRKSt6bitsetILm91EES2_>:
  401e80:       48 89 5c 24 e8          mov    QWORD PTR [rsp-0x18],rbx
  401e85:       48 89 6c 24 f0          mov    QWORD PTR [rsp-0x10],rbp
  401e8a:       48 89 fb                mov    rbx,rdi
  401e8d:       4c 89 64 24 f8          mov    QWORD PTR [rsp-0x8],r12
  401e92:       48 83 ec 18             sub    rsp,0x18
  401e96:       48 8b 3f                mov    rdi,QWORD PTR [rdi]
  401e99:       48 23 3e                and    rdi,QWORD PTR [rsi]
  401e9c:       48 89 f5                mov    rbp,rsi
  401e9f:       e8 bc ec ff ff          call   400b60 <__popcountdi2@plt>
  401ea4:       48 8b 7b 08             mov    rdi,QWORD PTR [rbx+0x8]
  401ea8:       48 23 7d 08             and    rdi,QWORD PTR [rbp+0x8]
  401eac:       41 89 c4                mov    r12d,eax
  401eaf:       e8 ac ec ff ff          call   400b60 <__popcountdi2@plt>
  401eb4:       49 8d 04 04             lea    rax,[r12+rax*1]
  401eb8:       48 8b 1c 24             mov    rbx,QWORD PTR [rsp]
  401ebc:       48 8b 6c 24 08          mov    rbp,QWORD PTR [rsp+0x8]
  401ec1:       4c 8b 64 24 10          mov    r12,QWORD PTR [rsp+0x10]
  401ec6:       48 83 c4 18             add    rsp,0x18
  401eca:       83 e0 01                and    eax,0x1
  401ecd:       c3                      ret    
  401ece:       66 90                   xchg   ax,ax

After:

0000000000401df0 <_Z5innerRKSt6bitsetILm91EES2_>:
  401df0:       48 8b 17                mov    rdx,QWORD PTR [rdi]
  401df3:       48 8b 47 08             mov    rax,QWORD PTR [rdi+0x8]
  401df7:       48 23 16                and    rdx,QWORD PTR [rsi]
  401dfa:       48 23 46 08             and    rax,QWORD PTR [rsi+0x8]
  401dfe:       f3 48 0f b8 d2          popcnt rdx,rdx
  401e03:       f3 48 0f b8 c0          popcnt rax,rax
  401e08:       48 01 d0                add    rax,rdx
  401e0b:       83 e0 01                and    eax,0x1
  401e0e:       c3                      ret    
  401e0f:       90                      nop

Additionally, Yoav Ben Shalom noticed that when we get 3 bad last letters we can skip all 2^6 iterations that will yield the same letters. The gist below has been updated and now the code runs in 0.7 seconds!

The answer

Running the code yields 14 solutions that cause the program to output “Correct”. A quick check against the program confirms that they all work. Here’s the full list:

B0CFbYG14gbvA
TSG2MZ0bt3JJN
Xnu073LG6YC7q
tDDR3OA6Q7YDv
sJUA3vYTH5BI1
r2F1l2z2SyK33
4cUZ89Rti11h2
2x0LSbXAIwB84
i05SJ5E9pnl7C
R3V3s1nGkRG0G <-- Looks like t3xt
9X8LdMPGZL4Dg
0o4CaRv15p20k
V62T3zKIuDZI3
Jl2gKZf008oK6

Because we didn’t finish this challenge during the competition I can’t be completely sure but it looks like R3V3s1nGkRG0G was the solution.

You can see our code below, first the python and then the c++