Creating a simple keygen

Index | Up

Table of Contents

1. Brief warning

I am not an expert on cryptography, so this article should be interpreted as just some notes about keygens, written by someone who hasn’t worked on real-world keygens. I was just interested on the topic, and decided to write about it. Don’t rely to hard on the information in this article.

2. What is a keygen?

From Wikipedia:

A key generator (key-gen) is a computer program that generates a product licensing key, such as a serial number, necessary to activate for use of a software application. Keygens may be legitimately distributed by software manufacturers for licensing software […], or they may be developed and distributed illegitimately in circumstances of copyright infringement or software piracy.

Note that in this article we are not going to reverse an existing keygen, but instead create our own program that generates and validates keys for users. If you are interested in reversing, I recommend you first read Reversing a simple keygen.

Many programs use the internet to validate the keys, which obviously has some advantages, but in our case we are going to validate them locally.

2.1. Types of license keys

First of all, I am not an expert on this area, so feel free to contribute to this blog if you have any suggestions. For more information about types of licenses, see keygen.sh.

We could use two main formats for the license keys:

  1. Username is embedded in the key: The user doesn’t need to introduce his user, as it’s already embedded in the key. We would need to validate if the key is valid, and extract (decode) the username from it. This is not the case on most commercial products since, as I mentioned, they use the internet to get the user associated to that key from a remote database.
  2. Log-in with a username: The user needs to provide his username, and the key will be checked against it. A key is only valid when comparing it against its username.

Depending on the format, we would have two ways of validating the input key. For the first one, we would have to apply the inverse function of the algorithm to the provided key to validate it and get the username. For the second one, we could just encode the username again to generate the key, and see if it matches with the key provided by the user.

The second validation method I explained is basically what it’s used to validate passwords against the hashes in a database when a user tries to log-in, but the key difference is that, although hashing can’t be reverted, we are encoding the username. The hashing algorithm used to generate a hash is not enough to revert it (since it’s a one-way algorithm), but the algorithm used to encode a key is the only thing needed to decode it.

Since the goal here is to keep it simple, we will be using the second method for our program, although it’s not very secure since the encoding algorithm is embedded in the program itself, and it can be easily reversed. We are going to make a simple key generation function, and an application that uses it to validate an input key from the user.

3. Things to avoid when making the function

When generating a program like this, it’s a good idea to asume that there is going to be someone attempting to reverse our program and figure out how our key generation algorithm works.

Here are some things we should try to avoid when making the function.

3.1. Generating similar keys for similar users

Imagine our algorithm just turned each letter of the name to its position in the alphabet. The user abcd would generate the key 1234.

If we generated the key for the user abzd, only the third character would change, which would tell the person trying to reverse our algorithm that there is a direct relationship between each character in the input and each character in the key.

His problem transforms from “how did this string turn into this other string” into “how did this character turn into this other character”, which is obviously easier to find.

3.2. Making the user and the key lengths proportional

Imagine we had the algorithm from the last example. The user is also able to tell that the lengths of the strings are proportional, for example: 

abcd  -> 1234
abcde -> 12345
ab    -> 12

This is not ideal, since it gives even more information to the person trying to reverse our program.

Our key should have a fixed number of characters, independently of the length of the user. Here are some examples on what to avoid, assuming our key length is 9: 

abcd       -> 123400000 (Same as previous example)
abcd       -> 123412341 (Repetition is easy to tell)
abcdefghij -> 123456789 (Last character is ignored, produces same output as abcdefghi)

3.3. Collisions

In cryptography, a collision is produced when two different inputs produce the same output. This is a problem when hashing, since one of the basic properties of hashes is that they should produce unique outputs.

In our case, we should try to avoid collisions as much as possible, but I won’t be focusing on this too much on this article.

4. The key generation function

This is a simple keygen function I came up with, but it’s far from perfect so feel free to contribute with a better version, as I said above.

The first loop is used to indicate how many times we want to apply the user to the key. This is arbitrary, I used KEY_KEN+1, but it should be at least ceil(KEY_LEN/user_len).

The second loop is used to iterate the user itself. First, it scrambles the bit pairs and bits just like in challenge 2. We then multiply the character in the previous position by the current iteration number (of the outer loop), and we XOR the current character by that number. Lastly, we XOR the character by the length of the user. We do this just to add even more variation to the final output. We can then store this character for the next iteration, and write it to the out pointer. 

