Keygenning Elgamal
Code :
http://xylibox.blogspot.com/2011/11/cracking-elgamal-keygenme.html
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
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:
Code :
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
Code :
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
Code :
00456C5D |. E8 36D2FFFF CALL 00453E98 ;
Who after is converted to fgint and checked
Code :
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/
Code :
p := 54042131087723322023;
K := GF(p);
g := K ! 1302299722409787264;
y := K ! 41067336953420739677;
x := Log(g, y);
x;
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:
Code :
;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
Code :
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
Code :
.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
Code :
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
Code :
;;
;; 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
Code :
;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:
Code :
<?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'
Spyke
Bon membre Messages : 353 Sujets : 20 Points: 13 Inscription : Jun 2011 |
Keygenning Elgamal
Je viens de le lire sur ton blog, je suis abonné. Ça me fait plaisir que tu t'investisse toujours autant. Sérieusement continue comme ça, même si j'ai pas les connaissances pour comprendre 100% de ton tuto, il est très bien construit et pourrai ravir Ivanlefou. gégé \o/
|
oxoo
Newbie Messages : 11 Sujets : 1 Points: 0 Inscription : Nov 2011 |
Keygenning Elgamal
Nice, comme toujours .
J'en profite en voyant ce topic pour poser une question qui me taraude depuis quelques jours où j'ai vu un fichier de conf chiffré avec un algo que j'ai identifié via google : ça existe, un tool qui détecte quel algo de chiffrement (DES, AES, RC4, etc.) est utilisé dans un appli donnée à une adresse donnée, par hasard ? A plux, keep up the good work |