if you have ever wondered how one breaks a 64 bit long secret key, read on...

Cracking the impossible

Written by The Owl

HWiNFO is a very nice hardware detection tool running under DOS. but that's not

the only thing it has been famous for... the registration scheme developed by

its author is very unique in that it uses a proprietary encryption algorithm to

protect a registration check related routine which is decrypted runtime only.

since the key used is 64 bits long, brute force attack has no chance to succeed.

yes, as you will see, history does play a very important role in cracking HWiNFO

so let me tell you about it. it began like 2.5 years ago when i first ran into

this program at SAC. it had a very good executable protection, which i eventually

broke and could finally load it into IDA to study the registration scheme. the

basic idea is that upon registration the user is provided with a character

string that encodes a 64 bit long number (four 16 bit ones actually). i don't

really have memories any longer if the key length was this much at the

beginning but for the v4.x versions it is the case.this long key was then used to decrypt a small routine runtime. initially the

length of the encrypted data was 64 bytes but last year when a few successful

cracks showed up (clever patches) the author increased it to 105 bytes (and

added a few more checks on the return values of this subroutine) which has

remained so up until v4.4.3.when one compared these encrypted blocks to each other it became obvious that

the core of the function has not changed, the new code was responsible for

generating the return values only. one possible way to get to the secret key

could have been the successful guessing of some plaintext bytes which would

have allowed the recovery of the key (we shall see soon how the encryption

algorithm works). unfortunately all of my attempts at this have failed for

over 2.5 years, no wonder now though ;-).what changed the situation is however the release of v4.4.4 at the end of

november where the author introduced yet another change in the encrypted data

(length became 107 bytes) because of another clever crack (which still wasn't

a full key generator since for that one would have needed the secret key). what

makes this change important is however the fact that the author inadvertantly

created a situation where the secret key could have been successfully recovered.the rest of the essay will concentrate on this recovery procedure but NOT on

a full featured key generator which i will personally refrain from writing ever

since the author has all my respects for his creation. i would also like to

discourage the reader from attempting this since HWiNFO itself is full-featured

and has a nag screen only that one can live with...

in short, do not destroy what you have not built yourself.

so, first let's see how the encryption/decryption algorithm works (study the code below for a few minutes): mov si, offset pEncryptedData

mov bx, [bp+key1] ; initialize registers

mov dx, [bp+key2] ; with the key

mov di, [bp+key3] ;

mov cx, [bp+key4] ;loop:

xor [si], bx ; decrypt a block

add [si+2], dx ;

sub [si+4], di ;

xor [si+6], cx ;

not word ptr [si+6] ;

ror cx, 1 ; next round

neg dx ;

xor di, 1234h ;

xchg dx, cx ;

xchg bx, di ;

add si, 8

cmp si, offset pEncryptedDataEnd

jb loop

;... some parameter setup code

call pEncryptedData

;... checks for the return values we can observe a few things from this code excerpt. first of all, we can divide

the subroutine into two independent parts. the first 5 instructions of the

decryption loop do the actual decryption (8 bytes at a time), the rest of the

loop prepares the keys for the next round. it is very important to note that

the key stream generation does NOT depend on the encrypted/decrypted data at

all. in other words, if we knew the initial values of the 16 bit key words

(THE key actually ;-), we could generate the rest of the key stream for an

arbitrary length of data.

let's make a little drawing on the relationship between the ciphertext bytes

and the keystream bytes. the initial values of the 16 bit key words are denoted

by A0, B0, C0 and D0, the upcoming generations by Ai, Bi, Ci and Di where i is

an integer. the encrypted data is represented by Ei, the decrypted data by Fi.

E0 E1 E2 E3 E4 E5 E6 E7 E8 ...

A0 B0 C0 D0 C1 D1 A1 B1 A2 ...

F0 F1 F2 F3 F4 F5 F6 F7 F8 ...

there's a very simple relationship between the values in each column (read the

code ;-), and between two consecutive generations of the 16 bit key words

(i use the C language operators here and some ASM instructions):

F0 = E0 ^ A0 A(2*i+1) = ROL A(2*i),1 A(2*i) = XOR A(2*i-1),1234h

F1 = E1 + B0 B(2*i+1) = NEG B(2*i) B(2*i) = ROR B(2*i-1),1

F2 = E2 - C0 C(2*i+1) = XOR C(2*i),1234h C(2*i) = ROL C(2*i-1),1

F3 = ~(E3 ^ D0) D(2*i+1) = ROR D(2*i),1 D(2*i) = NEG D2

