Hello everybody,

I'm in the process of reversing/cracking a nasty regcode protection.
After a lot of tinkering with OllyDbg I finally found the "attack point".
The way I got there is interesting in its own self, with lots of SMC and jumps in the middle of instructions, etc, but it's not the subject of this request for help

To make a long story short (but hopefully comprehensible), the target makes a lot of shuffling around with the username and outputs 7 bytes.
Then it takes the regcode, which apparently must consist of 25 characters chosen among an alphabet of 32, which makes for a total of 125 bits (25 chars * 5 bits/char); from the regcode a new output sequence of 115 bits is calculated.
Each output bit is calculated starting from all of the 125 regcode bits and a sequence of 7876 hardcoded bits (the first output bit is always calculated using the same 7876 bits, the second one uses a different sequence of 7876 bits which anyway is fixed and so on... hope this makes sense, in total a fixed sequence of 115*7876=905740 bits that is hardcoded into the program is used).

Every output bit is calculated as follows:

out_bit(x) = ( sum_for_i_0_to_7875 of (sequence_bit(x,i)*regcode_seq_bit(i) ) modulus 2

where i = 0..7875
sequence_bit(x,i) is the 7876 bits sequence used for the xth bit
regcode_seq_bit(i) is a sequence of 7876 bits calculated from the regcode as follows:

regcode_seq_bit(0)=1
regcode_seq_bit(1..125)=regcode_bit(0..124)
regcode_seq_bit(126..7875)=a sequence of bits representing the products between the 7750 possible unique pairs of regcode_bits.

Then, only 42 bits of the shuffled username are compared to the corresponding 42 bits of the out_bit(x) sequence, and the regcode is considered valid if they match.

The question is: I totally understand the matching algorithm, but HOW DO I GENERATE A VALID REGCODE?

I'm not very deep into maths/cryptography and the like, but as I understand it I have 42 binary equations with 125 unknowns (i.e. lots of degrees of freedom); the problem is the equations are nonlinear (because of the regcode_bits products) so a simple matrix solver is not viable.
Is this a standard/known keygen check scheme?
Is there a known way to generate the regcode?
I'm going to try with a brute force type of approach but I'm not very optimistic.

Any idea is greatly appreciated!

-- Bitman

Hi Bitman.

Welcome to the board.
You certainly have spent your time in the algo analysis and I commend you for that.

Before me spending a lot of time figuring out your scheme interpretation, I suggest you run your program through PEID, using the KANAL crypto analyzer plug-in. Both tools are widely available in the web, plus perhaps also running your program through some other crypto signature finding utilities.

That way you may answer your own question about this scheme being a known/standard keygen/hashing algorithm already described somewhere else and save yourself quite a bit of time in the research and analysis.

Thank you for the tips! I used to do some reversing in the old DOS days but then I lost interest when Windows 95 came along... and now my knowledge of current packers/unpackers/tools is very scarce.

The program seems to be encrypted using ASProtect SKE 2.1x.
There seem to be very little if NO information about the keygen algorithm on the Internet.
I tried a brute force approach (starting from a random key and then changing bits and keeping the changes which satisfy an increasingly larger number of equations) but this approach gets stuck with 30 to 32 equations satisfied out of 42; i.e. it gets stuck on local maxima as I feared.
Maybe my description seems a little bit complicated but the basic idea is really quite simple! Please try to understand and give me a hand

Regards
-- bitman

P.S.: I've also downloaded ASProtect SKE to reverse its key generator, but I cannot even find the attack point... the usual GetDlg... and Point H approaches don't seem to work... these guys did their homework (or -maybe- I didn't

AsProtect by Alexey Solodovnikov.

The application is protected with a well known packer/encryptor.
I have heard of no one attacking the name/key checking of any packer.
Believe me, this guy, Alexey, did his homework.

The majority of this key validation schema relies on hashing algorithms that cannot easily be reversed.
Most of the attacks on packed executables consist on allowing the packer itself to unpack the code, for instance before a trial is up, then dumping the code form memory and modifying the resulting file to be runnable again.

A frontal attack on AsProtect validation routine? may be someone around here may have attempted it. . .

This tut might have some information on this issue as related to ASProtect. I have not reviewed it however.

You will find it on tuts4you.com:

Unpacking | ASProtect 2.xx SKE (Attack on Activation Key)

Downloads -> Unpacking
ASProtect SKE provides function CheckKeyDecrypt. It verifies the registration key for all implemented modes and saves it to the external configuration...
Author: shoooo | Date added: Thursday 07 September 2006 - 05:58:33

Regards,

Yep, I looked at the contents of the tut. At a superficial first pass, shooo describes operations that are in the same "mood" to the analysis that Bitman has described so far.
Thank you, JMI for the link.

Thanks JMI for the tutorial.

The hashing that my target operates on the serial is indeed "in the same mood" as the one described in the tutorial but quite different!

I can see something very similar to a RC4 hashing done on the username, but I think this is unessential; I could use the username hashing algorithm as a "black box" and take whatever output it gives to match it to the hashing of the serial... unless I wanted to write a "username generator" given a serial

The hashing done on the serial is not based on a known algorithm (well, not on one that *I* know of), certainly it's not RC4 nor MD5. Are we sure that PEiD identified the packer correctly?

The key is to solve the set of 42 equations based on the serial's bits.

Regards
-- bitman

PEID is not perfect. There are other packer Identification tools: RDG Packer Detector for instance. Google for "packer detector" and visit the tools repositories linked below, test your app with several. If they all call it Asprotect, I think the evidence is somewhat better.
It is also possible for an app to "disguise" itself as a Asprotected, by faking the signature bytes that most packer detectors search for. (There is a thread or two in this board describing those mascaraders.

However, the fact that you found several characteristics of the hashing algorithm makes me believe that you are indeed working with Asprotect.

It would not surprise me that Alexey introduced a variety of different validation procedures either for each version or even as a polymorphic-like machine, to prevent the eventuality that once someone defeats THE Asprotect validation algorithm, all Asprotected applications are automatically compromised.

Finallly, did you try my suggestion to use KANAL, the plugin for PEID, to look for other hash or crypto signatures. There are other tools that do the same function.

Very likely indeed!



Kanal added no further info; RDG Packer Detector confirms "ASProtect SKE 2.xx".

Regards,
-- bitman

ASProtect uses RSA assymetric encryption for registrations keys; this is well documented. If you are able to break ASProtect and generate keys, that means you are able to derive the private key, and by extension you are also able to break RSA; congratulations, you just solved a hard problem in computing/mathematics! --See edit; possible in some cases due to poor usage.

This is why all attacks on ASProtect rely on circumventing, rather than generating keys. Even for previous versions, I only know of exactly -one- (private) key generator for an ASProtect protected program in existance, and it exists only because the machine which hosted the key generator (for automated registration via electronic purchase) was compromised, resulting in the private key being found. In which case, again, ASProtect wasn't broken; something else was.

Edit: I take some of that back; after reading up more on it, it seems that ASProtect uses a poor implementation so that you can recover some of the needed values, and then bruteforce the remaining RSA section since it is only 32 bits, then you are free to generate keys. The tutorial mentioned above goes into this.

When someone has all the tools at their disposal, but uses them poorly, makes things easy to break.

The entire purpose of the "SKE" version (Short Key Edition) of Asprotect is to have shorter keys than the originally used full-length RSA keys. This means that the entire security of the RSA algorithm isn't used (if RSA is actually used at all for the short keys, contrary to the long ones?).

it's been a while since i had a look, but... doesn't asprotect ske use streamsec libraries?

nah,
to me it reminds some matrix accumulation of the elliptic curves. I tried to look at, but the snippet you posted might be 'everything'. I'm sure there are things you missed, because by this way it cannot be rebuilt properly. However, it really resembles it could, when I gave it a deeper look.

However, it is known that you can shorten evaluation of the bit-strings by precalculating -and that's what ASPR looks like to do.

Have really nor the time nor the will to upack aspr ske dll and try to rebuild the algo -also, I'm pretty sure chunks of it will be polyed
mmh...
I had some very good link somewhere on a paper about binary strings, elliptic curves and such -try to google with both, a nice PDF will pop out somewhere.

edit----
nice, didnt know about streamsec library... and yeah, they implements ECC over finite (and binary I'am sure about) fields^^