#include <stdint.h>
#include <string.h>

#define KEY_LEN 20

static void generate_key(const char* user, uint8_t* out) {
    const int user_len = strlen(user);

    int key_pos          = 0;
    unsigned char last_c = 0;

    /* Iterate the user KEY_LEN+1 times */
    for (int iter = 0; iter < KEY_LEN + 1; iter++) {
        /* Iterate the user */
        for (int user_pos = 0; user[user_pos] != '\0'; user_pos++) {
            unsigned char c = user[user_pos];

            /* Swap every bit pair with the adjactent pair */
            c = ((c & 0x33333333) << 2) | ((c & 0xCCCCCCCC) >> 2);

            /* Swap every bit with the adjactent one */
            c = ((c & 0x55555555) << 1) | ((c & 0xAAAAAAAA) >> 1);

            /* Also change depending on previous char and iteration */
            c ^= (last_c * iter) % 0xFF;

            /* Depending on the length of the input, change the output */
            c ^= user_len & 0xFF;

            /* Save current character for next iteration */
            last_c = c;

            /* Write the char to the current position */
            out[key_pos++] = c;

            /* Don't overflow the key */
            if (key_pos >= KEY_LEN)
                key_pos = 0;
        }
    }
}

This is an example of a simple keygen program: 

#include <stdio.h>

int main(int argc, char** argv) {
    if (argc < 2) {
        fprintf(stderr, "Usage: %s <username>\n", argv[0]);
        return 1;
    }

    const char* username = argv[1];
    uint8_t key[KEY_LEN] = { 0 };

    generate_key(username, key);

    printf("%s : ", username);
    for (int i = 0; i < KEY_LEN; i++)
        printf("%02x", key[i]);
    putchar('\n');

    return 0;
}

5. Validating a user login

We could use the previous keygen program to generate a key for each user, and use that to log-in. In this case we will be using the same generate_key function for comparing the real key with the provided one. This is obviously not ideal, and we should use at least the inverse function of generate_key.

I made these two function for reading the key from the user. The first one just converts a hexadecimal character to its corresponding nibble (group of 4 bits).

The second one reads the user input into a local buffer using scanf. The maximum length of the string should be KEY_LEN*2+1 since every byte takes up 2 characters, and we need an extra space for the null terminator. We iterate each character of the string and, for each pair, we OR the higher nibble (after shifting) with the lower one. 

#include <stdio.c>

/* (KEY_LEN * 2) + '\0' */
#define STR_KEY_LEN 41

/* 'f' -> 15 */
static inline int8_t char2nibble(char c) {
    if (c >= '0' && c <= '9')
        return c - '0';
    else if (c >= 'a' && c <= 'f')
        return c - 'a' + 10;
    else if (c >= 'A' && c <= 'F')
        return c - 'A' + 10;
    else
        return -1;
}

static void read_key(uint8_t* out) {
    int out_pos = 0;

    char key[STR_KEY_LEN] = { 0 };
    scanf("%41s", key);

    /* "3f5d" -> { 0x3f, 0x5d } */
    for (int i = 0; key[i] != '\0'; i++) {
        /* First half of the byte: '3' -> 3 */
        int8_t nibble = char2nibble(key[i]);
        if (nibble == -1)
            break;
        out[out_pos] = nibble;

        i++;
        if (key[i] == '\0')
            break;

        /* Move previous bits to higher half of byte */
        out[out_pos] <<= 4;

        /* Second half of the byte: 'f' -> 15 */
        nibble = char2nibble(key[i]);
        if (nibble == -1)
            break;
        out[out_pos] |= nibble;

        out_pos++;
    }
}

The main function just reads an username with scanf, a key with our read_key, and we generate the real key with generate_key. We compare the two with a simple loop, and store if they match. 

#include <stdbool.h>

int main(void) {
    printf("Username: ");
    char user[255] = { 0 };
    scanf("%255s", user);

    printf("Key: ");
    uint8_t user_key[KEY_LEN] = { 0 };
    read_key(user_key);

    uint8_t real_key[KEY_LEN] = { 0 };
    generate_key(user, real_key);

    bool match = true;
    for (int i = 0; i < KEY_LEN; i++)
        if (user_key[i] != real_key[i])
            match = false;

    if (match)
        puts("Correct key.");
    else
        puts("Invalid key.");

    return 0;
}

6. Other resources