Breaking Software Protection: ElGamal Signature Scheme
Introduction
In today's article, we will see a more advanced cryptosystem than the previous one: the ElGamal Signature scheme (not to be confused with ElGamal Encryption). So before you start reading this, read the first article for more details.
FREE roleguided training plans
Tools Needed
What is ElGamal?
ElGamal is a publickey cryptosystem developed by Taher Elgamal in 1985. It has two variants: Encryption and Digital Signatures (which we'll learn today). Its strength lies in the difficulty of calculating discrete logarithms (DLP Problem).
Key generation
 Choose a key length (measured in bits).
 Generate a random prime number P.
 Generate two random numbers, generator G and Private key X, with (G<P and X<P).
 Calculate Y=G^X mod P.
 Public keys are: (P, G and Y), Private key is X.
Signing
To sign a message (M) (where M < P), one would:
 Generate a random number K where (K<P1).
 Compute:
R=G^K (mod p)
S=(H(M)RX)*K^(1) (mod p1)
The signature will be the pair C(R,S).
Verification
To verify a given pair C(R,S), we would compute:
V1=G^M (mod p)
V2=Y^R * R^S (mod p)
And confirm:
V1==V2
Example
For an example, we will use the ELGAMALSiGNiT Tool which is an automation of all of the above. The tool is very easy to use in just a few steps:
 Choose a key size from 16 to 1024.
 Click 'GENERATE KEYS (P,G,X) to get the prime (P), generator (G) and private keys (X).
 Click 'CALCULATE Y=G^X (MOD P)' to compute Y.
 Check the output mode of M: (HEX, MD5 or SHA256).
 Type something in 'M', you'll see H(M) changing while you're typing.
 To generate a random K click 'GENERATE' (remember to click 'GENERATE' every time you want a new signature).
 To Sign a message, click 'Sign'.
 To verify C(R,S) click 'Verify'.
You can see the result in the following picture:
Target analyses
In every challenge (Keygenme), or at least those that I've seen, they use the verification formulas to check the serial(s) in the same way as what we are going to see here.
I will assume you've read the first article and know or have done these steps: target analyses in PEiD, crypto signatures extraction from IDA, and importing signatures into OllyDbg using GODUP. I'll jump straight to the debugging process.
Set a breakpoint on 00401189 (F2) (serial verification algorithm) and press F9. The target will run, enter any name (between 3 and 15 characters) and a serial (that has exactly 64 characters). Click 'Check' if everything is good, and the debugger will break at that address. Keep tracing (F8).
The target first gets the size of our name, puts it in EBX, and then generates an md5 hash for our name and converts it to hexadecimal. The result is put in 0x408063.
Here is an algo that divides our serial into two parts of 33 chars (PUSH 21). The 1^{st} part is put in 0x407863 and the 2^{nd} in 0x407C63. Similar to lstrcpyn.
Here we see a lot of _BigCreate (I assume you already know what it does from the first article).
In the above picture we can see the calls to _BigIn. We can see a lot of numbers are divided serials and md5. The rest are for ElGamal's verification.
To make things a little clearer:
 0x407863 = 11111111111111111111111111111111 (Serial1) = 0x408818 (Address of serial1 in big integer)
 0x407C63 = 11111111111111111111111111111111 (Serial2) = 0x40881C
 0x408063 = 4D945493477571DE563E281CA4145EB9 (MD5Hash) = 0x408808
 0x407000 = 8D11C0544299C92AB3A2B2DF361DFB97 (BigNum1) = 0x40880C
 0x407021 = 3D87547CD25B3F8703CCFBB81ACB4423 (BigNum2) = 0x408810
 0x407042 = 120820939A56802A8558641177EAB1CA (BigNum3) = 0x408814
Let's make our variables from the above:
 R = 0x408818
 S = 0x40881C
 M = 0x408808
 X = 0x40880C
 Y = 0x408810
 Z = 0x408814
That is what really interests us.
 At address 0x4012CF there is a call to _BigMod used as follows: M = M mod X. This is used to check if M < X (which is P).
 At 0x4012EC a call to _BigPowMod which is used as: 0x408820 = Y^M mod X
 At 0x401309 another call to _BigPowMod: 0x408824 = Z^R mod X
 A third call to _BigPowMod at 0x401326 : 0x408828 = R^S mod
 At 0x401343 a call to _BigMulMod : 0x40882C = 0x408824 * 0x408828 mod X
 At 0x401354 a call to _BigCompare, which compares 0x408820 with 0x40882C. If they're equal, no jumps, otherwise we jump and get the bad message.
Now that we know how the target works, let's make some corrections first:
X = P and Y = G and Z = Y
And let's assign some variables:
 V1 = 0x408820 = G^M mod P
 Vt1 = 0x408824 = Y^R mod P
 Vt2 = 0x408828 = R^S mod P
 V2 = Vt1 * Vt2 mod P
So now we only need to solve the DLP Problem (Y=g^x mod p) and then we can find our pair C(R,S).
To solve DLP we can use one of the following websites:

http://www.alpertron.com.ar/DILOG.HTM (requires Java):

http://magma.maths.usyd.edu.au/calc/: to use Magma Calculator we would fill the textbox with the following code and click 'submit':
p := 187513317350689708750027795311890398103;
K := GF(p);
g := K ! 81785581430583092797817457721148654627;
y := K ! 23968303030409235163863560552895394250;
x := Log(g, y);
x;
Or we could just use figugegl's DLPTool (which is what I've used):
I've got the following result:
X = 258A82FDE1F2E37D4FBC02BA3063FC4B
Let's get a valid pair now. We'll use the ELGAMALSiGNiT Tool again, so load it up and copy/paste each key in its place:
P=8D11C0544299C92AB3A2B2DF361DFB97
G=3D87547CD25B3F8703CCFBB81ACB4423
X=258A82FDE1F2E37D4FBC02BA3063FC4B
Click directly 'CALCULATE Y=G^X (MOD P)' you should get:
Y=120820939A56802A8558641177EAB1CA
Now check MD5 as an output mode for M (if you recall it's what's used in the challenge).
Type something in M, I've typed 'Jamal Chahir'.
Click 'GENERATE' to generate random K.
Click 'Sign'.
I've got:
R =
8CA772849B8D7C3CDDEEE6C674DAA602
S =
834F0C6C10E2248C7CAA26F307321E3D
Let's join these together: R+S
8CA772849B8D7C3CDDEEE6C674DAA602834F0C6C10E2248C7CAA26F307321E3D
Now load up the challenge. Enter the name you typed in (M) and the joined pair R+S and click 'Check', you should be able to get the correct message:
Conclusion
Now you should be able to bypass softwares that use the ElGamal cryptosystem. The only two problems that you'll encounter are: to identify the cryptographic library used by the software or not (depending on the programming languages), and the key size problem which must not be big (512bits, 1024bits). It could take a lot of time to solve DLP. I hope all is clear.
Download links:
http://www.ollydbg.de/
Sources: