Due to permanent lack of time and really long personal TODO list I’m not frequent crackme-solver, but sometimes it is good to check if my skills didn’t get rusty. I’ve browsed through unsolved crackmes on crackmes.de and found quite new gim913’s crackme that was unsolved for almost 2 months (yup, I know that it’s not much :) ). Knowing reputation of the author I’ve decided to give it a try, as probably there will be something interesting inside. So, let’s start.

### Static analysis

Crackme is written in pure **C++** without any obfuscation and anti-debugging, loading it to some old version of **IDA** didn’t showed much. Crackme was compiled by **Visual Studio 2010**, so I had to update my **IDA** signatures. Quick **PEiD** scan revealed that crackme is using **MD5** algorithm, which is worth to note, because I’ll take advantage of this info later. Identifying function that is responsible for user/pass check is fairly easy, looking for references to below strings may help:

.rdata:0041C560 db 'C O N G R A T U L A T I O N S !',0 .rdata:0041C580 db 'Wrong username!',0 .rdata:0041C590 db 'Wrong password!',0 |

All those strings are referenced by function that starts at **0x0040188E** address and this function plays a main role in the crackme, so I’ll call it **serial_check()** and refer to it by that name. **serial_check()** is quite long (almost 3kB of binary code) and calls many unrecognized functions. Manual analysis of those calls could take some time, but there is an easier way. I’ve looked at constant strings embedded in the executable and after filtering out all common strings that are in every executable, I’ve found some suspicious strings:

.rdata:004191AC db '3.90625E-3',0 .rdata:004191B8 db '1.5625E-2',0 .rdata:004191C4 db '8.0E-3',0 .rdata:004191CC db '0.85',0 .rdata:004191D4 db '0.5',0 .rdata:004191D8 db '10',0 |

Querying google for the first two values reveal many results, but most of them are irrelevant. I’ve found what I was looking for at 9th and 10th place on the first page, it was part of the source code of **MAPM Library**:

m_apm_set_string(MM_5x_125R, "8.0E-3"); m_apm_set_string(MM_5x_64R, "1.5625E-2"); m_apm_set_string(MM_5x_256R, "3.90625E-3"); |

**MAPM**, A Portable Arbitrary Precision Math Library in C is quite old (and previously unknown to me), complex library for various math computations, it supports big integers as well as big floating point values. I’ve managed to compile **MAPM** with **Visual Studio 2010** (library has batch script for **VC 6.0** and it still works). **IDA** signatures made from that lib were partially ok, **IDA** matched 23 out of ~40 functions. Not matched functions were easily recognizable manually, by matching source code with overall structure of each not recognized function and by looking at references to other recognized functions and data.

Besides low-level api for numerical computations, **MAPM** library has also wrapper class that implements all operators, so it can be used almost transparently. Mentioned wrapper isn’t included in the library itself, it is part of the header file, so I had to manually resolve also functions from this class. After this initial analysis **serial_check()** looks a bit more friendly, but there was still a lot of unrecognized functions. It is because of heavy usage of **STL**, if I’m correct, crackme uses **std::string**, **std::vector** and **std::list** to maintain **MAPM** structures during execution. I’ve decided to not bother with exact recognition of all those functions, because all in all I didn’t need it. That’s pretty much all of static analysis.

### Dynamic approach

For easier debugging I’ve removed **ASLR** from the executable. First of all I’ve checked which data are hashed by **MD5**, triggering breakpoint on **MD5** function showed that **MD5** is calculated from username, so I had first step for keygen:

usermd5 = MD5(username); |

Second guess (my dynamic approach was ‘guessing game’ until I’ve reached point, where I was sure what is what) was related to **MAPM** library, it is using **m_apm_set_long()** function to initialize **MAPM** object with integer value:

void m_apm_set_long(M_APM, long); |

I’ve set breakpoint on that function and just waited, it was good guess, I’ve logged values that were going to this function:

0x00, 0x67, 0x100, 0x69, 0x100, 0x6D, 0x100, 0x39, 'g' 'i' 'm' '9' 0x100, 0x31, 0x100, 0x33, 0x100, 0x21, 0x100, 0x95 '1' '3' '!' |

I’ve traced function that is calling **m_apm_set_long()** with above values, and I was able to deduce that it is creating some bignum value from given string:

MAPM createValue(unsigned char* data, unsigned int dataSize) { MAPM v = 0; for (unsigned int i = 0; i < dataSize; i++) { v *= 0x100; v += data[i]; } return v; } |

String **“gim913!\x95”** is evaluated to **7451607150867194261**, which is prime value. This is second information that will be used in keygen:

MAPM p = createValue("gim913!\x95"); |

Further logging of **m_apm_set_long()** revealed that **MD5** from username is used to initialize 4 values, so next steps for keygen:

MAPM a = createValue(usermd5, 5); MAPM b = createValue(usermd5 + 5, 5); MAPM c = createValue(usermd5 + 10, 5); MAPM d = createValue(usermd5 + 15, 1); |

At this point I could switch back to **serial_check()** function, as most of calculations is done there by various **MAPM** functions. When username is preprocessed, crackme adjusts **‘b’** value:

b = (512 * b) + d; |

Then it calculates:

MAPM D = b*b - 4*a*c; |

Above formula is nothing more than discriminant of the quadratic equation and in this case it is used to check if crackme is keygenable for given username. Crackme at first checks if **D >= 0**, if it is it performs additional calculations:

D %= p; MAPM A = powmod(D, (p - 1)/2, p); |

Above formula is called **Legendre symbol** and it is used to check if value is quadratic residue modulo prime number. If it isn’t, crackme will generate **“Wrong username!”** message. Some of you probably already know what was the protection scheme but I’ll quote **Steve Jobs**:

“… you can’t connect the dots looking forward; you can only connect them looking backwards. So you have to trust that the dots will somehow connect in your future.”

So, I didn’t connected the dots, because my knowledge about quadratic congruence equations was equal to zero. Let’s leave it for now, I was performing further analysis of **serial_check()** function. Next part of **serial_check()** was filled with bunch of calls to unrecognized functions that were forming loop. That wasn’t encouraging, so I’ve decided to do some wild guess and I’ve set hardware breakpoint on memory where inscribed serial number was stored. After first hit I’ve traced values that were taken from serial number, few functions above I saw that each character from serial number is converted to **int** value, but not all characters, only numbers and big letters (at least **A-F**, because I was trying hex numbers as a serial number). Each value was then processed by below algorithm:

int V = 0; for (int i = 0; i < cnt; i++) { V *= 36; V += getNextValueFromSerialNumber(); } |

Identification was rather easy, it is **base36** converter. It is called 3 times, each time converts 5 letters from serial number to **int** value, so proper serial number should be 15 characters long composed from below charset:

`"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"`

Values gathered from serial number will be called **sn1**, **sn2**, **sn3**. Each **sn** value is checked by below algorithm:

unsigned int v; // word value to compute the parity of v ^= v >> 16; v ^= v >> 8; v ^= v >> 4; v &= 0xf; return (0x6996 >> v) & 1; |

It is checking if **v** contains odd or even number of bits set, crackme requires even numbers. After this check, **sn** values are shifted by one in the right direction:

sn1 >>= 1; sn2 >>= 1; sn3 >>= 1; sn1 &= 0xFFFFFF; sn2 &= 0xFFFFFF; sn3 &= 0xFFFFFF; |

Thanks to this operation, parity check doesn’t interfere with values that will be used in equation. **SN** values are used then to create one value:

MAPM SN = (sn1*0x1000000 + sn2)*0x1000000 + sn3; |

How do I know? Again, old breakpoint that was set on **m_apm_set_long()** at the beginning of this paragraph comes in handy. The last step performed by **serial_check()** function is calculation of value described by below formula and comparing it to 0:

MAPM Y = (a*SN*SN + b*SN + c) % p; |

## Quadratic Congruence Equation

Solving this equation is fairly simple, but due to lack of proper knowledge I was struggling on it for some time. I asked for help my old friend from http://gdtr.wordpress.com/ and he pointed out some resources that I should read before solving it. At first I’ve tried **WolframAlfa** to check if everything is correct, so I’ve wrote down my equation with coefficients generated from username **“ReWolf”** and I’ve received below results:

Then I’ve converted roots to proper **base36** serial number and crackme showed **“C O N G R A T U L A T I O N S !”** message box. Now how to solve it manually ? Basically the solution is similar to standard quadratic equation, but all operations should take into account modular arithmetic.

There are two problems in the above formulas:

- modular multiplicative inverse
- modular square root

First problem can be solved by **extended Euclidean algorithm**, second is more complicated but there are few algorithms that can help:

I’ve chosen **Tonelli-Shanks** as it seems to be most popular solution, at least from the google search perspective. In the keygen I’ve used **Tonelli-Shanks** implementation written by **Eli Bendersky**:

http://eli.thegreenplace.net/2009/03/07/computing-modular-square-roots-in-python/

It’s written in **python**, but it was very straightforward to port it to **C++**. That’s pretty much all, check source code of a keygen for implementation details.

### Erratum

Here are a few post-analysis details that I’ve learned from the crackme author after I’ve sent him keygen:

**MD5**is taken from**Crypto++ Library**- Crackme is really using
**STL**: <map>, <list>, <string>, <vector>, <algorithm> - Crackme is using
**FC++: Functional Programming in C++**to “obfuscate” code - Those few strings that I’ve used to identify
**MAPM Library**were left intentionally as a hint for cracker

Author was kind enough to send me source code of the crackme, here are my favourite fragments:

- Creating
**MAPM**object from**std::string**: - Parsing
**MD5**:

std::string gim913 = "\x67\x69\x6d\x39\x31\x33\x21\x95"; MAPM prime = foldl([](MAPM left, int b) { return 256*left + b; }, mapm_zero, List<e_ubyte>(gim913.begin(), gim913.end())); |

auto res = splitAt(5, chunks_mdu); coefficients.push_back( foldl([](MAPM left, int b) { return 256*left + b; }, mapm_zero, res.first) ); |

### References (other than already mentioned)

- http://math.stackexchange.com/questions/160385/how-to-solve-this-quadratic-congruence-equation
- http://math.stackexchange.com/questions/30778/is-there-a-formula-for-solving-the-congruence-equation-ax2-bx-c-0
- http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
- http://www.johndcook.com/quadratic_congruences.html
- http://www.alpertron.com.ar/QUADMOD.HTM

22:46, July 24, 2012p_k /

Good work on the crackme, also this is the nicest formatted tutorial I’ve seen http://i.imgur.com/ysIpt.jpg

17:18, July 25, 2012olesio /

Good work and nice tutorial rewolf :) Btw, some time ago you wrote on some IRC channel about yourself “/me lame” – in my opinion you are far too low self-esteem :) You have a powerful knowledge, I’m too lazy, lame and have low konwoledge to solve crackmes like that ;/

00:46, July 30, 2012andrewl /

yes nice tutorial :) expressed well by p_k’s pic :)