Cracking the impossible
If I were a software house manager I would enlist him at once.
In the mean time I'm happy that he's still working for all of us, for free, and I thank him sincerely for giving us his superior knowledge, his feeling , his understandings... Head the advice of a really great +cracker: "do not destroy what you have not built yourself"!
Off topic... but important for us
Since I happen to know that The Owl was a personal friend of +ORC, and since I'm sure that +ORC -wherever he is- will of course read a new essay written by the Owl, I'll take this opportunity to ask the Old Red Cracker to contact us. We don't have any news since July. That's not nice for many young (and less young) reversers that need guidance... What's going on master?
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
;... some parameter setup code
;... 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
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.