by
CASIMIR
Part B
Software by MaeDae Enterprises
(You might need to use FTP Search to find the software.)
This file presents cracking procedure for both proprietary algorithms found in this software:
Introduction
Strategy
PART A - REVERSING OF EIW
1. Warm up
2. What's going on with my input?
2.1. Task 1: Computation of Block_size
2.2. Task 2: Permutations in encrypted file
3. Building of Sum_vector
4. Making of Xor_vector
5. Making of Cmp_vector
6. The Ultimate CMP
PART B - ANALYSIS AND BREAKING OF EIW
1. Questions/answers
2. Mimic of EIW
3. The 3 solving methods
3.1. High speed solving method
3.2. Medium speed solving method
3.3. Low speed solving method
PART C - SOURCE FOR CRACKER
Q: OK, so what if we just try any possible input until we find the good one?
A: Well... We don't know password'length (i.e. how many characters it contains). With only 5 characters, we would have 2565=1,099,511,627,776 combinations to try, which is a lot even for a fast PC. So just forget it.
Q: Maybe we can just patch EIW so it would let us in even if input is wrong.
A: Right, this method is also used to "register" stolen software. Go on, try it! To disable final CMP, we can modify following instructions:
CS:40EBA7 change cmp dl,bl to cmp dl,dl
CS:40EBB7 change cmp dl,bl to cmp dl,dl
Now EIW let us decrypt file, BUT we got a "File Corrupt!" message... The problem is that EIW uses the wrong input to decrypt file, that's why we obtain garbage! (With a very weak crypto-soft, such as Turbo Encrypto, this method would have worked fine. That's because TE uses *original* pwd to decrypt file.)
Q: We could watch carefully encrypted text, and search for patterns,redundancy...
A: It may work, i don't know, i don't even know exactly how 3 Ways and Multilayer algos work. Have a look and tell me if something shows up!
Conclusion: we must find out what original pwd was to decrypt. So we'll try to build an input that pass final CMP, using same routines as EIW.
Our strategy will depend on password'length (small,medium, or large).
Let's sum up actions performed by EIW (chronological order):
We're going to mimic EIW.
We don't know pwd'length, so we try out every possible length (from 5 to 40 (Int.) or 123 (U.S.) characters). Then we must build permuted text. As we don't know password (!), we can't compute Block_size... Nevermind, there are only 16 possible values for Block_size (see PART A, Chapter 2), we're going to try each of them. Once permuted text is built, we choose a solving method in function of pwd'length.
Pseudo-code:
For each pwd'length
{
For each Block_size
{
Build permuted text;
Switch(pwd'length)
{
case( 5=pwd'length=20 chars) : use high speed solving method; break;
case(21=pwd'length=29 chars) : use medium speed solving method; break;
case(30=pwd'length=40 chars) : use low speed solving method; break;
}
}
}
Now we'll study each solving method. We'll use International version of EIW, but it works the same with U.S. Version.
Every method takes advantage of the "static" data structure used by EIW to store original file name and password (see PART A, Chapter 5). If the pwd is good, we're sure that Cmp_vector must look like this:
Cmp_vector: |FILENAME.TXT|0|PASSWORD00000000000000000000000000000000|0|
|<------ Tail (40+1=41 characters) ------->|
The more 0s we have in Tail (i.e. the smaller pwd is), the easier pwd can be found.
We suppose our permuted text is:
11111111112222222222333333333344444444445555
012345678901234567890123456789012345678901234567890123
Permuted_txt: |ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz01|
|<-------------- 12+1+40+1=54 characters ------------->|
3.1. High speed solving method
We search a small pwd (length<=20), for instance length=10. So we must find:
Password: 0123456789 0123456789 0123456789 0123456789 0123456789 0123
Cmp_vector'struct: FILENAME.T XT0??????? ???0000000 0000000000 0000000000 0000
0123456789 1111111111 2222222222 3333333333 4444444444 5555
0123456789 0123456789 0123456789 0123456789 0123
If pwd is good, we should have:
0=Xor_vector[23]^Pwd[3] <=> Xor_vector[23]=Pwd[3] (remember: x^y=0 <=> x=y)
0=Xor_vector[24]^Pwd[4] <=> Xor_vector[24]=Pwd[4]
0=Xor_vector[25]^Pwd[5] <=> Xor_vector[25]=Pwd[5]
0=Xor_vector[26]^Pwd[6] <=> Xor_vector[26]=Pwd[6]
0=Xor_vector[27]^Pwd[7] <=> Xor_vector[27]=Pwd[7]
0=Xor_vector[28]^Pwd[8] <=> Xor_vector[28]=Pwd[8]
0=Xor_vector[29]^Pwd[9] <=> Xor_vector[29]=Pwd[9]
0=Xor_vector[30]^Pwd[0] <=> Xor_vector[30]=Pwd[0]
0=Xor_vector[31]^Pwd[1] <=> Xor_vector[31]=Pwd[1]
0=Xor_vector[32]^Pwd[2] <=> Xor_vector[32]=Pwd[2]
Step_2 We know that: Xor_vector[i]=Sum_vector[i]^Permuted_txt[i], so we have:
Pwd[3] = Sum_vector[23]^Permuted_txt[23] = Sum_vector[23]^X
Pwd[4] = Sum_vector[24]^Permuted_txt[24] = Sum_vector[24]^Y
Pwd[5] = Sum_vector[25]^Permuted_txt[25] = Sum_vector[25]^Z
Pwd[6] = Sum_vector[26]^Permuted_txt[26] = Sum_vector[26]^a
Pwd[7] = Sum_vector[27]^Permuted_txt[27] = Sum_vector[27]^b
Pwd[8] = Sum_vector[28]^Permuted_txt[28] = Sum_vector[28]^c
Pwd[9] = Sum_vector[29]^Permuted_txt[29] = Sum_vector[29]^d
Pwd[0] = Sum_vector[30]^Permuted_txt[30] = Sum_vector[30]^e
Pwd[1] = Sum_vector[31]^Permuted_txt[31] = Sum_vector[31]^f
Pwd[2] = Sum_vector[32]^Permuted_txt[32] = Sum_vector[32]^g
Step_3 We know that:
Instead of masking result of xorization, we can mask sum:
Sum_vector[i]={(Pwd'sum+Pwd[0]+...+Pwd[i mod Pwd'len])&FF}^Pwd[i mod Pwd'len]
We formulate:
Init_12_pwd={Pwd'sum+Pwd[0]+...+Pwd[22mod10]}&FF={Pwd'sum+Pwd[0]+...+Pwd[2]}&FF
So: Sum_vector[23]={(Init_12_pwd+Pwd[3])&FF}^Pwd[3]
Problem: we still don't know password (!), so we can't compute Init_12_pwd...
Nevermind, because of masking there are only 256 possible values for Init_12_pwd (0x00,...,0xFF), we'll try them out.
Step_4 We saw in Step_2 that:
Pwd[3]=Sum_vector[23]^Permuted_txt[23], so:
Pwd[3]={(Init_12_pwd+Pwd[3])&FF}^Pwd[3]^Permuted_txt[23]; which becomes:
(Init_12_pwd+Pwd[3])&FF=Permuted_txt[23]
2 cases:
Step_5 We repeat Step_4 with Pwd[4],Pwd[5],...,Pwd[2]:
(Init_12_pwd+Pwd[3]+Pwd[4])&FF=Permuted_txt[24] --> Pwd[4] found
(Init_12_pwd+Pwd[3]+Pwd[4]+Pwd[5])&FF=Permuted_txt[25] --> Pwd[5] found
.
.
.
(Init_12_pwd+Pwd[3]+Pwd[4]+...+Pwd[2])&FF=Permuted_txt[32] --> Pwd[2] found
The whole password is recovered... But is it the GOOD password?Step_6 Checks
Remember we made assumptions on:
-password'lenght -Block'size -Init_12_pwdSo pwd found must be checked. There are various tests performed:
-we compute Block'size using pwd found, then we check if:
Block'size computed = Block'size estimated?
-we compute Init_12_pwd using pwd found, then we check if:
Init_12_pwd computed = Init_12_pwd estimated?
-if pwd passed tests above, then we perform the same test as EIW: we build Cmp_vector using
pwd found and we check if:
Cmp_vector[13]=Pwd[0]?
Cmp_vector[14]=Pwd[1]?
Cmp_vector[15]=Pwd[2]?
Cmp_vector[16]=Pwd[3]?
Cmp_vector[17]=Pwd[4]?
Cmp_vector[18]=Pwd[5]?
Cmp_vector[19]=Pwd[6]?
Cmp_vector[20]=Pwd[7]?
Cmp_vector[21]=Pwd[8]?
Cmp_vector[22]=Pwd[9]?
-to be sure, we can also check that:
--Cmp_vector[12]=0?
and
--Cmp_vector[23]=Cmp_vector[24]=...=Cmp_vector[52]=Cmp_vector[53]=0?
If a password pass every test, well, this IS the pwd we're looking for! So stop searching and have a beer!Here follows pseudo-code for high speed solving method (pwd'length=10):
For each Init_12_pwd
{
Compute Pwd[3],Pwd[4],Pwd[5],...,Pwd[2]
Check whole password
{
if OK: password found! Display it and say bye-bye!
else : go on searching...
}
}
Conclusion
We can't use high speed method with big password'lengths, because there are not enough 0s left in Tail to find whole password. Anyway, if Pwd'lenght is not too large, we can still take advantage of 0s in Tail. We search a medium password (Pwd'length<=29 characters), let's say length=28. So we look for: Pwd[0],Pwd[1],...,Pwd[27].
111111111122222222 1111111111222222
Password: 0123456789012345678901234567 01234567890123456789012345
Cmp_vector'struct: FILENAME.TXT0??????????????? ?????????????0000000000000
0123456789111111111122222222 22333333333344444444445555
012345678901234567 89012345678901234567890123
|< only 13 >|
0s in Tail
Step_1
Init_12_pwd={Pwd'sum+Pwd[0]+...+Pwd[37mod25]}&FF={Pwd'sum+Pwd[0]+...+Pwd[12]}&FF
There are only 256 possible values for Init_12_pwd (0x00,...,0xFF), we'll try them out.
(Init_12_pwd+Pwd[13])&FF=Permuted_txt[38] --> Pwd[13] found
(Init_12_pwd+Pwd[13]+Pwd[14])&FF=Permuted_txt[39] --> Pwd[14] found
.
.
.
(Init_12_pwd+Pwd[13]+Pwd[14]+...+Pwd[24])&FF=Permuted_txt[49] --> Pwd[24] found
Once we have found 12 characters from password we can enter Step_2 (Pwd[13] to Pwd[24]: 12 chars).
Step_2
Now we introduce a new value, Init_12, which is similar to Init_12_pwd:
(Init_12+Pwd[12])&FF=Permuted_txt[12]=0
2 cases:
Once we have found Pwd[12],Pwd[13],...,Pwd[24] we can enter Step_3.
Step 3 If password is correct, we should have: Cmp_vector[13]=Pwd[0]
We know that: Cmp_vector[i]=Xor_vector[i]^Pwd[i modulo Pwd'length], so:
Pwd[0]=Xor_vector[13]^Pwd[13]
We know that: Xor_vector[i]=Sum_vector[i]^Permuted_txt[i], so we have:
Pwd[0]=Sum_vector[13]^Permuted_txt[13]^Pwd[13]
and: Sum_vector[13]={(Init_12+Pwd[12]+Pwd[13])&FF}^Pwd[13]
We obtain finally:Step_4 Ok, we have found Pwd[0],...,Pwd[24]. Now we will search Pwd[25], Pwd[26] and Pwd[27] to finish recovering pwd.
Don't forget we made assumptions on:
-password'lenght -Block'size -Init_12_pwd -Init_12As with high speed method, we perform various checks:
Block'size computed = Block'size estimated?
Init_12_pwd computed = Init_12_pwd estimated?
Init_12 computed = Init_12 estimated?
Cmp_vector[13] = Pwd[0]?
.
.
.
Cmp_vector[40] = Pwd[27]?
To be sure, we can also check that:
--Cmp_vector[12]=0?
and
--Cmp_vector[41]=Cmp_vector[42]=...=Cmp_vector[52]=Cmp_vector[53]=0?
Here follows pseudo-code for medium speed solving method (pwd'length=28): For each Init_12_pwd
{ Compute Pwd[13],Pwd[14],Pwd[15],...,Pwd[24]
For each Init_12
{
Compute Pwd[12]
Compute Pwd[0],Pwd[1],...,Pwd[11]
Compute Pwd[25],Pwd[26],Pwd[27]
Check whole password
{
if OK: password found! Display it and say bye-bye!
else : go on searching...
}
}
}
Conclusion
This method is about 256 times slower than high speed method, because we have 256*256=65536 possibilities to explore, which is not too much. It requires a minimum of 12 0s in Tail to work, so we can't use it to recover passwords with pwd'length>=30 characters.
This method was designed to recover very BIG passwords (up to 40 or 123 characters). So it doesn't use 0s in Tail, it only uses the 0 just before password in Cmp_vector. For instance, let's search a password of length=40 characters. We hunt 40 variables: Pwd[0],...,Pwd[39].
111111111122222222293333333333 1111
Password: 0123456789012345678901234567890123456789 01234567890123
Cmp_vector'struct: FILENAME.TXT0??????????????????????????? ?????????????0
0123456789111111111122222222223333333333 44444444445555
012345678901234567890123456789 01234567890123
As with medium speed method, we introduce Init_12 value, in order to compute Pwd[12]:
(Init_12+Pwd[12])&FF=Permuted_txt[12]=0 --> Pwd[12] found
We have seen that ('Pwd[i]' is written just '[i]'):
[ 0]=Permuted_txt[13]^{FF&(Init_12+[12]+[13])} ** 40 [ 1]=Permuted_txt[14]^{FF&(Init_12+[12]+[13]+[14])} * e . * q . * u . * a [ i]=Permuted_txt[13+i]^{FF&(Init_12+[12]+[13]+[14]+...+[i mod 40])} * t . * i . * o . * n [39]=Permuted_txt[52]^{FF&(Init_12+[12]+[13]+[14]+...+[39]+[0]+...+[12])} ** s
Have a look at first equation: [ 0]=Permuted_txt[13]^{FF&(Init_12+[12]+[13])}
Pwd[0] and Pwd[13] are unknown. We'll assign an arbitrary value to Pwd[13], then Pwd[0] will be known.
Pwd[13],Pwd[14],...,Pwd[24] are called FREE variables, because they don't depend on any other variable.
All other variables but Pwd[12] are called SLAVED variables, because they depend on at least one other variable.
For each free variable, there are 256 possible values (0->FF), we start with value: 0. So we obtain:
[13]=0 --> [0]=Perm_txt[13]^{FF&(Init_12+[12]+0)} --> [0] found ** 12
*
We go on with following equations, assigning value 0 to free variables * e Pwd[14],Pwd[15],...,Pwd[24]: * q
* u
[14]=0 --> [1]=Perm_txt[14]^{FF&(Init_12+[12]+0+0)} --> [1] found * a
[15]=0 --> [2]=Perm_txt[15]^{FF&(Init_12+[12]+0+0+0)} --> [2] found * t
. * i
. * o
. * n
[24]=0 --> [11]=Perm_txt[24]^{FF&(Init_12+[12]+0+...+0)} --> [11] found ** s
So we have assigned a value (0) to 12 free variables (Pwd[13],...,Pwd[24]), and we have calculated respective values of 12 slave variables (Pwd[0],...,Pwd[11]). Now we'll calculate remaining slave variables (Pwd[25],...,Pwd[39]).Step_2 Computation of remaining slave variables
We use remaining equations:
[12]=Perm_txt[25]^{FF&(Init_12+[12]+0+...+0+[25])} --> [25] found ** 15
[13]=Perm_txt[26]^{FF&(Init_12+[12]+0+...+0+[25]+[26])} --> [26] found * eq
. * ua
. * ti
. * on
[26]=Perm_txt[39]^{FF&(Init_12+[12]+0+...+0+[25]+...+[39])} -> [39] found ** s
So we found the whole password, using arbitrary values for Pwd[13],...,Pwd[24].
[27]=Perm_txt[40]^{FF&(Init_12+[12]+0+...+0+[25]+...+[39]+[0])} ? ** 13
[28]=Perm_txt[41]^{FF&(Init_12+[12]+0+...+0+[25]+...+[39]+[0]+[1])} ? * t
. * e
. * s
. * t
[39]=Perm_txt[52]^{FF&(Init_12+[12]+0+...+0+[25]+...+[39]+[0]+...+[12])} ? ** s
If eveything goes right, password is good. But if pwd doesn't pass tests, it means that one free variable (at least) is wrong, and we must change assignation(s). New assignation(s)
So we start again the whole process, but with different assignation'values for free variables. For instance:
|[13]|[14]|[15]|[16]|[17]|[18]|[19]|[20]|[21]|[22]|[23]|[24]| checks:
s a | 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| --> pwd bad
u s | 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 1| --> pwd bad
c s | 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 2| --> pwd bad
c i .
e g .
s n .
s a | 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| FF| --> pwd bad
i t | 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 1| 0| --> pwd bad
v i | 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 1| 1| --> pwd bad
e o | 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 1| 2| --> pwd bad
n . . . . . . . . . . . .
s . . . . . . . . . . . .
. . . . . . . . . . . .
| 6D| 6F| 74| 20| 64| 65| 20| 70| 61| 73| 73| 65| --> pwd good
Problem: for each free variable, there are 256 values possible (0->FF). As we have 12 free variables, we have 25612=8E28 combinations to try, which is A LOT! It would cost too much time to explore all of them. So we'll solve this problem using slicing technique.The Slicing Technique
It consists in solving system with 40 unknows at BIT level, instead of BYTE level (as we did above). Remember a byte consists of 8 bits, for instance:
<-------- increasing weight -----------
bit7 bit6 bit5 bit4 bit3 bit2 bit1 bit0
Pwd[i]=41: 0 1 0 0 0 0 0 1
* * * * * * * *
80 40 20 10 8 4 2 1
---------------------------------------
41= 0 + 40 + 0 + 0 + 0 + 0 + 0 + 1
Pwd[i] can be cut in 8 bits:
Pwd[i]=80*Pwd_bin[i][7]+40*Pwd_bin[i][6]+20*Pwd_bin[i][5]+10*Pwd_bin[i][4]
+8*Pwd_bin[i][3]+ 4*Pwd_bin[i][2]+ 2*Pwd_bin[i][1]+ 1*Pwd_bin[i][0]
We solve problem 'slice by slice': instead of 1 'big' system whose variables can vary from 0 to FF, we'll solve successively 8 'small' systems whose variables are binary (0 or 1). Systems must be solved in right order, from low weight to high weight (bit0,bit1,...,bit7), because solution to system n+1 depends on solution to system n.
Solving of System n:
we search Pwd_bin[0][weight n], Pwd_bin[1][weight n],...,Pwd_bin[39][weigth n]
So we assign values to 12 free variables (Pwd_bin[13][n],...,Pwd_bin[24][n]), then we compute slave variables and we perform tests. If OK: go to next system; otherwise change assignation(s).
|[13]|[14]|[15]|[16]|[17]|[18]|[19]|[20]|[21]|[22]|[23]|[24]| results: s a | 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| --> pwd bad u s | 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 1| --> pwd bad c s | 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 1| 0| --> pwd bad c i | 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 1| 1| --> pwd bad e g | 0| 0| 0| 0| 0| 0| 0| 0| 0| 1| 0| 0| --> pwd bad s n | 0| 0| 0| 0| 0| 0| 0| 0| 0| 1| 0| 1| --> pwd bad s a | 0| 0| 0| 0| 0| 0| 0| 0| 0| 1| 1| 0| --> pwd bad i t | 0| 0| 0| 0| 0| 0| 0| 0| 0| 1| 1| 1| --> pwd bad v i | 0| 0| 0| 0| 0| 0| 0| 0| 1| 0| 0| 0| --> pwd bad e o | 0| 0| 0| 0| 0| 0| 0| 0| 1| 0| 0| 1| --> pwd bad n . . . . . . . . . . . . s . . . . . . . . . . . . . . . . . . . . . . . . | 1| 1| 0| 0| 0| 1| 0| 0| 1| 1| 1| 1| --> pwd good
So we have 212=4096 combinations by slice, and as we have 8 slices, we've only got 8*4096=32768 possible combinations to try. Nice cutdown, huuum?
Here follows pseudo-code for low speed solving method (pwd'length=40):
For each Init_12
{ Compute Pwd[12]
For each slice i
{
For each possible assignation
{
Assign free variables (Pwd_bin[13][i],...,Pwd_bin[24][i])
Compute slave variables
(Pwd_bin[0][i],...,Pwd_bin[11][i],Pwd_bin[25][i],...,Pwd_bin[39][i])
Check whole password
{
if OK: password found! Display it and say bye-bye!
else : go on searching...
}
}
}
}
Conclusion
This is the slowest method, about 128 times slower than medium speed method , because we have 256*32768=8388608 combinations to try. Anyway, that's the one i prefer, because i believe slicing method could be used again to reduce dramatically solving times in other crypto problems {;-). Click for PART C - SOURCE FOR CRACKER
Mail Casimir. Copyright June 1998 by Casimir.
Converted to hypertext June 21, 1998 by Joe Peschel.