Breaking B0rken ElGamal KeygenMe, part 2

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!