Home > Reverse Engineering > Solving confidence 2011 crackme for fun and profit

Solving confidence 2011 crackme for fun and profit

Confidence is a security conference organized in Poland. During this year’s edition (and like during few previous editions) a crackme contest took place — attendees were invited to provide a solution (serial, keygen). The fastest one would win the prize (pocketbook reader).

Surprisingly, no one was able to solve the crackme during the con, except for simonzack, who apparently wasn’t an attendee. Simon posted a solution few days ago, you can read it on his blog.

I didn’t plan to participate, because I didn’t want to spend time analyzing crackmes during lectures, besides I didn’t even take a laptop with me, as I figured few days without staring at a screen would have a good impact on my mental health :P. Luckily, since no attendee provided a solution, organizers decided to prolong the contest, so I was able to take a look at the crackme after I got back from the con.

Fun

I won’t bore you with deadlistings this time, but provide a high-level view of the protection and my approach.

def check(name, serial):
    hash = hash(name) #identified as CubeHash, by Dcoder
    d1, d2 = mangle(hash+serial)
    return d1==const1 and d2==const2

Serial is a 64-bit number. Function mangle consumes whole input buffer, one dword at a time and returns two 32-bit values. Since we can’t control hash variable, we’ll have to use serial to force mangle to return expected values (const1, const2).

The main problem is that mangle is very long (~10KB) and “obfuscated” with heavy macro use. Analysing it by hand seemed like a boring thing to do.

By the look of this function (mostly bit manipulations) and considering the fact that it takes a big buffer, with serial appended at the end I started suspecting it’s some kind of CRC. “Reversing” a N-bit CRC requires only N-bits of input (see this, or this). That means if you have a buffer, and want (for example) CRC32 of that buffer to be X, you need to append a special DWORD at the end. You don’t need to bruteforce this magic DWORD, you can compute it easily.

By evaluating mangle on some constants you will notice its results don’t match those of a standard CRC64. Perhaps this function isn’t CRC at all? There is one property that all variants of CRC64 should share: linearity. Every CRC (starting value and polynomial don’t matter) is a homomorphism with respect to XOR:

CRC(x \oplus y) = CRC(x) \oplus CRC(y)

Proof here (appendix A). Quick check in a debugger shows that’s indeed the case.

With this information, we can easily reimplement the algorithm, by observing that any value can be represented as a XOR of powers of 2. For example: 1011 = 1000 \oplus 0000 \oplus 0010 \oplus 0001

Generally, let e_i = 2^i, then (our variant takes one dword at a time):

CRC64(\sum_{i=0}^{31} e_i) = CRC64(e_0) \oplus CRC64(e_1) \oplus ... \oplus CRC64(e_{31})

As a consequence, it’s sufficient to compute CRC64(e_i) for 0\leq i \leq 31, to be able to evaluate CRC64 for any input. We can use the crackme itself to compute these values, with a bit of OllyScript magic :).

Here’s the reimplemented CRC64:

def crc64(hi, lo, tab, dw): #tab is the ripped table
    HI = 0
    LO = 1

    old_lo = lo

    lo = 0
    hi = 0
    for pos in range(32):
        b = dw>>pos
        b = b & 1
        if b:
            hi ^= tab[pos][HI]
            lo ^= tab[pos][LO]

    return (hi^old_lo,lo)

Much better than ~10KB of code :).
Back when I was solving it, time was of essence — I didn’t knew with how many people I’m racing for a solution, so instead of reversing this algorithm (it’s a set of linear equations, tab is a matrix, dword a vector, and it can be solved fast with gaussian elimination, for example) I ported it to C and bruteforced a solution (~10 mins).

There are few technicalities left out. Producing a working serial is a bit more complicated, than just reversing the CRC, but in my opinion that was the biggest obstacle worth describing.

So here it is, a working serial number:

pa_kt
7e476857-pcp1aa1agslatl3tptgs

Crackme and sources are available here.

Profit

These photos could have been better, sorry about that :P. If you are wondering: the OS is just custom a linux distro, you can upload your binaries and run them without any restrictions, so there is nothing to break, unfortunately :).

Speaking of linux, crackme unpacks an ELF binary from its resources (.rsrc section) and cleverly maps into it’s own address space. It’s quite cool, so check it out :).

Advertisements
  1. 30/06/2011 at 09:13

    Good work, mate! Bah, you only overtook me by a few hours… 🙂

    • 04/07/2011 at 22:24

      I hope next year crackme will be released *before* the con, so people can pick it apart without missing the lectures…

  2. 05/07/2011 at 10:19

    Yeah, that’s my expectation, as well – not only in the context of the CrackMe, but also other conference competitions that might’ve been solved, if people were given more time / better working conditions.

  1. No trackbacks yet.

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

%d bloggers like this: