# Identify password generation algorithm

I'm a newbie who just started own way through reverse engineering so I apologize if my question is not appropriate. Currently I'm going through different Crackme puzzles and now I'm stuck. I've spend a couple of days trying to solve it but I can't.

We enter a login and a password. Then we apply algorithm #1 on login. And algorithm #2 on password. In both cases we get a number as a result. And if the two numbers are equal, then the password is correct. I'm trying to find a way to generate a correct password for any given login.

I've figured out both algorithms with IDA and wrote a program in C++ to test my solutions.

### Algorithm For Login

Login should be at least 4 chars.

login = "Vasya_Pupkin"


1) From login we get two first chars ("Va") and two last ("in") and write its ASCII-code into hex number:

V = 0x56, a = 0x61, i = 0x69, n = 0x6e
hexVain = 0x5661696e


2) We go through the login string and add up all ASCII-codes:

for (int j = 0; j < login.length(); j++)


For Vasya_Pupkin we get asciiSum = 0x4da

3) We xor those values with some number 0xfec0135a:

hexVain ^ asciiSum ^ 0xfec0135a


### Algorithm For Password

Password should be at least 12 chars and should contain only'a'-'f', 'A'-'F', '0'-'9'. We enter password as string. Then we divide the length by 2.

password_str = "011c0d0f090e00";
n = password_str.length() / 2;  // n = 7


Then we convert string representation to hex and aplly this algorithm: We go through every byte from left to right and calculate new magic value.

password = 0x011c0d0f090e00;
for (int i = 0; i < n; i++)
{
// we count bytes from left to right
passByte = getByte(password, i);

// multiplication by 32 is left shift for 5 bytes
magicValuePass = passByte ^ (32 * magicValuePass + 1) ^ 0xdeadbeef;
}


The output of this function is following:

Byte:  01
Magic: deb8052f

Byte:  1c

Byte:  0d
Magic: eb0edca3

Byte:  0f
Magic: bf762a81

Byte:  09
Magic: 3068eec7

Byte:  0e
Magic: d3b06600

Byte:  00
Magic: a8a17eee


In the end we get magicValuePass = 0xa8a17eee which is the same value we get for login so the password is correct.

### What I've Tried

I thought about reversing magicValuePass generation but but came to conclusion that's a bad idea.

• I guess instead of identifying the algorithm you want to RE to be able to write a keygen of some sort, right? – Paweł Łukasik Oct 9 '17 at 9:05
• @PawełŁukasik Exactly! We have to figure out the correct password for a given login. – Neilana Oct 9 '17 at 18:58

As you have just started into RE, try looking into SAT solvers. Z3 is a great tool that will help you in such simple tasks with APIs in all major languages. Here is a solution I tried in python.

password = BitVec("password",64)
magicValuePass = BitVec("magicValuePass",64)

s = Solver()
idx = 7
magicValuePass =  (((password&(0xff<<(8*idx)))>>(8*idx))^ (32 * 0xadde + 1) ^ 0xdeadbeef) & 0xffffffff
for i in xrange(6,0,-1):
magicValuePass =  (((password&(0xff<<(8*i)))>>(8*i))^ (32 * magicValuePass + 1) ^ 0xdeadbeef) & 0xffffffff

if s.check() == sat:


First declare password to be a 64 bit variable. Then iterate byte by byte calculating the intermediate values and finally set the magicValuePass equal to magicValueLogin. If a solution exists to such conditions Z3 will run for some time and give the solution which is printed. Full script here which on running gives such output

$python test-so.py Vasya_Pupkin 0x11c0d0f090e0000$ python test-so.py ABCD
0x1171f0902111a00
\$ python test-so.py DEfg
0x1150f070b1a0500

• I agree, SAT Solvers are the mathematical way out. But, your examples aren't correct : login:ABCD has a magic number of 0xbf825114 and Password: 1171f0902111a00 has a magic number of 0x79660be7. No match! – yaspr Oct 9 '17 at 10:57
• I think my assumptions might be flawed such as taking 64 bit passwords and operating only on the lower 56 bits, but once given the binary I can verify what I want and assume. I was just trying to give him some ways to try instead of giving a complete solution. – sudhackar Oct 9 '17 at 11:10
• @sudhackar Wow, that worked! I've tried both of those examples in the crackme puzzle and it worked. Unfortunately I didn't have much time today to take a look on either SAT or Z3. So just for now I don't understand how it worked. I'll check it later and write back! Thank you for your answer. – Neilana Oct 9 '17 at 18:53
• @sudhackar Okay, I've just looked closer and now I can fully understand what's going on in your script. I've also tested it on some other values and it works perfectly. Thanks, didn't know about existing of SAT solvers, will definitely keep that in mind. Now I have even harder crackme to solve (didn't look at it yet), I think I could apply my new knowledge there as well! – Neilana Oct 9 '17 at 21:19

To start, algorithm 1 looks like the weakest link. Algorithm 2 is a one directional hash function and there's no way you can extract the characters by only knowing the magic number and the password bias. It involves some advanced math work and time. I explain the process of breaking Algorithm 2 in the second section.

Suppose :

log_bias = 0xfec0135a

Let's look at algorithm 1:

2) log_checksum = Sum(login, 0, n);

3) log_magicnumber = log_chunk ^ log_checksum ^ log_bias;

