## ESET CONFidence 2010 Crackme - WriteUp

By JB » Wednesday 1 December 2010, 15:43 - Conferences

ESET proposed a crackme during the CONFidence conference. Challenge started on November, 29th and lasted two days. The goal was to find a valid username/serial combination. Challenge was won by Dmitry Sklyarov, from ElcomSoft. This article will present a solution for the crackme, and the steps needed to write a key generator for it. Even if the crackme size is only 11.5kB, many tricks are used to make the verification routine tricky enough to resist a few hours.

## An easy start

The crackme is a Windows application, and asks for a name and a serial number. The serial must be composed of two parts, separated by a hyphen. The first part is 8 chars long, the second one is 20 chars.

First, the name is hashed with MD5. The resulting hash is converted to a string of 16 lower chars, using a basic encoding function:

`for(i = 15; i >= 0; i--)`

{

out[i] = 'a' + (hash[i] % 26);

}

The resulting string is converted to UNICODE and hashed with the `RtlHashUnicodeString`

function. This function is exported by `ntdll.dll`

. It returns a 32 bits hash using the x65599 (?) hashing algorithm. Input string is processed case insensitive. A pseudo-code for this function would be:

`def x65599(string_to_hash):`

hash = 0

s2 = string_to_hash.upper()

for i in range(len(s2)):

c = ord(s2[i])

hash = (hash * 65599) & 0xffffffff

hash = (hash + c) & 0xffffffff

return hash

To sum up, a 32 bit hash is obtained from the user name.

## Reversing CRC32

The first part of the serial, composed of 8 chars, is hashed using CRC32. The computation is done with the `RtlComputeCrc32`

function. The initial value of the CRC32 is fixed to 'ESET' (`0x45534554`

). The resulting hash must be equal to the x65599 hash previously computed.

Obtaining a string with a given CRC32 is easy, if you can fix 4 bytes in it. For more information about CRC32 reversing, check this paper. The additional difficulties here are the custom start value and the fact that this string must be written using a custom set of 32 chars: "2WQKHTL3VJBYG6PZCM9AXF0UED5RS7N8".

How to handle such case? I chose to generate a string of 4 random chars taken in the charset, and to fix its CRC adding 4 bytes to it, so that the CRC is equal to the x65599 hash. Then, if the 4 added bytes are in the charset, the problem is solved. Else, I try with another string.

It is a small bruteforce: considering the possibility of each char to be in the charset is 32/256, the probability that the 4 added chars are in the charset is 1/2^12, which is really acceptable.

Here is the Python code used to fix the CRC:

`def build_crc_tables():`

for i in range(256):

fwd = i

rev = i << 24

for j in range(8, 0, -1):

# build normal table

if (fwd & 1) == 1:

fwd = (fwd >> 1) ^ 0xedb88320

else:

fwd >>= 1

crc32_table[i] = fwd

# build reverse table =)

if rev & 0x80000000 == 0x80000000:

rev = ((rev ^ 0xedb88320) << 1) | 1

else:

rev <<= 1

crc32_reverse[i] = rev

def crc32forge3(wanted_crc):

''' return a 8 chars string whose crc32 is equal to wanted_crc '''

charset = '2WQKHTL3VJBYG6PZCM9AXF0UED5RS7N8'

start_value = 0x45534554 ^ 0xffffffff # ESET

while 1:

# generate random string of 4 chars

s = ''.join(charset[random.randint(0, 31)] for i in range(4))

crc = start_value

for i in range(4):

crc = (crc >> 8) ^ crc32_table[(crc ^ ord(s[i])) & 0xff]

s += pack('<L', crc)

crc = wanted_crc ^ 0xffffffff

for i in range(7, 3, -1):

crc = (crc << 8) ^ crc32_reverse[crc >> 24] ^ ord(s[i])

crc &= 0xffffffff

s2 = s[:4] + pack('<L', crc)

# check if added bytes are in the charset

# else same player play again

valid = True

for i in range(4):

if charset.find(chr((crc >> (8 * i)) & 0xff)) == -1:

valid = False

continue

if valid == True:

return s2

crc32forge3(x65599_hash) # for example

Finding the first part of the serial is quite immediate.

## A strange decimal conversion

The second part of the serial is 20 chars long. It is converted to a 64 bit integer `n`

in the `sub_4012DC`

function. This function is a bit tricky. Basically, it does a decimal string to integer conversion: each time a byte is read, `n`

is multiplied by 10, the serial byte is converted to an integer between 0 and 9, and added to `n`

.

How are the chars converted to a decimal value? This is the difficulty of this part. Input chars are checked like this:

`movzx eax, byte ptr [esi] ; esi points to the input string`

inc esi

test eax, eax

jz short end_function

xor ebx, ebx

xor edx, edx

sub eax, 32h ; eax -= 0x32

jb short end_function

test eax, 0E0h

jnz short end_function

mov edx, 1Fh ; 5 bits set to 1

mov ecx, 4

loop1_start: ; CODE XREF: sub_4012DC+3D

cmp eax, edx

jz short loop1_end

btc edx, ecx ; test and complement

inc ebx

dec ecx

jns short loop1_start

loop1_end: ; CODE XREF: sub_4012DC+36

jz short loop2_end

mov ecx, 4

loop2_start: ; CODE XREF: sub_4012DC+4F

cmp eax, edx

jz short loop2_end

btc edx, ecx ; test and complement

inc ebx

dec ecx

jns short loop2_start

loop2_end: ; CODE XREF: sub_4012DC:loop1_end

; sub_4012DC+48

jnz short end_function

0x32 is subtracted to each char. Resulting value must be different from 0. Then, two loops are executed. They iterate reading the 5 lower bits of each char. Each loop exits when the read bit is different from the previous one. Once the two loops have been executed, the 5 bits have to be read. That means that to be valid, a char must be composed of

