PDA

View Full Version : B4 I start coding: Does my algorithm make sense ? Picture/Diagram inside


este
January 15th, 2006, 18:18
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 ?

LLXX
January 16th, 2006, 04:21
I believe I might've figured it out without the need to bruteforce!

Quote:
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.
That "factoring function" must be examined carefully.

In your first diagram, connect the output from the second bl0wfish into the input of the first, and run that loop until it converges.

este
January 17th, 2006, 03:17
I found a mistake with my picture.

It seems that the key is taken into an indexing function, returns 8 bytes that I 'thought' was going into blowfish to be encrypted, actually it is being decrypted. HOW they are taking the index and feeding it into blowfish decipher and know that some index for any key will decrpyt into anything they know to use is WAY beyond me.

So that 'de'crypted index is sent to the factor function, the return value is very odd however. Like this :

dIndex: 03 FE AB 46 00 85 11 C7

factor: 02 00 01 A8 00 00 01 01 00 01 00 00 00 00 01 01 00 00

The funny thing about the factor is that only bytes 1 and 4 are ever anything other then 00/01. I've never seen Byte 1 get above 0A or so. Byte 4 is the only normal range byte, I've seen it from 00 to FF. I don't have my notes here but If i remember right. All 18 are read into the modified factor/index function and 8 are created from that, 4 are discarded. Its wierd ass hell.

I've been trying to calculate the time it will take to brute force 16.7 million keys, I figure less then ~1000 lines of ASM code, I took out all the blowfish key generating, have a dual 250 opteron with 4gb ram, I don't think it'll take long at all. I don't know if I should figure the MIPS of the processor or what, I don't really care, but if I found out it'll take awhile I'de keep working at finding a non-brute force method.

Besides, there are actually at least 25 variations of this program that usable / installable, thats all based on the key. It would be helpfull for me to have the list of valid keys for my mesh.

LLXX
January 17th, 2006, 05:03
Could you link an updated diagram? When you said
Quote:
I 'thought' was going into blowfish to be encrypted, actually it is being decrypted.
It all makes sense now. One is decrypting and the other is encrypting, correct? I'd just like to see an updated diagram, since I already have it nearly figured out
Quote:
I've been trying to calculate the time it will take to brute force 16.7 million keys, I figure less then ~1000 lines of ASM code
Depends how speed-optimised your implementation is. 1000 lines of Asm sounds a bit on the high side though...unless you plan to inline the crossing function and all the key XOR'ing. But 16,777,216 iterations shouldn't take more than a few minutes.

este
January 17th, 2006, 06:01
I do plan on doing everything in my diagram. I was thinking anywhere between 1 and 5 minutes. But I was a little worried that maybe I had a number mixed up somewhere and it ended up being a few days. You know, little mistakes.

I'm not so sure its acutally decrypting. I mean, they have ConstCode which is 32 bytes and looks somthing like this "AF2KSBR5C..." then key which is pretty much "F2AK5..." a total of 16 digits. The index for my example would be 01-02-00-03-07... No numbers above 1F (31).... How could this possibly be somthing that blowfish could decrpyt. Also, this is the first instance of blowfish besided the key generation it does at the beggining. I'm thinking that they fed the decrypt algorithm the index to encrypt it. Only difference between the two in blowfish is the order of the PI table, so its going to be like encrypting. That is something I'm going to keep in mind however, using a decrypting function to encrypt.

Oh... Hmmm.... I guess maybe when they encrpyt the modified portion for real that would really be crypting the factor part.... nah, eIndex is so hacked up by the time it gets to the legit blowfish cipher that there is no way they could make a connection. maybe this company cracked blowfish. ....... hahhahaha

I just figured 1000 since the original was over 1750 and I'm crappy at C++ But cutting out the init_blowfish routine and just starting with the right tables should make a pretty big difference.

Thanks for all your help, if I didn't find this place I'de still be stuck WAY back there trying to crack what I didn't know was blowfish. That would have been embarasing.

LLXX
January 18th, 2006, 02:00
I have a suggestion: Don't think of the Blowfish as being "Encrypting" or "Decrypting", just identify which direction they're going. Either A -> B or B -> A. Thinking of it as encryption/decryption will only restrict your progress. Just think of it as A -> B in one direction, and B -> A in the other.

Going one way, the two dords of data will be XOR'd with the two elements in the subkey array first, and then be pass into the cross-combining ladder in one order, in the other way it'll go through the "ladder" first and then be XOR'd with the elements of the subkey array in the opposite order.

este
January 22nd, 2006, 20:03
Yea, I actually kind of came across that concept myself the other day.

Its really just changing the that data, I did notice that one is A>B and the other B>A so that helped.

I have finished the brute force part. Coded everything I needed into C++. I also found out that of the 3 bytes I narrowed it down to if byte1 is over 7F then it creates an invalid key. So, that means my list of possible keys per sn/name combo has been capped at 8 million... Which I have the list of, and by the by it took my computer all of about 30 seconds WITH the fstream each completed key to a txt file

