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
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
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
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
(You can see the result on the stack when out, 4E0E9CF5 for Xylitol)
Who after is converted to fgint and checked
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/
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:
And eventually a manifest.xml for the folklore:
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'