[KeygenMe] Fun KeygenMe #1

[Office Jesus]

Hello, everyone!I want to present my first keygenme in quite a while. This one is a continuation of a series I started 4 years ago. (You can find Fun KeygenMe #0 on crackmes.de, of course.)The main goal with this "series" is to help ease novices into the art of reversing (patching, keygenning, etc.) while having a bit of fun. I hope that you guys will solve this and provide tutorials. Hopefully the tutorials will be spread around the Internet for all new people to enjoy and learn from!Features of this keygenme:

• Coded (poorly) in MASM
• Not packed
• No cryptos
• Simple yet tricky?
• Difficulty: 1-2/10

I have it on good authority that this keygenme is a 1 or 2 on the crackmes.de difficulty scale. That does not mean it is completely easy, though. The point here is to expose newcomers to different problems and different ideas. There are definitely some interesting yet simple things happening in this keygenme, I think. I hope you guys solve this and post tutorials (text, flash, anything) in this thread!I fully expect ChOoKi to solve this within five minutes of downloading. I also expect him to half-ass his way through a tutorial and then not post it. Good luck, everyone! Let's help the beginners learn the trade!

 

If you find any bugs, please report them here so I can fix them.Cheers,
Office Jesus

 

fkgm1.zip

 

Solutions

sama

xSRTsect

Gyver75

GrindStone

Edited November 28, 2014 by Office Jesus

[ChOoKi]

I fully expect ChOoKi to solve this within five minutes of downloading. I also expect him to half-ass his way through a tutorial and then not post it

 

Damn!! You know me too well

IMHO this challenge is a treat and everyone should try it, in saying that, I will not be presenting a solution + tutorial any time soon.

 

Cheers

[xSRTsect]

I'd finish the keygen - but neither it is interesting enough nor do I have the time right now.

 

xSRTsect

 

4WG004C=4:T>-PJKGGAZ0OKA9-BZEE0ZZZ00ZZ-ZKZZZZZ<Z<Z<

Edited November 15, 2014 by xSRTsect

[sama]

quick and dirty solution.

DONKEY_Perignon.rar

[Gyver75]

This is  my solution: in the zip archive you can find a ida database file and the keygen written in python.

Thanks to Office Jesus for this funny keygenme.

 

 

fkgm1 solution.zip

[GrindStone]

Try to fix my rusty brain and cleanse my unholy soul. This is my solution :

http://gs-playground.com/kgm_sol/OfficeJesusFunKeygenMe1.html

Try to work it on javascript now, just trying something new. And definitely, source is included, well, viewable at least.

 

Very nice keygenme, it sure long, but it's do entertain me. Thanks for that, OJ.

 

For the tutorial, i will not going into detail, just tell some general idea of this KGM. And, here it is :

 

First, KGM will do some modification to the inputted name. Length check is there, of course. And KGM will force inputted name to have 16 character length, by padding inputted name with reverse version of itself. Of course, if the inputted name already 16 char long, KGM will do nothing. And after that, name will be uppercase'd and replace space character with ! character. Oh, and there is some checking to the format of inputted serial. Accepted format will be like this : XXXXXXXXXXXX-XXXXXXXXXXXX-XXXXXXXXXXXX-XXXXXXXXXXXX, with "X" is the character with ASCII code between 48 - 90, divided into four part with twelve characters each part.

 

Then, KGM will do some rather long operation to the name, to create one string (or byte array), which will be used in serial checking later. I refer to this variable as spice in my code. This operation including string (or byte array) table for lookup with size of 26. So, every calculation will used modulo 26, so it could fit the size of the table. And, the result of each calculation will be used to lookup to the table, to be added to spice. So, our spice will be filled by the value of the table, which actually act as lookup index. To be more clear, let we go more technical : 

 

Let the table = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" (not the real table value, used here for clearance purpose)

 

So, if the resulted spice  = "GRINDSTONE" , it's just mean spice = [6, 17, 8, 13, 3, 18, 19, 14, 13, 4], because 6 is the index of "G" in the table, 17 is index of "R", and so on. Remember, this is 0-based index. 

 

After the spice is ready, KGM will do the serial-checking based on that. So, as you already know, serial is divided into four part, separated by "-" character. And this KGM will check each one with different method. And here it is how to solve each part :

 

Part 1 :

 

KGM will do some calculation to each other character in this part, to be checked againts some part of spice. Let we take a look in first section of this part-checking :

 

Let x_n be the inputted serial, _n is the index position of the inputted serial.

Let y_n be the spice, and yes, _n is the index position. Remember, the value of spice is the lookup index of the table, not the ascii value of the character itself.

I used 1-based index for the serial, and 0-based index for the spice. Incosistent you may say, but meh...

 

(x₁ + x₃) % 26 = y₀

 

That's the condition we must achieve in order to pass first section of this part-one checking. Well, at this point, i assure you, we could always do some bruteforcing, which is nice, but lets we take further analysis. From the equation above, it is clear that we must find both x₁ and x₃ that macth the spice. So, in order to move foward, we should determine one of the x's to find other x's. I choose to determine x₁ with some random value in range 48-90, then find x₃. Modular arithmetic understanding is required to solve this equation, but, since me myself not have some strong grip at that field, i couldn't explain it briefly, which i'm affraid will cause more confusion, instead i would just tell you what i do.

 

First, i will move x₁ to the right side of equation, which mean i substracted y₀ with x₁. And i will keep adding the result with 26, until it's in 48-90 range. And that's the result of x₃. Lets we take some example with the value of the table and spice as mentioned above, and let say we get 65 as random result of x₁. So, the equation will be :

 

(65 + x₃) % 26 = 6

x₃ = 6 - 65

x₃ = -59

-59 + 26 = -33 -> -33 + 26 = -7 -> -7 + 26 = 19 -> 19 + 26 = 45 -> 45 + 26 = 71 (in range 48-90)

 

So, the valid x₁ = 65 ("A" char), and x₃ = 71 ("G" char), you could verify to the original equation if you want.

 

And in the second section, there's similar check, but instead use ADD operator, it used XOR. Well, because of unique behaviour of XOR, i couldn't repeat previous method with 100% success rate. So, i slightly modified the function just for the XOR operation. Instead keep adding the result with 26, i just check if the result is in range straight away. If it isn't, then change the determinate value, untill the condition is fulfilled. And yes, that's bruteforcing. Well, at least its less time than bruteforcing whole part.

 

And so that's the checking of the part-one going, the rest of the section use this very same method. Well, there is some other checking, but that just checking the value of spice to the serial, which is i'm sure you would consider easy. Let's move to part 2.

 

Part 2 :

 

Let's see the first section of this part, the equation must be fulfilled is : 

 

x₁ * x₃ > y₈ * 79

 

So, to achieve this condition, we should generate random value greater than the value of the right side of the equation. I mean, multiplying greater number will yield greater result, isn't it? So, i choose to set x₁ > y₈, and x₃ > 79, and that's enough guarantee to pass this test. Second section of this part, use similar method, but instead using MUL operator, it's used ADD operator, and this is not a problem to the method above, as adding greater number yield greater result too, right? The problem will arise when we proceed to section 5 (i skipped section 3 and 4, because it just checking serial againts some constant). The problem is because that operator again, XOR. Well, we can not guarantee in any way that greater number produce greater result with this operator. This where the bruteforce take place again. Okay, lets move to next part.

 

Part 3 :

 

This part is similar to part 2, but instead finding OFFICE1, you will find JESUS14 in this part!

 

Part 4 :

 

This last part is most troublesome for me, and i beleive there's some minor bug in this KGM at the last section of this part, but let's we talk about it later. For now, let's we see condition it must fulfilled to pass first section :

 

x₁ + x₃ * x₅ > y₂₄ * y₂₅

 

Well, it's looks like part 2 checking, but now we must determine 3 variable. But, actually, what we must concern is just x₃ * x₅, because, if we could produce greater result here, then the addition will be just bonus. So, like part 2, i set x₃ > y₂₄, x₅ > y₂₅, and x₁ any number that in range. Next section use exactly same method. But, in third method, it slightly change the method to :

 

x₂ + x₄ + x₆ > y₂₈ + y₂₉

 

Looks like it can be solved like previous method, but alas, it's not that easy. The problem is because KGM used ADD operator in byte type data. That's mean, any result that exceed 255 (or FF in hex), will be wrapped up. So we lost our guarantee that adding greater number yield greater result. So, we must again bruteforcing this method, to set that 3 pieces of number is small enough so it wont exceed 255, but big enough so its greater than y₂₈ + y₂₉.

 

And here comes the last section which i talked about. The method is similar like method in previous section, but it's used lesser-than (<) operator. That's not the problem, because we just set x's is smaller than y's to get problem solved. But, there's lie one problem, after the addition, the result get AND-ed (&) by 15 (F in hex), which mean it's only take last number of result (in hex). So, again, we lost our guarantee adding lesser number yield lesser result. I would to do bruteforcing again, until i think some other way around this. 

 

The way is to determine fixed (not random) value for the first number, which is doesn't matter, so i just generate random number for last number, based on last number of y's. Better told it with example : 

 

Say, y₃₀ = 71, y₃₁ = 83

So, y₃₀ + y₃₁ = 154 (9A in hex)

Then, 154 & 15 = 10 (A in hex)

 

So, in order to produce lesser number, our 3 pieces addition last number must less than 10. So, to make sure, i divide (distribute) the result (10) by 3, and append any first number to it (in my case, i choose 30 in hex). So, its guarantee, it will produce lesser last number. Then, you're done, your serial registered within your name.

 

But, how about the bug i talked about? Well, while i'm coding special function to pass last section, i had some tought. What if, under very special circumstances, the addition of the y's yield 0 as the last number. I mean, let's say y₃₀ = 51, and y₃₁ = 61, the addition will be 112, then AND-ed with 15, will yield 0, then yes, there will be no serial valid for that name. Well, having saying this, i cannot produce the bug myself. I already tried all possible name i ever heard, even the worst and the foolest name on earth, still no result. Well, maybe someone can find that most unfortunate name on this very earth?

 

Well, actually, the bug is not big problem, as i said, it happen under very special circumtances, and hard to reproduce. Overall, i found this keygenme is interesting, especially for someone who just want to arise gold old memory of reverse engineering, like me.

 

Okay than, this tutorial is finish, hope you like it.  

[Office Jesus]

Try to fix my rusty brain and cleanse my unholy soul.

 

I know the feeling! Talk about my surprise seeing GrindStone here. I'm glad you enjoyed it!

 

there's some minor bug in this KGM

Isn't there always at least one? Or maybe it's a design feature?

Edited November 28, 2014 by Office Jesus