- a sequence of 1 followed by a sequence of 0,
- or a sequence of 0 followed by a sequence of 1.

Only 10 5-bit values validate this condition: 11111, 01111, 00111, 00011, 00001, 10000, 11000, 11100, 11110. Adding 0x32 to each of these values, we obtain the 10 bytes charset: 'Q', 'A', '9', '5', '3', '2', 'B', 'J', 'N' and 'P'. The value between 0 and 9 is contained, after the two loops, in the ebx register. It means that it is equal to the number of iterations the two loops have been executed while reading the byte.

To sum up, we know that `sub_4012DC`

converts a string encoded in a 10 bytes custom charset into a 64 bit integer. In order to write a key generator, the inverse function has to be coded. It takes a number as input, and generates the corresponding encoded string. Here is the code:

`def decimal_encode(n): `

charset = 'QA9532BJNP' # btc stuff

s = ''

for i in range(20):

s = charset[n % 10] + s

n /= 10

return s

## ElGamal signature

The last part of the crackme is about a ElGamal signature verification. ElGamal signatures are composed of two numbers (r, s).

### Retrieving message and signature

The first part of the serial, whose generation is explained above, is hashed with MD5. A 16 byte digest is obtained. It is used to generate a 64 bit integer. This integer is the `r`

in the ElGamal signature. The function that converts the digest to a 64 bit integer is the following one:

`sub_4012C2 proc near ; CODE XREF: sub_4014C3+C6`

; sub_4014C3+DB

arg_0 = dword ptr 4

push esi

mov esi, [esp+4+arg_0]

mov eax, [esi]

mov edx, [esi+4]

xor eax, [esi+8]

xor edx, [esi+0Ch]

and edx, 7FFFFFFFh

pop esi

retn 4

sub_4012C2 endp

Basically it casts the digest into an array of unsigned integers `ll`

, and computes ` & 0x7fffffffffffffff`

.

`s`

is the second part of the serial after its conversion to a number using explained above.

The user name is hashed with MD5. The resulting hash is converted to a 64 bit integer with `sub_4012C2`

. Let's call this number `h`

.

### Finding group parameters

ElGamal security relies on the discrete logarithm problem. To make it short, it consists in finding x such as g^x = y mod p, given g, y and p. g, y and p are public parameters.

The signature is checked in `sub_40121A`

. This function calls two big integers functions, `powmod64`

(`sub_4011B0`

) which is a basic square-and-multiply modular exponentiation, and `mulmod64`

(`sub_401178`

). Before being able to generate valid signatures, public parameters have to be identified.

The group generator is easy to spot: it is present in the signature verification function.

`.text:00401237 mov dword ptr [edx], 3 ; generator`

.text:0040123D mov dword ptr [edx+4], 0

.text:00401244 push esi ; h

.text:00401245 push edx

.text:00401246 push eax ; result

.text:00401247 call powmod64 ; compute g^h mod p

So `g = 3`

. `y`

is also easy to identify: its value is 0x5353453233444f4e (`"NOD32ESS"`

).

`p`

is not a parameter of the `powmod64`

function, which is a bit confusing. It is actually hardcoded inside this function, more precisely in the `mod64`

function (`sub_40110B`

):

`.text:0040113E push 0FFFFFFFFh`

.text:00401140 push 0FFFEA007h

.text:00401145 push edx

.text:00401146 push eax

.text:00401147 call RtlLargeIntegerSubtract

Hence `p = 0xFFFFFFFFFFFEA007`

, which is prime.

### Generating signatures

All the parameters have been found, we can now generate a signature. First, the private key has to be found: it is `x`

such as `g^x = y mod p`

.

The order of the generator `g=3`

is `p-1`

, which is a smooth number:

p-1 = 2 * 3 * 3 * 5 * 7 * 11 * 13 * 3797 * 42701 * 1262887

Hence the private key can be efficiently computed using the Pohlig-Hellman algorithm. I included a version of the algorithm in the keygen source code. It is inspired from the Handbook of Applied Cryptography.

`x`

is quickly found: `x = 0x62dd00828bb0e577L`

Now we have all the necessary information to generate valid signatures. Wikipedia gives us the formula:

`p = 0xfffffffffffea007L`

g = 3

y = 0x5353453233444f4eL

x = 0x62dd00828bb0e577L

h = ...

k = ... # random_value such as gcd(k, p-1) == 1

r = pow(g, k, p)

s = ((h - x * r) % (p-1))

s = s * number.inverse(k, p-1) % (p-1)

And the crackme is solved. Almost.

### A last problem

The code just above generates `r`

and `s`

values that sign the message `h`

. The problem is different here: remind that `r`

comes from the MD5 of the first part of the serial. It cannot be chosen randomly, and must be considered as a fixed value...

`r = pow(g, k, p)`

is fixed. What is rather annoying is that `k`

, normally chosen at random, is necessary to compute `s`

. How to retrieve `k`

from `r`

? Solving another discrete logarithm problem is necessary...

`r`

depends on the hash of the first part of the serial. This part depends on the hash of the user name. Hence, for each user name, a discrete logarithm has to be solved to generate a valid signature.

Finally, once `k`

has been found, one has to check that it is co-prime with p-1, else k has no inverse mod p-1, and `s`

cannot be computed.

Once all theses steps have been understood, it is time to code a key generator. Source code is attached. The more interesting parts in this source are the CRC32 reversing function, and the runtime DLP solver, which uses Pohlig-Hellman and Pollard's Rho algorithm to compute rather efficiently the logarithms, even if it is written in Python.

I thank the ESET team for this nice crackme. Hiding such tricks in a so small piece of code is tremendous =)

## Comments

Awesome! Excellent work man :)