KeygenMe 01 "Psychic powers or brute strength your choice"

[lostit]

Difficulty : 6
Language : C/C++
Platform : Windows 32bit
OS Version : Windows XP+ (tested on win xp 32bit vm with sp3 and win 10 x64) 
Packer / Protector : None

Description :

Pretty straight forward keygenme, input a name, and a key and see if they're valid. The goal is to write a keygen for it without patching the file. Hopefully when thinking about this one you don't forget the code you can't see. But if that isn't going well you can always try brute force on it.

Again there is 1 goal, write a keygen for it without patching it. 

Screenshot :

Download :

KeygenMe_01.zip

Edited January 14, 2016 by lostit

[koolk]

Name: tutsyoututsyoutututsyoututsyoutulostitlostitlost

Key: RkIomczPduF4Se2T

This program decode the base64 and check if it is 12 bytes, than it checks each 6 bytes according to the name. It gives us two valid name/key pairs (lostit and tutsyou), but doesn't allow us to use them (specifically) 

The first check:

The first 6 bytes (expended to 16 bytes) are hashed 1000 times with md5. Than the first two bytes of the name are used to select 6 bytes from a predefined array, and the first 6 bytes of the md5 are checked against that.

Since it is hard to find such hash (=bruteforce), we can use 6 bytes from one of the given keys, (and the corresponding 2 first characters in the name). In my case I used the tutsyou/RkIomczPYHNrJoCA pair.

The second check:

The name is expended to 16 bytes (if it is shorter, it is repeated, if it is longer, each 16 bytes are xored), than it hashes the name 1000 times, and checked against the the second 6 bytes of the key.

This check is really easy to pass, because you can just generate the second 6 bytes of the key from any name. But I am going to do something else, because it seems that you meant that this check will be hard too (and not straightforward).

So lets assume that this was the case, we can still use the other name/key given. I am going to use the second half of the key of lostit/RY5obY7IduF4Se2T pair. If we use the lostit name, the string after expansion is lostitlostitlost. But we need that the first 2 characters will be "tu". So we can just take any 16 bytes string that start with "tu", write it twice, and than write lostitlostitlost. The string that will be hashed would be lostitlostitlost, because all the 16 bytes are xored. And the given 6 bytes will help use to pass this check.

Edited January 14, 2016 by koolk

[lostit]

59 minutes ago, koolk said:

Name: tutsyoututsyoutututsyoututsyoutulostitlostitlost

Key: RkIomczPduF4Se2T

This program decode the base64 and check if it is 12 bytes, than it checks each 6 bytes according to the name. It gives us two valid name/key pairs (lostit and tutsyou), but doesn't allow us to use them (specifically) 

The first check:

The first 6 bytes (expended to 16 bytes) are hashed 1000 times with md5. Than the first two bytes of the name are used to select 6 bytes from a predefined array, and the first 6 bytes of the md5 are checked against that.

Since it is hard to find such hash (=bruteforce), we can use 6 bytes from one of the given keys, (and the corresponding 2 first characters in the name). In my case I used the tutsyou/RkIomczPYHNrJoCA pair.

The second check:

The name is expended to 16 bytes (if it is shorter, it is repeated, if it is longer, each 16 bytes are xored), than it hashes the name 1000 times, and checked against the the second 6 bytes of the key.

This check is really easy to pass, because you can just generate the second 6 bytes of the key from any name. But I am going to do something else, because it seems that you meant that this check will be hard too (and not straightforward).

So lets assume that this was the case, we can still use the other name/key given. I am going to use the second half of the key of lostit/RY5obY7IduF4Se2T pair. If we use the lostit name, the string after expansion is lostitlostitlost. But we need that the first 2 characters will be "tu". So we can just take any 16 bytes string that start with "tu", write it twice, and than write lostitlostitlost. The string that will be hashed would be lostitlostitlost, because all the 16 bytes are xored. And the given 6 bytes will help use to pass this check.

You've gotten 2/3rd's of the way there. Now you just need to add a keygen that can generate keys for names other than the ones based on the two "blacklisted" names/keys in the keygenme.

[koolk]

On 1/14/2016 at 11:40 PM, lostit said:

You've gotten 2/3rd's of the way there. Now you just need to add a keygen that can generate keys for names other than the ones based on the two "blacklisted" names/keys in the keygenme.

Oh, so this is the "psychic powers" part?

The problem is the first 6 bytes. The first two characters are multiplied (the index of the alphabet of them), so we get a result number 1 and 676, and it is used as an index to choose 6 bytes from a table (to compare to what I described before). So if I want to generate a key for an arbitrary name (that doesn't start with "tu/ut/lo/ol/rj/jr"), I will have to guess the exact 6 bytes that were used to generate the bytes in the table. 

The only thing that I can think of is to figure out the way that you chose those 6 bytes (from an index) from the two samples that I have. which I will probably need psychic powers for  

[lostit]

2 hours ago, koolk said:

Oh, so this is the "psychic powers" part?

The problem is the first 6 bytes. The first two characters are multiplied (the index of the alphabet of them), so we get a result number 1 and 676, and it is used as an index to choose 6 bytes from a table (to compare to what I described before). So if I want to generate a key for an arbitrary name (that doesn't start with "tu/ut/lo/ol/rj/jr"), I will have to guess the exact 6 bytes that were used to generate the bytes in the table. 

The only thing that I can think of is to figure out the way that you chose those 6 bytes (from an index) from the two samples that I have. which I will probably need psychic powers for  

Yea or brute force. The key system isn't my own invention, I worked on a very similar system on a different app, and I tried to duplicate the same mistakes they made. The reason is that I hope they hint at a certain lack of understanding about how some of the stuff works together. So if the developer didn't fully grasp how to not leak info from blacklisted keys maybe they didn't understand how to pick those 6 bytes well. Of course its not entirely fair since the code isn't in front of you but that shouldn't be a reason to rule out potential mistakes that could be made when picking the numbers. Especially if its easy to test for some common mistakes.

I'm fairly certain you'll figure it out. Psychic powers would make it really easy, but a good assumption will get you there as well. Maybe I should change the difficulty to a 3.

[SmilingWolf]

SmilingWolf
DV4cAmDEGu2A+Txr

koolk
de1erFNaKP/Q5w94

What happens here? lostit generated a stream of 4056 bytes using something like:

srand(unknownSeed);
char plaintextsStream[4056];
for (int i = 0; i < 4056; i++) {
  plaintextsStream[i] = rand() & 0xFF;
}

There was no way to know this, so I made a guess, ripped rand() from msvcrt.dll and just did some experiments.
After some tinkering I was able to recover plaintextsStream by bruteforcing unknownSeed.
Luckily the author gave away some plaintexts to test with when he included some blacklisted keys in the executable.
lostit then generated a table of of the first 6 bytes of the MD5 values each calculated using 6 bytes from the plaintextsStream using something like:

char MD5sTable[4056];
for (int i = 0; i < 676; i++) {
  MD5(&plaintextsStream[i*6], 6, &MD5Store);
  memcpy(&MD5sTable+(i*6), &MD5Store, 6);
}

Results: knowing the seed I can pick the right value for RandomCounter using the first two letters of the username as explained by @koolk, seed the PRNG with unknownSeed (now known), call it RandomCounter * 6 times in order to discard the bytes I don't need, then generate the plaintext corresponding to the MD5 stored at offset MD5sTable + (RandomCounter * 6) in the keygenme executable.

Relevant sources: https://bitbucket.org/SmilingWolf/kgcollection/src/cdf8856327e23ed97041ff27428fbc8c8e2ff8a2/lostitKGM_01.asm

Edited August 22, 2017 by SmilingWolf

[zero_gear]

1. Program flow explanation

at start program checks if:

 5 <= len(NAME)< 256
16 <= len(KEY) < 256

it lowercase all NAME chars, and delete from name all non a-z chars. Then it delete all non base64-alphabet chars from KEY, and check if len(KEY) == 16. Lets consider NAME as a string with length 5 or greater, and which consist from 'a'-'z' chars. Lets consider KEY as a string with length 16, and which consist from base64-alphabet chars ('+','/','0'-'9','A'-'Z','a'-'z').

Then program compare if NAME:KEY pair is not

• "lostit":"RY5obY7IduF4Se2T"
• "tutsyou":"RkIomczPYHNrJoCA"

which are valid NAME:KEY pairs, but for some reason blacklisted in such way.

Now your program begin to calculate different hashes and make different checks.

FIRST HASH: hash retrieved from KEY, lets give to it a name K_hash_1. K_hash_1 is 12-byte hash, each 4 bytes of KEY converted to 3 bytes of K_hash_1 .  Below code snippet explain this transformation, consider get_K_hash_1() function:

char base64alphabet_map[] = {
	/* 01*/ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	/* 10*/ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	/* 20*/ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	/* 30*/ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	/* 40*/ 0, 0, 0,62, 0, 0, 0,63,51,53,/*43:+,47:/,48:0*/
	/* 50*/54,55,56,57,58,59,60,61, 0, 0,
	/* 60*/ 0, 0, 0, 0, 0, 0, 1, 2, 3, 4,/*65:A*/
	/* 70*/ 5, 6, 7, 8, 9,10,11,12,13,14,
	/* 80*/15,16,17,18,19,20,21,22,23,24,
	/* 90*/25, 0, 0, 0, 0, 0, 0,26,27,28,/*90:Z,97:a*/
	/*100*/29,30,31,32,33,34,35,36,37,38,
	/*110*/39,40,41,42,43,44,45,46,47,48,
	/*120*/49,50,51, 0, 0, 0, 0, 0, 0, 0/*122:z*/
};


void get_K_hash_1_quarter(const char in[4], char out[3]) {
	unsigned int c0 = base64alphabet_map[in[0]];
	unsigned int c1 = base64alphabet_map[in[1]];
	unsigned int c2 = base64alphabet_map[in[2]];
	unsigned int c3 = base64alphabet_map[in[3]];

	unsigned int hash_chunk = (((((c0 << 6) + c1) << 6) + c2) << 6) + c3;

	unsigned int temp_hash;
	temp_hash = hash_chunk >> 16;
	out[0] = (char)temp_hash;
	temp_hash = hash_chunk >> 8;
	out[1] = (char)temp_hash;
	out[2] = (char)hash_chunk;
}

void get_K_hash_1(const char *key, char custom_hash[16]) {
	for (int i = 0, n = 0; i < KEY_LEN, n < HASH_LEN; i = i + 4, n = n + 3) {
		get_K_hash_1_quarter(key + i, custom_hash + n);
	}
}

SECOND HASH: 16-byte hash, which is retrieved from K_hash_1, lets name it K_hash_2. K_hash_2 initialized using function in listing below.

void init_K_hash_2(const char src_hash[16], char dest_hash[0x10]) {
	dest_hash[0x0] = src_hash[0];
	dest_hash[0x1] = src_hash[1];
	dest_hash[0x2] = src_hash[2];
	dest_hash[0x3] = src_hash[3];
	dest_hash[0x4] = src_hash[4];
	dest_hash[0x5] = src_hash[5];

	dest_hash[0x6] = src_hash[0];
	dest_hash[0x7] = src_hash[1];
	dest_hash[0x8] = src_hash[2];
	dest_hash[0x9] = src_hash[3];
	dest_hash[0xA] = src_hash[4];
	dest_hash[0xB] = src_hash[5];

	dest_hash[0xC] = src_hash[0];
	dest_hash[0xD] = src_hash[1];
	dest_hash[0xE] = src_hash[2];
	dest_hash[0xF] = src_hash[3];
}

Then K_hash_2 is used as input string to calculate MD5 hash. K_hash_2 is XOR-ed with resulting hash. See code below:

#include <openssl/md5.h>

void MD5_and_XOR(char hash_buffer[16]) {
	char md5[MD5_DIGEST_LENGTH] = { 0 };
	MD5((const unsigned char *)hash_buffer, 16, (unsigned char *)md5);
	for (int i = 0; i < 16; i++)
		hash_buffer[i] ^= md5[i];
	return;

This operation repeated 1000 times.

THIRD HASH: getting 16-byte hash from NAME, lets name it N_hash. N_hash initialized using function in listing below.

void init_N_hash(const char * name, unsigned char name_len, char dest_hash[0x10]) {
	if (name_len <= 0x10) {
		for (int i = 0; i < 0x10; i++) {
			dest_hash[i] = name[i % name_len];
		}
	}
	if (name_len > 0x10) {
		memcpy(dest_hash, name, 0x10);
		for (int i = 0; i < name_len - 0x10; i++)
			dest_hash[i % 0x10] ^= name[i + 0x10];
	}
}

Then N_hash is hashed with MD5 and XOR-ed 1000 times in the same way as K_hash_2 (described above).

1ST CHECK:
Note: python lists used for below pseudo-code

N_hash[0:6] == K_hash_1[6:12]

2ND CHECK:

K_hash_2[0:6] == [0xE9, 0x85, 0x5D, 0x5B, 0x2F, 0x41]

 

2. Checks bypass

1ST CHECK:

we have NAME, consequently we can produce N_hash. N_hash[0:6] according to 1st check conditions should be equal to K_hash_1[6:12], from K_hash_1[6:12] we can easily get 2nd part key - KEY[8:16]. Below code of function that help us retrieve KEY[8:12] from N_hash[0:3] and KEY[12:16] from N_hash[3:6].

void brute_key_quarter(const char * in_3chars, char * out_4chars) {
	/*Brute-force init*/
	char input[4] = { '.','/' ,'/' ,'/' }; 	// '/'-'9', 'A'-'Z', 'a'-'z'
	unsigned int* p2input_as_dw = (unsigned int*)input;
	char output[3] = { 0 };
	/*Brute-force loop*/
	do {
	START:
		(*p2input_as_dw)++;
		for (int i = 0; i < 4; i++) {
			if (
				!(input[i] >= '/' && input[i] <= '9') &&
				!(input[i] >= 'A' && input[i] <= 'Z') &&
				!(input[i] >= 'a' && input[i] <= 'z')
				) {
				goto START;
			}
		}
		get_K_hash_1st_quarter(input, output);
	} while (
		!(output[0] == in_3chars[0] && output[1] == in_3chars[1] && output[2] == in_3chars[2])
		);
	/*Brute-force end*/
	out_4chars[0] = input[0];
	out_4chars[1] = input[1];
	out_4chars[2] = input[2];
	out_4chars[3] = input[3];
};

2ND CHECK:
we have 2nd 8-bytes part of KEY, we could try to brute 1st 8-bytes part of KEY and pass this check.

Repository (LINK) contains keygen based on multi thread brute, brute threads quantity is equal to quantity of cores on your PC .

CAUTION: This solution is far from elegance. Required  powerful multi-core computer and a lot of time (. You processor will burn and you will burn with impatience.

Edited June 21, 2018 by zero_gear

[zero_gear]

Correction to above post :
above LINK to repository with keygen is non-valid, this one is correct : https://github.com/smart-rabbit/keygen_for_lostit_brute-strength.

[zero_gear]

In above @lostit`s and  @SmilingWolf`s posts mentioned that "psychic power" solution variant use:

    blacklisted KEY:NAME pairs
    key system(link to post)
    a stream of 4056 bytes(link to post)

Unfortunately, i have not grasped how it works.

Please, could someone give broader and more precise explanation about how "psychic power" solution works and how topic starter generate keys.

Edited June 22, 2018 by zero_gear

[zero_gear]

Above post has mistaken explanation of 2nd CHECK, correct explanation, full write-up,  keygen sources and binary are HERE, and also keygen binary attached to this post.

Valid NAME:KEY pairs examples:

• bigben:4aWfjhuWTgv6NSM2
• impossible:tbxCCxODKA5M7XWB

P.S.:  also there is forum topic about this task on main post-soviet  reverse-engineering forum - LINK.

P.P.S.: @lostit, thank you for this challenge.

Keygen.exe

Edited June 28, 2018 by zero_gear