So, thats cool and all, but there is a second check now that takes in the key and checks to see which version to install. If its of Valid Type, but not valid Value for this program, version, options, etc it gives me a nice error saying so. Which is cool, it really helps that it doesn't just say "Wrong Key" like the other error. (Some times programmers are sooo dumb)

I am however having a little bit of trouble tracking down where this key is re-checked.

I'm working on it now, it would help if I could get OllyDBG working, but for the life of me I can NOT get it to set break points on my dll. Also, it would be nice If I could figure out how set softice to stop if EAX equals the ascii of my key.

I know that this part will probably not be as hard as the first part, just having trouble following the code. I've narrowed it down to one of two functions:

This code starts after I return from a successfull key compare
Code:

10002A0E call sub_10003AB1 ;1
10002A13 lea ecx, [ebp-50h]
10002A16 mov byte ptr [ebp-4], 3
10002A1A call sub_10003E9E ;2
10002A1F test al, al
10002A21 jnz short loc_10002A2C
10002A23 mov ecx, esi
10002A25 call sub_100024DA ;Loads "error"


Problem is I don't know if key is being checked in 1 or 2. If its loaded in 1 and then modified or factored somehow if I look in 2 I won't know what to look for so I might just skip right over it.

LLXX
January 23rd, 2006, 00:48
Quote:
[Originally Posted by este]Its really just changing the that data, I did notice that one is A>B and the other B>A so that helped.
You actually didn't need to bruteforce it at all.

Could you diagram the second check along with your revised flow diagram for the entire algorithm? I like looking at pictures more than I do reading through code

Maximus
January 23rd, 2006, 09:47
Quote:

I'm working on it now, it would help if I could get OllyDBG working, but for the life of me I can NOT get it to set break points on my dll.

? You mean that -when opening the list of DLLs with ALT+E, selecting the one you wish to break into, opening the func name and placing a bp in the right point- Olly does not stop?

este
January 24th, 2006, 05:26
Yea I discovered that at the modified index potion I can start the entire code from nothing. Its ok, the brute force seriously took me all of 30 seconds to run at 16.7million codes with some seriously sloppy C++. I'm done with this portion!!!! I got my code ! YAY

The code acutally starts between the modified and eIndex (which turned out to be decrypted index). It starts life as an 18 byte string with real simple values like 01 in byte 9 for option 1 to be on etc etc. Gets made into the modified index cut in half, that gets combined with the serial/name mesh, blowfished, that forms a key, the key then disolved into Index again, blowfished (now to decrpyt) and then checked to see if it is == to starting value, its pretty easy now that I understand it. All except the part that takes the encrypted blowfish that contains the mesh and they make a key from that, still confuses me, but I'm done with it and its my first project so its to be expected I don't understand a litle part of it. Fine with me. I'll daigram it for you when I'm at work,

Except there is 1 problem, this is a hardware and software implementation. The hardware has a util that will allow me to enter keys in it, and the software was protected too. I figured I'de crack the software, get the universal key for my serial and be done with it.

I entered in my valid code but the hardware util says its invalid. Well, acutally it says check the typing and some crap about the driver but just the same.

Good thing is, I followed the code in the update util and found that they are doing at least some of the same factoring as the software part! The .exe even has blowfish. The part that confuses me is WHY didn't they do all the key factoring/checking work inside the hardware !? They have the power and the time for it.

I'm not sure. I found the part that takes the key and makes the Index out of it. After that it calls a CreateFileA then looks for a hardware name. Its a PCMCIA device so I'm pretty sure they are not opening a stream with CreateFile or anything like that, but maybe I guess.

As of right now it looks like they will either open the hardware to pull some data (like serial number, since the util does not ask me for it) and go on about processing the key, where on sucess they write to the key. OR, they processed a little of the key and now they will pass it into hardware to finish and return an answer. 50/50.

I'm really hoping for software since I can crack that. I know the .exe has blowfish tables so its looking good for software. I know that the function used on the key so far is identical to the one in the program installer. Thats good too.

What I don't know is why they didn't make the two keys the same. Each key holds a program type, version number, region, and 8 or so option bits. But, apparently the key that goes into the hardware is different somehow.



As far as Olly is concered I can't get a single damn thing to work on my x64 machine. I start Olly, open the .exe and it never comes to the screen. Fine. I start the .exe in windows and then attach to it, I can set a bp but when I hit resume nothing happens. On normal XP i can get it to open and start the program but it doesn't respond to breakpoints at all. If I attach it just locks the program up, worthless to me. I like softice in that when I say its time to debug.... its time.

este
January 24th, 2006, 06:26
Crap!!!!!!!! I wasn't sure, but I couldn't sleep so I looked at the code again. Whats really odd is that this looks like a serial comm .... but, they seem do it out of order, ie: close, sprintf, createfile. Also, I have a pcmcia card, I wonder... can you talk with that via normal serial comm ?

They have drivers installed so I wonder if this is really sending the string to the hardware for checking (in which case then why would they need blowfish in the .exe), why use serial comm to talk to your own hardware ?


Code:

.text:00406AEE cmp eax, esi
.text:00406AF0 mov [esp+78h+var_68], esi
.text:00406AF4 jz short loc_406AFD
.text:00406AF6 push eax
.text:00406AF7 call ds:CloseHandle

.text:00406AFD mov ebx, [esp+78h+arg_4]
.text:00406B04 mov edi, ds:sprintf
.text:00406B0A mov ebp, ds:CreateFileA

.text:00406B10 cmp ebx, 1
.text:00406B13 jnz short loc_406B27
.text:00406B15 push esi

Maximus
January 24th, 2006, 11:20
Well, closehandle can be called to close the handle if it were already open, pretty usual attitute of old-style programmers (=prevent error situations before they happen)
...
are print&createfile they called in that order, too? your code shows only 2 moves...

este
January 24th, 2006, 23:11
I'm not 100% on what they were doing with that CreatFileA, but it wasn't writing to hardware.

Unfortunetly I DID find that later. It does write to the hardware I followed the code in the utill from when I hit the OK button to the error screen, it goes like this:

The code is entered in 4 sections/blocks, first the program lines these blocks up nice and even in memory

The index is taken of each letter vs a constant string.

This result is run through a shifting algorithm where the first 4 are calulated then the remaining 12, the final result (what I've been calling index) is 10 byte number, in the software program i cracked it was 8 bytes, this adds 2 for some reason.

The low nibble of the 2nd extra byte determines the name the CreateFileA will make (hardware goes from 1-5). If above 5 or less then 1 the program quits with an error.

The CreateFileA 'seems' to do nothing. I think it makes a file called modelxx.info, where modelxx is the name of the hardware i'm using.

Once the file crap is done the index (which is blowfishable, not sure if the key is the same), is sent into the pcmcia card via a "call dseviceIoControl" command. I have the in & outputbuffer sizes, dwIoControlCode, hDevice etc, but I fear I am stuck.

I can't open the card. Its sonic welded and too expensive to tear open.

I'm so frustrated I'm about to lose it. I worked all of this through just to get shut out right at the end.

Its 10 bytes direct to hardware so I can't force it. Might even be a section in the hardware saying "delay 5 seconds between retry" or somthing like that.

Anyone have any ideas ?? I'm sad.

este
January 26th, 2006, 01:19
Good news!

I looked into it further, I know most of the actual checking is being done after the IO call.... however, I follow it through windows (gotta love softice!) and got into the .sys driver.

They are doing all the checking and comparing in the driver to the hardware instead of doing it inside the hardeare itself...... W H Y !? I mean, this is great for me, but its retarded.

Its pretty much the same thing, Key to Index which becomes the blowfish encrypted form of a meaningfull 8 byte block... like for instance I know that 4 of those bytes are the serial number, have not dug in any further then that.

Crazy huh !?

I'm really really hoping that since they did the key to index to blowfish and then compared the serial of that to the one on the card that they will carry on some more and factor the rest of the key in the driver and then if its valid they will write the bit to the hardware.... I'll know more tomorrow.

este
January 27th, 2006, 03:26
Last update in this thread.

I looked into the hardware a little more and get this, none of the calculation for the hardware licenses is acually done in the hardware. Its all done in the driver. (DUMB!)

It starts of pretty easy, new blowfish codes, different factoring algorithm, then it go really crazy as starts doing a few calls to NTDLL!POOL and does a ton of memory moving, I got bored and then stumbled upon a way to generate keys per my serial number but random other then that, two bytes (of 10 don't even do anything, 4 are for serial (known) and guess what....... They ALL unlock somthing. (EVEN DUMBER!)

All I have to do is send in a key that is valid for my serial with random values for the other bits and they do a calculation and unlock whatever. I unlocked 80 some options today

Once I unlock one I can write down its values and repeat it (if I ever had to do that, prolly never tho). Problem is now I'm getting 90% collisions (unlocking an item i already unlocked)

I could go in and follow the code better, but its driver code and thus harder then normal dasm. Plus they are doing blowfish twice which I dont really get, I don't know I'm half tempted just to generate a list of 1000 or so and set a macro program up to enter them in for me, I have all the important options charted but for sake of finishing the job I'de like to have the licenses to stuff i'll never use.

They fucked up HUGE with this. The software was 10 times harder then the hardware. How lame is it to do all the calc in the driver! Thats messed up. Its like driving all the way to grandmas house to make a secret pie but instead of going inside you just stand at the door and make your pie in front of everybody, then when your all done you slip it in the window and go home.

dELTA
February 1st, 2006, 19:23
Congrats on a well done project este, your stubborness and will to put some serious work in yourself paid off in the end!

We hope to see more of you and your projects here in the future.

este
February 7th, 2006, 18:52
Thanks!

Yea, I'll be hanging around here for sure.

I'm just about to start another program that works with my newly unlocked hardware see if I can get some sort of proof-of-concept thing,

Still can't beleive that they did the calculating in the .sys driver and not the hardware! Blows my freakin mind. It would have been soooo easy!

Ah well,
Thanks again for all your help everyone,