Dennis Yurichev <dennis@conus.info>
Sometimes amateur cryptosystems appear to be pretty bizarre.
I was asked to revese engineer an amateur cryptoalgorithm of some data crypting utility, source code of which was lost.
(I also got permit from customer to publish the algorithm details)
I started from top. Here is a function taking two file names and password.
.text:00541320 ; int __cdecl crypt_file(int Str, char *Filename, int password) .text:00541320 crypt_file proc near ; CODE XREF: _main+42 .text:00541320 .text:00541320 Str = dword ptr 4 .text:00541320 Filename = dword ptr 8 .text:00541320 password = dword ptr 0Ch .text:00541320
Open file and return error in case of error:
.text:00541320 mov eax, [esp+Str] .text:00541324 push ebp .text:00541325 push offset Mode ; "rb" .text:0054132A push eax ; Filename .text:0054132B call _fopen ; open file .text:00541330 mov ebp, eax .text:00541332 add esp, 8 .text:00541335 test ebp, ebp .text:00541337 jnz short loc_541348 .text:00541339 push offset Format ; "Cannot open input file!\n" .text:0054133E call _printf .text:00541343 add esp, 4 .text:00541346 pop ebp .text:00541347 retn .text:00541348 ; --------------------------------------------------------------------------- .text:00541348 .text:00541348 loc_541348: ; CODE XREF: crypt_file+17
Get file size via fseek/ftell:
.text:00541348 push ebx .text:00541349 push esi .text:0054134A push edi .text:0054134B push 2 ; Origin .text:0054134D push 0 ; Offset .text:0054134F push ebp ; File .text:00541350 call _fseek .text:00541355 push ebp ; File .text:00541356 call _ftell ; get file size .text:0054135B push 0 ; Origin .text:0054135D push 0 ; Offset .text:0054135F push ebp ; File .text:00541360 mov [esp+2Ch+Str], eax .text:00541364 call _fseek ; rewind to start
This piece of code calculates file size aligned to 64-byte border. This is because this algorithm works with only 64-byte blocks. Its operation is pretty simple: divide file size by 64, forget about remainder and add 1, then multiple by 64 again. The following code removes remainder as if value was already divided and adds 64. It is almost the same.
.text:00541369 mov esi, [esp+2Ch+Str] .text:0054136D and esi, 0FFFFFFC0h ; reset all lowest 6 bits .text:00541370 add esi, 40h ; align size to 64-byte border
Allocate buffer with aligned size:
.text:00541373 push esi ; Size .text:00541374 call _malloc
Do memset(), e,g, clear allocated buffer.
.text:00541379 mov ecx, esi .text:0054137B mov ebx, eax ; allocated buffer pointer -> to EBX .text:0054137D mov edx, ecx .text:0054137F xor eax, eax .text:00541381 mov edi, ebx .text:00541383 push ebp ; File .text:00541384 shr ecx, 2 .text:00541387 rep stosd .text:00541389 mov ecx, edx .text:0054138B push 1 ; Count .text:0054138D and ecx, 3 .text:00541390 rep stosb ; memset (buffer, 0, aligned_size)
Read file via standard C function fread().
.text:00541392 mov eax, [esp+38h+Str] .text:00541396 push eax ; ElementSize .text:00541397 push ebx ; DstBuf .text:00541398 call _fread ; read file .text:0054139D push ebp ; File .text:0054139E call _fclose
Call crypt(). It takes buffer, buffer size (aligned) and password string.
.text:005413A3 mov ecx, [esp+44h+password] .text:005413A7 push ecx ; password .text:005413A8 push esi ; aligned size .text:005413A9 push ebx ; buffer .text:005413AA call crypt ; do crypt
Create output file. By the way, developer forgot to check if it is was created correctly! File opening result is being checked though.
.text:005413AF mov edx, [esp+50h+Filename] .text:005413B3 add esp, 40h .text:005413B6 push offset aWb ; "wb" .text:005413BB push edx ; Filename .text:005413BC call _fopen .text:005413C1 mov edi, eax
Now file handle is in EDI register. Write signature "QR9".
.text:005413C3 push edi ; File .text:005413C4 push 1 ; Count .text:005413C6 push 3 ; Size .text:005413C8 push offset aQr9 ; "QR9" .text:005413CD call _fwrite ; write file signature
Write actual file size:
.text:005413D2 push edi ; File .text:005413D3 push 1 ; Count .text:005413D5 lea eax, [esp+30h+Str] .text:005413D9 push 4 ; Size .text:005413DB push eax ; Str .text:005413DC call _fwrite ; write original file size
Write crypted buffer:
.text:005413E1 push edi ; File .text:005413E2 push 1 ; Count .text:005413E4 push esi ; Size .text:005413E5 push ebx ; Str .text:005413E6 call _fwrite ; write crypted file
Close file and free allocated buffer:
.text:005413EB push edi ; File .text:005413EC call _fclose .text:005413F1 push ebx ; Memory .text:005413F2 call _free .text:005413F7 add esp, 40h .text:005413FA pop edi .text:005413FB pop esi .text:005413FC pop ebx .text:005413FD pop ebp .text:005413FE retn .text:005413FE crypt_file endp
Here is reconstructed C-code:
void crypt_file(char *fin, char* fout, char *pw)
{
FILE *f;
int flen, flen_aligned;
BYTE *buf;
f=fopen(fin, "rb");
if (f==NULL)
{
printf ("Cannot open input file!\n");
return;
};
fseek (f, 0, SEEK_END);
flen=ftell (f);
fseek (f, 0, SEEK_SET);
flen_aligned=(flen&0xFFFFFFC0)+0x40;
buf=(BYTE*)malloc (flen_aligned);
memset (buf, 0, flen_aligned);
fread (buf, flen, 1, f);
fclose (f);
crypt (buf, flen_aligned, pw);
f=fopen(fout, "wb");
fwrite ("QR9", 3, 1, f);
fwrite (&flen, 4, 1, f);
fwrite (buf, flen_aligned, 1, f);
fclose (f);
free (buf);
};
Decrypting procedure is almost the same:
.text:00541400 ; int __cdecl decrypt_file(char *Filename, int, void *Src) .text:00541400 decrypt_file proc near ; CODE XREF: _main+6E .text:00541400 .text:00541400 Filename = dword ptr 4 .text:00541400 arg_4 = dword ptr 8 .text:00541400 Src = dword ptr 0Ch .text:00541400 .text:00541400 mov eax, [esp+Filename] .text:00541404 push ebx .text:00541405 push ebp .text:00541406 push esi .text:00541407 push edi .text:00541408 push offset aRb ; "rb" .text:0054140D push eax ; Filename .text:0054140E call _fopen .text:00541413 mov esi, eax .text:00541415 add esp, 8 .text:00541418 test esi, esi .text:0054141A jnz short loc_54142E .text:0054141C push offset aCannotOpenIn_0 ; "Cannot open input file!\n" .text:00541421 call _printf .text:00541426 add esp, 4 .text:00541429 pop edi .text:0054142A pop esi .text:0054142B pop ebp .text:0054142C pop ebx .text:0054142D retn .text:0054142E ; --------------------------------------------------------------------------- .text:0054142E .text:0054142E loc_54142E: ; CODE XREF: decrypt_file+1A .text:0054142E push 2 ; Origin .text:00541430 push 0 ; Offset .text:00541432 push esi ; File .text:00541433 call _fseek .text:00541438 push esi ; File .text:00541439 call _ftell .text:0054143E push 0 ; Origin .text:00541440 push 0 ; Offset .text:00541442 push esi ; File .text:00541443 mov ebp, eax .text:00541445 call _fseek .text:0054144A push ebp ; Size .text:0054144B call _malloc .text:00541450 push esi ; File .text:00541451 mov ebx, eax .text:00541453 push 1 ; Count .text:00541455 push ebp ; ElementSize .text:00541456 push ebx ; DstBuf .text:00541457 call _fread .text:0054145C push esi ; File .text:0054145D call _fclose
Check signature (first 3 bytes):
.text:00541462 add esp, 34h .text:00541465 mov ecx, 3 .text:0054146A mov edi, offset aQr9_0 ; "QR9" .text:0054146F mov esi, ebx .text:00541471 xor edx, edx .text:00541473 repe cmpsb .text:00541475 jz short loc_541489
Report an error:
.text:00541477 push offset aFileIsNotCrypt ; "File is not crypted!\n" .text:0054147C call _printf .text:00541481 add esp, 4 .text:00541484 pop edi .text:00541485 pop esi .text:00541486 pop ebp .text:00541487 pop ebx .text:00541488 retn .text:00541489 ; --------------------------------------------------------------------------- .text:00541489 .text:00541489 loc_541489: ; CODE XREF: decrypt_file+75
Call decrypt().
.text:00541489 mov eax, [esp+10h+Src] .text:0054148D mov edi, [ebx+3] .text:00541490 add ebp, 0FFFFFFF9h .text:00541493 lea esi, [ebx+7] .text:00541496 push eax ; Src .text:00541497 push ebp ; int .text:00541498 push esi ; int .text:00541499 call decrypt .text:0054149E mov ecx, [esp+1Ch+arg_4] .text:005414A2 push offset aWb_0 ; "wb" .text:005414A7 push ecx ; Filename .text:005414A8 call _fopen .text:005414AD mov ebp, eax .text:005414AF push ebp ; File .text:005414B0 push 1 ; Count .text:005414B2 push edi ; Size .text:005414B3 push esi ; Str .text:005414B4 call _fwrite .text:005414B9 push ebp ; File .text:005414BA call _fclose .text:005414BF push ebx ; Memory .text:005414C0 call _free .text:005414C5 add esp, 2Ch .text:005414C8 pop edi .text:005414C9 pop esi .text:005414CA pop ebp .text:005414CB pop ebx .text:005414CC retn .text:005414CC decrypt_file endp
Here is reconstructed C-code:
void decrypt_file(char *fin, char* fout, char *pw)
{
FILE *f;
int real_flen, flen;
BYTE *buf;
f=fopen(fin, "rb");
if (f==NULL)
{
printf ("Cannot open input file!\n");
return;
};
fseek (f, 0, SEEK_END);
flen=ftell (f);
fseek (f, 0, SEEK_SET);
buf=(BYTE*)malloc (flen);
fread (buf, flen, 1, f);
fclose (f);
if (memcmp (buf, "QR9", 3)!=0)
{
printf ("File is not crypted!\n");
return;
};
memcpy (&real_flen, buf+3, 4);
decrypt (buf+(3+4), flen-(3+4), pw);
f=fopen(fout, "wb");
fwrite (buf+(3+4), real_flen, 1, f);
fclose (f);
free (buf);
};
OK, now let's go deeper.
Function crypt():
.text:00541260 crypt proc near ; CODE XREF: crypt_file+8A .text:00541260 .text:00541260 arg_0 = dword ptr 4 .text:00541260 arg_4 = dword ptr 8 .text:00541260 arg_8 = dword ptr 0Ch .text:00541260 .text:00541260 push ebx .text:00541261 mov ebx, [esp+4+arg_0] .text:00541265 push ebp .text:00541266 push esi .text:00541267 push edi .text:00541268 xor ebp, ebp .text:0054126A .text:0054126A loc_54126A: ; CODE XREF: crypt+41
This piece of code copies part of input buffer to internal array "cube64". The size is in ECX register. MOVSD means "move 32-bit dword", so, 16 of 32-bit dwords are exactly 64 bytes.
.text:0054126A mov eax, [esp+10h+arg_8] .text:0054126E mov ecx, 10h .text:00541273 mov esi, ebx ; EBX is pointer within input buffer .text:00541275 mov edi, offset cube64 .text:0054127A push 1 .text:0054127C push eax .text:0054127D rep movsd
Call rotate_all_with_password():
.text:0054127F call rotate_all_with_password
Copy crypted contents back from cube64 to buffer:
.text:00541284 mov eax, [esp+18h+arg_4] .text:00541288 mov edi, ebx .text:0054128A add ebp, 40h .text:0054128D add esp, 8 .text:00541290 mov ecx, 10h .text:00541295 mov esi, offset cube64 .text:0054129A add ebx, 40h ; add 64 to input buffer pointer .text:0054129D cmp ebp, eax ; EBP contain ammount of crypted data. .text:0054129F rep movsd
If EBP is not bigger that input argument size, then continue to next block
.text:005412A1 jl short loc_54126A .text:005412A3 pop edi .text:005412A4 pop esi .text:005412A5 pop ebp .text:005412A6 pop ebx .text:005412A7 retn .text:005412A7 crypt endp
Reconstructed crypt() function:
void crypt (BYTE *buf, int sz, char *pw)
{
int i=0;
do
{
memcpy (cube, buf+i, 8*8);
rotate_all (pw, 1);
memcpy (buf+i, cube, 8*8);
i+=64;
}
while (i<sz);
};
OK, now let's go deeper into function rotate_all_with_password(). It takes two arguments: password string plus number. In crypt(), number 1 is used, and in decrypt() (where rotate_all_with_password() function is called too), number is 3.
.text:005411B0 rotate_all_with_password proc near ; CODE XREF: crypt+1F .text:005411B0 ; decrypt+36 .text:005411B0 .text:005411B0 arg_0 = dword ptr 4 .text:005411B0 arg_4 = dword ptr 8 .text:005411B0 .text:005411B0 mov eax, [esp+arg_0] .text:005411B4 push ebp .text:005411B5 mov ebp, eax
Check for character in password. If it is zero, exit:
.text:005411B7 cmp byte ptr [eax], 0 .text:005411BA jz exit .text:005411C0 push ebx .text:005411C1 mov ebx, [esp+8+arg_4] .text:005411C5 push esi .text:005411C6 push edi .text:005411C7 .text:005411C7 loop_begin: ; CODE XREF: rotate_all_with_password+9F
Call tolower(), standard C function.
.text:005411C7 movsx eax, byte ptr [ebp+0] .text:005411CB push eax ; C .text:005411CC call _tolower .text:005411D1 add esp, 4
Hmm, if password contains non-alphabetical character, it is skipped! Indeed, if we run crypting utility and try non-alphabetical characters, they seem to be ignored.
.text:005411D4 cmp al, 'a' .text:005411D6 jl short next_character_in_password .text:005411D8 cmp al, 'z' .text:005411DA jg short next_character_in_password .text:005411DC movsx ecx, al
Subtract "a" value (97) from character.
.text:005411DF sub ecx, 'a' ; 97
After subtracting, we'll get 0 for "a" here, 1 for "b", etc. And 25 for "z".
.text:005411E2 cmp ecx, 24 .text:005411E5 jle short skip_subtracting .text:005411E7 sub ecx, 24
It seems, "y" and "z" are problematic characters too. After that piece of code, "y" becomes 0 and "z" -- 1. This means, 26 latin alphabet symbols will become values in range 0..23, (24 in total).
.text:005411EA .text:005411EA skip_subtracting: ; CODE XREF: rotate_all_with_password+35
This is actually division via multiplication. Read more here:
http://blogs.msdn.com/b/devdev/archive/2005/12/12/502980.aspx
The code actually divides password character value by 3.
.text:005411EA mov eax, 55555556h .text:005411EF imul ecx .text:005411F1 mov eax, edx .text:005411F3 shr eax, 1Fh .text:005411F6 add edx, eax .text:005411F8 mov eax, ecx .text:005411FA mov esi, edx .text:005411FC mov ecx, 3 .text:00541201 cdq .text:00541202 idiv ecx
EDX is the remainder of division.
.text:00541204 sub edx, 0 .text:00541207 jz short call_rotate1 ; if remainder is zero, go to rotate1 .text:00541209 dec edx .text:0054120A jz short call_rotate2 ; .. it it is 1, go to rotate2 .text:0054120C dec edx .text:0054120D jnz short next_character_in_password .text:0054120F test ebx, ebx .text:00541211 jle short next_character_in_password .text:00541213 mov edi, ebx .text:00541215
Remainder is 2, call rotate3. EDI is a second argument of rotate_all_with_password(). As I already wrote, 1 is for crypting operations and 3 is for decrypting. So, here is a loop. When crypting, rotate1/2/3 will be called the same number of times as given in the first argument.
.text:00541215 call_rotate3: ; CODE XREF: rotate_all_with_password+6F .text:00541215 push esi .text:00541216 call rotate3 .text:0054121B add esp, 4 .text:0054121E dec edi .text:0054121F jnz short call_rotate3 .text:00541221 jmp short next_character_in_password .text:00541223 ; --------------------------------------------------------------------------- .text:00541223 .text:00541223 call_rotate2: ; CODE XREF: rotate_all_with_password+5A .text:00541223 test ebx, ebx .text:00541225 jle short next_character_in_password .text:00541227 mov edi, ebx .text:00541229 .text:00541229 loc_541229: ; CODE XREF: rotate_all_with_password+83 .text:00541229 push esi .text:0054122A call rotate2 .text:0054122F add esp, 4 .text:00541232 dec edi .text:00541233 jnz short loc_541229 .text:00541235 jmp short next_character_in_password .text:00541237 ; --------------------------------------------------------------------------- .text:00541237 .text:00541237 call_rotate1: ; CODE XREF: rotate_all_with_password+57 .text:00541237 test ebx, ebx .text:00541239 jle short next_character_in_password .text:0054123B mov edi, ebx .text:0054123D .text:0054123D loc_54123D: ; CODE XREF: rotate_all_with_password+97 .text:0054123D push esi .text:0054123E call rotate1 .text:00541243 add esp, 4 .text:00541246 dec edi .text:00541247 jnz short loc_54123D .text:00541249
Fetch next characted from password string.
.text:00541249 next_character_in_password: ; CODE XREF: rotate_all_with_password+26 .text:00541249 ; rotate_all_with_password+2A ... .text:00541249 mov al, [ebp+1]
Increment character pointer within password string:
.text:0054124C inc ebp .text:0054124D test al, al .text:0054124F jnz loop_begin .text:00541255 pop edi .text:00541256 pop esi .text:00541257 pop ebx .text:00541258 .text:00541258 exit: ; CODE XREF: rotate_all_with_password+A .text:00541258 pop ebp .text:00541259 retn .text:00541259 rotate_all_with_password endp
Here is reconstructed C code:
void rotate_all (char *pwd, int v)
{
char *p=pwd;
while (*p)
{
char c=*p;
int q;
c=tolower (c);
if (c>='a' && c<='z')
{
q=c-'a';
if (q>24)
q-=24;
int quotient=q/3;
int remainder=q % 3;
switch (remainder)
{
case 0: for (int i=0; i<v; i++) rotate1 (quotient); break;
case 1: for (int i=0; i<v; i++) rotate2 (quotient); break;
case 2: for (int i=0; i<v; i++) rotate3 (quotient); break;
};
};
p++;
};
};
Now let's go deeper and investigate rotate1/2/3 functions. Each function calls two another functions. I gave them names "set_bit" and "get_bit".
Let's start with "get_bit":
.text:00541050 get_bit proc near ; CODE XREF: rotate1+16 .text:00541050 ; rotate2+16 ... .text:00541050 .text:00541050 arg_0 = dword ptr 4 .text:00541050 arg_4 = dword ptr 8 .text:00541050 arg_8 = byte ptr 0Ch .text:00541050 .text:00541050 mov eax, [esp+arg_4] .text:00541054 mov ecx, [esp+arg_0] .text:00541058 mov al, cube64[eax+ecx*8] .text:0054105F mov cl, [esp+arg_8] .text:00541063 shr al, cl .text:00541065 and al, 1 .text:00541067 retn .text:00541067 get_bit endp
... in other words: calculate an index in the array cube64: arg_4 + arg_0 * 8. Then shift a byte from an array by arg_8 bits right. Isolate lowest bit and return it.
Let's see another function, "set_bit":
.text:00541000 set_bit proc near ; CODE XREF: rotate1+42 .text:00541000 ; rotate2+42 ... .text:00541000 .text:00541000 arg_0 = dword ptr 4 .text:00541000 arg_4 = dword ptr 8 .text:00541000 arg_8 = dword ptr 0Ch .text:00541000 arg_C = byte ptr 10h .text:00541000 .text:00541000 mov al, [esp+arg_C] .text:00541004 mov ecx, [esp+arg_8] .text:00541008 push esi .text:00541009 mov esi, [esp+4+arg_0] .text:0054100D test al, al .text:0054100F mov eax, [esp+4+arg_4] .text:00541013 mov dl, 1 .text:00541015 jz short loc_54102B
DL is 1 here. Shift left it by arg_8. For example, if arg_8 is 4, DL register value became 0x10 or 1000 in binary form.
.text:00541017 shl dl, cl .text:00541019 mov cl, cube64[eax+esi*8]
Get bit from array and explicitly set one.
.text:00541020 or cl, dl
Store it back:
.text:00541022 mov cube64[eax+esi*8], cl .text:00541029 pop esi .text:0054102A retn .text:0054102B ; --------------------------------------------------------------------------- .text:0054102B .text:0054102B loc_54102B: ; CODE XREF: set_bit+15 .text:0054102B shl dl, cl
If arg_C is not zero...
.text:0054102D mov cl, cube64[eax+esi*8]
... invert DL. For example, if DL state after shift was 0x10 or 1000 in binary form, there will be 0xEF after NOT instruction or 11101111 in binary form.
.text:00541034 not dl
This instruction clears bit, in other words, it saves all bits in CL which are also set in DL except those in DL which are cleared. This means that if DL is, for example, 11101111 in binary form, all bits will be saved except 5th (counting from lowest bit).
.text:00541036 and cl, dl
Store it back:
.text:00541038 mov cube64[eax+esi*8], cl .text:0054103F pop esi .text:00541040 retn .text:00541040 set_bit endp
It is almost the same as get_bit(), except, if arg_C is zero, the function clears specific bit in array, or sets it otherwise.
We also know that array size is 64. First two arguments both in set_bit() and get_bit() could be seen as 2D cooridnates. Then array will be 8*8 matrix.
Here is C representation of what we already know:
#define IS_SET(flag, bit) ((flag) & (bit))
#define SET_BIT(var, bit) ((var) |= (bit))
#define REMOVE_BIT(var, bit) ((var) &= ~(bit))
char cube[8][8];
void set_bit (int x, int y, int shift, int bit)
{
if (bit)
SET_BIT (cube[x][y], 1<<shift);
else
REMOVE_BIT (cube[x][y], 1<<shift);
};
int get_bit (int x, int y, int shift)
{
if ((cube[x][y]>>shift)&1==1)
return 1;
return 0;
};
Now let's get back to rotate1/2/3 functions.
.text:00541070 rotate1 proc near ; CODE XREF: rotate_all_with_password+8E .text:00541070
Internal array allocation, its size 64 bytes:
.text:00541070 internal_array_64= byte ptr -40h .text:00541070 arg_0 = dword ptr 4 .text:00541070 .text:00541070 sub esp, 40h .text:00541073 push ebx .text:00541074 push ebp .text:00541075 mov ebp, [esp+48h+arg_0] .text:00541079 push esi .text:0054107A push edi .text:0054107B xor edi, edi ; EDI is loop1 counter
EBX is a pointer to internal array:
.text:0054107D lea ebx, [esp+50h+internal_array_64] .text:00541081
Two nested loops are here:
.text:00541081 first_loop1_begin: ; CODE XREF: rotate1+2E .text:00541081 xor esi, esi ; ESI is loop2 counter .text:00541083 .text:00541083 first_loop2_begin: ; CODE XREF: rotate1+25 .text:00541083 push ebp ; arg_0 .text:00541084 push esi ; loop1 counter .text:00541085 push edi ; loop2 counter .text:00541086 call get_bit .text:0054108B add esp, 0Ch .text:0054108E mov [ebx+esi], al ; store to internal array .text:00541091 inc esi ; increment loop1 counter .text:00541092 cmp esi, 8 .text:00541095 jl short first_loop2_begin .text:00541097 inc edi ; increment loop2 counter .text:00541098 add ebx, 8 ; increment internal array pointer by 8 at each loop1 iteration .text:0054109B cmp edi, 8 .text:0054109E jl short first_loop1_begin
... we see that both loop counters are in range 0..7. Also, they are used as first and second arguments of get_bit(). Third argument of get_bit() is the only argument of rotate1(). What get_bit() returns, is being placed into internal array.
Prepare pointer to internal array again:
.text:005410A0 lea ebx, [esp+50h+internal_array_64] .text:005410A4 mov edi, 7 ; EDI is loop1 counter, initial state is 7 .text:005410A9 .text:005410A9 second_loop1_begin: ; CODE XREF: rotate1+57 .text:005410A9 xor esi, esi ; ESI is loop2 counter .text:005410AB .text:005410AB second_loop2_begin: ; CODE XREF: rotate1+4E .text:005410AB mov al, [ebx+esi] ; value from internal array .text:005410AE push eax .text:005410AF push ebp ; arg_0 .text:005410B0 push edi ; loop1 counter .text:005410B1 push esi ; loop2 counter .text:005410B2 call set_bit .text:005410B7 add esp, 10h .text:005410BA inc esi ; increment loop2 counter .text:005410BB cmp esi, 8 .text:005410BE jl short second_loop2_begin .text:005410C0 dec edi ; decrement loop2 counter .text:005410C1 add ebx, 8 ; increment internal array pointer .text:005410C4 cmp edi, 0FFFFFFFFh .text:005410C7 jg short second_loop1_begin .text:005410C9 pop edi .text:005410CA pop esi .text:005410CB pop ebp .text:005410CC pop ebx .text:005410CD add esp, 40h .text:005410D0 retn .text:005410D0 rotate1 endp
... this code is placing contents from internal array to cube global array via set_bit() function, BUT, in different order! Now loop1 counter is in range 7 to 0, decrementing at each iteration!
C code representation looks like:
void rotate1 (int v)
{
bool tmp[8][8]; // internal array
int i, j;
for (i=0; i<8; i++)
for (j=0; j<8; j++)
tmp[i][j]=get_bit (i, j, v);
for (i=0; i<8; i++)
for (j=0; j<8; j++)
set_bit (j, 7-i, v, tmp[x][y]);
};
Not very understandable, except if we will take a look at rotate2 function:
.text:005410E0 rotate2 proc near ; CODE XREF: rotate_all_with_password+7A .text:005410E0 .text:005410E0 internal_array_64= byte ptr -40h .text:005410E0 arg_0 = dword ptr 4 .text:005410E0 .text:005410E0 sub esp, 40h .text:005410E3 push ebx .text:005410E4 push ebp .text:005410E5 mov ebp, [esp+48h+arg_0] .text:005410E9 push esi .text:005410EA push edi .text:005410EB xor edi, edi ; loop1 counter .text:005410ED lea ebx, [esp+50h+internal_array_64] .text:005410F1 .text:005410F1 loc_5410F1: ; CODE XREF: rotate2+2E .text:005410F1 xor esi, esi ; loop2 counter .text:005410F3 .text:005410F3 loc_5410F3: ; CODE XREF: rotate2+25 .text:005410F3 push esi ; loop2 .text:005410F4 push edi ; loop1 .text:005410F5 push ebp ; arg_0 .text:005410F6 call get_bit .text:005410FB add esp, 0Ch .text:005410FE mov [ebx+esi], al ; store to internal array .text:00541101 inc esi ; increment loop1 counter .text:00541102 cmp esi, 8 .text:00541105 jl short loc_5410F3 .text:00541107 inc edi ; increment loop2 counter .text:00541108 add ebx, 8 .text:0054110B cmp edi, 8 .text:0054110E jl short loc_5410F1 .text:00541110 lea ebx, [esp+50h+internal_array_64] .text:00541114 mov edi, 7 ; loop1 counter is initial state 7 .text:00541119 .text:00541119 loc_541119: ; CODE XREF: rotate2+57 .text:00541119 xor esi, esi ; loop2 counter .text:0054111B .text:0054111B loc_54111B: ; CODE XREF: rotate2+4E .text:0054111B mov al, [ebx+esi] ; get byte from internal array .text:0054111E push eax .text:0054111F push edi ; loop1 counter .text:00541120 push esi ; loop2 counter .text:00541121 push ebp ; arg_0 .text:00541122 call set_bit .text:00541127 add esp, 10h .text:0054112A inc esi ; increment loop2 counter .text:0054112B cmp esi, 8 .text:0054112E jl short loc_54111B .text:00541130 dec edi ; decrement loop2 counter .text:00541131 add ebx, 8 .text:00541134 cmp edi, 0FFFFFFFFh .text:00541137 jg short loc_541119 .text:00541139 pop edi .text:0054113A pop esi .text:0054113B pop ebp .text:0054113C pop ebx .text:0054113D add esp, 40h .text:00541140 retn .text:00541140 rotate2 endp
It is *almost* the same, except of order of arguments of get_bit() and set_bit(). Let's rewrite it in C-like code:
void rotate2 (int v)
{
bool tmp[8][8]; // internal array
int i, j;
for (i=0; i<8; i++)
for (j=0; j<8; j++)
tmp[i][j]=get_bit (v, i, j);
for (i=0; i<8; i++)
for (j=0; j<8; j++)
set_bit (v, j, 7-i, tmp[i][j]);
};
Let's also rewrite rotate3 function:
void rotate3 (int v)
{
bool tmp[8][8];
int i, j;
for (i=0; i<8; i++)
for (j=0; j<8; j++)
tmp[i][j]=get_bit (i, v, j);
for (i=0; i<8; i++)
for (j=0; j<8; j++)
set_bit (7-j, v, i, tmp[i][j]);
};
Well, now things are simpler. If we consider cube64 as 3D cube 8*8*8, where each element is bit, get_bit and set_bit take just coordinates of bit.
rotate1/2/3 functions are in fact rotating all bits in specific plane. Three functions are each for each cube side and v argument is setting plane in range 0..7.
Maybe, algorithm's author was thinking of 8*8*8 Rubik's cube?!
Yes, indeed.
Let's get closer into decrypt() function, I rewrote it here:
void decrypt (BYTE *buf, int sz, char *pw)
{
char *p=strdup (pw);
strrev (p);
int i=0;
do
{
memcpy (cube, buf+i, 8*8);
rotate_all (p, 3);
memcpy (buf+i, cube, 8*8);
i+=64;
}
while (i<sz);
free (p);
};
It is almost the same excert of crypt(), BUT password string is reversed by strrev() standard C function and rotate_all is called with argument 3. This means, that each corresponding rotate1/2/3 call will be performed thrice. This is almost as in Rubik'c cube! If you want to get back, do the same in reverse order and direction! Rotating one plane in clockwise direction is the same effect as rotating it in counter-clockwise direction thrice.
rotate1() is probably for rotating "front" plane. rotate2() is probably for rotating "top" plane. rotate3() is probably for rotating "left" plane.
Let's get back to core of rotate_all() function:
q=c-'a';
if (q>24)
q-=24;
int quotient=q/3; // in range 0..7
int remainder=q % 3;
switch (remainder)
{
case 0: for (int i=0; i<v; i++) rotate1 (quotient); break; // front
case 1: for (int i=0; i<v; i++) rotate2 (quotient); break; // top
case 2: for (int i=0; i<v; i++) rotate3 (quotient); break; // left
};
Now it is much simpler to understand: each password character defines side (one of three) and plane (one of 8). 3*8 = 24, that's why two last characters of latin alphabet are remapped to fit an alphabet of exactly 24 elements.
The algorithm is clearly weak: in case of short passwords, one can see, that in crypted file there are some original bytes of original file in hex editor.
Here is reconstructed whole source code:
qr9.cppHere is also IDA exported listing from original crypting utility: qr9_original.lst
Need a reverse engineering like this? -> dennis@conus.info