PDA

View Full Version : Blowfish and SHA-1 analysis on cacheX


Lbolt99
May 28th, 2002, 17:18
CacheX program and keygen analysis.
Disassembled keygen (eclipse) and also registration routine in CacheX opera version.

Crypto used: SHA-1, blowfish

Blowfish: Subkey tables stored in file and copied (0x1048 bytes)

Seems to deviate from blowfish spec: subkey table is continuously modified by CacheX

ďNullĒ represents 64 bits of zeros in this document (ie hex 00 00 00 00 00 00 00 00)

Serial # format: hex digits, 64 bits (ie 5E43-347E-5223-7A43)

The name and serial # are stored in the registry. These are pulled from the registry when the program starts, a simple XOR operation is done on the S/N to get it to the same code that is entered at the dialog box when registering program. The reverse operation is done when registering the prog; the code entered is XORíed with a constant and stored in the registry. Either way, it proceeds to the below procedure:

Procedure (initially, the keygen and the internal cachex routine do the same thing):

Part I
1) SHA-1 the name (after itís converted to uppercase)

2) XOR the hash of the name with the blowfish P-table (0x48 bytes)

3) Blowfish (64 bit data: null). Iterates 0x12 times, churning thru subkey table, updating all 0x48 bytes of P table

4) Blowfish (64 bit data: end result of last iteration of #3). Iterates 0x200 times, churning thru 0x1000 size table

5) NOTE: As of this point, the Eclipse keygen and the programís internal routine have done the same thing.

5a) the KEYGEN at this point calls blowfish again, with data that is preinitalized at the start of the keygen: 85 09 1E 93 91 9D FD 74. After blowfish is done, it results in the correct S/N to enter into CacheX opera. The keygen is finished.

5b) only CacheX after this point. (keygen doesnít do any of this)

6) Swap P1 thru P18 of blowfish subkey table

7) Single blowfish call: data is the Serial number: After blowfish is done, it results in the same preinitialized data that was in the keygen: 85 09 1E 93 91 9D FD 74

Part II
8) OK. Whew. This part seems to be a large constant operation, in general. Iíve commented it in one of the attached documents, but all in all I believe it generates the same info every time regardless of name/Serial#.

9) SHA-1 the memory image of the program

10) Blowfish: see steps 2-4 in part 1. (Xor with hash of memory image this time tho)

11) Blowfish: decrypts executable code (executed at the CALL ESI routine cs:443b02)

Part III
12) Now weíre looking inside the CALL ESI

13) SHA-1 on 9D 91 93 1E 00 80 74 FD (see step 7)

14) Blowfish: see steps 2-4 in part 1. Xor is with hash of hex digits in step 13

15) The following iterates twice:
a. Read 30h data (constant) from low memory, copy

b. Blowfish crap all over again (xor subkey table w/30h data read in), 0x12 iteration , 0x200 iteration, p1 thru p18 swap).

c. Iterates 0x1F4 times:
blowfish 30h byes of data copied (w/modified subkey table)

d. read and copy different 30h data from low ram

e. Final Check: 1st 8 bytes of the 30h data. Read bytes 5-8, NOT them, compare with bytes 1-4. if same, exit. They will be the same on the 2nd iteration of Step #15, if your code is correct.

e. iterate back to step a (once only,assuming correct code)

OK, now that itís all in a nutshell, I have a bad feeling that there is no way to keygen CacheX unless you have a valid code, in order to find out the CONSTANT: 85 09 1E 93 91 9D FD 74. This constant is different between the different cachexís: IE/netscape and Opera. The subkey tables in the three version are the same, for what itís worth. Since the constant is unknown, and there doesnít seem to be any way to figure it out from working backwards in part 3. Is my analysis correct?

So eclipse must have had a valid serial in order to figure out the obscured constant?

mike
May 28th, 2002, 21:11
Quote:
e. Final Check: 1st 8 bytes of the 30h data. Read bytes 5-8, NOT them, compare with bytes 1-4. if same, exit. They will be the same on the 2nd iteration of Step #15, if your code is correct.


In the end, then, the check is against a 32-bit number? It looks as though you could bruteforce the whole process, though you'd probably need to distribute it. How long does it take to run through a single check of the name/SN?

Lbolt99
May 28th, 2002, 21:42
Quote:
Originally posted by mike


In the end, then, the check is against a 32-bit number? It looks as though you could bruteforce the whole process, though you'd probably need to distribute it. How long does it take to run through a single check of the name/SN?


