by
CASIMIR
Part B
Caz presents : the Cracking of MasterKey v1.02/1.05 by Ph. MELLERET
Table of contents:
Abstract
What do i need?
Target's description
PART A. REVERSING OF MASTERKEY
A1. Input handling
A2. Building of K1
A3. Building of K2
A4. Building of K3
A5. Final cmp
A6. Monitoring Registry
PART B. BREAKING OF MASTERKEY
B1. General constraints
B2. Splitting
B21. Validity of splits
B22. Sorting splits
B3. Isolated column(s)
B4. Modulo (K2 -> K3)
B5. Solving method
B51. Exhaustive search
B52. Optimization and main algorithm
B53. Password check
PART C. BATCH FILE FOR REGISTRY'S KEY EXPORT
PART D. 'C' SOURCE FOR CRACKER
OK, let's try the easy way: we overwrite K3 with KEY_CHK just before the compare part starts. It works {:-) : MK lets us in! Unfortunately, we see nothing but garbage in protected directories {:-( . Huuuummmm... Seems MK uses our (wrong) input to decrypt directories.
So we'll have to do it the hard way: we'll write a nice cracker to guess the correct password.
Let's sum up actions performed by MK:
f_1 f_2 f_3 cmp K3,KEY_CHK
PASSWORD ----> K1 ----> K2 ----> K3 -------------------
(x bytes) (12 bytes) (y bytes) (y bytes) |
|
V
if equal then decrypt
Reverse-engineering (see PART A) gave us the 3 functions : f_1, f_2 and f_3.
If we have K3=KEY_CHK then we know we have the good password (remember KEY_CHK is written down in Registry, we just have to read it).
=======================================
=======================================
OK, let's start from the very beginning.
We know password must be at least 5 characters long and can not exceed 63 characters:
LEN_|MAX|_PWD = |3F
|MIN| |5
Since we look for pwd whose characters belong to non-extended ASCII table, we have:
MIN|_CHAR = |20 (lower values can not be used)
MAX| |7F
K1 is 12-byte long, we can divide it in three 4-byte keys:
K1 = K1oe K1o K1e
Let P[i]=char i from PWD (i starts from 0):
K1oe = sum of (P[i] , i being odd or even)^2
K1o = sum of (P[i] , i being odd )^2
K1e = sum of (P[i] , i being even )^2
Let
String_oe = P[i] , i being odd or even (i.e. PWD itself)
String_o = P[i] , i being odd
String_e = P[i] , i being even
We have:
LEN_|MAX|_String_oe = LEN_|MAX|_PWD
|MIN| |MIN|
( LEN_|MAX|_PWD )
( |MIN| )
LEN_|MAX|_String_o = trunc ( ------------- )
|MIN| ( 2 )
( LEN_|MAX|_PWD )
( |MIN| )
LEN_|MAX|_String_e = trunc ( ------------- ) [ +1 if LEN_|MAX|_PWD odd ]
|MIN| ( 2 ) |MIN|
Now we want to know mini and maxi values that K1oe, K1o and K1e can take:
|MAX|_|K1oe| = |MAX|_CHAR^2 * LEN_|MAX|_|K1oe|
|MIN| |K1o | |MIN| |MIN| |K1o |
|K1e | |K1e |
We obtain:
MAX_K1oe = 7F^2 * 3F = F813F MIN_K1oe = 20^2 * 5 = 1400
MAX_K1o = 7F^2 * 1F = 7A11F MIN_K1o = 20^2 * 2 = 800
MAX_K1e = 7F^2 * 20 = 7E020 MIN_K1e = 20^2 * 3 = C00
So K1oe, K1o and K1e belong to [800 ; F813F].
In order to obtain K2, we must get rid of null-byte(s) from K1:
LEN_K2 = LEN_K1 - (number of null-byte(s) in K1)
= 12 - (number of null-byte(s) in K1)
Since LEN_K2 = LEN_K3, LEN_K2 is known so we have:
number of null-byte(s) in K1 = 12 - LEN_K3
The problem is: how do we know WHERE null-byte(s) are located in K1? Well, we can not guess it, so we try every possibility. Each possibility is called a split.=======================================
=======================================
K1 is 12-bytes long, we can divide K1 into three 4-bytes keys: K1oe, K1o and K1e. We introduce new variables (yes, i know: once more...but it's the last time, i swear) to tell if a specific byte is null or not:
K1oe = 1 * K1oe_b0 * K1oe_n0
+ 100 * K1oe_b1 * K1oe_n1
+ 10000 * K1oe_b2 * K1oe_n2
+ 1000000 * K1oe_b3 * K1oe_n3
K1oe_b0 : lower byte from K1oe
K1oe_b3 : higher byte from K1oe
K1oe_n0,1,2,3 : if byte b0,1,2,3 is null then 0 else 1
For instance, with K1oe=000256B0:
000256B0 = 1 * B0 * 1
+ 100 * 56 * 1
+ 10000 * 02 * 1
+ 1000000 * 00 * 0
We do the same with K1o and K1e:
K1o = 1 * K1o_b0 * K1o_n0
+ 100 * K1o_b1 * K1o_n1
+ 10000 * K1o_b2 * K1o_n2
+ 1000000 * K1o_b3 * K1o_n3
K1e = 1 * K1e_b0 * K1e_n0
+ 100 * K1e_b1 * K1e_n1
+ 10000 * K1e_b2 * K1e_n2
+ 1000000 * K1e_b3 * K1e_n3
A split is totally described by the values of n0, n1, ...
split_K1oe = K1oe_n0 K1oe_n1 K1oe_n2 K1oe_n3
split_K1o = K1o_n0 K1o_n1 K1o_n2 K1o_n3
split_K1e = K1e_n0 K1e_n1 K1e_n2 K1e_n3
split_K1 = split_K1oe split_K1o split_K1e
For instance, let LEN_K3 = 6 bytes, a possible split_K1 is:
<- split_K1oe -> <- split_K1o -> <- split_K1e ->
split_K1 = 1 1 0 0 1 1 0 0 1 1 0 0
It means that K1oe_b2, K1oe_b3, K1o_b2, K1o_b3, K1e_b2, K1e_b3 are null.
***************************************
***************************************
Fortunately, not every possible split is a valid one. This will reduce the number of splits to try out.
-Since K1oe, K1o and K1e belong to [C00 ; F813F] we must have:
- K1oe_n3 = K1o_n3 = K1e_n3 = 0
- K1oe, K1o and K1e are greater than FF, so these 3 keys have at least 1 non-
null byte (n1 or n2).
-Since K1oe = K1o + K1e, some possible splits must be discarded. For instance:
split_K1oe = 1 1 0 0
split_K1o = 0 0 1 0
split_K1e = 0 0 1 0
This split is not valid because we would have K1o and K1e greater than K1oe.So, given LEN_K3, we'll try out every valid split to recover pwd. The number of valid splits depends on LEN_K3, but it is always < 100.
***************************************
***************************************
Only one 4-byte number out of 100 ends with a null byte (00 against 01, 02, ..., FF). So a split such as 0110 is less frequent than 1100.
We'll sort splits by decreasing frequency before trying them.
=======================================
=======================================
We know that: K1oe = K1o + K1e. A byte "column" (i.e. for a same indice i: K1oe_bi, K1o_bi and K1e_bi) can be "isolated" or not from other columns. A column i is isolated if we ALWAYS have: Kloe_bi = K1o_bi + K1e_bi, no matter values of K1oe_bi, K1o_bi and K1e_bi. This means that column i can not receive a carry from column i-1. For instance:
K1oe = 6958AD --> K1oe_b0 = AD , K1oe_b1 = 58 , K1oe_b2 = 69 K1o = 3117B0 --> K1o_b0 = B0 , K1o_b1 = 17 , K1o_b2 = 31 K1e = 3840FD --> K1e_b0 = FD , K1e_b1 = 40 , K1e_b2 = 38-column 0 can not receive a carry because there is no other column on its left-side. So we have:
K1oe_b0 = K1o_b0 + K1e_b0 This gives us one more equation to help us to recover pwd. -columns 1 and 2 can receive a carry from the left, for instance we have: K1oe_b1 <> K1o_b0 + K1e_b0 , so we can't use them.=======================================
=======================================
We know that each byte K3oe_bi from K3oe (K3o and K3e ditto) is obtained like this:
K3oe_bi = (K2oe_bi modulo 5E) + 20 So, to recover K2oe_bi (K2o_bi and K2e_bi ditto): K3oe_bi - 20 = K2oe_bi%5E Problem: we don't know how many times the modulo 5E is applied to K2oe_bi. So we obtain: K2oe_bi = K3oe_bi - 20 + j*5E , with j = 0, 1, ..., n Fortunately, since K3oe_bi < 100 (K3oe_bi is a byte), n can not be greater than 2. For instance, let K3oe_bi = 61, there are 3 possible values for K2oe_bi: - j=0 : K2oe_bi = 41 - j=1 : K2oe_bi = 9F - j=2 : K2oe_bi = FD But with K3oe_bi = 75, there are only 2 possible values for K2oe_bi: - j=0 : K2oe_bi = 55 - j=1 : K2oe_bi = B3So, for each byte of K3, we have a maximum of 3 possible values for the matching byte in K2. It means that, given LEN_K3, we'll have less than LEN_K3^3 possible K2s to try out. For instance, let LEN_K3=6 bytes, we have less than 6*6*6=216 (dec) K2s to try.
=======================================
=======================================
Now it's time for gathering up our findings {:-)
(actually, terms in K*_b3 are all null)
- the main sum:
K1oe = K1o + K1e
- the 3 sub-sums:
K1oe = 1*K1oe_b0 + 100*K1oe_b1 + 10000*K1oe_b2 + 1000000*K1oe_b3
K1o = 1*K1o_b0 + 100*K1o_b1 + 10000*K1o_b2 + 1000000*K1o_b3
K1e = 1*K1e_b0 + 100*K1e_b1 + 10000*K1e_b2 + 1000000*K1e_b3
- the 12 line equations:
P[0] + K1oe_b0 = K2oe_b0 , K2oe_n0 = 0 or 1
P[.] + K1oe_b1 = K2oe_b1 , K2oe_n1 = 0 or 1
P[.] + K1oe_b2 = K2oe_b2 , K2oe_n2 = 0 or 1
P[.] + K1oe_b3 = K2oe_b3 , K2oe_n3 = 0
P[.] + K1o_b0 = K2o_b0 , K2o_n0 = 0 or 1
P[i] + K1o_b1 = K2o_b1 , K2o_n1 = 0 or 1
P[.] + K1o_b2 = K2o_b2 , K2o_n2 = 0 or 1
P[.] + K1o_b3 = K2o_b3 , K2o_n3 = 0
P[.] + K1e_b0 = K2e_b0 , K2e_n0 = 0 or 1
P[.] + K1e_b1 = K2e_b1 , K2e_n1 = 0 or 1
P[.] + K1e_b2 = K2e_b2 , K2e_n2 = 0 or 1
P[j] + K1e_b3 = K2e_b3 , K2e_n3 = 0
- the 3 squared sums:
K1oe = P[0]^2 + P[1]^2 + ... + P[i]^2 + ... + P[I]^2
K1o = P[1]^2 + P[3]^2 + ... + P[2j+1]^2 + ... + P[2J+1]^2
K1e = P[0]^2 + P[2]^2 + ... + P[2k]^2 + ... + P[2K]^2
- the 4 column equations:
K1oe_b0 = K1o_b0 + K1e_b0 , column 0 isolated = yes or no
K1oe_b1 = K1o_b1 + K1e_b1 , column 1 isolated = yes or no
K1oe_b2 = K1o_b2 + K1e_b2 , column 2 isolated = yes or no
K1oe_b3 = K1o_b3 + K1e_b3 , column 3 isolated = yes or no
We did a good work {:-). Here is our strategy:
1. we "fix" (i.e. give arbitrary value to) P[0].
2. with the help of P[0], we try to compute P[1], ..., P[I] using
all our equations above. If every character from PWD is fixed or computed
then we jump to 3. else we go on fixing character(s):
we fix P[1] if it is unknown yet. If P[1] has already been computed or
fixed, we fix P[2], or P[3], ect...
3. we check PWD found. If PWD is good then we stop, else we go back to 1. and
we fix P[0], ... with different values.
Example:
PWD to recover : CASIM (43 41 53 49 4D)
PWD_LEN : 5
K3 : Pka*HR (50 6B 61 2A 48 52)
LEN_K3 : 6
good split_K1 : 1 1 0 0 1 1 0 0 1 1 0 0 so:
K3oe_b0 = 50
K3oe_b1 = 6B
K3o_b0 = 61
K3o_b1 = 2A
K3e_b0 = 48
K3e_b1 = 52
good K2:
K2oe_b0 = 30
K2oe_b1 = A9
K2o_b0 = 9F
K2o_b1 = 68
K2e_b0 = E4
K2e_b1 = 90
The equations become:
- the main sum:
K1oe = K1o + K1e
- the 3 sub-sums:
K1oe = 1*K1oe_b0 + 100*K1oe_b1
K1o = 1*K1o_b0 + 100*K1o_b1
K1e = 1*K1e_b0 + 100*K1e_b1
- from the 12 line equations, only 6 not-null remain (removed eqs are enclosed in ()): P[0] + K1oe_b0 = K2oe_b0 , K2oe_n0 = 1 P[1] + K1oe_b1 = K2oe_b1 , K2oe_n1 = 1 (P[2] + K1oe_b2 = K2oe_b2 , K2oe_n2 = 0) (P[3] + K1oe_b3 = K2oe_b3 , K2oe_n3 = 0) P[4] + K1o_b0 = K2o_b0 , K2o_n0 = 1 P[0] + K1o_b1 = K2o_b1 , K2o_n1 = 1 (P[1] + K1o_b2 = K2o_b2 , K2o_n2 = 0) (P[2] + K1o_b3 = K2o_b3 , K2o_n3 = 0) P[3] + K1e_b0 = K2e_b0 , K2e_n0 = 1 P[4] + K1e_b1 = K2e_b1 , K2e_n1 = 1 (P[0] + K1e_b2 = K2e_b2 , K2e_n2 = 0) (P[1] + K1e_b3 = K2e_b3 , K2e_n3 = 0) So: P[0] + K1oe_b0 = 30 P[1] + K1oe_b1 = A9 P[4] + K1o_b0 = 9F P[0] + K1o_b1 = 68 P[3] + K1e_b0 = E4 P[4] + K1e_b1 = 90 - the 3 squared sums: K1oe = P[0]^2 + P[1]^2 + P[2]^2 + P[3]^2 + P[4]^2 K1o = P[1]^2 + P[3]^2 K1e = P[0]^2 + P[2]^2 + P[4]^2 - form the 4 column equations, only remains the first one: K1oe_b0 = K1o_b0 + K1e_b0This system is a mess, because we have a mix of linear and quadratic equations. To solve it, we proceed this way:
step 1. we fix P[0] with lowest possible value: P[0] = MIN_CHAR = 20
step 2. we update equations with fixed P[0]:
P[0] + K1oe_b0 = 30 => 20 + K1oe_b0 = 30 => K1oe_b0 = 10
P[0] + K1o_b1 = 68 => 20 + K1o_b1 = 68 => K1o_b1 = 48
K1oe = P[0]^2 + P[1]^2 + P[2]^2 + P[3]^2 + P[4]^2 => K1oe = 20^2 + P[1]^2 + P[2]^2 + P[3]^2 + P[4]^2
K1e = P[0]^2 + P[2]^2 + P[4]^2 => K1e = 20^2 + P[2]^2 + P[4]^2
step 3. we try to use extra info from updated equations in other equations:
K1oe = 1*K1oe_b0 + 100*K1oe_b1 => K1oe = 1*10 + 100*k1oe_b1
K1o = 1*K1o_b0 + 100*K1o_b1 => K1o = 1*K1o_b0 + 100*48
K1oe_b0 = K1o_b0 + K1e_b0 => 10 = K1o_b0 + K1e_b0
step 4. we evaluate the progress of search: did we find an other P[i]?
-if yes then go to step 2.
-if no then we must fix an other P[i] by ourselves.
In our case, search did not progress, so we fix P[1] = MIN_CHAR = 20, and we go on.
step 2. again: we update equations with fixed P[1]:
P[1] + K1oe_b1 = A9 => 20 + K1oe_b1 = A9 => K1oe_b1 = 89
K1oe = 20^2 + P[1]^2 + P[2]^2 + P[3]^2 + P[4]^2 => K1oe = 20^2 + 20^2 + P[2]^2 + P[3]^2 + P[4]^2
K1o = P[1]^2 + P[3]^2 => K1o = 20^2 + P[3]^2
step 3. again: we try to use extra info from updated equations in other equations:
K1oe = 1*10 + 100*k1oe_b1 => K1oe = 8910
K1oe = 20^2 + 20^2 + P[2]^2 + P[3]^2 + P[4]^2 => 8910 = 20^2 + 20^2 + P[2]^2 + P[3]^2 + P[4]^2
step 4. again: search did not progress, so we fix P[2] = MIN_CHAR = 20, and we go on.
step 2. again: we update equations with fixed P[2]:
8910 = 20^2 + 20^2 + P[2]^2 + P[3]^2 + P[4]^2 => 8910 = 20^2 + 20^2 + 20^2 + P[3]^2 + P[4]^2
K1e = 20^2 + P[2]^2 + P[4]^2 => K1e = 20^2 + 20^2 + P[4]^2
step 3. again: no info can be extracted
step 4. again: search did not progress, so we fix P[3] = MIN_CHAR = 20, and we go on.
step 2. again: we update equations with fixed P[3]:
P[3] + K1e_b0 = E4 => K1e_b0 = C4
8910 = 20^2 + 20^2 + 20^2 + P[3]^2 + P[4]^2 => 8910 = 20^2 + 20^2 + 20^2 + 20^2 + P[4]^2 => P[4]^2 = 7910
So P[4] = sqrt(7910). Unfortunately, 7910 is not square, so value found for P[4] is wrong => we reject this PWD.
***************************************
***************************************
To compute PWD, we've successively fixed P[0], P[1], P[2] and P[3]. Since PWD found is wrong, we must fix these characters with different value(s), until good PWD is found:
P[0] P[1] P[2] P[3] => PWD
1° try: 20 20 20 20 wrong
2° try: 20 20 20 21 wrong
3° try: 20 20 20 22 wrong
...
n° try: 43 41 53 49 good : we compute P[4]=4D ***************************************
***************************************
Well, this method works, but it is not the best one. In fact, there's a problem. Since a character can take 60 (96 dec) values (MIN_CHAR=20, MAX_CHAR=7F):
- if we have to fix 4 characters (for instance: P[0], P[1], P[2] and P[3]) then we have: 60^4 combinations to try out while searching. - if we have to fix 3 characters then we only have 60^3 combinations to try out.So we must minimize FIX_NB, the number of character(s) to fix to find PWD.
The minimal -and best- value for FIX_NB is 1, since we'll always have to fix at least one character to "launch" system solving.
The maximal -and worst- value for FIX_NB is PWD_LEN, it means that equations did not help us to compute any character.
We proceed in 2 steps:
step 1: we search the minimal FIX_NB. To do so, we fix character(s) in every possible orders until remaining characters can be computed.
For instance, with PWD_LEN=5 characters: 1° order: 0 1 2 3 -> FIX_NB=4 2° order: 0 1 2 4 -> FIX_NB=4 ... n° order: 0 4 -> FIX_NB=2 , this is the best FIX_NB we can find.step 2: once the best FIX_NB is found, we can perform an exhaustive search.
OK, now we can draw the main algo of our cracker:
each split
{
each LEN_PWD (for given split)
{
each K2 (for given split and LEN_PWD)
{
step 1: choose best (i.e. smallest) FIX_NB
step 2: solve system (exhaustive search)
step 3: check pwd found, if OK : stop
}
}
}
***************************************
***************************************
We perform 3 checks on password found:
- we must have, for each character P[i] from password:
P[i] + K1oe_bi = K2oe_bi (ditto K1o and K1e)
- we must have: K1oe = K1o + K1e
- we must have PWD's ASCII characters between 0x20 (Space) and 0x7F ()
If a password pass every checks, then it is the good one. Unfortunately, we may sometimes obtain more than one good password (usually: 2 or 3). Those 'fake' passwords are accepted by MK, but content of decrypted directories is pure garbage. (NB: data is *not* lost: once correct password is entered, correct content is recovered)Here are Parts C and D
Copyright October, 2000 by Casimir.
Mail Casimir
Converted to hypertext by Joe Peschel October 19, 2000.