Je ne connaissais pas vraiment Elgamal, j'ai donc demandé à un ami de me faire un KeygenMe pour m'exercer.
Après avoir pas mal trainé sur Efnet, lu des solutions sur la vulnérabilité d'elgamal, discuté avec des gars de la Team iNFECTiON etc ... j'ai eu l'idée d'écrire (enfin?) Une solution lame sur mon blog.
Le keygenme, le source asm du keygen se trouvent ici dans ce pack: Pack.zip
MD5: 6b4a6008e235d8f6225aeeb359077a57
Commençons par un clic-droit>Searh for>All referenced text strings
Nous avons une combinaison de chiffres et deux chaînes « Good Work » et « Bad serial ».
On voit aussi un « Edit2Change » et « Edit1Change » ainsi que « TForm1 », des noms qui laissent suggérer que le programme a été codé en utilisant Delphi.
Le keygenme n'utilisant pas de bouton sur son interface pour vérifier le sérial, les calculs sont probablement effectués dès que le texte change dans les inputs.
Les évènements Edit1Change et Edit2Change sont donc dignes d’intérêt pour nous.
Double-cliquons sur « Edit2Change » et suivons le saut en haut.
Posons une breakpoint au début de la routine
En scannant le KeygenMe avec KANAL ou Keygener Assistant, ils nous détectent certains FGint (Fast Gigantic Integers) probablement utilisés par Elgamal.
FGint est une suite de code Delphi libre créé par Triade Systems utilisé pour implémenter plusieurs algorithmes à clé publique.
Afin d'avoir une meilleure visibilité à ce sujet, chargeons le keygenme dans IDA et le pack de signatures FGInt.
Allons à l'adresse : 00456DB0 avec IDA
Nous voyons deux appels GetText et juste après un autre appel, vérifions.
Pressons la touche Tabulation pour afficher le pseudocode
Juste avant la condition pour aller sur "bad serial" ou sur "Good Work", on observe:
On identifiera le pseudocode un peu plus tard mieux que ça, mais maintenant on sait qu'on a une présence d'elgamal pour valider le serial.
D'accord, créons un fichier MAP pour le plugin godup de ollydbg
File>Produce file>Create MAP file
Puis chargeons notre fichier MAP dans olly (Load labels/Load comments)
Supprimons le breakpoint dans Olly et exécutons la cible (F9)
Remplissons les champs nom/sérial ; reposons notre breakpoint et entrons quelque chose dans le champs du sérial pour breaker à nouveau.
Continuons avec F8 jusqu'à ce que nous arrivions sur le CALL 00456B84
Les commentaires du fichier MAP généré d'IDA que l'on a importé, nous offrent plus de lisibilité sur fgint dans le debugger.
On appuie sur F7 pour entrer dans la CALL et suivre la procédure.
On continu avec F8 et on voit ce saut:
Il nous renvoie directement sous le message « Good Work », pour sortir de la routine de validation du sérial,
nous avons sûrement oublié quelque chose.
Alors recommençons et suivons pas à pas la procédure avant le Jump if Equal (JE).
Nous constatons en fait que le KeygenMe cherche un tiret « - » en hexa =(2D) dans le champ du sérial, le format du sérial devrait ressembler à quelque chose comme ceci: « AAAA-BBBB ».
Ajoutons un tiret à notre sérial et réessayons, cette fois-ci nous ne sautons pas, et nous allons dans la partie Elgamal.
Juste avant les intergers, nous avons un CALL, il calcule le CRC32 de votre nom
(Vous pouvez voir le résultat sur la pile à la sortie, 4E0E9CF5 pour le string "Xylitol"),
qui après est converti en fgint et vérifié.
Vous pouvez afficher votre crc32 dans eax, et le convertir en fgint à:
00456C9A |. E8 F1D8FFFF CALL 00454590 ;
Bon cool ! :) nous avons ces nombres en base 10:
P = 54042131087723322023
G = 1302299722409787264
Y = 41067336953420739677
Nous devons à présent résoudre le DLP (problème de logarithme discret)
Vous pouvez trouver la solution ici: http://en.wikipedia.org/wiki/ElGamal_signature_scheme
y = g ^ x mod p
p est un nombre premier, x et g sont inférieurs à p, où x est la clé privée
Ensuite, choisissez un nombre aléatoire k, tel que k est premier relatif à p-1
Pour obtenir x, on peut utiliser Magma calculator ici: http://magma.maths.usyd.edu.au/calc/
p := 54042131087723322023; K := GF(p); g := K ! 1302299722409787264; y := K ! 41067336953420739677; x := Log(g, y); x;
Nous obtenons le résultat: 37134730343699938001
Ident du pseudocode dans IDA:
Maintenant, tout est clair, nous devons simplement coder le keygen en utilisant l'algorithme de génération de signature Elgamal.
r, s (la signature) sont les deux parties qui compose le serial soit: r-s
Nous avons m, x, p et aussi de Wikipedia la formule pour r, s:
r = g ^ k mod p
s = (m-x * r) * k ^ -1 mod p-1
Bon, voilà mon keygen pour le quel j'ai utilisé la librairie BigNum de Drizz:
; Xyl2k: þ
; QOTD: calculatrice Windows 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
Et éventuellement un manifest.xml pour le 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>
Vous le saviez probablement déjà, mais vous pouvez utiliser aussi l'outil RSATool 2 by tE!
pour convertir de l'hexa, il vous suffit par exemple de vous mettre en base10 et de coller 54042131087723322023 (P)
dans n'importe quelle zone d'édition et de changer en base16.
(pour une raison quelconque, Keygenner Assistant n'est pas aussi rapide dans l'exécution et la conversion en hexa,
un comble pour ce genre d'outil 
)
Pour finir, je tiens à remercier KKR et qpt ^ J pour leur aide / la documentation, Elgamal est assez complexe ...
Cela m'aura pris du temps, mais j'ai finalement réussi: 
Si vous êtes intéressé par Elgamal, je vous suggère de jeter également un coup d'œil au crackme 9 de Encrypto « DEPENDANCE »
Copyright (C)- xtx Team (2021)
