Check if a generated license is valid

Question

I have a PHP script that generates some strings which will be used as license keys:

function KeyGen(){
     $key = md5(microtime());
     $new_key = '';
     for($i=1; $i <= 25; $i ++ ){
               $new_key .= $key[$i];
               if ( $i%5==0 && $i != 25) $new_key.='-';
     }
  return strtoupper($new_key);
  }
$x = 0;
while($x <= 10) {
  echo KeyGen();
  echo "<br />";
$x++; 
}

After running the script once, I got these:

8B041-EC7D2-0B9E3-09846-E8C71
C8D82-514B9-068BC-8BF80-05061
A18A3-E05E5-7DED7-D09ED-298C4
FB1EC-C9844-B9B20-ADE2F-0858F
E9AED-945C8-4BAAA-6938D-713ED
4D284-C5A3B-734DF-09BD6-6A34C
EF534-3BAE4-860B5-D3260-1CEF8
D84DB-B8C72-5BDEE-1B4FE-24E90
93AF2-80813-CD66E-E7A5E-BF0AE
C3397-93AA3-6239C-28D9F-7A582
D83B8-697C6-58CD1-56F1F-58180

What I now am trying to do is change it so that I have another function that will check if the key has been generated using my script. Currently, what I am thinking is setting the $key to the MD5 of one specific string (for example, test) but, of course, that returns all the strings the same.

Can anyone help?

Unsegregated

Where are you storing these keys? – Shitty

you are hashing a "sortof" random value. without storing it and looking through stored keys you can not know if it was generated by your script. please also note that MD5 does not generate unique values. you might get 2 the same. And using microtime, on a very fast server it might output 10 identical keys. (or at least 2 ;) ) – Selda

@YogeshSuthar This is just me playing around, trying to learn PHP. The values are not being stored anywhere permanently, just once as $mykey = KeyGen(). – Unsegregated

@Selda I know that as well. Thanks for mentioning it though :) – Unsegregated

This is Interesting .. let me see what i can come up with – Cassius

Answer 1

Note:

This solution is on the assumption you want your licence key to always be in fixed format (see below) and still self authenticated

  FORMAT : XXXXX-XXXXX-XXXXX-XXXXX-XXXX

If that is not the case refer to @ircmaxell for a better solution

Introduction

Self authenticated serial is tricky solution because:

• Limited Size of Serial
• It need to authenticate it self without Database or any storage
• If private key is leaked .. it can easily be reversed

Example

$option = new CheckProfile();
$option->name = "My Application"; // Application Name
$option->version = 0.9; // Application Version
$option->username = "Benedict Lewis"; // you can limit the key to per user
$option->uniqid = null; // add if any


$checksum = new Checksum($option);
$key = $checksum->generate();
var_dump($key, $checksum->check($key));

Output

string '40B93-C7FD6-AB5E6-364E2-3B96F' (length=29)
boolean true

Please note that any modification in the Options would change the key and make it invalid;

Checking for collision

I just ran this simple test

set_time_limit(0);

$checksum = new Checksum($option);
$cache = array();
$collision = $error = 0;
for($i = 0; $i < 100000; $i ++) {
    $key = $checksum->generate();
    isset($cache[$key]) and $collision ++;
    $checksum->check($key) or $error ++;
    $cache[$key] = true;
}

printf("Fond %d collision , %d Errors  in 100000 entries", $collision, $error);

Output

  Fond 0 collision , 0 Errors in 100000 entries 

Better Security

By default the script uses sha1 but PHP has a lot of better hash functions you can get that with the following code

print_r(hash_algos());

Example

$checksum = new Checksum($option, null, "sha512");

Class Used

class Checksum {
    // Used used binaray in Hex format
    private $privateKey = "ec340029d65c7125783d8a8b27b77c8a0fcdc6ff23cf04b576063fd9d1273257"; // default
    private $keySize = 32;
    private $profile;
    private $hash = "sha1";

    function __construct($option, $key = null, $hash = "sha1") {
        $this->profile = $option;
        $this->hash = $hash;

        // Use Default Binary Key or generate yours
        $this->privateKey = ($key === null) ? pack('H*', $this->privateKey) : $key;
        $this->keySize = strlen($this->privateKey);
    }

    private function randString($length) {
        $r = 0;
        switch (true) {
            case function_exists("openssl_random_pseudo_bytes") :
                $r = bin2hex(openssl_random_pseudo_bytes($length));
                break;
            case function_exists("mcrypt_create_ivc") :
            default :
                $r = bin2hex(mcrypt_create_iv($length, MCRYPT_DEV_URANDOM));
                break;
        }
        return strtoupper(substr($r, 0, $length));
    }

    public function generate($keys = false) {
        // 10 ramdom char
        $keys = $keys ?  : $this->randString(10);
        $keys = strrev($keys); // reverse string

        // Add keys to options
        $this->profile->keys = $keys;

        // Serialise to convert to string
        $data = json_encode($this->profile);

        // Simple Random Chr authentication
        $hash = hash_hmac($this->hash, $data, $this->privateKey);
        $hash = str_split($hash);

        $step = floor(count($hash) / 15);
        $i = 0;

        $key = array();
        foreach ( array_chunk(str_split($keys), 2) as $v ) {
            $i = $step + $i;
            $key[] = sprintf("%s%s%s%s%s", $hash[$i ++], $v[1], $hash[$i ++], $v[0], $hash[$i ++]);
            $i ++; // increment position
        }
        return strtoupper(implode("-", $key));
    }

    public function check($key) {
        $key = trim($key);
        if (strlen($key) != 29) {
            return false;
        }
        // Exatact ramdom keys
        $keys = implode(array_map(function ($v) {
            return $v[3] . $v[1];
        }, array_map("str_split", explode("-", $key))));

        $keys = strrev($keys); // very important
        return $key === $this->generate($keys);
    }
}

Cassius

Security Through Obscurity at its best. Also, abusing names (what you call a salt is not a salt, but a private key, as its effectiveness is tied to its secrecy). – Yardmaster

Can you show any example of this algorithm being used or vetted for security in the public? It looks REALLY odd and home-grown (especially the $hash1 and $hash2 parts. I mean, why crc32()? It seems like it was derived from the motto The more hash cycles, the better. In other words: SHA1 ALL THE THINGS!. Which offers no increase in security... – Yardmaster

1. Similar case, A offline j2me application the application was distributed via Bluetooth but licensed with 16 code (Its hard) We are to come up with offline verification 2. crc32($keys) exactly what i want ... You did not expect it its all about prediction 3. SHA1 ALL THE THINGS! I am not Merely chaining hash , this is done in the context that preserved the entropy of the 32 binary key. Fine you can argue cryptographic strength of the HMAC depends upon the cryptographic strength of the underlying hash function (sha) but that can be changed. – Cassius

4 yes its how grown and a lof of testing was done even with simple sha not HMAC. 5 Evening without changing the hash function i still argue that its far better than your ` $license = base64_encode($rand . $signature);` which by the way does not meet the OP 25 key licence format. Finally I already said in my answer If that is not the case refer to @Yardmaster for a better solution if you have a better solution to fixed sized (20-25) offline licence and not just by changing (hash function) .. be my guest I love to learn .. thanks – Cassius

@Baba: "surprise" is the enemy of security. The ONLY thing that should be secret is the private key. Remember Schneier's Law: Anyone can invent an encryption scheme that they themselves can't break. My answer is based on tried and true cryptographic principles. The "Option 2" which you're arguing is weak, is the basis for all authententicated cryptography. In fact, it's what the HMAC was designed to do (and how it was designed to work). The only difference is I didn't bother putting it in the format the OP demonstrated. But that's trivial once the security part is taken care of... – Yardmaster

@Yardmaster i see where you are coming from .. thanks for the clarification i would work on improving the class .. thanks – Cassius

Answer 2

There are three basic ways of handling this. How you do it will depend on how many keys you're generating, and how important is may be to be able to invalidate keys at a later day. Which you choose is up to you.

Option 1: Server Database Storage

When the server generates a key (like using your algorithm), you store it in a database. Then later all you need to do to check the key is see if it's in the database.

Note that your algorithm needs a lot more entropy than you're providing it. The current timestamp is NOT enough. Instead, use strong randomness:

$key = mcrypt_create_iv($length_needed, MCRYPT_DEV_URANDOM);

Or, if you don't have mcrypt:

$key = openssl_random_pseudo_bytes($length_needed);

Or if you don't have mcrypt and openssl, use a library

Note that md5 returns a hex output (a-f0-9), where all of the above return full random binary strings (characters 0 - 255). So either base64_encode() it, or bin2hex() it.

Pros:

• Simple to implement
• Can "deactive" issued keys at a later date
• Impossible to forge a new key

Cons:

• Requires persistent storage per key
• May not scale that well
• Requires "key server" to validate keys

Option 2: Signing Keys

Basically, you generate a strong random key (from here out called the private key), and store it on your server. Then, when generating the license key, you generate a random blob, and then HMAC sign it with the private key, and make the license part of that block. That way, you don't need to store each individual key.

function create_key($private_key) {
    $rand = mcrypt_create_iv(10, MCRYPT_DEV_URANDOM);
    $signature = substr(hash_hmac('sha256', $rand, $private_key, true), 0, 10);
    $license = base64_encode($rand . $signature);
    return $license;
}

function check_key($license, $private_key) {
    $tmp = base64_decode($license);
    $rand = substr($tmp, 0, 10);
    $signature = substr($tmp, 10);
    $test = substr(hash_hmac('sha256', $rand, $private_key, true), 0, 10);
    return $test === $signature;
}
    

Pros:

• Simple to implement
• Does not require persistent storage
• Trivial to scale

Cons:

• Cannot "Deactivate" keys individual
• Requires storing "private keys"
• Requires "key server" to validate keys.

Option 3: Public Key Crypto

Basically, you generate a public/private key pair. You embed the public key in your application. Then, you generate a key (similar to "signing keys" above), but instead of signing it with the HMAC signature, you sign it with a private key.

That way, the application (which has the public key) can verify the signature directly without needing to call back to your server.

function create_key($private_key) {
    $rand = mcrypt_create_iv(10, MCRYPT_DEV_URANDOM);

    $pkeyid = openssl_get_privatekey($private_key);
    openssl_sign($rand, $signature, $pkeyid);
    openssl_free_key($pkeyid);

    $license = base64_encode($rand . $signature);
    return $license;
}

function check_key($license, $public_key) {
    $tmp = base64_decode($license);
    $rand = substr($tmp, 0, 10);
    $signature = substr($tmp, 10);

    $pubkeyid = openssl_get_publickey($public_key);
    $ok = openssl_verify($rand, $signature, $pubkeyid);
    openssl_free_key($pubkeyid);

    return $ok === 1;
}

Pros:

• Simple to implement
• Does not require persistent storage
• Trivial to scale
• Does not require "key server" to validate keys

Cons:

• Cannot "Deactivate" keys individual
• Requires storing "private keys"

Yardmaster

Thank's a lot for your answer, sadly I cannot accept both Baba's and yours. – Unsegregated

Option 3: Public Key Crypto is awesome :D I wish to give 10 upvotes!! – Finella

Answer 3

What you are actually looking for is an algorithm like Partial Key Validation

See this article for the workings and port it to PHP

http://www.brandonstaggs.com/2007/07/26/implementing-a-partial-serial-number-verification-system-in-delphi/

Selda

Thanks. It looks like it would be quite a lot of work to convert the Delphi to PHP, so I am still looking for another option but if it comes to it then I will do that. – Unsegregated

Answer 4

Store these keys in a database when you create them.Later match them with the database rows and voila..It will be done

Dermatosis

I understand that the best way is to store in a database, however I am trying to find a way of doing it without storing, in a similar way to how Adobe products can be activated even if they are offline. – Unsegregated

Answer 5

Note that it's not impossible that you will get duplicate keys with this algorithm, it's unlikely, but so is winning the lottery. You will have to store the keys in a database or file to check if it allready exists.

Aintab