so far so good, but why the heck does this help us in any way in recovering A0,

B0, C0 and D0? from a cryptoanalytical point of view one would need to know the

values of Fi in order to be able compute the key words. this is where one can

make educated guesses only, e.g. observe the compiler generated code elsewhere

in the program and assume that our encrypted routine has some similar code

patterns as well (which turns out not to be case in the end, but it's a good

exercise anyway to give it a few tries). we could also guess some other

instructions which must occur in the code, e.g. retn or retf, or some other

magical numbers i didn't talk about (nor will i since this is not a keygen

tutorial).

this has been the situation for a few years now, however as i already mentioned

something happened in the latest version of HWiNFO... let's have a look at the

new decryption routine (only the change):

mov si, offset pEncryptedData-2 ;... usual register setup ;... usual decryption loop ;... usual parameter setup call pEncryptedData ;... usual checks

so, what happened? we have an extra 2 bytes at the beginning of our encrypted

routine, which effectively shifts the applied keystream by 2 bytes as well.

let's make another drawing to make it clear (underscore refers to the fact

that we could have different values at those positions than previously): E-1 E0_ E1_ E2_ E3_ E4_ E5_ E6_ E7_ ...

A0 B0 C0 D0 C1 D1 A1 B1 A2 ... F-1 F0_ F1_ F2_ F3_ F4_ F5_ F6_ F7_ ... hmmm. does it look like it would help us? well, if we knew ONLY this data then

we would be in exactly the same situation as we were before with the other set

of data. however now we have BOTH. since the length of the new encrypted block

is exactly 107 bytes, we can make an assumption: Fi = Fi_ for i=0,1,... another hmmm. does this start out to look like we could have a few more or less

linear equations for the key stream words? yes it does ;-) F0 = E0 ^ A0 = E0_ + B0 = F0_ (0)

F1 = E1 + B0 = E1_ - C0 = F1_ (1)

F2 = E2 - C0 = ~(E2_ ^ D0) = F2_ (2)

F3 = ~(E3 ^ D0) = E3_ ^ C1 = F3_ (3) so, we have 4 equations and 5 unknown variables (A0, B0, C0, D0 and C1),

kind of sucks. but wait a minute... didn't i say somewhere above that the

keystream doesn't depend on anything but itself? in plain english that means

that we have a relationship (read: another equation) between C0 and C1: C1 = C0 ^ 0x1234 (4) wow, we did it. nothing should prevent us now from solving this system of

equations. let's substitue the value of C1 back into eq.(3) and then express

D0 from it: D0 = E3 ^ ~(E3_ ^ C0 ^ 0x1234) from eq.(2) we also have: D0 = ~(E2 - C0) ^ E2_ which means that E3 ^ ~(E3_ ^ C0 ^ 0x1234) = ~(E2 - C0) ^ E2_ (5) holds as well. reducing one side to C0 only we have: C0 = E2 - ~(E2_ ^ E3 ^ ~(E3_ ^ C0 ^ 0x1234)) (6) so, all what's left to do is write a small program that enumerates all the

values of C0 for which eq.(6) holds. as it turns out, we have 64 different

solutions for C0 and thus for A0, B0 and D0 as well (it's fairly easy to see

that for each value of C0 there's exactly one value for A0, B0 and D0). once we have the key candidates, we can write a small brute forcer program

which decrypts our data using these keys. a simple inspection of the decrypted

data in a disassembler will quickly reveal which key is the real one... which

i won't publish here for various reasons, the most important ones being my

respect for the author (after all we're here for learning and not for stealing),

and also i'd like the reader to do his/her homework ;-).

i hope everyone has learned something from this little essay. on one hand the

author of this otherwise excellent protection (and i didn't even talk about the

executable protection which is another interesting one...) has had to learn

a more or less painful lesson on how one should not undermine his own scheme

by hacking it inappropriately (probably in a hurry to defeat that crack i

mentioned in the intro and the program docs talk about as well), on the other

hand the reverse engineers should have got a lesson on how to be persistent

(beleive it or not, i did expect such a mistake to happen after i had seen the

author's reaction on the various crack/patch attempts last year) and how some

elementary knowledge in cryptoanalysis can help in cracking an otherwise large

(and thus secure) key.

Advanced reversing

homepage links search_forms

+ORC students' essays academy database

reality cracking how to search javascript wars

tools anonymity academy cocktails antismut CGI-scripts

mail_reverser

Is reverse engineering legal?