All right, run test3.com a few times to get an idea of whatÆs going on. Now, letÆs try to figure out the password. If you run it though Soft-Ice, youÆll notice that the com is encrypted/compressed. The method used has some anti-debugging routines which cause Soft-Ice to crash if you trace through parts of the decryption routine (at least it crashed on my system). Unfortunately, I donÆt know which encryption/anti-hack routine was used and I donÆt have a utility capable of decrypting it. However, I did manage to decrypt it by hand by running the com, popping into Soft-Ice after it was decrypted and copying the entire segment in which the com dwells to a free area of RAM. After exiting the program, I just saved the copy in RAM to disk. You can actually do all of this in Soft-Ice, using the m (copy memory) command to copy the data and the GENINT 21 command to use dosÆ file routines. IÆve included a decrypted copy of the program with this tutorial as it is much easier to trace than the original encrpyted com. IÆve also disabled the 1ch interrupt hook which is used to achieve the psychedelic color display in order to make the program even easier to trace.
Have a look at the program and try to see what it does. It first checks to make sure the 5th and 10th characters of your input are a ôvö and ôrö, respectively (thatÆs our first clue to the correct password). It then converts your input in to a ô32-bitö key (it doesnÆt really use all 32-bits). Then, it uses this key to generate some other numbers and a final key. If some of the numbers generated donÆt match certain hard-wired values, out you go. Lastly, it uses this final key to decrypt a ôCongratulations, you have the correct passwordö message. Finally, if the message is decrypted correctly (2 characters of the message are checked), you get the ôCongratulationsö message and a big smile on your face. To recap, there are three general parts of the program:
WeÆre going to crack this program in three steps. WeÆll start from part 3, then part 2 and finally part 1.
HereÆs the guts of this section of the program (your code segment will likely be different):
143A:01BF BEF101 MOV SI,01F1 ; Point ds:si to beginning of
; encoded ôcongratulationsö
; message
143A:01C2 668B1E1806 MOV EBX,[0618] ; Load EBX with
; decryption key
143A:01C7 301C XOR [SI],BL ; Decrypt one character
143A:01C9 FE061C06 INC BYTE PTR [061C] ; Increment a counter
; [061c] is initiallized
; to 0 before this code
143A:01CD 803E1C0608 CMP BYTE PTR [061C],08 ; Have we decoded
; the 8th char?
143A:01D2 7505 JNZ 01D9
143A:01D4 803C75 CMP BYTE PTR [SI],75 ; Is the 8th char
; a ôuö?
143A:01D7 7571 JNZ 024A ; If not, we have bad password
143A:01D9 803E1C0612 CMP BYTE PTR [061C],12 ; Have we decoded
; the 18?
143A:01DE 7505 JNZ 01E5
143A:01E0 803C2E CMP BYTE PTR [SI],2E ; Is the 18th char
; a ô.ö?
143A:01E3 7565 JNZ 024A ; If not, we have bad password
143A:01E5 803C24 CMP BYTE PTR [SI],24 ; Have we finished
; decrypting? The
; last char is ô$ö
143A:01E8 7458 JZ 0242 ; This jump will be taken if
; we have a good password
143A:01EA 66C1C304 ROL EBX,04 ; Rotate the decryption key
; one nibble to the left
143A:01EE 46 INC SI ; Point ds:si to next char to
; decrypt
143A:01EF EBD6 JMP 01C7 ; Go and decrypt more
Read my comments and you should understand what is going on. This code decrypts the message we would get if we typed the correct password. Since the message is encrypted, we donÆt exactly know what is is (yet :). The message begins at cs:1f1 and the decryption key is stored in cs:[618]. Notice that the decryption key is 32-bits long. What we need to do is figure out what decryption key will jump through the hurdles of this algorithm without throwing us out. We could use brute force to figure out what the correct 32-bit key in [618] is, but brute-forcing 32-bits is not only rather ineligant, but also time consuming (32-bits is too long to brute force). The code actually enables us to simplify our problem. We know that the eighth character must be 75h (ôuö) and the 18th character 2eh (ô.ö). When the program decrypts the eighth character at cs:01C7, EBX will have been rotated left (8-1)*4 = 28 times. This means that bit zero of the decryption key will now be at bit 28 of EBX (i.e. the 29th bit from the right). This means that EBX will look like the following:
b31 b30 b29 b28 b27 b26 ... b07 b06 b05 b04 b03 b02 b01 b00(bxx represents bit xx of EBX while kxx represents bit xx of the decryption key) This means that BL will contain bits 4 through 11 of our 32-bit key. At the eighth character, cs:[1f8] will be xored with BL to get 75h. [1f8] is preset to 6ch. We can now figure out what bits 4 through 11 of our key is with a little math:
6ch XOR ? = 75h ? = 75h XOR 6ch ? = 1bh
b31 b30 b29 b28 b27 b26 ... b07 b06 b05 b04 b03 b02 b01 b00 ----------------------------------------------------------- k27 k26 k25 k24 k23 k22 ... k03 k02 k01 k00 k31 k30 k29 k28
At the 18th character, cs:[202] will be xored with BL to get 2eh. [202] is preset to ech. Bits 0 to 3 and 28 to 31 can be figured out as follows:
ech XOR ? = 2eh ? = 2eh XOR ech ? = 0c2h
HereÆs what our 32-bit key looks like so far:
2????1bch
Now, we need to brute force only 16 bits. This has saved us 2^32 - 2^16 = 4,294,901,760 iterations! In actuality, even though 16 bits is small enough to brute-force, we can use a little intuition and guess the correct key. Notice that Lord ByteÆs previous cracking tests greet us with a message which begins with the word ôCongratulationsö if we get the right password. Is it just a coincidence that the 8th character of ôCongratulationsö is also a ôuö as is the case here? Well, letÆs give it a try.
We need to find 2 places where the xor key in BL represents nibbles 3, 4, 5 and 6 of the 32-bit key (we know that what nibbles 0, 1, 2 and 7 are from the above). When the forth character ([1f4] = 83h) is decoded, BL will hold nibbles 6 and 5 of the 32-bit key (because it will be rotated left 12 times). The forth character should be decoded to ôgö = 67h (weÆre guessing). Likewise, when the 6th character ([1f6] = c8h) is decoded, BL will hold nibbles 4 and 3 of the 32-bit key. The sixth character should be decoded to ôaö = 61h (again, weÆre only guessing). HereÆs the math:
83h XOR ? = 67h ? = 83h XOR 67h ? = e4h and c8h XOR ? = 61h ? = 61h XOR c8h ? = a9h
The 32-bit decryption key is: 2e4a91bch. LetÆs see whether it works. Load up the decrypted COM with ôdldr test3ö and type ôrip 1bfö. This will take us to the part which decodes the congratulations message. Press F8 to load SI with 1f1h. Press F8 again to load EBX with the key. Now, type ôREBX 2e4a91bcö so that we can test our key. Next, press [CTRL]-d. You should get the following message:
Congratulations .... Valid password ! .. Ask LordByte to give you the prize !
Well, it looks as if we have the correct 32-bit key. LetÆs move on.
The next task, is to see what we must to in order to get the correct key (i.e. 2e4a91bch) into [618]. This involves looking at the second part of the program.
143A:016A BB0000 MOV BX,0000 ; Clear BX
143A:016D 668D36E403 LEA ESI,[03E4] ; ESI := 3e4h
143A:0172 668B30 MOV ESI,[BX+SI]
143A:0175 6683FE00 CMP ESI,+00 ; Are we finished?
143A:0179 741D JZ 0198 ; If so exit loop
143A:017B 53 PUSH BX
143A:017C E8DF00 CALL 025E ; Calculate some numbers
143A:017F 5B POP BX
143A:0180 83FB50 CMP BX,+50 ; Have we processed the 51st
; double word?
143A:0183 750E JNZ 0193
143A:0185 6651 PUSH ECX ; If we just processed the
143A:0187 668B0E1006 MOV ECX,[0610] ; 51st double word, save
143A:018C 66890E1806 MOV [0618],ECX ; whatÆs in [610] to the
143A:0191 6659 POP ECX ; decryption key at [618]
143A:0193 83C304 ADD BX,+04 ; Point to next double word
143A:0196 EBD5 JMP 016D ; Do some more calculations
143A:0198 6681360C0608+ XOR DWORD PTR [060C],A628D108 ; The numbers
143A:01A1 0F85A500 JNZ 024A ; calculated
143A:01A5 6681361006FC+ XOR DWORD PTR [0610],1EF4EEFC ; above must
143A:01AE 0F859800 JNZ 024A ; yield these
143A:01B2 668136140649+ XOR DWORD PTR [0614],67C05D49 ; results or
143A:01BB 0F858B00 JNZ 024A ; weÆre
; kicked out
HereÆs the code at cs:25e which is called from cs:17c:
143A:025E 6633DB XOR EBX,EBX ; This section calculates
143A:0261 668BC3 MOV EAX,EBX ; some numbers and saves
143A:0264 6646 INC ESI ; them in [60c],[610],[614]
143A:0266 668B3E0806 MOV EDI,[0608]
143A:026B 660FAFF7 IMUL ESI,EDI
143A:026F 66678D5301 LEA EDX,[EBX+01]
143A:0274 66BF01000000 MOV EDI,00000001
143A:027A 8ACB MOV CL,BL
143A:027C 66D3E7 SHL EDI,CL
143A:027F 6623FE AND EDI,ESI
143A:0282 8ACA MOV CL,DL
143A:0284 6683FF01 CMP EDI,+01
143A:0288 661BFF SBB EDI,EDI
143A:028B 6647 INC EDI
143A:028D 66D3E7 SHL EDI,CL
143A:0290 660BC7 OR EAX,EDI
143A:0293 66BF01000000 MOV EDI,00000001
143A:0299 66D3E7 SHL EDI,CL
143A:029C 6623FE AND EDI,ESI
143A:029F 8ACB MOV CL,BL
143A:02A1 6683FF01 CMP EDI,+01
143A:02A5 661BD2 SBB EDX,EDX
143A:02A8 6683C302 ADD EBX,+02
143A:02AC 6642 INC EDX
143A:02AE 66D3E2 SHL EDX,CL
143A:02B1 660BC2 OR EAX,EDX
143A:02B4 6683FB20 CMP EBX,+20
143A:02B8 7CB5 JL 026F
143A:02BA 6631060C06 XOR [060C],EAX ; write to [060c]
143A:02BF 6601061006 ADD [0610],EAX ; write to [0610]
143A:02C4 6603060C06 ADD EAX,[060C]
143A:02C9 6629061406 SUB [0614],EAX ; wrtie to [0614]
143A:02CE C3 RET
First, letÆs figure out the inputs and outputs of this part of the code. If you examine it, youÆll notice that the inputs are as follows:
[03e4] - ? Hard-wired data [0608] The general key calculated in part one of the program The ouputs are: [060c] Initially hard wired to 0 [0610] Initially hard wired to 0 [0614] Initially hard wired to 0 [0618] Aha! This is the decryption key used in part 3!
Our goal, thus, is to determine the inputs which will cause the output to [0618] to be 2e4a91bch (i.e. the correct decryption key we previously calculated). Since the data beginning at [0608] is initially fixed, we can only play with [0608] (the general key) to acieve our goal. Although this key is technically 32-bits, the actual key calculated does not occupy all of the 32 bits (youÆll see this later). Given that the maximum number of characters in the password is 12 (try to enter more and youÆll see it wonÆt let you), a little mathematical insight tells us that the maximum value for the general password is 7ffffh (actually, 3ffff if only ascii-typeable characters are allowed). This is only 19 bits bits long. This could be small enough to brute force IF AND ONLY IF we use efficient code. Instead of writing a program to perform the brute force for us, weÆre going to modify the original (decrypted) program to do it instead. Type the following in a dos box:
dldr t3p.com [enter](t3p1 is the decrypted com included in this file)
(you should pop into soft-ice)
rip 16a [enter]
a cs:1bf [enter]
cmp dword ptr [618], 2e4a91bc [enter]
je 1ea [enter]
inc dword ptr [608] [enter]
xor eax, eax [enter]
mov dword ptr [60c], eax [enter]
mov dword ptr [610], eax [enter]
mov dword ptr [614], eax [enter]
cmp dword ptr [608], 7ffff [enter]
jne 16a [enter]
nop [enter]
nop [enter]
[enter]
bpx cs:1e9
bpx cs:1ea
Now, type u cs:198 and you should see the following:
143A:0198 6681360C0608+ XOR DWORD PTR [060C],A628D108
143A:01A1 0F85A500 JNZ 024A
143A:01A5 6681361006FC+ XOR DWORD PTR [0610],1EF4EEFC
143A:01AE 0F859800 JNZ 024A
143A:01B2 668136140649+ XOR DWORD PTR [0614],67C05D49
143A:01BB 0F858B00 JNZ 024A
143A:01BF 66813E1806BC+ CMP DWORD PTR [0618],2E4A91BC
143A:01C8 7420 JZ 01EA
143A:01CA 66FF060806 INC DWORD PTR [0608]
143A:01CF 6633C0 XOR EAX,EAX
143A:01D2 66A30C06 MOV [060C],EAX
143A:01D6 66A31006 MOV [0610],EAX
143A:01DA 66A30806 MOV [0614],EAX
143A:01DE 66813E0806FF+ CMP DWORD PTR [0608],0007FFFF
143A:01E7 7581 JNZ 016A
143A:01E9 90 NOP
143A:01EA 90 NOP
Now, press [ctrl]-d and let the program run. It took about 3 minutes on my system (75 MHz Pentium--yeah, I know I have an outdated computer) until Soft-Ice pops up. If Soft-Ice pops in at cs:1e9, that means it didnÆt find the correct general key; if this is the case, it means that either we have the wrong decryption key or the program is not crackable without a patch (highly unlikely). However, if it pops in at cs:1ea, that means that the correct general key was found. Fortunately, Soft-Ice does pop in at cs:1ea. Type ôd cs:608ö to see what the correct key is; donÆt forget that the Pentium is a big-endian CPU, so you have to reverse the order of each byte to get the key. Aha, the correct general key is 0003d3c5h. LetÆs verify this. Go to dos and run the program by typing ôdldr t3pö. Now type ôrip 16aö to get us to the second part of the program. Type ôe cs:608ö followed by our key (reversed) ôc5d30300ö. This sets the general key to the one we just found. Then, just press [ctrl]-d and let the program run. You should get the ôCongratulationsö message, which confirms that we have the correct general key. Onto the final part of the crack...
The first part of the program calculates the ô32-bitö general key from the inputted password. HereÆs a dissassembly:
143A:0113 BABE03 MOV DX,03BE
143A:0116 B8000A MOV AX,0A00
143A:0119 CD21 INT 21 ; input password
143A:011B BEC003 MOV SI,03C0 ; point ds:si to first char
143A:011E 807C0476 CMP BYTE PTR [SI+04],76 ; is 5th char ôvö?
143A:0122 0F852401 JNZ 024A
143A:0126 807C0972 CMP BYTE PTR [SI+09],72 ; is 10th char ôrö?
143A:012A 0F851C01 JNZ 024A
143A:012E 6633FF XOR EDI,EDI ; edi := 0
143A:0131 6633C0 XOR EAX,EAX
143A:0134 BEC003 MOV SI,03C0 ; point ds:si to first char
143A:0137 8A04 MOV AL,[SI]
143A:0139 3C0D CMP AL,0D ; exit loop if char is return
143A:013B 7428 JZ 0165
143A:013D 3C20 CMP AL,20 ; is char a space? If so, do
; nothing & process next char
143A:013F 7421 JZ 0162
143A:0141 6625FF000000 AND EAX,000000FF
143A:0147 3C61 CMP AL,61 ; is char an 'a'?
143A:0149 7C06 JL 0151
143A:014B 3C7A CMP AL,7A ; is char a 'z'?
143A:014D 7F02 JG 0151
143A:014F 2C20 SUB AL,20 ; if ('a' <= character <= 'z')
; then char := char - 32
; (i.e. convert to upper case)
143A:0151 6603FF ADD EDI,EDI
143A:0154 6633C7 XOR EAX,EDI
143A:0157 668BF8 MOV EDI,EAX ; EDI := (EDI+EDI) XOR EAX
143A:015A 6685FF TEST EDI,EDI
143A:015D 7D03 JNL 0162 ; jump if sign and overflow
; flags are equal
143A:015F 66F7DF NEG EDI ; If H.O. bit of EDI is set,
; then EDI := NEG EDI
143A:0162 46 INC SI ; point to next char
143A:0163 EBD2 JMP 0137
First, the code kicks the user out if the 5th character is not a ôvö and the 10th character is not an ôrö. Next comes the gernal key generation algorithm. Two obervations: (1) all characters are converted to upper case, and (2) spaces are not processed. Consider the code beginning at cs:15a (TEST EDI, EDI; JNL 0162). ôWhat does this do?ö, you may ask. Well, the TEST instruction clears the carry and overflow flags and sets the zero, sign and parity flags according to a logical AND of the two operands. The JNL instruction jumps only if the sign and overflow flags are the same (i.e. either both clear or both set). Since the TEST instruction always clears the overflow flag, the jump will only be taken if the sign flag is cleared, meaning that EDI is a positive twoÆs complement number (i.e. its H.O. bit is 0). The NEG EDI function will hence only be executed if EDIÆs H.O. bit is 1, which, with a little math, youÆll find is impossible when the maximum number of characters to enter is 12 (recall that the maximum value of the general key is 7ffffh, a number whose H.O. bit is not set). Therefore, you could technically NOP the TEST EDX, EDX, JNL 162, and NEG EDI and the program would function EXACLTY as it would without any modifications. The general key generation algorithm can be summarized by (and simplified to) the
GeneralKey := 0;
For i := 1 to length(UserPassword) do
begin
if (UserPassword[i] >= 'a') and (UserPassword[i] <= 'z') then
UserPassword[i] := char(ord(UserPassword[i])-32);
if UserPassword[i] <> ' ' then
GeneralKey := (2*GeneralKey) XOR ord(UserPassword[i]);
end;
Clearly, the input of this section of the program is the password we enter and the output is the general key. Our goal is to find what input (password) yields us the general key found above (0003d3c5h). This is not an easy task. Whenever a 32-bit number is calculated from a 12-character string, there is the potential that several strings will yield the same 32-bit number (this is called a one-to-many relationship). We know that the password is at least 10 characters long (the 10th character must be an 'r') and at most 12. Well, brute forcing 10-12 characters is out of the question (unless you plan on living past 100 years of age). Unfortunately, we have to resort to using our brain :)
Okay, we have to get a feel for what is going on in this algorithm. For each new character, EDI is added to itself and then XORed with a character. Well, adding EDI to itself is the same as multiplying EDI by 2. 2 is a special number: it is the radix of the binary number system. Whever we multiply a number by its radix, itÆs the same as shifting the number left one digit. Therefore, the ADD EDI, EDI instruction is idential to a SHL EDI, 1 instruction.
HereÆs what we have so far. We start with a key of 0. Then, for each character, we first shift the key left by one bit, then we XOR it with the character. HereÆs a visual diagram which shows whatÆs going on:
18 17 16 15 14 13 12 11 10 09 08 07 06 05 04 03 02 01 00
--------------------------------------------------------
Character 1: b7 b6 b5 b4 b3 b2 b1 b0
Character 2: b7 b6 b5 b4 b3 b2 b1 b0
Character 3: b7 b6 b5 b4 b3 b2 b1 b0
Character 4: b7 b6 b5 b4 b3 b2 b1 b0
Character 5: b7 b6 b5 b4 b3 b2 b1 b0
Character 6: b7 b6 b5 b4 b3 b2 b1 b0
Character 7: b7 b6 b5 b4 b3 b2 b1 b0
Character 8: b7 b6 b5 b4 b3 b2 b1 b0
Character 9: b7 b6 b5 b4 b3 b2 b1 b0
Character 10: b7 b6 b5 b4 b3 b2 b1 b0
Character 11: b7 b6 b5 b4 b3 b2 b1 b0
Character 12: b7 b6 b5 b4 b3 b2 b1 b0
---------------------------------------------------------
General Key: b1 b1 b1 b1 b1 b1 b1 b1 b1 b9 b8 b7 b6 b5 b4 b3 b2 b1 b0
8 7 6 5 4 3 2 1 0
From this diagram, we can see the bit 18 of the general key is equal to bit 7 of the first character. Similarly, bit 17 of the general key is equal to bit 7 of character 2 XORed with bit 6 of character 1. Bit 16 of the general key is equal to bit 5 of character 1 XORed with bit 6 of character 2 XORed with bit 7 of character 3. And so forth. Now, letÆs pool together all the information we have regarding the general key and the characters of the password:
18 17 16 15 14 13 12 11 10 09 08 07 06 05 04 03 02 01 00
--------------------------------------------------------
Character 1: 0 1 b5 b4 b3 b2 b1 b0
Character 2: 0 b6 b5 b4 b3 b2 b1 b0
Character 3: 0 b6 b5 b4 b3 b2 b1 b0
Character 4: 0 b6 b5 b4 b3 b2 b1 b0
Character 5: 0 1 0 1 0 1 1 0
Character 6: 0 b6 b5 b4 b3 b2 b1 b0
Character 7: 0 b6 b5 b4 b3 b2 b1 b0
Character 8: 0 b6 b5 b4 b3 b2 b1 b0
Character 9: 0 b6 b5 b4 b3 b2 b1 b0
Character 10: 0 1 0 1 0 0 1 0
Character 11: 0 b6 b5 b4 b3 b2 b1 b0
Character 12: 0 b6 b5 b4 b3 b2 b1 1
---------------------------------------------------------
General Key: 0 1 1 1 1 0 1 0 0 1 1 1 1 0 0 0 1 0 1
---------------------------------------------------------
18 17 16 15 14 13 12 11 10 09 08 07 06 05 04 03 02 01 00
We can easily deduce that bit 6 of character 1 is one because it has to satisfy the equation b6 XOR 0 = 1. Similarly, we can deduce that bit 0 of character 12 is 1. Now, we have a set of 19 sumultaneous equations. Unfortunately, they canÆt be (uniquely) solved because we have more than 19 unknowns (this is precisely why we have a one-to-many relationship). However, we have successfuly built a template which we can use to find valid paswords. HereÆs how:
Consider column 16 (i.e. the one corresponding to bit 16 of the general key). We know that when all bits in that column are XORed with each other, we must get a 1. That means that there must be an odd number of ones in those bits (if you don't understand this, play around with XORing a few numbers and youÆll see). In this case, it means that either bit 5 of character 1 is a one or bit 6 of character 2 is a 1 (recall that bit 7 of character 3 must be 0 if weÆre interested only in ascii-typeable passwords). LetÆs arbitrarily choose to turn on bit 6 of character 2. Similarly, we can go through all the other columns and do the same thing (i.e. turing on an odd number of bits where the general key bit is 1 and turning on an even number of bits where the general key bit is 0). Remember that there are some other restrictions you must meet, namely:
If you follow these rules, youÆll generate a valid password. It sure beats brute-forcing 12 characters (which is, for all practical purposes, impossible). HereÆs one I generated:
18 17 16 15 14 13 12 11 10 09 08 07 06 05 04 03 02 01 00
--------------------------------------------------------
Character 1: 0 1 0 0 1 0 1 0
Character 2: 0 1 0 0 0 0 0 1
Character 3: 0 1 0 0 0 0 1 0
Character 4: 0 0 1 0 1 0 0 0
Character 5: 0 1 0 1 0 1 1 0
Character 6: 0 0 1 1 0 0 0 1
Character 7: 0 1 0 1 0 1 0 0
Character 8: 0 1 0 1 1 0 0 0
Character 9: 0 1 0 0 1 1 0 0
Character 10: 0 1 0 1 0 0 1 0
Character 11: 0 1 0 0 0 0 1 0
Character 12: 0 0 1 0 1 0 0 1
---------------------------------------------------------
General Key: 0 1 1 1 1 0 1 0 0 1 1 1 1 0 0 0 1 0 1
---------------------------------------------------------
18 17 16 15 14 13 12 11 10 09 08 07 06 05 04 03 02 01 00
Now, converting all characters to ASCII and putting them in lowercase (actually, only characters 5 and 10 need to be in lowercase) gives us the password: ôjab(v1txLrb)ö (I capitalized the L because itÆs hard to distinguish 1 from l in courier font :) Try it out. It works :)
We now have all the information needed to write a keygenerator. IÆll leave this up to you as IÆm too lazy :)
