Cracking an Elgamal KeygenMe

I'm not really familiar with elgamal so i've asked a friend to make me a KeygenMe as exercise.
After lurking on Efnet, reading solutions about elgamal defeating, talking with guys of team iNFECTiON etc... I've got the idea to write (finaly?) a lame solution on my blog.

The keygenme can be found here: download - download 2
MD5: 6b4a6008e235d8f6225aeeb359077a57

Let's start by a Right Click>Searh for>All referenced text strings

We have a suit of numbers and two strings Good Work/Bad Serial
We also see an  'Edit2Change' and 'Edit1Change' (Delphi powered)
Double click on Edit2Change and follow the jump at the top

Take a breakpoint at the begining

By scanning the KeygenMe with KANAL or Keygener Assistant, he will detect some FGint (Fast Gigantic Integers) possibly used by Elgamal.

For get a better view on this, we will load the keygenme in IDA with the FGInt signatures package.

Jump to 00456DB0 on IDA
We see two GetText call and just after another call, let's check.

Push Tabulation for view the Pseudocode

Good:

Elgamal_Verify(v12, v14, v13, &v11, &v10, &v9, &v7);

Alright, make a MAP file for the godup plugin of ollydbg
File>Produce file>Create MAP file

 Then load your MAP file in olly (Load labels/Load comments)

Remove the breakpoint in Olly and run the target (F9)
Complete the fields name/serial re-take your breakpoint and enter something in the serial input for breal again.

So we continue to F8 until we reach CALL 00456B84

00456DEA  |.  E8 95FDFFFF   CALL 00456B84

Not better with comments? :)
Press F7 to follow the procedure

Continue with F8 and see this jump:

It send us directly under the Good Work maybe we have made something wrong.
So let's rebreak again and follow the procedure before the Jump if Equal (JE)
We can see the KeygenMe look for a dash '-' (2D) in the serial field, the format should be something like: AAAA-BBBB

Add a dash to your serial and retry, this time we don't take the jump, and we go in the Elgamal part.

Just before the intergers we have a CALL, it will calc the CRC32 of your name

00456C5D  |.  E8 36D2FFFF   CALL 00453E98  ; 

(You can see the result on the stack when out, 4E0E9CF5 for Xylitol)

Who after is converted to fgint and checked

00456C8F  |.  E8 00D6FFFF   CALL 00454294  ;
You can view your crc32 in eax, and converted to fgint at:
00456C9A  |.  E8 F1D8FFFF   CALL 00454590  ; 

Well, we have these base 10 numbers:
P = 54042131087723322023
G = 1302299722409787264
Y = 41067336953420739677

Now we need to solve the DLP (discrete logarithm problem)
You can find the solution here: http://en.wikipedia.org/wiki/ElGamal_signature_scheme
y = g^x mod p
p is a prime number, x and g are less than p, where x is the private key
Then choose a random number k, such that k is relative prime to p-1

For get x we can use Magma calc: http://magma.maths.usyd.edu.au/calc/

p := 54042131087723322023;
K := GF(p);
g := K ! 1302299722409787264;
y := K ! 41067336953420739677;
x :=  Log(g, y);
x;

We get the result: 37134730343699938001

Ident of the pseudocode in IDA:

Now all is clear, we need to just code the keygen using the elgamal signature generation algorithm.
r-s (signature) are the serial parts
We have m, x, p and also from Wikipedia the formula r=g^k mod p then s=(m-x*r)*k^-1 mod p-1

Alright, here is my keygen using the Drizz's BigNum lib:

;Xyl2k :þ
;QOTD: windows calculator sux!
.586
.model  flat, stdcall
option  casemap :none

include     keygen.inc
include     crc32.asm
include     algo.asm

.code
start:
    invoke  GetModuleHandle, NULL
    mov hInstance, eax
    invoke  DialogBoxParam, hInstance, IDD_MAIN, 0, offset DlgProc, 0
    invoke  ExitProcess, eax
    invoke  InitCommonControls

DlgProc proc uses esi edi hWnd:DWORD,uMsg:DWORD,wParam:DWORD,lParam:DWORD
    mov eax,uMsg

    .if eax == WM_INITDIALOG
        invoke  LoadIcon,hInstance,200
        invoke  SendMessage, hWnd, WM_SETICON, 1, eax
    .elseif eax == WM_COMMAND
        mov eax,wParam
        .if eax == IDB_EXIT
            invoke  SendMessage, hWnd, WM_CLOSE, 0, 0
        .elseif eax == IDB_GENERATE
            invoke  Generate,hWnd
            invoke  Clean
        .endif
    .elseif eax == WM_CLOSE
        invoke  EndDialog, hWnd, 0
    .endif
    xor eax,eax
    ret
DlgProc endp
end start

algo.asm:

include bignum.inc
includelib  bignum.lib

Generate    PROTO   :HWND
HexToChar   PROTO   :DWORD,:DWORD,:DWORD
Clean       PROTO

.data
szName      db  100h    dup(?)
szSerial    db  100h    dup(?)
Message     dd  20h     dup(?)
hash        dd  20h     dup(?)
SerPart1    db  30h     dup(?)
SerPart2    db  30h     dup(?)

.code
Generate    Proc    hWnd:HWND
LOCAL   P,G,X,R,S,M,KRND:DWORD
    pushad
    invoke bnInit,128
    bnCreateX P,G,X,R,S,M,KRND
   
    invoke  GetDlgItemText,hWnd,IDC_NAME,addr szName,sizeof szName
    .if eax <= 2
        invoke  SetDlgItemText,hWnd,IDC_SERIAL,chr$('Type more chars!')
    .elseif eax >= 50
        invoke  SetDlgItemText,hWnd,IDC_SERIAL,chr$('Type less chars!')
    .elseif
        invoke  CRC32,addr szName,eax,0
        bswap eax
        mov dword ptr hash,eax
        invoke  HexToChar,addr hash,addr Message,4
        invoke  bnFromHex,addr Message,M
        invoke  bnFromHex,chr$('2EDFC37E594D7DAA7'),P
        invoke  bnFromHex,chr$('1212B2B299533F80'),G
        invoke  bnFromHex,chr$('20359107FD6277AD1'),X
        invoke  bnRsaGenPrime,KRND,32
        invoke  bnModExp,G,KRND,P,R
        invoke  bnDec,P
        invoke  bnModInv,KRND,P,KRND
        invoke  bnAdd,M,P
        invoke  bnMul,X,R,S
        invoke  bnMod,S,P,S
        invoke  bnSub,M,S
        invoke  bnMod,M,P,M
        invoke  bnMul,M,KRND,S
        invoke  bnMod,S,P,S
        invoke  bnInc,P
        invoke  bnToStr,R,addr SerPart1
        invoke  bnToStr,S,addr SerPart2
        invoke  lstrcat,addr szSerial,addr SerPart1
        invoke  lstrcat,addr szSerial,chr$('-')
        invoke  lstrcat,addr szSerial,addr SerPart2
        invoke  SetDlgItemText,hWnd,IDC_SERIAL,addr szSerial
    .endif

    bnDestroyX
    invoke bnFinish
    popad
    Ret
Generate endp
HexToChar Proc HexValue:DWORD,CharValue:DWORD,HexLength:DWORD
    mov esi,[ebp+8]
    mov edi,[ebp+0Ch]
    mov ecx,[ebp+10h]
    @HexToChar:
    lodsb
    mov ah, al
    and ah, 0fh
    shr al, 4
    add al, '0'
    add ah, '0'
    .if al > '9'
    add al, 'A'-'9'-1
    .endif
    .if ah > '9'
    add ah, 'A'-'9'-1
    .endif
    stosw
    loopd @HexToChar
    Ret
HexToChar endp
Clean   Proc
    invoke  RtlZeroMemory,addr szName,sizeof szName
    invoke  RtlZeroMemory,addr szSerial,sizeof szSerial
    invoke  RtlZeroMemory,addr Message,sizeof Message
    invoke  RtlZeroMemory,addr hash,sizeof hash
    invoke  RtlZeroMemory,addr SerPart1,sizeof SerPart1
    invoke  RtlZeroMemory,addr SerPart2,sizeof SerPart2
    Ret
Clean endp

crc32.asm:

.data
CRC32Table dd 000000000h, 077073096h, 0EE0E612Ch, 0990951BAh, 0076DC419h, 0706AF48Fh, 0E963A535h, 09E6495A3h
dd 00EDB8832h, 079DCB8A4h, 0E0D5E91Eh, 097D2D988h, 009B64C2Bh, 07EB17CBDh, 0E7B82D07h, 090BF1D91h
dd 01DB71064h, 06AB020F2h, 0F3B97148h, 084BE41DEh, 01ADAD47Dh, 06DDDE4EBh, 0F4D4B551h, 083D385C7h
dd 0136C9856h, 0646BA8C0h, 0FD62F97Ah, 08A65C9ECh, 014015C4Fh, 063066CD9h, 0FA0F3D63h, 08D080DF5h
dd 03B6E20C8h, 04C69105Eh, 0D56041E4h, 0A2677172h, 03C03E4D1h, 04B04D447h, 0D20D85FDh, 0A50AB56Bh
dd 035B5A8FAh, 042B2986Ch, 0DBBBC9D6h, 0ACBCF940h, 032D86CE3h, 045DF5C75h, 0DCD60DCFh, 0ABD13D59h
dd 026D930ACh, 051DE003Ah, 0C8D75180h, 0BFD06116h, 021B4F4B5h, 056B3C423h, 0CFBA9599h, 0B8BDA50Fh
dd 02802B89Eh, 05F058808h, 0C60CD9B2h, 0B10BE924h, 02F6F7C87h, 058684C11h, 0C1611DABh, 0B6662D3Dh
dd 076DC4190h, 001DB7106h, 098D220BCh, 0EFD5102Ah, 071B18589h, 006B6B51Fh, 09FBFE4A5h, 0E8B8D433h
dd 07807C9A2h, 00F00F934h, 09609A88Eh, 0E10E9818h, 07F6A0DBBh, 0086D3D2Dh, 091646C97h, 0E6635C01h
dd 06B6B51F4h, 01C6C6162h, 0856530D8h, 0F262004Eh, 06C0695EDh, 01B01A57Bh, 08208F4C1h, 0F50FC457h
dd 065B0D9C6h, 012B7E950h, 08BBEB8EAh, 0FCB9887Ch, 062DD1DDFh, 015DA2D49h, 08CD37CF3h, 0FBD44C65h
dd 04DB26158h, 03AB551CEh, 0A3BC0074h, 0D4BB30E2h, 04ADFA541h, 03DD895D7h, 0A4D1C46Dh, 0D3D6F4FBh
dd 04369E96Ah, 0346ED9FCh, 0AD678846h, 0DA60B8D0h, 044042D73h, 033031DE5h, 0AA0A4C5Fh, 0DD0D7CC9h
dd 05005713Ch, 0270241AAh, 0BE0B1010h, 0C90C2086h, 05768B525h, 0206F85B3h, 0B966D409h, 0CE61E49Fh
dd 05EDEF90Eh, 029D9C998h, 0B0D09822h, 0C7D7A8B4h, 059B33D17h, 02EB40D81h, 0B7BD5C3Bh, 0C0BA6CADh
dd 0EDB88320h, 09ABFB3B6h, 003B6E20Ch, 074B1D29Ah, 0EAD54739h, 09DD277AFh, 004DB2615h, 073DC1683h
dd 0E3630B12h, 094643B84h, 00D6D6A3Eh, 07A6A5AA8h, 0E40ECF0Bh, 09309FF9Dh, 00A00AE27h, 07D079EB1h
dd 0F00F9344h, 08708A3D2h, 01E01F268h, 06906C2FEh, 0F762575Dh, 0806567CBh, 0196C3671h, 06E6B06E7h
dd 0FED41B76h, 089D32BE0h, 010DA7A5Ah, 067DD4ACCh, 0F9B9DF6Fh, 08EBEEFF9h, 017B7BE43h, 060B08ED5h
dd 0D6D6A3E8h, 0A1D1937Eh, 038D8C2C4h, 04FDFF252h, 0D1BB67F1h, 0A6BC5767h, 03FB506DDh, 048B2364Bh
dd 0D80D2BDAh, 0AF0A1B4Ch, 036034AF6h, 041047A60h, 0DF60EFC3h, 0A867DF55h, 0316E8EEFh, 04669BE79h
dd 0CB61B38Ch, 0BC66831Ah, 0256FD2A0h, 05268E236h, 0CC0C7795h, 0BB0B4703h, 0220216B9h, 05505262Fh
dd 0C5BA3BBEh, 0B2BD0B28h, 02BB45A92h, 05CB36A04h, 0C2D7FFA7h, 0B5D0CF31h, 02CD99E8Bh, 05BDEAE1Dh
dd 09B64C2B0h, 0EC63F226h, 0756AA39Ch, 0026D930Ah, 09C0906A9h, 0EB0E363Fh, 072076785h, 005005713h
dd 095BF4A82h, 0E2B87A14h, 07BB12BAEh, 00CB61B38h, 092D28E9Bh, 0E5D5BE0Dh, 07CDCEFB7h, 00BDBDF21h
dd 086D3D2D4h, 0F1D4E242h, 068DDB3F8h, 01FDA836Eh, 081BE16CDh, 0F6B9265Bh, 06FB077E1h, 018B74777h
dd 088085AE6h, 0FF0F6A70h, 066063BCAh, 011010B5Ch, 08F659EFFh, 0F862AE69h, 0616BFFD3h, 0166CCF45h
dd 0A00AE278h, 0D70DD2EEh, 04E048354h, 03903B3C2h, 0A7672661h, 0D06016F7h, 04969474Dh, 03E6E77DBh
dd 0AED16A4Ah, 0D9D65ADCh, 040DF0B66h, 037D83BF0h, 0A9BCAE53h, 0DEBB9EC5h, 047B2CF7Fh, 030B5FFE9h
dd 0BDBDF21Ch, 0CABAC28Ah, 053B39330h, 024B4A3A6h, 0BAD03605h, 0CDD70693h, 054DE5729h, 023D967BFh
dd 0B3667A2Eh, 0C4614AB8h, 05D681B02h, 02A6F2B94h, 0B40BBE37h, 0C30C8EA1h, 05A05DF1Bh, 02D02EF8Dh

.code

CRC32 proc uses esi lpBuffer:DWORD,dwBufLen:DWORD,dwCRC:DWORD
    mov eax,dwCRC
    mov ecx,dwBufLen
    xor eax,-1
    test ecx,ecx
    mov esi,lpBuffer
    jz @F
    .repeat
        xor al,[esi]
        movzx edx,al
        shr eax,8
        mov edx,[CRC32Table+edx*4]
        inc esi
        xor eax,edx
        dec ecx
    .until zero?
@@: xor eax,-1
    ret
CRC32 endp

keygen.inc:

include     windows.inc
include     user32.inc
include     kernel32.inc
include     comctl32.inc
include     advapi32.inc

includelib  user32.lib
includelib  kernel32.lib
includelib  comctl32.lib
includelib  advapi32.lib

include \masm32\macros\macros.asm

DlgProc     PROTO   :DWORD,:DWORD,:DWORD,:DWORD
;
.const
IDD_MAIN        equ 1000
IDB_EXIT        equ 1001
IDC_NAME        equ 1002
IDC_SERIAL      equ 1005
IDB_GENERATE    equ 1006
IDB_ABOUT       equ 1007

.data

.data?
hInstance   dd  ?

bignum.inc:

;;
;; BNlib Version 1.0
;;

BN struct DWORD
    dwSize DWORD ?
    bSigned DWORD ?
    dwArray DWORD ?;,?,?,?,?,? ;BN_MAX_DWORD back to 1based array
BN ends
pBN typedef ptr BN



bnCreateX macro args:VARARG
    for arg,<args>
        invoke bnCreate
        mov &arg,eax
    endm
    bnDestroyX macro; args:VARARG
        for arg,<args>
            invoke bnDestroy,&arg
        endm
    endm
endm

if 0
bnSCreateX equ bnCreateX
bnSDestroyX equ bnDestroyX
else

; use in recursion :P
; you must not abuse EBP!
bnSCreateX macro args_locals:VARARG
    mov edx,BN_ALLOC_BYTES
    xor ecx,ecx
    for arg,<args_locals>
        sub esp,edx
        add ecx,edx
        mov &arg,esp
    endm
    mov edx,esp
    push edi
    xor eax,eax
    mov edi,edx
    shr ecx,2
    rep stosd
    pop edi
    inc eax
    for arg,<args_locals>
        mov edx,&arg
        mov [edx],eax
    endm
    bnSDestroyX macro
    LOCAL ii
        mov ecx,BN_ALLOC_BYTES
        ii = 0
        for arg,<args_locals>
            ii = ii + 1
        endm
        imul ecx,ii
        add esp,ecx
    endm
endm
endif

BN_IS_ZERO macro bnreg:req
    exitm <(([bnreg].BN.dwSize == 1) && ([bnreg].BN.dwArray[0] == 0))>
endm

BN_IS_ONE macro bnreg:req
    exitm <(([bnreg].BN.dwSize == 1) && ([bnreg].BN.dwArray[0] == 1) && ([bnreg].BN.bSigned == 0))>
endm

;ABSolute
ABS_BN_IS_ONE macro bnreg:req
    exitm <(([bnreg].BN.dwSize == 1) && ([bnreg].BN.dwArray[0] == 1))>
endm

BN_IS_EVEN macro bnreg:req
    exitm <(!([bnreg].BN.dwArray[0] & 1))>
endm

BN_IS_ODD macro bnreg:req
    exitm <([bnreg].BN.dwArray[0] & 1)>
endm

bnAdd PROTO :DWORD,:DWORD
bnAddDw PROTO :DWORD,:DWORD
bnBits PROTO :DWORD
bnClear PROTO :DWORD
bnCmp PROTO :DWORD,:DWORD
bnCmpAbs PROTO :DWORD,:DWORD
bnCreate PROTO
bnCreateDw PROTO :DWORD
bnCreatei PROTO :SDWORD
bnDec PROTO :DWORD
bnDestroy PROTO :DWORD
bnDiv PROTO :DWORD,:DWORD,:DWORD,:DWORD
bnDivDw PROTO :DWORD,:DWORD,:DWORD
bnFinish PROTO
bnInc PROTO :DWORD
bnInit PROTO :DWORD
bnMod PROTO :DWORD,:DWORD,:DWORD
bnModDw PROTO :DWORD,:DWORD
bnMov PROTO :DWORD,:DWORD
bnMovsx PROTO :DWORD,:SDWORD
bnMovzx PROTO :DWORD,:DWORD
bnMul PROTO :DWORD,:DWORD,:DWORD
bnMulDw PROTO :DWORD,:DWORD
bnShl1 PROTO :DWORD
bnShl PROTO :DWORD,:DWORD
bnShr1 PROTO :DWORD
bnShr PROTO :DWORD,:DWORD
bnSquare PROTO :DWORD
bnSub PROTO :DWORD,:DWORD
bnSubDw PROTO :DWORD,:DWORD
bnXchg PROTO :DWORD,:DWORD
bnToHex PROTO :DWORD,:DWORD
bnFromBytes PROTO :DWORD,:DWORD,:DWORD,:DWORD
bnToBytes PROTO :DWORD,:DWORD
bnFromBytesEx PROTO :DWORD,:DWORD,:DWORD,:DWORD
bnToBytesEx PROTO :DWORD,:DWORD
bnFromStr PROTO :DWORD,:DWORD
bnToStr PROTO :DWORD,:DWORD
bnFromHex PROTO :DWORD,:DWORD
bnGCD PROTO :DWORD,:DWORD,:DWORD
bnLCM PROTO :DWORD,:DWORD,:DWORD
bnModExp PROTO :DWORD,:DWORD,:DWORD,:DWORD
bnMulpow2 PROTO :DWORD,:DWORD,:DWORD
bnDivpow2 PROTO :DWORD,:DWORD,:DWORD
bnModInv PROTO :DWORD,:DWORD,:DWORD
bnBinGCD PROTO :DWORD,:DWORD,:DWORD
bnModpow2 PROTO :DWORD,:DWORD,:DWORD
bnMontyModExp PROTO :DWORD,:DWORD,:DWORD,:DWORD
bnRandom PROTO :DWORD,:DWORD
bnRabinMillerpt PROTO :DWORD,:DWORD
bnFermatpt PROTO :DWORD
phase1 PROTO :DWORD
bnTrialDivpt PROTO :DWORD
bnIsPrime PROTO :DWORD
bnRsaGenPrime PROTO :DWORD,:DWORD

Keygen.rc:

;This Resource Script was generated by WinAsm Studio.

#define IDD_MAIN 1000
#define IDB_EXIT 1001
#define IDC_STATIC1003 1003
#define IDC_STATIC1004 1004
#define IDC_NAME 1002
#define IDC_SERIAL 1005
#define IDB_GENERATE 1006
#define IDC_STATIC1007 1007

1 24 DISCARDABLE "manifest.xml"

IDD_MAIN DIALOGEX 10,10,295,59
CAPTION "KKR kgm elgamal"
FONT 8,"Tahoma"
STYLE 0x90c80804
EXSTYLE 0x00000000
BEGIN
    CONTROL "Exit",IDB_EXIT,"Button",0x10010000,247,43,45,13,0x00000000
    CONTROL "",IDC_NAME,"Edit",0x50010000,30,9,261,13,0x00000200
    CONTROL "Name",IDC_STATIC1003,"Static",0x50000000,7,8,20,8,0x00000000
    CONTROL "Serial",IDC_STATIC1004,"Static",0x50000000,7,28,20,9,0x00000000
    CONTROL "",IDC_SERIAL,"Edit",0x50010800,30,28,261,12,0x00000200
    CONTROL "Generate",IDB_GENERATE,"Button",0x10010000,200,43,44,13,0x00000000
    CONTROL "Protection: Elgamal 66 bits and CRC32",IDC_STATIC1007,"Static",0x58000000,7,46,184,10,0x00000000
END

And eventually a manifest.xml for the folklore:

<?xml version="1.0" encoding="UTF-8" standalone="yes"?>
<assembly
  xmlns="urn:schemas-microsoft-com:asm.v1"
  manifestVersion="1.0">
<assemblyIdentity
   processorArchitecture="x86"
   version="5.1.0.0"
   type="win32"
   name="program.exe"/>
    <description>Mx XP Program</description>
    <dependency>
    <dependentAssembly>
    <assemblyIdentity
        type="win32"
        name="Microsoft.Windows.Common-Controls"
        version="6.0.0.0"
        publicKeyToken="6595b64144ccf1df"
        language="*"
        processorArchitecture="x86"/>
    </dependentAssembly>
    </dependency>
</assembly>

Also, maybe you know already but you can use RSA tool for convert the hex, you just have to paste number in any edit box, and change base. (keygenner assistant is not that fast in running and converting :))

For finish i want to thanks KKR and qpt^J for the help/docs, Elgamal is quite complex..
It will take time for me. but eventually i will succeed :þ
If you are interested in Elgamal i suggest you to have also a look to the crackme 9 of Encrypto 'dEPENDENCE'