# Breaking B0rken ElGamal KeygenMe by SmilingWolf

Some weeks ago I found a nice keygenme on URET forum. The description looked interesting enough:

Yet another company is making wild claims! Your mission: prove that people shouldn't trust companies promoting "revolutionary" crypto algos. Keygen this son of a crypto nightmare and write a DETAILED tutorial!

Rules:

1) The only acceptable solution is a keygen

2) No patching of course

It was not solved for few weeks, so I decided to take a look at it. smile

### Crash-course in ElGamal signature scheme

I hate cryptography. It's complex, it's confusing and unless you're prepared to study this field for years, you can't really understand why stuff works this or that way.

So, here's a short version, just enough to solve this keygenme. It's based on the explanation in InfoSec Institute's tutorial.

#### Key generation

- Generate a random prime number
*P*with chosen length. - Generate two random numbers,
*G*and*X*, with*G<P*and*X<P*. - Calculate
*Y=G^X mod P*. - Public key consists of 3 numbers: (
*P*,*G*and*Y*), Private key is*X*.

All 3 numbers of public key are hardcoded in keygenme and are 256 bits long. We can find them in disassembly:

1 2 3 |
P = FE6D5B4400B30374A403F88CFBA3642435FB269AEC2BE5C8C2F331545EF37AB3 G = 7FB7E340473674B34C7B9BDF338897277CB2A17E0296D5DD08C60D5B3D839219 Y = CC945009A3E4215D042284F4FE567DFDAAEB906E8A620597FAF4953935F217EC |

Private key *X* is.. well, private. smile Without it we can't generate correct keys for a name of our choice. So, the challenge would be to recover the private key somehow.

#### Signing

To sign a message *M*, one would:

- Make a hash of message,
*H(M)*. In this crackme, it's SHA1 of the username - Generate a random number
*K*where*K<P-1* - Calculate
*R=G^K (mod P)* - Calculate
*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)*, one would:

- Compute
*V1=G^M (mod P)* - Compute
*V2=Y^R * R^S (mod P)* - If
*V1==V2*, the signature is valid

### Breaking ElGamal

Strength of ElGamal algorithm lies in the Discrete Logarithm Problem (DLP). What it means is that easy to calculate *Y=G^X mod P*, but it's bloody hard to find out *X*, if you know *P*, *G* and *Y*.

In the InfoSec Institute's tutorial the author is using figugegl's DLPTool to solve the problem for 128-bit integers. However, it's not even possible to enter 256-bit integers in that tool. And the rest of the suggested tools can't handle such large integers either.

So, we must find another way to break the keygenme. After all, it's called "B0rken ElGamal", so there must be a weakness somewhere!

### Inside the keygenme

The keygenme itself is an application that generates ElGamal keys. It would be logical to assume that SmilingWolf used this same application to generate keys for the keygenme. So, let's examine the application and see how ElGamal is implemented in it.

I'll skip the boring "unpack modified UPX part", as it's been explained dozens of times already.

So, here's the relevant code for key generation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
SW0:00401104 push 0FFh SW0:00401109 push big_temp SW0:0040110F call bigint_random_1 SW0:00401114 SW0:00401114 push big_temp SW0:0040111A push big_p SW0:00401120 call bigint_copy SW0:00401125 SW0:00401125 push 2 SW0:00401127 push big_p SW0:0040112D call biginit_mul_by_int SW0:00401132 SW0:00401132 push big_p SW0:00401138 call bigint_find_nearest_prime SW0:0040113D SW0:0040113D push 0FFh SW0:00401142 push big_g SW0:00401148 call bigint_random_2 SW0:0040114D SW0:0040114D push 0FFh SW0:00401152 push big_x ; PRIVATE SW0:00401158 call bigint_random_2 SW0:0040115D SW0:0040115D push big_y ; calculated by powmod SW0:00401163 push big_p ; prime! SW0:00401169 push big_x ; PRIVATE SW0:0040116F push big_g ; less than p SW0:00401175 call bigint_powmod ; Y=G^x mod P |

Looks legit, right? smile Well, not so fast.

Random numbers don't just magically appear out of thin air. They are generated using random number generators. If the generators are flawed, the numbers are not really random. You can read a lot about such attacks on Wikipedia.

So, let's examine random number generator used in this keygenme.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
SW0:004018B0 random proc near SW0:004018B0 SW0:004018B0 arg_0 = dword ptr 8 SW0:004018B0 SW0:004018B0 push ebp SW0:004018B1 mov ebp, esp SW0:004018B3 push ecx SW0:004018B4 push edx SW0:004018B5 mov eax, random_seed SW0:004018BA xor edx, edx SW0:004018BC mov ecx, 127773 SW0:004018C1 div ecx SW0:004018C3 mov ecx, eax SW0:004018C5 mov eax, 16807 SW0:004018CA mul edx SW0:004018CC mov edx, ecx SW0:004018CE mov ecx, eax SW0:004018D0 mov eax, 2836 SW0:004018D5 mul edx SW0:004018D7 sub ecx, eax SW0:004018D9 xor edx, edx SW0:004018DB mov eax, ecx SW0:004018DD mov random_seed, ecx SW0:004018E3 div [ebp+arg_0] SW0:004018E6 mov eax, edx SW0:004018E8 pop edx SW0:004018E9 pop ecx SW0:004018EA leave SW0:004018EB retn 4 SW0:004018EB random endp |

If you search for those constants, you'll see that it's a very standard PRNG which is not great but supposed to be reliable enough. You could bruteforce all 2^32 possibilities but it will take a long time. Another dead end?

Well, not really. Any PRNG must be initialized somehow, see *random_seed* variable above. So, let's see how SmilingWolf is initializing his PRNG..

1 2 |
SW0:0040108F mov eax, [ebp+arg_0] SW0:00401092 xor random_seed, eax ; original seed value = 0x37333331 |

Hmm, that's weird. Normally PRNG is initialized using *rdtsc* instruction or something even less predictable than that. And what exactly is *arg_0*? It's a handle of the DialogBox - not random at all!

Finally, we've found a reason why this ElGamal implementation is broken! smile

### Bruteforcing the private key

Now that we know the weakness, we can write a bruteforcer that will go through all possibilities of random seeds and generate all possible ElGamal keys. Once we generate a key that has the same *P*, *G* and *Y* as in the keygenme, we will also know the correct private key *X*. But generating all these numbers is a slow process!

Let's look back at the code and see what we can optimize.

1) We don't need to generate all the numbers. It's enough if we find correct *P* - the rest of numbers will match automatically. So, let's remove the rest of the code.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
SW0:0040108F mov eax, [ebp+arg_0] SW0:00401092 xor random_seed, eax ; original seed value = 0x37333331 ... SW0:00401104 push 0FFh SW0:00401109 push big_temp SW0:0040110F call bigint_random_1 SW0:00401114 SW0:00401114 push big_temp SW0:0040111A push big_p SW0:00401120 call bigint_copy SW0:00401125 SW0:00401125 push 2 SW0:00401127 push big_p SW0:0040112D call biginit_mul_by_int SW0:00401132 SW0:00401132 push big_p SW0:00401138 call bigint_find_nearest_prime |

2) First 32 bits of 256 bit integer will almost certainly not change when searching for nearest prime. Therefore, we could get rid of *bigint_find_nearest_prime* call which is the slowest piece of code. This means we won't be looking for number FE6D5B4400B30374A403F88CFBA3642435FB269AEC2BE5C8C2F331545EF37AB3, but any number starting with FE6D5B44...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
SW0:0040108F mov eax, [ebp+arg_0] SW0:00401092 xor random_seed, eax; original seed value = 0x37333331 ... SW0:00401104 push 0FFh SW0:00401109 push big_temp SW0:0040110F call bigint_random_1 SW0:00401114 SW0:00401114 push big_temp SW0:0040111A push big_p SW0:00401120 call bigint_copy SW0:00401125 SW0:00401125 push 2 SW0:00401127 push big_p SW0:0040112D call biginit_mul_by_int |

