by
CASIMIR
Part A
The cracking code was revised by Casimir include to include version 2.6 -- Joe Peschel
Caz presents: the cracking of Gregory Braun's Crypto v3.5.
Once upon a time, I was asked by PlanetKeeper's staff [Planet Keeper] to review the proprietary encryption of a friend of theirs: Gregory Braun. They were planning to license from him, but I dissuaded them from doing so {:-)
Table of contents:
Abstract What do I need? From the outside PART A. REVERSING OF BRAUN'S CRYPTO V3.5 A1. Input handling A2. Hash tables and the making of KEY_0 A3. The making of KEY_1 A4. The making of KEY_2 A5. The check routine A6. The decryption process PART B. ANALYSIS AND BREAKING OF BRAUN'S CRYPTO V3.5 B1. The recovery of KEY_1 B11. Method 1 B12. Method 2 B13. Method 2 vs Method 1 B2. The recovery of KEY_0 and PASSWORD B21. Feasibility B22. Unicity B23. KEY_0's range B24. Reduced ASCII Character Set B25. Choosing suitable Password's length(s) B26. Building a Password B3. Benchmark PART C. 'C' SOURCE FOR CRACKER
Braun pretends to use the BlowFish algorithm to provide secure encryption in his application Crypto v3.5. Actually the algorithm used is a weak proprietary one.
In order to decrypt a file, Crypto v3.5 feeds with the Password a home-made hash function which produces a 32-bit key: KEY_1. Then KEY_1 is manipulated (shifts, ANDs) to produce a second 32-bit key: KEY_2. KEY_2 is compared against a third 32-bit key: KEY_CHK, which is stored in the header of the encrypted file. If KEY_2 = KEY_CHK, then Crypto v3.5 decrypts file using KEY_1 as the decryption key.
Weakness of Crypto v3.5 follows from the fact that:
Target : Crypto v3.5 crypto.exe : 188416 bytes Crypto 3.5 Tools needed:
OK, before tearing apart this app, let's play with it for a while. Encrypt various files with different content/content's size, name/name's lenght, password/password's lenght. Now examine them with Hex Workshop (nice editor BTW): we notice that Crypto adds 276 bytes to every encrypted file, no matter which password was used. Crypto doesn't seem to perform any compression before encryption, it probably doesn't add random garbage to file (files' size would vary much more).
So we can assume that:
encryption 1 character in plaintext ----------------> 1 character in ciphertext These 276 bytes constitute a header, which has the following structure: CryptoHdrBlk????pathfilename.............encryptedfile <------------- 276 bytes --------------->< original > sizeHuuummmm... Those 4 mysterious characters between original location and filename raise my interest. Their values seem to be only function of password, they don't depend on plaintext's content. It would be a nice place for an encrypted password (OK, I cheat, I've already reversed and cracked it, but it's a nice assumption anyway, right?).
Since Braun used a home-made algorithm (and forgot to give us the recipe {:), we'll have to reverse his program. Prepare a test file: braun.txt with content: ABCDEF (6 bytes, UPPERCASE). Encrypt it with pwd: CASIMIR (UPPERCASE), obtaining encrypted file braun.(=txt=):
Dump of braun.txt:
=======================================
=======================================
As usual, I'll take a 'live' approach: I'll use Winice to discover what's going on with my input. Select file braun.(=txt=) for decryption, enter a wrong pwd: 13579 (do not use 012345... cause this sequence is often present in memory). Before checking OK, enter Winice and set BPXs on Windows functions that are usually used to collect such inputs. This time function GetDlgItemTextA pops up, and here is what we see:
... CS:405EB2 mov ebx,[USER32!GetDlgItemTextA] CS:405EB8 push 100 CS:405EBD push eax <-- Watch out! Input is copied to DS:EAX CS:405EBE push 65 CS:405EC0 push esi CS:405EC1 call ebx <-- get input and copy it to DS:EAX ...=======================================
=======================================
Let's set a BPR DS:EAX EAX+5 RW so we know when and where our input is used. Input is read in CS:405EE0 (don't know why), then we enter the interesting part:
* Reference To: KERNEL32.lstrlenA, Ord:029Ch :0040CD68 xor edi,edi <-- edi=0 :0040CD6A push esi :0040CD6B Call dword ptr [0042D48C] <-- return input's length in eax :0040CD71 test esi, esi :0040CD73 je 0040CDA7 :0040CD75 test eax, eax :0040CD77 je 0040CDA7 :0040CD79 mov ecx, 00000000 :0040CD7E jle 0040CDA7Before going any further, notice that Crypto uses 2 hash tables:
- HashTable_1 starting at DS:41DDF8 23 73 65 72 42 26 6E 7A 7C 6D 66 4D 31 2F 35 28 21 73 64 24 4D 71 2E 7B 73 5D 2B 73 46 6A 74 4B 70 7A 53 64 74 7A 6F 58 71 6D 62 5E 41 6C 40 64 76 3A 73 3F 78 2F 00 00 7C 62 21 70 7A 2A 6C 73 3B 72 6E 7C 6C 66 24 76 69 5E 41 78 70 65 29 72 78 35 61 69 63 26 39 2F 32 6D 35 6C 73 69 34 40 30 64 6D 5A 77 39 34 63 6D 71 70 66 68 77 00 00 - HashTable_2 starting at DS:41DE30 7C 62 21 70 7A 2A 6C 73 3B 72 6E 7C 6C 66 24 76 69 5E 41 78 70 65 29 72 78 35 61 69 63 26 39 2F 32 6D 35 6C 73 69 34 40 30 64 6D 5A 77 39 34 63 6D 71 70 66 68 77 00 00Those tables are always the same, they do not depend on input or plaintext.
***>:0040CD80 movsx ebx, byte ptr [eax+ecx+0041DDF8] <-- read 1 character * from HashTable_1 * :0040CD88 movsx ebp, byte ptr [esi+ecx] <-- read 1 character from input * :0040CD8C lea edx, dword ptr [ecx+01] <-- edx=ecx+1 * L :0040CD8F imul ebx, ebp * O :0040CD92 movsx ecx, byte ptr [ecx+0041DE30] <-- read 1 character from * O HashTable_2 * P :0040CD99 imul ebx, ecx * :0040CD9C imul ebx, edx * :0040CD9F add edi, ebx <-- edi=accumulator * :0040CDA1 mov ecx, edx * :0040CDA3 cmp eax, edx ***<:0040CDA5 jg 0040CD80 <-- loop eax (5) times :0040CDA7 mov eax, edi :0040CDA9 pop ebp :0040CDAA pop edi :0040CDAB pop esi :0040CDAC pop ebx :0040CDAD retTo sum up, if we have input's length=len :
edi = HashTable_1[len+1] * HashTable_2[1] * 1 * Input[1] + HashTable_1[len+2] * HashTable_2[2] * 2 * Input[2] + ... + HashTable_1[len+len] * HashTable_2[len] * len * Input[len] let Coef[i] = HashTable_1[len+i] * HashTable_2[i] * i , we have: edi = Coef[1]*Input[1] + Coef[2]*Input[2] + ... + Coef[len]*Input[len] for instance, with input: 13579, we obtain: edi=0x00868500There is something interesting from our cracker point-of-view: coefficients depend only on input's length. It means that, for a given input's length, we can pre-compute each coefficient. It will spare us a lot of computing time during cracking process.
We'll call edi value: KEY_0 from now on.
=======================
=======================
Then KEY_0 gets copied to eax (CS:40CDA7), and eax gets copied to DS:42A0F0. As usual, we survey this memory location, and find out that value is copied in CS:405D4C and CS:402282. But a most important handling occurs in CS:402AC4 :
CS:402AC4 or [esi],06A30DE8 // DS:[esi] contains KEY_0 06A30DE8 is a constant We obtain a new 4 bytes key, KEY_1 : KEY_1 = KEY_0 or 06A30DE8 = 00868500 or 06A30DE8 = 06A78DE8=======================
=======================
KEY_1 is used in following code sequence:
:0040B2F0 push esi :0040B2F1 push edi :0040B2F2 mov esi, dword ptr [esp+0C] // copy KEY_1 to esi :0040B2F6 push esi :0040B2F7 call 00411450 // copy KEY_1 to DS:4205F4 :0040B2FC add esp, 00000004 :0040B2FF call 00411460 // first_call :0040B304 mov edi, eax // eax=00001799 (see first_call walk-thru) :0040B306 call 00411460 // second_call :0040B30B shl eax, 00000010 // eax=00004411 (see second_call walk-thru) :0040B30E add eax, edi // eax = 44110000+00001799 = 44111799 :0040B310 pop edi :0040B311 add eax, esi // add KEY_1 to eax, giving KEY_2: // KEY_2 = 06A78DE8 + 44111799 = 4AB8A581 :0040B313 pop esi :0040B314 retLet's see what's going on during first call at CS:411460
first_call
---------- :00411460 mov eax, [004205F4] // copy KEY_1 to eax :00411465 lea ecx, dword ptr [eax+4*eax] // ecx = 5*eax :00411468 lea ecx, dword ptr [ecx+4*ecx] // ecx = 5*ecx = 19*eax :0041146B add ecx, eax // ecx = 1A*eax :0041146D lea ecx, dword ptr [eax+8*ecx] // ecx = eax+8*1A*eax = D1*eax :00411470 shl ecx, 00000008 // ecx = 100*ecx = D100*eax :00411473 sub ecx, eax // ecx = ecx-eax = D0FF*eax :00411475 lea eax, dword ptr [eax+4*ecx+269EC3] // eax = 343FD*eax+269EC3 :0041147C mov [004205F4], eax // copy KEY_TMP_1 = eax to DS:4205F4 :00411481 and eax, 7FFF0000 // mask eax :00411486 shr eax, 00000010 // right shift : 12345678 becomes 00001234 :00411489 ret So with KEY_1 = 06A78DE8 we obtain : KEY_TMP_1 = 343FD*KEY_1+269EC3 = 1799950B and eax (returned value) = (KEY_TMP_1 and 7FFF0000) / 10000 = 00001799But this portion of code is called a second time, and the value of KEY_TMP_1 is used :
second_call
----------- :00411460 mov eax, [004205F4] // copy KEY_TMP_1 to eax :00411465 lea ecx, dword ptr [eax+4*eax] // ecx = 5*eax :00411468 lea ecx, dword ptr [ecx+4*ecx] // ecx = 5*ecx = 19*eax :0041146B add ecx, eax // ecx = 1A*eax :0041146D lea ecx, dword ptr [eax+8*ecx] // ecx = eax+8*1A*eax = D1*eax :00411470 shl ecx, 00000008 // ecx = 100*ecx = D100*eax :00411473 sub ecx, eax // ecx = ecx-eax = D0FF*eax :00411475 lea eax, dword ptr [eax+4*ecx+269EC3] // eax =343FD*eax+269EC3 :0041147C mov [004205F4], eax // copy KEY_TMP_2 = eax to DS:4205F4 :00411481 and eax, 7FFF0000 // mask eax :00411486 shr eax, 00000010 // right shift : 12345678 becomes 00001234 :00411489 retSo with KEY_TMP_1 = 1799950B we obtain :
KEY_TMP_2 = 343FD*KEY_TMP_1+269EC3 = 4411CBA2 and eax (returned value) = (KEY_TMP_2 and 7FFF0000) / 10000 = 00004411=====================
=====================
As we'll see soon, KEY_2 is used immediatly after computation. Follow return at CS:40B314, here's what you see:
:00402D73 call 0040B2F0 <--- the place we return from :00402D78 add esp, 00000004 :00402D7B cmp eax, dword ptr [esp+258] // compare KEY_2 against KEY_CHK :00402D82 je 00402DC3 // jump only if KEY_2 = KEY_CHK :00402D84 mov eax, dword ptr [esp+14] // bad guy, let's kick his ass :00402D88 push eax * Reference To: KERNEL32.CloseHandle, Ord:0017h :00402D89 Call dword ptr [0042D4E0] :00402D8F mov eax, dword ptr [esp + 10] :00402D93 push eax * Possible Reference to String Resource ID=02007: "File: %sThis file was not encrypted with the current key" :00402D94 push 000007D7 :00402D99 jmp 004033BF We have: KEY_2 = 4AB8A581 and: KEY_CHK = 6BF6F492Keys are not the same, so Braun refuses to decrypt file.
Question: where does KEY_CHK come from? Well, you remember the 276-bytes header, don't you? There were 4 mysterious bytes in this header:
00000000 43 72 79 70 74 6F 48 64 72 42 6C 6B 92 F4 F6 6B CryptoHdrBlk...k <-KEY_CHK->This small, very small key is used by Braun to tell if password is good or not.
==========================
==========================
If password is correct, Braun decrypts the file. Decryption process presents no interest, so I won't describe it. The only important thing to notice is that Braun does not use the password to decrypt file, instead he uses KEY_1.
Copyright September 1999 by Casimir.
Mail Casimir
Converted to hypertext by Joe Peschel September 16, 1999.