Hi, thanks for the quick response. It does look like the final check is done on a 32 bit #. It just compares it with another 32 bit number, inversed. Looks like this:
MOV EAX, [EDX+4]
NOT EAX
MOV EBX, [EDX]
CMP EAX, EBX
if equal, registered, else loops back up, increments to the next 0x30 bytes of data to read in (see step 15a) until a certain value
is reached, then it kicks out and sets the unregistered flag.

I don't know if this is an accurate assessment of speed, but I set a BP before the serial check, a BP afterwards once everything checked out, got an ET=54 milliseconds, on a pentium 266 (i'm at work)

Part II could be cut out and pre-set, which would probably save a few ms

Anyway, thanks for the help

mike
May 28th, 2002, 21:59
What debugger did you use? SI doesn't give very good timing for very short bits of code. Perhaps you could go in and alter the code in memory so it tries a test 100000 times and then check the time between breakpoints.

Assuming it takes 50 ms = 1/20 s per test, then it will take ~6 P266-years to "force brutally"

I bet it runs much faster than that, though.

Lbolt99
May 29th, 2002, 02:38
Used SICE 4.05 on a w98 platform.. figured that wasn't too accurate of a time capture

I've thought about this whole problem for awhile, and I think I've simplified it to the point that two-thirds of it can be cut out. So it's down to two years now

Basically, regardless of what name/serial number is entered, if it is a correct combination, it ALWAYS results in the same "constant" discussed before.

Since we only need to find out this constant, Part I can be canned, as well as Part II. All part II really does is decrypt Part III (the code that runs at the CALL ESI).

Part III runs the hash on the constant, XOR's hash w/P-table, does all the blowfish crap, etc.

I'll give your suggestion a shot tomorrow and see how long it takes on just part 3 @ several hundred thousand iterations.. in fact, might even replicate the process in C++, but that'd have to wait until the weekend.. no time now..

This got me wondering how the author managed to get two 32 bit numbers next to each other, one the inverse of the other, after all this blowfishing and everything.. could there possibly be several different constants, other than those the author "picked" which would somehow result in it passing the final check? I guess I'll have to take a closer look at the data passed in Step 15-c.. maybe that holds a clue.

Once the constant is figured out, you can replace the one in the eclipse keygen (opera) with the brute forced one and it should generate the code for the IE version

mike
May 29th, 2002, 03:20
Quote:
could there possibly be several different constants, other than those the author "picked" which would somehow result in it passing the final check?

Yes, absolutely. The constant is 8 bytes, while the check is only 4 bytes, so there are 2^32 constants that would work. It would take about 4 billion times longer to try to find a S/N that matches the original 8-byte constant.

BTW, the check might seem to be 8 bytes, but for *any* first four bytes, there's a valid last four bytes. So the check is really only 32 bits. The "NOT" op is irrelevant.

Lbolt99
May 29th, 2002, 21:51
Thanks for the ideas. I've done a little more analysis on exactly what is going on in the CALL ESI routine. As stated before, regardless of name/code, it will always arrive at the same (unknown) constant.

My speculation at this point is that the author has picked 8 random hex bytes. Then he:
1) hashes it with sha-1
2) xors with 0x48 byte p-table
3) churns thru blowfish table, updating continuously

So now the hash is "meshed" into the blowfish table.

Now he's got his highly modified blowfish 0x1048 byte long table set up.

He picks out 0x30 bytes of random data, ensuring that the 2nd set of 4 bytes are the inverse of the 1st set of 4 bytes.

Then he parses thru the 30 bytes, 8 at a time, with blowfish. Does the same thing about 200 or so times

Stores it in the exe file.

Now, when the program is run, with a correct serial, it will arrive at the correct 8 byte constant, do steps 1-3, in addition to a P1 thru p18 reverse..

Pulls the data from the exe (30 bytes), and after all the looping, arrives "back at" the original 30 bytes of random data he picked out.

I have found out, unfortunately, that in addition to the 32 bit check, there are other checks on these 30 bytes throughout the program.. it stores the final 30 bytes produced and checks throughout program

So all 30 bytes have to pass internal checks in cachex, as well as the initial 4 bytes = NOT 4 bytes check...

I would have to brute-force 48 bits and "emulate" all these checks.. (I originall thought it was a 64 bit constant, but the program discards the first 16 bits for whatever reason). I verified this by overwriting them after the registeration number was blowfished into the constant.

Anyway hope all this makes sense How realistic is it to Bruteforce 48 bits?

If not, I'm going to dump the encrypted code and just hard patch it. Problem is it happens thruout the program, pain in the neck. It's not wrapped with anything like aspr or anything

thanks for the help

crUsAdEr
May 29th, 2002, 22:05
Hi Lbolt,

Actually, most of the encrypted are used to decrypt other code as well as generating SHA key... I only found the main message loop call important.. i actually nop the first few call to Decrypt and execute code... only dump one long section right at the end which contains the Nags call as well as Messageloop... hard patch it and it runs fine now... the rest are not important.. though i did dump them to study the decryption routine.. just a suggestion if you find bruteforcing infeasible...

Regards,
crUsAdEr

Lbolt99
May 31st, 2002, 02:03
thanks for the suggestions as far as going the route of dumping the encrypted parts.. plan to play around with that tomorrow. Sounds like it's the easiest approach to this. Really wish I could have done something as far as keygenning it. Is this a general trend of shareware authors towards "impossible" to keygen programs? Seems strange, seeing things like CloneCD and Elcomsoft advanced disk catalog keygenned, that something like this would stand out. Even code decryption with AZPR is possible, as you demonstrated

Maybe it's something I'm missing, or I just don't know enough about the mathematics of cryptanalysis to go about this.. fwiw, didn't even know what a "hash" or "block cipher" was two weeks ago, so this is all new stuff

Interesting.. looking into how hard a 48 bit brute force would be.. I've streamlined the process, and could parallel process across several 1ghz machines I guess. Wish I had a few 450mhz ultrasparc 2i's at my disposal, lol

seir
June 2nd, 2002, 09:13
Hey Lbolt99,

unfortunately you won't have a chance to bruteforce the
48bits. The problem is that the blowfish loop that you
need to execute 6x500 times slows down the whole process
too much.

I just digged in my sources ... I've written a bruteforcer
for it that tries to find a value which satisfies the
32 bit comparsion. After I found a value it wasn't of too much
help though. As you already found out the whole table is
used to decrypt memory for later usage. So with the value
I found the app simply crashed.

My keygen was only possible as you already supposed with a
valid license. That's actually the weakness of this protection
system. BTW, I think this is a modified/custom compliled
Armadillo. Some time ago I reversed an Armadillo protected app.
It was using crc32 and blowfish, but the whole registration
process was exactly the same as in cachex. And I figured out
that you can break it in a reasonnable time with a bruteforcing
approach. If you are interested in the target just leave a Private
Message and I may also give you my bruteforcer source.

Greetz,

- seir

Lbolt99
June 13th, 2002, 20:27
Hi, thanks for the info. I reset CacheX into trial mode, and took a look at what happens. I took the constant produced but unfortunately it doesn't look like it works with the "registered-mode" decryption routine. The routines look the same but are different and in different locations of the program.

They must use a different algo and key for decrypting the data between the unreg and reg versions. I think that's why the constant arrived at when running in trial mode doesn't work. Basically, I took the constant and planted it into the Eclipse CXOE keygen. Didn't work.

Two options I see at this point:

1) pay for it

The upside is that it would reveal the CONSTANT, allowing the keygen to be complete.

2) reduce the keyspace that needs to be searched for brute forcing the 48 bits. Mike would know more about this than me. Maybe there's a way to detect a "pattern" of values that allow
the 32 bit comparison to check out. Search thru ONLY those values, looking for a 48 bit number that will generate the CORRECT 0x30 bytes for the decryption..

Artifex
July 5th, 2002, 06:32
Hi, Lbolt99 and all fellows.
As we don't know the proper 64-bit constant for Cxie, couldn't we try to use the Opera constant and get our Cxie decrypting process to think that we are using Opera.

1. Would we have to modify many things in Cxie decrypting routine ? It seems that a lot is shared between versions. First step could be to get correct decrypting in live, as we can't patch the prog without altering the process.

2. Could you explain what would we have to dump and paste to restore the decrypting process if we patch the prog ?

(As far as cryptology is concern I am still in the Enigma times).

Artifex

Lbolt99
July 8th, 2002, 17:00
Quote:
Originally posted by Artifex
Hi, Lbolt99 and all fellows.
As we don't know the proper 64-bit constant for Cxie, couldn't we try to use the Opera constant and get our Cxie decrypting process to think that we are using Opera.

1. Would we have to modify many things in Cxie decrypting routine ? It seems that a lot is shared between versions. First step could be to get correct decrypting in live, as we can't patch the prog without altering the process.


Unfort. the 1000+ byte blowfish subkey table is heavily modified by itself with the sha-1 of the 64 bit constant So despite the fact that the routines are similar, the key table is completely different. (By the way, this violates the official blowfish specification: the subkey table is not supposed to be modified after it is generated)


2. Could you explain what would we have to dump and paste to restore the decrypting process if we patch the prog ?


The 1040 byte subkey table (it is copied from low ram to the himem area when the decryption takes place) AFTER it finishes modifiying itself zillions of times


(As far as cryptology is concern I am still in the Enigma times).

Artifex


I was too, these helped out as far as understanding the crypto used in cx:

SHA-1 specification:
hxxp://www.itl.nist.gov/fipspubs/fip180-1.htm

Blowfish spec:
hxxp://www.counterpane.com/bfsverlag.html
hxxp://www.codeproject.com/cpp/blowfish.asp

Lbolt99
July 8th, 2002, 17:49
Quote:
Originally posted by Artifex
I will enter in "Unlock" name "DEFAULT" and SN = 3482-bc11-c786-e749, and will watch why first check is false and second is true.


Still thinking about this one.. I ran it, and successfully duplicated your results... at first glance it seems like it is never able to pass the final comparison check:
-----------------------------------------------------------------
Final check (Two 32bit#s next to each other, NOTs one, compares, same=registered). On 1st iteration, fails, loops back, reads another chunk of 30h bytes, 2nd time, correct, if youíve entered the right registration info. The checked bytes are @ 69f9d0)
--------------------------------------------------------------------
Note that it continues iterating, about 5 or so more times, reading in different chunks of 30h bytes to "decrypt" into the decryption key used to decrypt the stuff in other parts of the program.

It somehow comes up with a different (default) 64 bit number for the second call into 69FAF5, which allows it to pass the "final check".


In retrospect, it might be a quicker crack to paste in the blowfish subkey table, and let it do it's work, instead of dumping/pasting each section.. I'm going to give that a shot to see if it'll work..

Artifex
July 8th, 2002, 21:45
quote :
------------------------
Lbolt99 wrote :
"In retrospect, it might be a quicker crack to paste in the blowfish subkey table, and let it do it's work, instead of dumping/pasting each section.. I'm going to give that a shot to see if it'll work.."
-------------------------

I also feel that it is worthwhile.

Artifex

Lbolt99
July 9th, 2002, 15:02
Quote:
Originally posted by Artifex
quote :
------------------------
Lbolt99 wrote :
"In retrospect, it might be a quicker crack to paste in the blowfish subkey table, and let it do it's work, instead of dumping/pasting each section.. I'm going to give that a shot to see if it'll work.."
-------------------------

I also feel that it is worthwhile.

Artifex


I'm going to give this a shot sometime today or tomorrow -- hopefully this will be much quicker, with dumping each part it got more and more to the point of not being worth it.. if dumping and pasting the blowfish table instead is better, I'll document the method and everything..

UrgeOverKill
July 9th, 2002, 17:19
wow, what a great thread, I learned quite a bit by watching!

nice work guys!

Artifex
July 12th, 2002, 15:16
Hi, Lbolt99, UrgeOverKill and all fellows.

P and S-box tables dumping and patching seems to works.

First with a few patches to evit anti-patch, anti-softice and useless nag screen display, I arrived safely at
:0043ec81 call 0043eed8 (startup window display).

In there prog crashes (at :0043efdf call 00401f4c) because it calls an address in edxxxx that had not been correctly decrypted.
Decryption of that piece of code is at :
:0040bb44 call 00440bf4
We need correct P and S-box tables. So I dumped the correct bytes in the demo version :
/dump dd1050 1048 dumptables.bin
and I loaded them just before the call to 00440bf4.

Startup window popped up, and prog exited without crashing.

To stay in the prog :
bpx 418c3c
:00418c3c call 00440bf4
Again we have to load the correct tables at the right place. Tables
are different
/dump dd4c04 1048 dumptables1.bin
/load dd4bd8 1048 dumptables1.bin
Address to dump or paste is the last push before the call 440bf4.

Each function requires to load different tables.
So this method is worse than the other.

Artifex

senso
May 5th, 2004, 21:18
Is it possible that CacheX is using a method similar to "Shamir's secret sharing" scheme?