This algorithm shows two potential weaknesses. One, if you take the magic number and xor it with the log_bias constant you obtain : log_chunk ^ log_checksum. Two, log_chunk is a concatenation in hex of the first two characters and the last two characters and it provides a frame for the login; therefore, we can generate our own characters and give that variable a value.

After getting rid of the bias and choosing a value for the chunk, we can obtain a value for log_checksum.

log_checksum = (log_magicnumber ^ log_bias) ^ log_chunk;

What's left to do is to find a sequence of numbers representing characters which sum is the checksum.

How?

Well, if you look at the ASCII table you'll see that printable characters go from 33 to 126. If we generate a random value b between 33 and 126 and subtract it from the checksum we obtain a character value b and reduce the checksum value by b : log_checksum -= b. Repeat this operation until checksum value goes below 126 and only store characters which diff = (log_checksum - b) is greater or equal than 33. This way, all characters will be printable.

After filling the middle of the login string it can be represented as follows :

login = A B b0 b1 b2 ... bj C D

with A, B, C, D the characters we chose, and bi the characters generated from the checksum.

This reverse engineering approach is a cheap smart hack that targets the weakest hash function of the process and it will definitely work and save you time. From one password you'll obtain multiple logins : this is called a hash collision.

Here's an example output of this code:

Login: Vasya_Pupkin
Login    check : 0xa8a17eee
Password check : 0xa8a17eee
Check success :)
Valid login for pass_magicnumber 0xa8a17eee: Va[JiIUpHBI]in, length = 14
Valid login for pass_magicnumber 0xa8a17eee: VaU[^OnyD^fin, length = 13
Valid login for pass_magicnumber 0xa8a17eee: Va|IkHyi2in, length = 13
Valid login for pass_magicnumber 0xa8a17eee: VaTziSl^oK>in, length = 13
Valid login for pass_magicnumber 0xa8a17eee: VawNzAOGWktin, length = 13
Valid login for pass_magicnumber 0xa8a17eee: Vaeh]bmzbwin, length = 12
Valid login for pass_magicnumber 0xa8a17eee: VaugjXcNEvBin, length = 13
Valid login for pass_magicnumber 0xa8a17eee: VaJoMwQ{p[8in, length = 13
Valid login for pass_magicnumber 0xa8a17eee: VatBZwRR|Ein, length = 13
Valid login for pass_magicnumber 0xa8a17eee: VaIy[lkZQbKin, length = 13


All the listed valid logins will work for the password "011c0d0f090e00". If you alter the password a bit, say : "011c0d0f090efe", here's what you get :

Login: VaNpNa^Twin
Login    check : 0xa8a17e10
Password check : 0xa8a17e10
Check success :)
Valid login for pass_magicnumber 0xa8a17e10: VaeOTUkOG8in, length = 12
Valid login for pass_magicnumber 0xa8a17e10: VaUDFEzBx>in, length = 12
Valid login for pass_magicnumber 0xa8a17e10: Va|gktoein, length = 10
Valid login for pass_magicnumber 0xa8a17e10: VaaPRTogiin, length = 11
Valid login for pass_magicnumber 0xa8a17e10: VaFEzBpktin, length = 11
Valid login for pass_magicnumber 0xa8a17e10: VafCCzmQrin, length = 11
Valid login for pass_magicnumber 0xa8a17e10: VaFDWMHSNC<in, length = 13
Valid login for pass_magicnumber 0xa8a17e10: VaSvoIgR\in, length = 11
Valid login for pass_magicnumber 0xa8a17e10: Va[{eLdl?in, length = 11
Valid login for pass_magicnumber 0xa8a17e10: VaPaoDPXFDin, length = 12
`

Now, let's talk about generating passwords from a login magic number. You'll have to attack this function :

log_magicnumber = b ^ ((log_magicnumber << 5) + 1) ^ pass_bias

If you look closely, you'll see that current log_magicnumber is computed using the previous log_magicnumber value transformed and mixed up with an unknown byte value and a known bias. Iteratively, it looks like this:

log_magicnumber(i) = b ^ ((log_magicnumber(i - 1) << 5) + 1) ^ pass_bias

If we xor the pass_magicnumber and the pass_bias we're left with :

b ^ ((log_magicnumber << 5) + 1)

After generating all possible values of b (0-9 and a-f, 16 possibilities total) and deriving the corresponding value of log_magicnumber for each possible value of b, we apply the same step on these magic number values to obtain another value & we go on 8 times (the password string being a 64 bit value = 8 bytes with a minimum length of 6 bytes). We discard the two left-most bytes if set to zero and pack all the bytes into a password string; we then verify with the password magic number algorithm if the password's magic number matches the login's.

This approach amounts to creating an 8 stage tree where each node has 16 children. This means that we'll have to generate 16 to the power of 8 characters : 16^8 = (2^4)^8 = 2^32 = 4.294.967.296 characters (4GB) and combine them in strings of 6 to 8 characters with each string being checked for validation. It was fun to code :)

• Very interesting idea about generating logins from a password! That definitely works. I've spend many hours with that puzzle trying to came up with any algorithm that would generate any valid pair login\pass. But the thing you propose didn't came into mind. I like it :) Yes, I thought about implementing something like what you describing in the 2nd section but realized that's a pretty bad idea :D I mark question as solved and choose the sudhackar's answer as solution because it provides way to generate pass from login (not vise versa). – Neilana Oct 9 '17 at 21:58