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 role-guided training plans

Get 12 cybersecurity training plans — one for each of the most common roles requested by employers.

Download Now

Tools Needed

The target file (CryptoChallenge2.exe)

ELGAMALSiGNiT: An ElGamal signature scheme tool (requires dotNetFx4)

PEiD

IDA (Interactive Disassembler)

OllyDBG

RE-SIGS: IDA signature

GODUP: OllyDBG plugin

DLP Tool

What is ElGamal?

ElGamal is a public-key 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

1. Choose a key length (measured in bits).
2. Generate a random prime number P.
3. Generate two random numbers, generator G and Private key X, with (G<P and X<P).
4. Calculate Y=G^X mod P.
5. Public keys are: (P, G and Y), Private key is X.

Signing

To sign a message (M) (where M < P), one would:

1. Generate a random number K where (K<P-1).
2. Compute:

R=G^K (mod p)

S=(H(M)-RX)*K^(-1) (mod p-1)

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:

1. Choose a key size from 16 to 1024.
2. Click 'GENERATE KEYS (P,G,X) to get the prime (P), generator (G) and private keys (X).
3. Click 'CALCULATE Y=G^X (MOD P)' to compute Y.
4. Check the output mode of M: (HEX, MD5 or SHA256).
5. Type something in 'M', you'll see H(M) changing while you're typing.
6. To generate a random K click 'GENERATE' (remember to click 'GENERATE' every time you want a new signature).
7. To Sign a message, click 'Sign'.
8. 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):

Convert keys to base 10.

Enter G in Base text.

Y in Power text.

P in Mod text.

Click 'Find discrete logarithm' and wait.

• 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:

Target: https://www.dropbox.com/s/4zj1goynpf791sr/CryptoChallenge2.rar?dl=0

ELGAMALSiGNiT: https://www.dropbox.com/s/qpsz5247ad3m9jn/ELGAMALSiGNiT.rar?dl=0

PEiD: http://www.softpedia.com/get/Programming/Packers-Crypters-Protectors/PEiD-updated.shtml

IDA: https://www.hex-rays.com/products/ida

OllyDBG:
http://www.ollydbg.de/

RE-SIGS: https://tuts4you.com/download.php?view.3407

GODUP: https://tuts4you.com/download.php?view.54

DLP Tool: https://www.dropbox.com/s/qb5x8l1gwgdh8qn/dlptool.rar?dl=0

Sources:

• https://resources.infosecinstitute.com/breaking-software-protection-rsa/
• http://en.wikipedia.org/wiki/ElGamal_signature_scheme