Re: Little alogorithm brute-force problem ... help plz!
From: dimitri (fr1c@aris.ffk.hr)
Date: 01/30/03
- Next message: Mads Rasmussen: "visual cryptography - was - Re: So how is this kind of crypto classified?"
- Previous message: Roberto Gallo: "Random Generator on Hardware"
- In reply to: dimitri: "Little alogorithm brute-force problem ... help plz!"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
From: "dimitri" <fr1c@aris.ffk.hr> Date: Thu, 30 Jan 2003 19:15:45 +0100
plz! anyone ?
:-)
"dimitri" <fr1c@aris.ffk.hr> wrote in message
news:b13i0q$d9ts$1@as201.hinet.hr...
> Sorry for long text ... but i hope someone will check it out.
>
>
> Lil'
> cryto-breaking problem !
>
> - dimitri
>
>
>
> While i was reversing some program, i found interesting keyfile algorithm.
> Ofcourse, i've patched program and it's working... but, i wanted to
'crack'
> the algorithm. There is no problem understanding it, just problems with
> 'reconstructing' right keyfile. (NOTE : here is no LAW-BREAKING cuz this
> software isnt protected by copyright or anything, it's just program for
> practise (CrackMe or if u like better, ReverseMe )!!)
>
> Anyway, i've seen algorithm and i dont really see way to reverse it, only
> brute force it. If someone don't agree with me, plz, send me reversed
> algorithm, i'll be happy to see it!
>
>
>
> Ok, keyfile is divided in 2 parts, but yet connected in calculations!
>
>
>
> It looks like this :
>
>
>
> 4B65 7950 6172 7431 004B 6579 5061 7274
> KeyPart1.KeyPart
>
> 3200 0000 0000 0000 0000 0000
> 2...........
>
>
>
> So, we see : KeyPart1 - First part of key.
>
> 0h
>
> KeyPart2 - Second part of key
>
> 0h
>
>
>
> First, there is lil' algorithm for KeyPart1.
>
> There is loop and math operations on every byte of KeyPart1 until the end
> (00h).
>
> Every result for every byte is added in ECX (let's say buffer).
>
> This simple algorithm looks like this :
>
>
>
> /+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
>
> xor ecx, ecx
>
> mov esi, offset KeyPart1
>
>
>
> LoopAgain1: ; CODE XREF:
> MainKeyRoutine+38_j
>
> xor eax, eax
>
> lodsb
>
> test al, al
>
> jz short loc_0_40131C
>
> shl eax, 1
>
> rol eax, 1
>
> sub eax, 1Eh
>
> ror eax, 2
>
> sub eax, 1Fh
>
> xor eax, 20h
>
> shr eax, 2
>
> ror eax, 2
>
> sub eax, 44454144h
>
> add eax, 42454546h
>
> shr eax, 18h
>
> xor ah, al
>
> shr eax, 4
>
> add ecx, eax
>
> jmp short LoopAgain1
>
>
>
> loc_0_40131C: ; CODE XREF:
> MainKeyRoutine+C_j
>
> xor ecx, 0DEADh
>
> and cx, 0BEEFh
>
> /++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
>
>
>
> I think i dont need to comment assembler instructions since this is
advanced
> l33t group :-)
>
> After this, we are calculating sum of all chars (only KeyPart1).
>
> Assembler code looks like this :
>
>
>
> /++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
>
> mov esi, offset KeyPart1
>
> xor edi, edi
>
>
>
> LoopAgain2: ; CODE XREF:
> MainKeyRoutine+55_j
>
> xor eax, eax
>
> lodsb
>
> test al, al
>
> jz short loc_0_401339
>
> add edi, eax
>
> jmp short LoopAgain2
>
>
>
> loc_0_401339: ; CODE XREF:
> MainKeyRoutine+51_j
>
> /+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
>
>
>
> After that, we got SumOfCharsInKeyPart1 * ValueWeGotInFirstAlgorithmAbove.
>
> Than CALL to KeyRoutine2 (which i think we can skip while cracking it
?)...
>
> ...
>
> ...
>
> And on the end, our value must be equal to 17FE23FAh.
>
> So, this is CRC-like protection :-))
>
>
>
> Anyway, i wanted to get some responses and help on what could i do ...
>
> Since i said that i think it can't be reversed, i tried to brute force
it...
>
> Just, problem is it's divided in 2 parts, which are connected in
> algorithms...
>
> It's little bit more complex...
>
> So, i tried to code a brute force (with ripped algorithm (inline asm in
C)).
>
> Since my skills aren't big enought to code right algorithm for creating
> every possible combinations, i need help.
>
> I'm not crypto nor math guru, but, i'm learning ...
>
> I've coded some lame algorithm and i let it 'cracking' for some time, but,
> no result, so i terminated it ...
>
> And while thinking more about it, i know my approach is wrong, but can't
> find the right one.
>
> So, plz guys, help me ...
>
> Any idea, solution even question (?!) :) (but with explanation plz, i
wanna
> understand it) would be great!
>
>
>
> Below is whole (it's very little, so, plz, check it out) algorithm, and
> commented important stuff.
>
>
>
>
>
> Respect,
>
> dimitri
>
>
>
> --------
>
>
>
>
>
> MainKeyRoutine proc near ; CODE XREF:
sub_0_4011DD+3B_p
>
> xor ecx, ecx
>
> mov esi, offset KeyPart1
>
>
>
> LoopAgain1: ; CODE XREF:
> MainKeyRoutine+38_j
>
> xor eax, eax
>
> lodsb
>
> test al, al
>
> jz short NextStep1
>
> shl eax, 1
>
> rol eax, 1
>
> sub eax, 1Eh
>
> ror eax, 2
>
> sub eax, 1Fh
>
> xor eax, 20h
>
> shr eax, 2
>
> ror eax, 2
>
> sub eax, 44454144h
>
> add eax, 42454546h
>
> shr eax, 18h
>
> xor ah, al
>
> shr eax, 4
>
> add ecx, eax ; Save calculated
>
> jmp short LoopAgain1
>
> ;
>
???????????????????????????????????????????????????????????????????????????
>
>
>
> NextStep1: ; CODE XREF:
> MainKeyRoutine+C_j
>
> xor ecx, 0DEADh
>
> and cx, 0BEEFh
>
> mov esi, offset KeyPart1
>
> xor edi, edi
>
>
>
> LoopAgain2: ; CODE XREF:
> MainKeyRoutine+55_j
>
> xor eax, eax
>
> lodsb
>
> test al, al
>
> jz short NextStep2
>
> add edi, eax ; Sum all chars
>
> jmp short LoopAgain2
>
> ;
>
???????????????????????????????????????????????????????????????????????????
>
>
>
> NextStep2: ; CODE XREF:
> MainKeyRoutine+51_j
>
> imul ecx, edi
>
> mov LenMulPart1, ecx
>
> push offset KeyPart2
>
> call KeyRoutine2
>
> mov KeyRoutine2Val, eax
>
> mov esi, offset KeyPart2
>
> xor edx, edx
>
> inc edx
>
>
>
> LoopAgain3: ; CODE XREF:
> MainKeyRoutine+81_j
>
> xor eax, eax
>
> lodsb
>
> test al, al
>
> jz short NextStep3
>
> imul edx, eax
>
> jmp short LoopAgain3
>
> ;
>
???????????????????????????????????????????????????????????????????????????
>
>
>
> NextStep3: ; CODE XREF:
> MainKeyRoutine+7C_j
>
> mov eax, KeyRoutine2Val
>
> sub edx, eax
>
> sub edx, LenMulPart1
>
> push edx
>
> pop eax
>
> xor edx, edx
>
> mov edx, 0DEADh
>
> idiv eax
>
> mov ecx, edx
>
> xor edx, edx
>
> mov edx, 0BEEFh
>
> idiv eax
>
> sub ecx, edx ; ECX must contain
> 17FE23FAh after this!
>
> cmp ecx, 17FE23FAh ; Is our
> key same as this value ?
>
> jnz short BadKeyfile
>
> mov KeyStatus, 3 ; 3 means GoodKey
> status!
>
> jmp short ValidKeyFile
>
> ;
>
???????????????????????????????????????????????????????????????????????????
>
>
>
> BadKeyfile: ; CODE XREF:
> MainKeyRoutine+AE_j
>
> mov KeyStatus, 2 ; 2 means BadKey
> message!
>
>
>
> ValidKeyFile: ; CODE XREF:
> MainKeyRoutine+BA_j
>
> retn
>
> MainKeyRoutine endp
>
>
>
>
>
> ;
>
???????????????????????????????????????????????????????????????????????????
>
>
>
> ; S u b r o u t i n e
>
> ; Attributes: bp-based frame
>
>
>
> KeyRoutine2 proc near ; CODE XREF:
> MainKeyRoutine+65_p
>
>
>
> arg_0 = dword ptr 8
>
>
>
> push ebp
>
> mov ebp, esp
>
> push ebx
>
> push esi
>
> push edi
>
> mov edi, [ebp+arg_0] ; Points to
> KeyPart2!
>
> mov esi, [ebp+arg_0] ; Same as above!
>
> lea ecx, [ecx+0]
>
>
>
> loc_0_4013B8: ; CODE XREF:
> KeyRoutine2+14_j
>
> mov al, [edi]
>
> inc edi
>
> or al, al
>
> jnz short loc_0_4013B8
>
> sub esi, edi
>
> xor ebx, ebx
>
> add edi, esi
>
> xor edx, edx
>
> not esi
>
> jmp short loc_0_4013EE
>
> ;
>
???????????????????????????????????????????????????????????????????????????
>
>
>
> loc_0_4013CB: ; CODE XREF:
> KeyRoutine2+47_j
>
> mov al, [edi]
>
> cmp al, 41h
>
> jb short loc_0_4013DD
>
> sub al, 57h
>
> adc dl, 0
>
> shl dl, 5
>
> add al, dl
>
> jmp short loc_0_4013DF
>
> ;
>
???????????????????????????????????????????????????????????????????????????
>
>
>
> loc_0_4013DD: ; CODE XREF:
> KeyRoutine2+26_j
>
> sub al, 30h
>
>
>
> loc_0_4013DF: ; CODE XREF:
> KeyRoutine2+32_j
>
> lea ecx, [esi-1]
>
> and eax, 0Fh
>
> shl ecx, 2
>
> shl eax, cl
>
> add ebx, eax
>
> inc edi
>
> dec esi
>
>
>
> loc_0_4013EE: ; CODE XREF:
> KeyRoutine2+20_j
>
> or esi, esi
>
> jnz short loc_0_4013CB
>
> mov eax, ebx
>
> pop edi
>
> pop esi
>
> pop ebx
>
> leave
>
> retn 4
>
> KeyRoutine2 endp
>
>
>
- Next message: Mads Rasmussen: "visual cryptography - was - Re: So how is this kind of crypto classified?"
- Previous message: Roberto Gallo: "Random Generator on Hardware"
- In reply to: dimitri: "Little alogorithm brute-force problem ... help plz!"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
