View Full Version : B4 I start coding: Does my algorithm make sense ?
Hi,
I've been working on a project for a bit and think I finally found a small flaw in its security. I have another post about my earlier work but felt this deserved its own thread.
The program asks for a 16 digit key, a serial number and name. It then takes the key entered makes an 8 byte index from it where (A=13, B=FF, C=9B etc etc, the rule for this is just another string I call ConstantCode, I call this Index. Which is then run through an instance blowfish (which I do have the key for) and encrpyted. I call this eIndex. Then run through a factoring function which just makes a number based off that, this number is then split so that the lower half is taken and stored for later. This is which I call 2/2 Modified eIndex (2/2 Mod). The serial number and name are xored in a manner and the result I call Mesh, which is always 3 bytes. Now the two parts are brought togather where for example i will end up with: "01-XX-XX-XX-YY-YY-YY-01" the 01 upfront is constant, the XX XX XX is the Mesh, YY YY YY is the 2nd half of the Modified eIndex and that last 01 is a constant. This crazy number feed into blowfish again where it is encrypted. This I called "coeffiecent b/c it is run into another function that combined with the ConstantCode from earlier it re-creates a key, that I call MagicCode... I call it that because by some form of Magic it is supposed to equal the original key entered (if Valid), thats what the dashed line is for. Now, don't ask me how they are taking a blowfish encrpyted key and coming up with a set of rules to re-make a key like the one entered because I can NOT expalin it.
I hope that makes sense to someone. I would be more then happy to post code bits (in asm, don't have the C yet).
Anyway. My idea was that I attack it at the 2/2 Mod portion. This is the point in code where the key has been reduced to 3 bytes. 256*256*256 = 16777216 possible codes that this program can generate as MagicCodes PER given pair of serial and name. So I figured I rewrite the whole thing in C, start at the point where I have "01-XX-XX-XX-YY-YY-YY-01", brute force the YY bits, send this into blowfish take the Coeff number, generate a magiccode from it, send it into the start of the key function and follow all the way down to where 2/2 Mod / YY YY YY is created. If it matches my brute force bits the key was good....... I think. I came up with this while watching a girls gone wild infomercial at 3am half drunk so I don't if this will REALLY work, I have some huge flaw in my code. Thats why I'm posting.
I honestly have NO idea how they take a blowfish encryped value and derive a number that is meant to equal a key entered. I know its not blowfish decrypting anything, or if it is its not using the SBoxes or Pi talbe at all.
Key Process
http://tinypic.com/kb9n4i.gif
Algorithm
http://tinypic.com/kba7uh.gif
Any suggestions/comments/ideas ?
Hey!
I think I understand how this scheme works.
It's based on the probability that, given a range of possible values to be encrypted, the larger the range, the larger the likelihood that at least one of those values will encrypt to the same value as itself (Assuming that the unencrypted and encrypted form use the same range of possible values, which in this case they do.)
I'm not a student of probability so I can't explain this in a better way, but with an arbitrary encryption method, given and a range of 2 values that encrypt to 2 possible encrypted values, there is a 50% chance that those values will match unencrypted to encrypted. For 3 values this increases to 66% chance that at least one will match itself, and so on. With 256^3 possible values, probability makes it an almost certainty that at least one of the values in that range will match its encrypted form. Obviously in this case there is a very strong likelihood that more than one valid key exists for each name/serial.
AND Because the key is essentially reduced to 256^3 possible values (the "2/2 mod"), it is feasible to brute force all values that match unencrypted to encrypted in a relatively small amount of time. I don't think it's a security flaw - it's just by design. This is how the author generates the key(s) for a given name/serial, and how you will also :D .
So just bruteforce the "2/2 mod" value in order to find all possible keys for a given name/serial combination. :) Indeed your method is correct!
hope I helped,
see ya!
I'm not sure I understand the probabillity thing very well,
Here is the thing though, the coefficient (which is two constants, 3 bytes serial/name, and 3 keys derived from key) is sent to the MagicCodegenerator, every 1 byte of the Coeff directly make up 2 bytes of the Magiccode which if valid is to == key. It blows my mind as to how this works, and I've been starting at every line of the asm for a week and a half now.
I can promise that more then 1 key per mesh. The program has many variations of itself, some full featured, some with this option some with that etc etc. It knows which to install/run by the key entered. I know of at least 25 variations, but there could be more.
I didn't think about it as a design. Just seemed like a flaw to me. I mean, here they have keys, and factors, blowfish.... erm, make that 'modified' blowfish bt (Found that out today while I was coding it in C++, was thinking WTF why can't I code a simple blowfish alg correctly! They modified the order the SBoxes are being used), anyway do all this shit, huge complex algorithm, and then allow it to funnel down into 3 bytes for my brute forcing amusement. I'm glad as hell they did tho. If I sent this much time on my first attempt to RE anything and failed.... I'de be a sad panda fa sho. :D
I've coded the mesh, brute force part, blowfish, coefficient parts, thats a litle less then half I figure. Which is good b/c I was very rusty at C++. I think I should know if its going to work by tomorrow or wednesday. Modified blowfish did have me stumped for awhile.
Oh, also and this is pretty important. I made a mistake when I looked at the 1st blowfish part. Its not taking the Index and forcing into the BF encrypting code. Just the opposite. Somehow they are taking an index based directly from another string and then sending THAT into blowfish's deciphererer. I have a hunch that they are actually using the decryption algorithm to ENcrypt the index. Since the data tehy are sending in is just the index of each ASCII letter in the key. Tricky huh ?
Maybe they are decoding it, I don't know. I just can't wait till I have this up and running. I've also been trying to figure out just exactly how long its going to take to process 16.7million runs. I figure it will be ~1000 lines of asm, probably less. I'll make it as efficient as I can, I have dual opteron 250, 4gb ECC ram workstation, I'm just not sure if its going to be seconds, minutes, days ?? .... I don't really care. I'll let it run all week if it works B)
Originally posted by este@Jan 17 2006, 05:20 PM
I'm not sure I understand the probabillity thing very well,
Here is the thing though, the coefficient (which is two constants, 3 bytes serial/name, and 3 keys derived from key) is sent to the MagicCodegenerator, every 1 byte of the Coeff directly make up 2 bytes of the Magiccode which if valid is to == key. It blows my mind as to how this works, and I've been starting at every line of the asm for a week and a half now.
I can promise that more then 1 key per mesh. The program has many variations of itself, some full featured, some with this option some with that etc etc. It knows which to install/run by the key entered. I know of at least 25 variations, but there could be more.
I didn't think about it as a design. Just seemed like a flaw to me. I mean, here they have keys, and factors, blowfish.... erm, make that 'modified' blowfish bt (Found that out today while I was coding it in C++, was thinking WTF why can't I code a simple blowfish alg correctly! They modified the order the SBoxes are being used), anyway do all this shit, huge complex algorithm, and then allow it to funnel down into 3 bytes for my brute forcing amusement. I'm glad as hell they did tho. If I sent this much time on my first attempt to RE anything and failed.... I'de be a sad panda fa sho. :D
I've coded the mesh, brute force part, blowfish, coefficient parts, thats a litle less then half I figure. Which is good b/c I was very rusty at C++. I think I should know if its going to work by tomorrow or wednesday. Modified blowfish did have me stumped for awhile.
Oh, also and this is pretty important. I made a mistake when I looked at the 1st blowfish part. Its not taking the Index and forcing into the BF encrypting code. Just the opposite. Somehow they are taking an index based directly from another string and then sending THAT into blowfish's deciphererer. I have a hunch that they are actually using the decryption algorithm to ENcrypt the index. Since the data tehy are sending in is just the index of each ASCII letter in the key. Tricky huh ?
Maybe they are decoding it, I don't know. I just can't wait till I have this up and running. I've also been trying to figure out just exactly how long its going to take to process 16.7million runs. I figure it will be ~1000 lines of asm, probably less. I'll make it as efficient as I can, I have dual opteron 250, 4gb ECC ram workstation, I'm just not sure if its going to be seconds, minutes, days* ?? .... I don't really care. I'll let it run all week if it works* B)
1258
hi este,
Okay here is how I see it. From the "2/2 mod" value you start with, essentially what is done is it is encrypted by the time you come back to "2/2 mod". If the encrypted "2/2 mod" value matches the unencrypted "2/2 mod" value, then the "magic code" that was produced is a valid key for that serial/name "mesh".
I wish I could explain better why there is a VERY strong chance that there will always be AT LEAST ONE unencrypted "2/2 mod" value that matches it's encrypted value. The likelihood that there is at least one is 256^3:1 (99.9999 blah %). The author depends on this and knows for almost certain that bruteforcing the "2/2 mod" value will yield at least one valid key for a given serial/name - very likely many more as you say, 25 for example.
Did I explain this better?
Just a side note, the function involving the "coefficient" and "constant code", that produces the "magic code" is probably an inversion of the function involving the "key" and "constant code", that produces the "index".
If this is true, then feeding a given "coefficient" to produce the "magic code", and feeding the "magic code" as the "key" to produce an "index", will produce an "index" that matches the "coefficient" you started with.
The way I approach the problem is I view the "2/2 mod" as a 24-bit value to be encrypted, and the serial/name "mesh" as the seed for the encryption. This is what ensures different valid keys exist for different serial/name combinations.
For a 1-bit "2/2 mod" value here are the possible encryption outcomes for a given serial/name-seeded encryption:
possible encryption outcomes for 1-bit value encrypted with an arbitrary encryption seed.
possible outcome #1:
(unencrypted) 0 -> 0 (encrypted)
(unencrypted) 1 -> 1 (encrypted)
possible outcome #2:
(unencrypted) 0 -> 1 (encrypted)
(unencrypted) 1 -> 0 (encrypted)
The first encryption outcome has at least one match (two here), the second outcome has none. So, for a 1-bit value, there is a 50% chance at least one unencrypted value will match it's encrypted form in each possible encryption outcome.
You will find that the more bits in the value (the "2/2 mod" value in the algorithm being discussed), the higher this probability is that there is at least one match for each outcome. That is, a larger percentage of possible outcomes have at least 1 match unencrypted to encrypted.
Note that choosing a 24-bit value to be encrypted ensures an almost certainty that a match exists at least once for every possible seeded-encryption, so therefore in this case we can safely assume that a valid key will exist for every possible serial/name combo. Note also that a 24-bit value is conveniently not too large as to make finding the matches an impossible task. 24-bit values that match unencrypted to encrypted can be brute-forced. The author brute-forces all possible 24-bit values (for the user-supplied name/serial) through the 24-bit value ("2/2 mod"), and supplies a morphed/encrypted form of one of the found values to the user (a 16-digit key, see below).
Now if the author had just given the user this 24-bit value as the key, the user would easily be able to brute-force all possible values, just like the author can.
To prevent this, in the process of encrypting the 24-bit value "2/2 mod", it is morphed/encrypted into a 16-digit key before morphing/encrypting to a final encrypted 24-bit value. It must be morphed to/from the 16-digit key form in a way so the 16-digit key is cryptographically strong (shows no resemblance to the original 24-bit value, or to the encrypted 24-bit value). The algorithm uses strong encryption techniques (eg blowfish) in morphing/encrypting the value.
Now the 16-digit key can be given to the user and the weak point in the algorithm (where the 24-bit value "2/2 mod" exists) can remain hidden in the code. Much more secure. The 16-digit key can be tested to be valid by inputting it where the 16-bit value is morphed/encrypted back TO a 24-bit value, and comparing it to the output at the point where a 16-digit key is morphed/encrypted FROM the 24-bit value.
From the outside the only way the user can get a valid key is to bruteforce the 16-digit key - obviously an unrealistic option. But now you're inside, and you can brute-force the 24-bit value... yay! :)
savy?
I totally get ya!
The Key and Magic code are not completely understood by even them. They are just encrypted Index/Coeffs.
I bet you're right about MagicCodeGenerator being the inverse of the Index function. I'll go take a look at the code and see. Problem is I've been looking at it all morning and I'm having a crappy time getting MagicCodeGen into C++.
I threw in the asm thats giving me trouble, but without the stacks its pretty difficult to look at. I don't know, I'm half temped to write out my vars eax,ebc,edx,etc in C++ and write it out all over :blink:
Ok, I went to lunch and I got some progress in that code. I have almost the entire 8444 function done. There is just one part I'm curious about. I entered in a few different codes and it never did anything other then clear EAX, its this code:
1000847B mov * *al, 1Fh
1000847E cmp * *al, byte ptr [ebp-4]
10008481 pop * * esi
10008482 sbb * * al, al
10008484 not * * al
10008486 and * * eax, [ebp-4] *
10008489 leave
1000848A retn
It looks to me that the CMP is getting the result of AL-EBP (which as far as I can tell has never yet been equal or greater then 1F). I have not had to deal with the SBB command yet so I need to look up what thats going to result with.
Hi este,
1000847B mov * *al, 1Fh
1000847E cmp * *al, byte ptr [ebp-4]
10008481 pop * * esi
10008482 sbb * * al, al
10008484 not * * al
10008486 and * * eax, [ebp-4] *
10008489 leave
1000848A retn
this code is essentially:
if ( ebp_04 <= 0x1F )
* *return (ebp_04);
else
* *return (0);
The sbb subtracts the right from the left, and further subtracts 1 if the carry flag is set. Here the "sbb al, al" will set al to 0 if ebp_04 <= 0x1F, and set al to -1 (0xFF) if ebp_04 > 0x1F. Then al is NOTed so that when passing through the AND, ebp_04 will be returned if ( ebp_04 <= 0x1F ), and 0 will be returned if ( ebp_04 > 0x1F ).
I've learned a lot from this serial/name/key scheme, I'm glad you posted! I guess there would be quite a lot of schemes that use the same idea as this one. I've never tried to make a keygen myself, so I'm not sure how to go about writing one. But good luck anyhow!
I would try ripping out the binary code, and wrapping my own code around it to make it do what I want it to do. But to do this binary code would need to be placed in the same memory location it originally runs from, cuz it's likely not relocatable. And the environment it originally ran in needs to be emulated too, eg C runtime library calls can be substituted for your own. I dunno if other keygeners use this method? It saves writing the entire algorithm from scratch in C++.
Someone with experience coding keygens here could offer some better advice...
Since this is my first attempt at RE, even at asm, I'm not sure if this is a normal or difficult scheme. It was defientely tricky for me, but I know alot of that is b/c I had to learn asm. My next project .... oh boy!
I'm glad I posted too, I'm really really stoked I found this place. I absolutely could not have gone this far without help. Thanks Again!
Ya, I knew it was possible to the thier asm and make it work for me, but thiers has so much crap in it, filtering and all sorts of loaders for all sorts of data. I figured that since I pretty much wrote down and documented the function of every line of code (GREAT way to learn asm btw) that it would be easier for me just to rewrite in C++.
I have the 8444 function of magiccodegenerator (the logic part), which is probably the same as the index maker. Blowfish En and De chiper ard done. Mesh, and the function that combines it are all done. I just need to start on index and factor once I get this finished. Besides I really know nothing about integrating and moving asm code around.
I'll keep plugging away at it. The C++ is going slow, but this is all I've done at work for almost 2 weeks so I'm anxious to get it done. :D
I'm looking over the code some more and it looks like the Index Generator isn't the inverse of the Magic Code generator at all. I was hoping it was since I already have the magic code.
I'm actually having some issue getting the SHRD and SHLD commands to work.
The code I have is taking in the current letter of the key, and for the first three it shifts left by 0,5, then F. Adds each answer, then shifts the result usinga SHRD EAX,EDX,0x14 which since EDX is always 0 it seems to equate to a 'eax>>0x10' but I'm only sure of that for one example as I'm coding it right now.
I'll post the code since its the opposite to the other code I posted, sortof.
This is what I have
* for (x=0; x<=15; x++)
* * for (i=0; i<=31; i++)
* * * if (key[x] == ConstCode[i])
* * * *index[x]= i; * * *
*
* for (x=0; x<=15; x++)
* for (x=0; x<4; x++)
* * *temp1+= (index[x] << (x*5));
* temp1= temp1>>0x10; *//needed to be shrd
Originally posted by este@Jan 19 2006, 03:09 AM
I'm looking over the code some more and it looks like the Index Generator isn't the inverse of the Magic Code generator at all. I was hoping it was since I already have the magic code.
I'm actually having some issue getting the SHRD and SHLD commands to work.
The code I have is taking in the current letter of the key, and for the first three it shifts left by 0,5, then F. Adds each answer, then shifts the result usinga SHRD EAX,EDX,0x14* which since EDX is always 0 it seems to equate to a 'eax>>0x10' but I'm only sure of that for one example as I'm coding it right now.
I'll post the code since its the opposite to the other code I posted, sortof.
This is what I have
* for (x=0; x<=15; x++)
* * for (i=0; i<=31; i++)
* * * if (key[x] == ConstCode[i])
* * * *index[x]= i; * * *
*
* for (x=0; x<=15; x++)
* for (x=0; x<4; x++)
* * *temp1+= (index[x] << (x*5));
* temp1= temp1>>0x10; *//needed to be shrd
1267
hi este,
i'm not sure if u're still reading this but if the code is using "shrd/shld" instructions, it may be the case that the "temp1" variable above is being treated or is supposed to be a 64-bit variable. maybe (temporarily?) casting it to a 64-bit variable will help.
.
vBulletin® v3.6.4, Copyright ©2000-2016, Jelsoft Enterprises Ltd.