Home > Reverse Engineering > Dongles and Nyberg-Rueppel signature scheme

Dongles and Nyberg-Rueppel signature scheme

“Dongle me” by cyclops is, as name suggest, a crackme that requires a hardware dongle, or a software emulator. These two technical problems, combined with an uncommon authentication scheme, make it an interesting target to analyse.

First, we need to learn how our target detects and communicates with the dongle. In this case, since the executable is small and not packed/protected/obfuscated, a quick glance at imports section is sufficient to get to the dongle discovery procedure — HidD_* APIs from hid.dll give it away instantly.

Pseudocode:

#define VENDOR_ID  0x04d8
#define PRODUCT_ID 0x003f

device_t g_device = NULL;

// address: 00401090
bool find_hid_dongle(int vendor_id, int product_id){

    device_t dev;

    while(dev = next_hid_device()){

        if(dev->vid == vendor_id && dev->pid == product_id){
            g_device = dev;
            return TRUE;
        }
    }

    return FALSE;
}

And a high level view of authentication:

bool authenticate(){
    char buffer[N];

    if(!find_hid_dongle(VENDOR_ID, PRODUCT_ID)){
        return FALSE;
    }

    read_dongle(g_device, buffer);

    if(is_valid(buffer)){
        return TRUE;
    }

    return FALSE;
}

To make it even clearer: HID devices installed in the OS are enumerated one by one. Dongle is recognized by specific values of variables exposed by every HID: product_id and vendor_id. If found, device is opened with CreateFile and read with ReadFile (standard windows APIs). Finally, read data is validated. Before creating a dongle, or an emulator, we need to get familiar with HID.

Human interface devices

Human Interface Devices are devices that interact with humans — take input from them and/or present them output. Good examples are mouse and a keyboard. Primary motivation for HID, was to simplify the process of installation of PC input devices. Prior to HID, custom devices were required to implement their own protocols to communicate with the user, which of course forced developers to create custom drivers to handle these protocols, and users to install these drivers. HID protocol makes things simpler. Instead of custom drivers, developers need to “describe” their protocol using HID descriptors. Descriptors are parsed and interpreted by the OS itself, allowing developers to easily create complex devices from pritmitives provided by the OS.

To implement a hardware HID dongle, we can use Teensy, or any compatible clone. I found a Teensy 1.0 clone available for few bucks, preloaded with a PS3 hack :). With USB raw hid example it’s trivial to implement a simple dongle that waits for data from our keygen, saves it in EEPROM and then sends it back to the OS, in a loop. If you want to take a look at the implementation, see here.

Creating an emulator is more complicated and requires a HID miniport driver. While it certainly is possible to create it basing only on Win DDK HID samples, it is no easy feat, if you don’t have experience in kernel development. Fortunately, there is an excellent open source project called vmulti, created by Daniel Newton, that does exactly what we need: creates virtual HID devices that can be read / written to. Adapting it to our needs is a technicality that I feel isn’t worth describing, so check the sources if you are interested in details.

Emulator will simply pass stuff received from the keygen to anyone who invokes ReadFile(). Here’s a nice screenshot of device manager with successfully installed emulator:

Authentication

Finally, the most interesting part :). To recognize used authentication scheme, make shure to apply IDA signatures for MIRACL bignum library, otherwise you will unnecessarily spend a lot of time identifying functions. Crackme uses elliptic curve cryptography, so it’s very possible that failing to recognize MIRACL usage, would cost you digging deep into the assembly code with slim chances of making any sense out of it.

Cyclops used an elliptic curve variant of Nyber-Rueppel signature scheme. Current user’s username is “hashed” with CRC32. Then, CRC is compared to a message extracted from an ECNR signature read from the dongle. To pass authentication, we need to sign the CRC and push it to the dongle.

Nyberg-Rueppel Signature Scheme

Let E be an elliptic curve defined over \mathbb{Z}_p (p > 3 prime) such that E contains a cyclic subgroup H in which the discrete logarithm problem is intractable.

Let K=\{(E,k,P,Q): Q=k*P\}, where P \in H \subset E. Points P and Q are public, while k is secret. For K defined as above, for a (secret and random) t \in \mathbb{Z}_{|H|} and for a (message) m \in \mathbb{Z}_p, define:

sign_K(m, t) = (s_1, s_2)

where

(x_1, y_1) = t*P

s_1 = x_1 + hash(m) mod p

s_2 = t - k*s_1 mod p

and

verify_K(m, s_1, s_2) = true \iff z=hash(m)

where

(x_2, y_2) = s_2*P + s_1*Q

z = s_1-x_2

This works, because s_2*P + s_1*Q = (t - k*s_1)*P + s_1*k*P = t*P.

Since we now know what cryptosystem we are up against, and how to generate correct signatures, let’s take a look at curve parameters used in the crackme. Since author claims it’s solvable without patching, we expect either:

  1. a small curve, where ECDLP can be effectively solved
  2. a weak curve, that is suspectible to a cryptographic attack (examples in [3])
  3. something tricky :)

Quick inspection of parameters shows that 1) and 2) are not the case. Used curve is secp112r1, which is bad news for us, since secp* curves (their parameters) are chosen by Certicom research [2], to be optimal for cryptographic purposes. This means they provide maximal possible bit-strength security against fastest known ECDLP solving algorithms and aren’t weakened by special-case attacks.

Before using these curves, you may wonder how were their parameters chosen, after all, maybe NSA helped to pick them ;). Fortunately, these concerns were anticipated and curves were generated by a SHA-1 powered PRNG, seeded with a known value and then checked for desired properties, so no parameter could be predetermined. Since seeds and PRNG implementation are public [2], you can even repeat the process and verify chosen curves yourself.

We are left with option 3). Before doing anything complicated, I wanted to check if the ECDLP from crackme was referenced anywhere on the Internet. secp112r1 parameters (a, b, p) are common and won’t provide any interesting clues, but coordinates of point P  (or G , using Certicom’s nomenclature) could, as cyclops decided to use a non-standard base point.

Searching for 9487239995A5EE76B55F9C2F098 (x coord. of P) yields nothing of interest, but searching for 188281465057972534892223778713752 (same value, but in base 10) turns out to be a bull’s eye ;).

In 2009, Bos, Marcelo, KaiharaKleinjung, Lenstra and Montgomery solved an ECDLP over secp112r1, using 200 PS3 consoles. ECDLP instance they were solving was Q=k*P, where

P = (188281465057972534892223778713752, 3419875491033170827167861896082688),

Q = (1415926535897932384626433832795028, 3846759606494706724286139623885544).

Solution (which took ~6 months to find) is k=312521636014772477161767351856699. The exact same ECDLP is used in our crackme, so fortunately, all we have to do is to implement Nyber-Rueppel scheme and use k above to emit correct signatures :).

See here for sources (dongle\ folder, crackme in crackme\ :)).

References

[1] Henna Pietiläinen, Elliptic curve cryptography on smart cards, page 24, http://goo.gl/Lpr4h

[2] Certicom Research, SEC 2: Recommended Elliptic Curve Domain Parameters, 2000, http://goo.gl/sJV5A

[3] Matthew Musson, Attacking the Elliptic Curve Discrete Logarithm Problem, http://goo.gl/L4Dz8

About these ads
  1. Cyclops
    11/07/2011 at 08:23

    Nice work mate :)

  2. cs
    25/07/2011 at 18:03

    cool, it’s the HBO intro..

  1. 26/09/2011 at 23:10

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: