A word of caution before we begin: this method is likely not the most efficient as it's the first program I ever cracked. The good thing is that it works though.
Alright, pick up a copy of RBSTRIAL.COM from Lord Caligo's site and let's start. Run the program a couple of time to see the sequence of actions. Since the file is very small (308 bytes), you might as well print the entire disassembled code and have a look. Here's a disassembly:
241E:0100 6B4F5547 IMUL CX,[BX+55],+47 241E:0104 45 INC BP 241E:0105 52 PUSH DX 241E:0106 21D2 AND DX,DX 241E:0108 4D DEC BP 241E:0109 5A POP DX 241E:010A E98A00 JMP 0197 ... 241E:0190 F6D8 NEG AL 241E:0192 FEC3 INC BL 241E:0194 EB3F JMP 01D5 241E:0196 90 NOP 241E:0197 B409 MOV AH,09 241E:0199 BA0D01 MOV DX,010D 241E:019C CD21 INT 21 241E:019E BA8001 MOV DX,0180 241E:01A1 B40A MOV AH,0A 241E:01A3 CD21 INT 21 241E:01A5 42 INC DX 241E:01A6 8BF2 MOV SI,DX 241E:01A8 AC LODSB 241E:01A9 1C0A SBB AL,0A 241E:01AB 754D JNZ 01FA 241E:01AD 90 NOP 241E:01AE 90 NOP 241E:01AF 2BC0 SUB AX,AX 241E:01B1 33D2 XOR DX,DX 241E:01B3 46 INC SI 241E:01B4 BFE101 MOV DI,01E1 241E:01B7 BBA59D MOV BX,9DA5 241E:01BA B90B00 MOV CX,000B 241E:01BD 51 PUSH CX 241E:01BE F8 CLC 241E:01BF AC LODSB 241E:01C0 750F JNZ 01D1 241E:01C2 90 NOP ... 241E:01D1 02C3 ADD AL,BL 241E:01D3 72BB JB 0190 241E:01D5 0FAFCB IMUL CX,BX 241E:01D8 02CD ADD CL,CH 241E:01DA 2AC1 SUB AL,CL 241E:01DC AA STOSB 241E:01DD 750D JNZ 01EC ... 241E:01EC 86DF XCHG BL,BH 241E:01EE 59 POP CX 241E:01EF E2CC LOOP 01BD 241E:01F1 FD STD 241E:01F2 BECF01 MOV SI,01CF 241E:01F5 B90D00 MOV CX,000D 241E:01F8 F3 REPZ 241E:01F9 A6 CMPSB 241E:01FA B409 MOV AH,09 241E:01FC BA0802 MOV DX,0208 241E:01FF 7425 JZ 0226 241E:0201 90 NOP 241E:0202 90 NOP 241E:0203 CD21 INT 21 241E:0205 EB18 JMP 021F ... 241E:021F B8004C MOV AX,4C00 241E:0222 CD21 INT 21 ... 241E:0226 BA6B01 MOV DX,016B 241E:0229 EBD8 JMP 0203
(The code segment will likely be different on your machine.) Now, examine the code and trace through it with a debugger. Consider the following section of the code:
241E:0197 B409 MOV AH,09 241E:0199 BA0D01 MOV DX,010D 241E:019C CD21 INT 21 241E:019E BA8001 MOV DX,0180 241E:01A1 B40A MOV AH,0A 241E:01A3 CD21 INT 21
If we look at the contends of address 010Dh, we see it contains the introductory text. The first INT 21 call prints this text to the screen. The second INT 21 call gets the user input and saves it at 0180h. If you dump the contents of memory starting at 0180h, you will see your input. Now look at the next few lines:
241E:01A5 42 INC DX 241E:01A6 8BF2 MOV SI,DX 241E:01A8 AC LODSB 241E:01A9 1C0A SBB AL,0A 241E:01AB 754D JNZ 01FA
INC DX will set DX equal to 0180h+1h = 0181h. The contents of 0181h will be the length of the user's input (when interrupt 21 saves the user input, it precedes the data with the length of the user input). Thus, the next three lines check whether the user entered 0ah or 10 characters for the password. If the user did not, the computer will jump to 01fah which, upon examination, prints out "Incorrect Password" and terminates the program. We just learned our first clue: the correct password is 10 characters long.
241E:01AD 90 NOP 241E:01AE 90 NOP 241E:01AF 2BC0 SUB AX,AX 241E:01B1 33D2 XOR DX,DX 241E:01B3 46 INC SI 241E:01B4 BFE101 MOV DI,01E1 241E:01B7 BBA59D MOV BX,9DA5 241E:01BA B90B00 MOV CX,000B 241E:01BD 51 PUSH CX 241E:01BE F8 CLC 241E:01BF AC LODSB 241E:01C0 750F JNZ 01D1
After clearing the AX and DX registers, SI is incremented. SI should
now be pointing to the SECOND character of our input (remember this fact
for later). This is because the preceding LODSB command already
increased SI from 181h to 182h. SI is now 183h, which is where our
second input charater is. The next few lines initialize some
registers.
Note that DI is initialized to 01E1h. The LODSB will load AL with our
second input character. If that character is not equal to zero (which
it shouldn't unless you used escape codes in your input), we will jump
to 01D1h. Now comes the interesting part. Examine the next piece of
code:
241E:01D1 02C3 ADD AL,BL 241E:01D3 72BB JB 0190 241E:01D5 0FAFCB IMUL CX,BX 241E:01D8 02CD ADD CL,CH 241E:01DA 2AC1 SUB AL,CL 241E:01DC AA STOSB 241E:01DD 750D JNZ 01EC ... 241E:01EC 86DF XCHG BL,BH 241E:01EE 59 POP CX 241E:01EF E2CC LOOP 01BD 241E:01F1 FD STD 241E:01F2 BECF01 MOV SI,01CF 241E:01F5 B90D00 MOV CX,000D 241E:01F8 F3 REPZ 241E:01F9 A6 CMPSBHere's the code for the JB instruction at 01D3:
241E:0190 F6D8 NEG AL 241E:0192 FEC3 INC BL 241E:0194 EB3F JMP 01D5
Hmmm. This looks like an encryption procedure. It's modifying each of our input characters according to some algorithm and storing it beginning at 01E1h (recall that DI was initialized to 01E1h). After the encryption (i.e. starting at address cs:01F1h), you will see that the program compares our encrypted password to the something (REPZ CMPSB). Here is where the program checks to see whether we entered the correct password. Now, let's figure out where the correct password is stored. Since the direction flag is set (STD instruction at cs:01F1h), we know that the REPZ CMPSB will compare bytes BACKWARDS from memory. Thus, we know that the last character of the correct password is at ds:01CFh, which is what the SI register is initialized to at cs:01F2h. The CX register is initialized to Dh right before the comparison. This means that the REPZ CMPSB instructions will compare a maximum of Dh characters. Therefore, the beginning of the correct password is at ds:01CFh - Dh + 1h = 01C3. Well, let's see what's there by dumping the contents of memory beginning at ds:01C3:
There's only one problem. That data isn't exactly the correct password. It's the ENCRYPTED correct password. Remember that the program first encrypts our input and then compares our ENCRYPTED input with the above data. Now, you might think, "that's simple, let's just decrypt the data". You're on the right track but, unfortunately, decrypting the password is much more complicated that you probably think.
By now, you must be thinking, if we just change CS:01FF from JZ 0226 to JMP 0226, the program will say "Correct Password" for anything we type in. Sure, we could do that, but kOUGER!'s challenge was for us to to find out what the real password is.
To figure out what the password is, we must COMPLETELY understand what
the encryption algorithm is. So, sit back and examine the code
carefully. Examine it until you FULLY understand what's going on.
First, one character of our input is loaded into AL. Next, BL is added
to it. Then, if the addition caused an unsigned overflow (i.e. if AL +
BL > 255 causing the carry flag to be set), AL is negated and BL is
incremented by one. Next, the sum of the high and low bytes of CX*BX is
subtracted from AL to complete the encryption. After storing our
encrypted character, the high and low bytes of BX are exchanged and the
next character goes through the same process. Let's formalize this
algorithm mathematically. First, define a function f(x) which returns
the sum of the high and low bytes of its argument, x.
For example:
f(2FB4h) = 2Fh + B4h = E3h.
Here's how the encryption alorithm looks:
If AL + BL <= 255: If AL + BL > 255: output = input + BL - f(BX*CX) output = -(input+BL) - f[(BX+1)*CX]
Let's re-arrange the equations to solve for the input (i.e. this is the decryption algorithm):
If AL + BL <= 255: If AL + BL > 255: input = output - BL + f(BX*CX) input = -(output - f[(BX+1)*CX])-BL
No problem, you say. Just substitute the values for the correct encrypted password for "output" and solve for "input". While this seems simple, it has two problems. Here's the first problem: given BX and CX, there are up to two possible inputs which would yield the same output. One for when AL + BL <= 255 and the jump at CS:01D3h is not taken, and one for when AL + BL > 255 and jump at CS:01D3h is taken. For example, if we want to find the correct input for 0Ah (i.e. the second character of the correct encrypted password), we get either 42h or 39h which corresponds to "B" and "9" respectively. We could choose either one and proceed to decode the next character. The problem with this is that if we chose the wrong one, we may find that the later characters we decode fall outside the typeable range of ASCII characters. If we are VERY lucky and chose the correct path through the decryption, we will get the correct password. However, for 10 characters, there are 2^10 = 1024 different paths. That makes this option a little unattractive. The second problem however renders this option even less attractive.
The astute readers will notice that the correct password is 10 characters in length whereas the encryption and compare routines encrypt and compare 12 characters. Thus, the encryption procedure also encrypts the two bytes following our 10 character input beginning at address DS:0182h. Upon examination, we see that the program fixes these two bytes to 0Dh and 00. When these two bytes are encrypted, they will be compared to 1Fh and 61h (check the dump of the correct encrypted password to see where these numbers come from). To fully understand what this means, you have to realize that how each character is encrypted depends on how the previous characters were encrypted. This is because the BX register is changed according to whether the jump at CS:01D3h is taken. Thus, the correct password is one which follows a path which causes BX to equal a value which will correctly encode the 11th and 12th bytes to 1Fh and 61h, respectively.
Now, not only do we have to worry about taking a path which yields an ASCII typeable password, but we must also make sure that it sets BX to a value which correctly encodes the next two bytes. Solution: we will write a program which will go through all the possible paths and see whether one password gives us the same encryption as the correct encrypted password. Before going any further, recall the encryption procedure begins with the SECOND input character, not the first. Thus, the first character of our input is never encrypted at all. Although the password compare procedure actually compares the address where our first input character would have been stored had it been encrypted, we note that that address is fixed at 90h. Fortunately, 90h is exactly what it is compared to in the password compare procedure. This gives us the second clue to the password: it doesn't matter what you type for the first character.
Alright, here's the pascal program which goes through all the possible 2^9 = 512 (remember, the first character is irrelevant) paths. It will print out only those passwords which meet both of the following criteria: (1) All characters fall within the typeable ASCII range (2) Characters 11 and 12 (i.e. those "hard-wired" to 0Dh and 00) are correctly encoded to 1Fh and 61h, respectively. Note also that this program prints only characters 2 to 10 of the correct password(s) as the first character is irrelevant.
Program RbsTrialDecode (Input,Output);
Function LowByte(Value : word) : word;
Begin
LowByte := Value - (Value div 256)*256;
End;
Function HighByte(Value : word) : word;
Begin
HighByte := (Value - LowByte(Value)) div 256;
End;
Function Encode(Var InBX : word;
InCX : word;
CorrectInput : byte) : byte;
Var
BX,
CX : word;
CorrectOutput,
BH,
BL,
CH,
CL,
TempByte : byte;
Begin
BX := InBX;
CX := InCX;
BH := HighByte(InBX);
BL := LowByte(InBX);
CorrectOutPut := CorrectInput + BL;
If (CorrectOutput < CorrectInput) Then
Begin
CorrectOutput := (CorrectOutput XOR 255) + 1;
BL := BL + 1;
End;
BX := 256*BH + BL;
CX := CX*BX;
CL := LowByte(CX);
CH := HighByte(CX);
CorrectOutput := CorrectOutput - CH - CL;
BH := HighByte(BX);
BL := LowByte(BX);
BX := 256*BL + BH;
InBX := BX;
Encode := CorrectOutput;
End;
Function Decode(Var InBX : word;
InCX : word;
CorrectOutput : byte;
NoJump : boolean) : Byte;
Var
BX,
CX : word;
CorrectInput : byte;
BH,
BL,
CH,
CL,
TempByte : byte;
Begin
If NoJump Then
Begin
CX := InCX;
BX := InBX;
BL := LowByte(InBX);
BH := HighByte(InBX);
CX := CX * BX;
CL := LowByte(CX);
CH := HighByte(CX);
TempByte := CL + CH;
CorrectInput := CorrectOutput + TempByte - BL;
BX := BH + 256*BL;
TempByte := CorrectInput + BL;
If TempByte >= CorrectInput Then
Begin
Decode := CorrectInput;
InBX := BX;
End
Else
Decode := 0;
End
Else
Begin
CX := InCX;
BX := InBX;
BL := LowByte(BX);
BH := HighByte(BX);
BL := BL + 1;
BX := BL + BH*256;
CX := BX * CX;
CL := LowByte(CX);
CH := HighByte(CX);
TempByte := CL+CH;
CorrectInput := ((CorrectOutput + TempByte) XOR 255) + 1 -
LowByte(InBX);
BX := BH + 256*BL;
TempByte := CorrectInput + LowByte(InBX);
If TempByte < CorrectInput Then
Begin
Decode := CorrectInput;
InBX := BX;
End
Else
Decode := 0;
End;
End;
Const
EncodedPassword : array[2..11] of byte =
(31,245,207,138,86,33,217,123,86,10);
Var
InBX,
InCX,
Counter1,
Counter2,
Mask,
Temp : word;
CorrectInput,
a,b : byte;
GoodPassword,
NoJump : boolean;
PasswordString : String;
Begin
Writeln;
For Counter1 := 0 to 511 do
Begin
Mask := 1;
InBX := 40357;
GoodPassword := True;
PasswordString := '';
For Counter2 := 1 to 9 do
Begin
Temp := Counter1 and Mask;
NoJump := Temp <> 0;
InCX := 12 - Counter2;
CorrectInput := Decode(InBX,InCX,EncodedPassword[InCX],NoJump);
If (CorrectInput <= 126) and (CorrectInput >= 32) Then
PasswordString := PasswordString + Chr(CorrectInput)
Else
Begin
PasswordString := PasswordString + Chr(CorrectInput);
GoodPassword := False;
End;
Mask := Mask * 2;
End {for};
a := Encode(InBX,2,13);
b := Encode(InBX,1,0);
If GoodPassword and (a = 31) and (b = 97) Then
Writeln(PasswordString);
End {for};
End.
Remember that these are the 2nd to 10th characters and we can enter anything for the first character. It is likely that kOUGER!'s intended password was "RBS-Party!". Running the program and typing these passwords, we see that we have correctly "cracked" the program. Looking back now that I know the password, I think that it may be possible for someone to figure out the password by hand (i.e. without writing a program as I did) if he could see the pattern leading to the word "Party!".
