Tag: solution

In part 1 of the tutorial, I explained how badly initialized PRNG causes a serious problems and allows us to find the private key. In this part of tutorial, I'll show how to use another weakness in crackme to find private key without using bruteforce.

Looking deeper in the keygenme

If you analyze serial check in more details, you'll notice part of code that processes blacklisted names and keys:

SW0:00401762    mov     [ebp+bad_boy_counter], 0

SW0:00401769    push    offset aLordcarder ; "LordCarder"
SW0:0040176E    push    offset entered_name
SW0:00401773    call    compare_strings
SW0:00401778    add     [ebp+bad_boy_counter], eax
SW0:0040177B    push    offset a5e40b1700252c9 ; "5E40B1700252C909D6050ACDFE0674C0B745B8F"...
SW0:00401780    push    offset entered_sn
SW0:00401785    call    compare_strings
SW0:0040178A    add     [ebp+bad_boy_counter], eax
SW0:0040178D    push    offset aProthief ; "ProThief"
SW0:00401792    push    offset entered_name
SW0:00401797    call    compare_strings
SW0:0040179C    add     [ebp+bad_boy_counter], eax
SW0:0040179F    push    offset a5e40b1700252_0 ; "5E40B1700252C909D6050ACDFE0674C0B745B8F"...
SW0:004017A4    push    offset entered_sn
SW0:004017A9    call    compare_strings
SW0:004017AE    add     [ebp+bad_boy_counter], eax

SW0:004017B1    cmp     [ebp+bad_boy_counter], 0
SW0:004017B5    jnz     blacklisted

It looks like we have 2 blacklisted names & corresponding serials. We can quickly patch crackme and verify that these names and serials really work.

But did you also notice that those serials look a lot alike? That's weird.. Let's take a closer look at them:

SW0:0040518B a5e40b1700252c9 db '5E40B1700252C909D6050ACDFE0674C0B745B8FBAC1D57E38EF982DFDCB1FE9D'
SW0:0040518B                 db '79CA4A7D14DC506A542D661AEF4384554B348FA1A2F8CBB65C5BD16ABA16B6CE',0
..
SW0:00405215 a5e40b1700252_0 db '5E40B1700252C909D6050ACDFE0674C0B745B8FBAC1D57E38EF982DFDCB1FE9D'
SW0:00405215                 db 'C814338D071D56578B2D5CB176E08B56DE1A69A47467312AE32D4D83B46475CF',0

First part of the serial is exactly the same! Let's go back to ElGamal basics and think a bit.

Revisiting ElGamal signing algorithm

I'm sure you already remember the algorithm from my previous blog post. But here it is again.. 🙂

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).

So, in our case, R is always the same. G and P are hardcoded in the crackme. That means.. K is always the same. And that doesn't sound right! 🙂

Quick look in Wikipedia confirms that it's a really bad idea:

The signer must be careful to choose a different k uniformly at random for each signature and to be certain that k, or even partial information about k, is not leaked. Otherwise, an attacker may be able to deduce the secret key x with reduced difficulty, perhaps enough to allow a practical attack. In particular, if two messages are sent using the same value of k and the same key, then an attacker can compute x directly.[1]

The problem of reusing k and the attack itself is explained in Stinson's "Cryptography Theory And Practice", pages 290-291. Unfortunately, normal person has no chance to understand that "explanation".

Few Google searches later I found 2 writeups from Boston Key Party CTF 2015 which were slightly better:

• https://r3dey3.com/2015-03/bkpctf-wood-island-and-orient-heights/
• https://github.com/ctfs/write-ups-2015/tree/master/boston-key-party-2015/crypto/wood-island

So, let's try to get something useful out of them.

Reused K and recovering private key

As I said earlier, cryptography is a dark magic - if you don't spend years studying it, you can't understand it. So, I just took the code from those CTF writeups and added few more comments to it. And no, I still don't know why it works. 🙂

import hashlib
import gmpy
from gmpy import mpz
from gmpy import gcd

# hardcoded data from crackme
g = mpz(0x7FB7E340473674B34C7B9BDF338897277CB2A17E0296D5DD08C60D5B3D839219)
p = mpz(0xFE6D5B4400B30374A403F88CFBA3642435FB269AEC2BE5C8C2F331545EF37AB3)
y = mpz(0xCC945009A3E4215D042284F4FE567DFDAAEB906E8A620597FAF4953935F217EC)

# blacklisted key #1
m0 = mpz(hashlib.sha1("LordCarder").hexdigest(), 16)
r0 = mpz(0x5E40B1700252C909D6050ACDFE0674C0B745B8FBAC1D57E38EF982DFDCB1FE9D)
s0 = mpz(0x79CA4A7D14DC506A542D661AEF4384554B348FA1A2F8CBB65C5BD16ABA16B6CE)

# blacklisted key #2
m1 = mpz(hashlib.sha1("ProThief").hexdigest(), 16)
# r1==r0, no need to repeat myself.
s1 = mpz(0xC814338D071D56578B2D5CB176E08B56DE1A69A47467312AE32D4D83B46475CF)


# SOLVING k(s[0] - s[1]) = (m[0] - m[1]) mod p-1
# ka = side2 mod p-1
a = s0 - s1
side2 = m0 - m1

num = gcd(a, p-1)
num = int(num)

k_ = gmpy.divm(side2/num, a/num, (p-1)/num)
for i in range(0,num):
  k = k_ + (i*(p-1)/num)
  r_ = pow(g, k, p)
  if r_ == r0:
      print "FOUND K: "+ k.digits(16)
      break

# solve xr  = (m0 - ks0) mod p -1
side2 = m0 - k * s0
num = int(gcd(r0, p-1))

x_ = gmpy.divm(side2/num, r0/num, (p-1)/num)
for i in range(0, num):
  x = x_ + (i*(p-1)/num)
  y_ = pow(g, x, p)
  if y_ == y:
      print "FOUND x: " + x.digits(16)
      break

# Generate new key just to prove it works. No, we really shouldn't use hardcoded K. :)
userName = "kao"
m = mpz(hashlib.sha1(userName).hexdigest(), 16)
k = 1337
r = pow(g, k, p)
s = gmpy.divm(m - x*r, k, p-1)
print "Serial for " + userName + " is " + r.digits(16) + s.digits(16)

Conclusion

Wise man once said:

Knowledge is of two kinds. We know a subject ourselves, or we know where we can find information upon it.

You don't need to be a crypto wizard to solve crackmes - you just need to know where to find the necessary information. But if you're implementing cryptography in your software, better ask someone who understands those things.

Have fun!

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. 🙂

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:

P = FE6D5B4400B30374A403F88CFBA3642435FB269AEC2BE5C8C2F331545EF37AB3
G = 7FB7E340473674B34C7B9BDF338897277CB2A17E0296D5DD08C60D5B3D839219
Y = CC945009A3E4215D042284F4FE567DFDAAEB906E8A620597FAF4953935F217EC

Private key X is.. well, private. 🙂 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:

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? 🙂 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.

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..

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! 🙂

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.

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...

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...

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.

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:

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:

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. 🙂 So, if you're interested, try to figure out what is it and how to abuse it.