3) Multiplication by 2. Another unnecessary step. Let's just divide *P* by 2 and look for that number. Instead of looking for FE6D5B44..., we'll look for 7F36ADA2...

1 2 3 4 5 6 7 8 9 10 |
SW0:0040108F mov eax, [ebp+arg_0] SW0:00401092 xor random_seed, eax ... SW0:00401104 push 0FFh SW0:00401109 push big_temp SW0:0040110F call bigint_random_1 SW0:00401114 SW0:00401114 push big_temp SW0:0040111A push big_p SW0:00401120 call bigint_copy |

4) Copying bigints. Unnecessary.

1 2 3 4 5 6 |
SW0:0040108F mov eax, [ebp+arg_0] SW0:00401092 xor random_seed, eax ... SW0:00401104 push 0FFh SW0:00401109 push big_temp SW0:0040110F call bigint_random_1 |

There's not much left, I'm satisfied.

Now, how to bruteforce random seed? It's a window handle. Window handles are always even. Also, they consist of 2 parts, high word and low word. Low word is the actual handle. It is almost never higher than 0x2000. High word is the "uniquifier" - just a counter. It's usually quite small - on my PC it's never larger than 0x800.

Taking all these assumptions into account, my pseudo-code for bruteforcer would look like this:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
for (UInt16 uniquifier = 0; uniquifier < 0x800; uniquifier++) { for (UInt16 handle = 0; handle < 0x2000; handle += 2) { UInt32 seed = (uniquifier << 0x10) | handle; seed = seed ^ 0x37333331; InitPrng(seed); bigint_random_1(out bigint_temp, 0xFF); if (first 4 bytes of bigint_temp are 0x7F36ADA2) { we found the correct seed; } } } |

I implemented the bruteforcer in MASM32 with 95% of code ripped from keygenme and let it run. In less than 2 hours I had one (of the several possible) seed:

1 2 3 4 5 |
Seed = 0x00010968 P = FE6D5B4400B30374A403F88CFBA3642435FB269AEC2BE5C8C2F331545EF37AB3 G = 7FB7E340473674B34C7B9BDF338897277CB2A17E0296D5DD08C60D5B3D839219 X = 7F4BEFC372EED0BA1D4A3543243EE574734C8347459FA21E5BCC5BCF0351812D Y = CC945009A3E4215D042284F4FE567DFDAAEB906E8A620597FAF4953935F217EC |

Once we know *X*, implementing keygen is a child's play. Again, lots of ripped code and small UI around it. Problem solved!

Keygen for download: https://mega.nz/#!JtgVUDwb!xs3SgCDK3t5h3MabOfoNsDFYCj1mpHcI7GbQT-K1_RE

### Further reading

InfoSec Institute's tutorial about ElGamal: http://resources.infosecinstitute.com/breaking-software-protection-elgamal-signature-scheme/

Interactive webpage showing how ElGamal works with small numbers: https://asecuritysite.com/encryption/elgamal

### Final thoughts

As SmilingWolf told me after solving his keygenme - there is another way how to break this keygenme. There's one more thing broken in this implementation that makes generating keys really easy. smile So, if you're interested, try to figure out what is it and how to abuse it.

Nice post and explanation kao! :)

Never heard before about ElGamal, but as i can see there are a lot of similarity with RSA encryption.

In a 256bit value there are a lot of probability that the first 4 bytes are equal than bytes you need,

but maybe you didn't find them in your looping cycle range.

You were lucky or in your attemp to find the right seed did you find some fakes?

Considering that I was bruteforcing just 0x800 * 0x2000 = 0x100'0000 possibilities, chances of encountering a 4-byte collision are really low. ;)

Nice read. Thanks for sharing. Although I don't know how you have time to read all these different boards!