Licensing Using Symmetric and Asymmetric Cryptography

Algorithms and enlightenment for license key encryption.


August 01, 2003
URL:http://www.drdobbs.com/licensing-using-symmetric-and-asymmetric/184401687

Licensing Using Symmetric and Asymmetric Cryptography

Licensing is a good way to prevent misuse of your software, to enable temporary use of it, or to enable the creation of a complex pricing model. The best approach to secure and reliable licensing is through cryptography. In this article, I will present two options for implementing a software licensing system: one option uses symmetric (secret) key cryptography, and the other option uses asymmetric (public) key cryptography. I will describe the algorithms and provide a sample implementation based on OpenSSL. In closing, I will compare the two solutions and evaluate their strengths and weaknesses.

The Licensing System

In this article, the term licensing system refers to a system for authenticating access to a software product through the use of a key string supplied by the vendor and input by the user. The license key is typically input at installation, but the same technique could apply to updates or upgrades. Even casual computer users are familiar with the prompt from an installation wizard to enter a string printed somewhere on the package. In this article, I'll discuss where that license string comes from, how it works, and how to implement your own licensing system using OpenSSL.

The licensing system consists of a licensing authority, which issues the license keys, and an application, which consumes them. The inputs to the licensing authority are:

The license authority outputs a 20-digit string (for example, A7BF4-87FE3-1D4A7-8D451) that encodes the list of licensed features, the expiration time, and a piece of information that enables the application to verify the authenticity of the license. This piece of information is a cryptographic Message Authentication Code, also known as the MAC. The user types the license key into the application, which decodes the list of licensed features and the expiration time then verifies the authenticity of the license using the MAC.

In many ways, a license key is the electronic equivalent of a physical key that "unlocks" the software. As such, it should be easy to issue and use licenses but very difficult to forge them. The license key should be linked to a specific instance of the software and should not be transferable or shared between different instances. The license should also include a time limitation feature, which will enable things like temporary licenses or a complex pricing model using yearly licenses.

Once the application authenticates the license and extracts the encoded information, the application can then take any actions necessary to ensure that the software protected by the license is properly configured. The application, in this case, is typically an Install application used to set up and configure the licensed software. Note, however, that the license key encodes a list of licensed features, so this solution lends itself to situations in which a single CD holds all the necessary software for various licensing models and a user upgrades to a higher license level by obtaining a new key from the vendor.

Licensing and Cryptography

Cryptography has many objectives, two of which are most applicable to licensing: Data Integrity and Data Origin Authentication. Data Integrity addresses the unauthorized alteration of data. Data Origin Authentication addresses the identification of the entity that created the data.

The cryptographic MAC mentioned in the previous section ensures both the Data Integrity and the Data Origin Authentication. A valid MAC means that the data provided in the license has not been modified by an unauthorized party and that the licensing authority known to the application has issued the license.

It is not impossible to guess a valid MAC, but it is difficult. The level of difficulty (which is known as the level of security) is often given in terms of the number of operations required to defeat the protection. Typically, the level of security is defined by an upper bound on the number of operations necessary in order to break it.

For example, if a system is "40-bit secure" it means that breaking into it will take up to 2^40=1,099,511,627,776 operations. In our case, if every license check takes 10 msec, then guessing a license will take up to 348 years, which seems quite safe to me.

MAC Calculation

There are several known ways to generate a MAC. I will examine two options: one option uses a symmetric key, and the other option uses an asymmetric key. In symmetric key cryptography, encryption and decryption are performed using the same key. In the asymmetric case, there is a pair of two related keys, private and public. Encryption and signature verification is done using the public key, while decryption and signing is done using the private key (signing is the operation that binds information to an entity). Both implementations are based on well-known and well-tested cryptographic algorithms. It is important not to modify or invent new cryptographic algorithms. The topic is complex, and it is easy to make naïve mistakes.

Symmetric Key MAC

My symmetric key implementation is based on RFC 2104 [1] and FIPS-198a [2]. Both documents describe a mechanism for message authentication using cryptographic hash functions. This mechanism is called HMAC. To make it easier to describe the HMAC algorithm, let's define the following:

The HMAC algorithm takes M and K as input and generates a MAC as follows:

In general, any cryptographic hash function can be used in the HMAC algorithm. I think it is better to use a function that is FIPS approved [2], like SHA-1 [3]. The strength of the MAC depends on the strength of the underlying hash function. Therefore, it is best to avoid hash functions with known security issues like MD2, MD4 and MD5.

SHA-1 output is 160 bit and is considered to be 80-bit secure. This is due to the so-called birthday attack. Any hash function, when supplied with a random input, returns one of k equally likely values. By repeatedly hashing different inputs, we expect to obtain the same output after about k^0.5 trials.

It is a common practice to truncate the output of the MAC algorithm and use only the t leftmost bits as the MAC. You should remember that the probability of guessing a correct MAC is (1/2)t. Therefore, it is recommended to keep t >= L/2 and never use a t that is less than 32 bits. In our case, since each guess takes a while (the user has to somehow type it in and wait for the application response), I think t=48 will do.

Listing 1 provides an implementation of hmac_sha1(). OpenSSL includes an implementation of hmac_sha1, see hmac_openssl_sha1() in the downloadable code archive. Note that the MAC calculation and MAC verification use the exact same algorithm and the same key.

Asymmetric Key MAC

The RSA signature schema as described in RFC 2437 [4] and FIPS-186-2 [5] can be used to authenticate the content of a message. As opposed to the scheme described above, this scheme employs an RSA key pair instead of a single secret key. The data is signed using a private key and the signature is verified using a matching public key.

To make it easier to describe the RSA signature generation and verification algorithms, let's define the following:

The RSA signature generation algorithm takes M and PrivK as input and generates a signature as follows:

The RSA signature verification algorithm takes M, S, and PubK and generates a binary result (valid/invalid) as follows:

For the same reasons described in the symmetric key discussion, the recommended hash function is SHA-1 or one of its siblings SHA-256, 384 and 512.

The RSA signature is as secure as RSA encryption assuming you use a good hashing function (like SHA). Using an RSA private key of 1024 bits gives 80 bits of security. The signature size is 128 bytes (the same as the key size).

It is impossible to truncate the RSA signature. In the symmetric case, since both sides go through the exact same steps and use the same key, we could easily truncate the MAC and compare only the t leftmost bits. In this case, the verification algorithm requires the complete signature.

Listing 2 provides an implementation of rsa_sign() and rsa_verify().

HMAC Licensing System

The licensing authority (see Listing 3) associates a set of features and an expiration date with a specific instance of the licensed software (target system). The set of features is represented as a bit-mask and allows any combination of up to 16 features. The expiration date is represented as days (not seconds) since 1/1/1970. This way it only takes two bytes to represent the date and more room remains for the MAC. The target system is assumed to have a 64-bit unique identifier. You can embed one in your software or create one on the fly based on the system components (such as, CPU ID, MAC, IP address -- somewhat like WinXP [6]).

The licensing authority assembles all this information, calculates the MAC, and outputs the license string. The license string is a user-friendly representation of the following information:

The above ten bytes are converted into a 20-character string.

While processing the licensing string, the application extracts the feature set and the expiration date from the license string. It then concatenates the system-unique id and calculates the MAC. The leftmost bits of the MAC are compared to the bits provided in the license string. If they are identical, the license is valid. Note that the secret key used by the licensing authority must be identical to the key embedded in your application.

Sample Input and Output:
# gen_hmac_license 016653623F 20040101 featue1 feature2
License = 5F431-67DE5-78FF3-22AB3

# ver_hmac_license  5F431-67DE5-78FF3-22AB3
License expires on 2004-01-01, Features = feature1 feature2
I would like to discuss the pros and cons of the above system, but first I will describe the other system which uses asymmetric keys.

RSA Licensing System

The licensing authority in this case (Listing 4) does a similar job to the one described above, but with a few minor twists. The license string is too short to contain the RSA signature (128 bytes). In the previous case, I used the 48 leftmost bits of the HMAC result, and since the process is symmetric, it was good enough. Since the RSA method is asymmetric, the application must receive the complete signature to verify it.

To solve this problem, I will distribute a part of the signature with the application and the rest will come from the license string. The application will combine the two to form a complete signature that can be verified. This can be considered a very primitive form of "secret sharing" (more about this topic in [7]).

Given a target machine, every combination of licensed features and expiration date has a unique signature. Since part of every signature will be shipped with the application, it is necessary to limit the number of combinations.

Therefore, in the RSA based licensing system, the set of features is represented by a smaller bit-mask and allows any combination of up to six features. The expiration date has only 4 possible values, 1 week since activation, 3 months, 1 year, or lifetime. As before, the target system is assumed to have a 64-bit unique identifier.

The licensing authority assembles all this information, signs it using the private key, and outputs a license string. The license string is a user-friendly representation of the following information:

The above ten bytes are converted into a 20-character string.

While processing the license string, the application recreates the original data that was signed by extracting the feature set and the expiration code from the license string and concatenating the system unique id. Then it iterates through all of the partial signatures it has, reconstructs the complete signature by appending them to the signature bits extracted from the license, and tries to verify the message using each one of them (Listing 5). If any of them is valid, the license is valid. Note that the private key used by the licensing authority must be the key pair of the public key embedded in your application.

Cryptographic Considerations

The symmetric-key-generated license described here is less than 48-bit secure. Adding additional characters to the license string can increase it up to 80-bit. But the main security problem lies in the fact that the symmetric key is stored somewhere in the application; if found, it can be used to forge licenses.

The asymmetric-key-generated license described here is less secure. If the license contained the complete signature, it would have been 80-bit secure. Since I suggest embedding most of the signature in the application and including only some of it in the license, the solution cannot be considered to be more than a few bits secure (evaluating the strength is outside the scope of this article). Nevertheless, it is good enough to make a brute-force attack very difficult, and more importantly, breaking one system does not enable the attacker to break the others (as opposed to the symmetric case).

Cryptographic strength aside, you should remember that the license check provides procedural security -- in almost every case there is a procedural way to bypass the cryptographic protection. For example, in many cases the license check is a single if statement in the code. If that check is found and removed, the need for a license is gone.

I ignored the topics of key generation and key management. Good recommendations can be found in FIPS 140-2 [8].

Implementation Considerations

Not all platforms are capable of performing RSA calculations in a reasonable time. Asymmetric key cryptography is hard to implement on systems with limited resources (i.e., 8-bit CPU with no hardware support for RSA). Some platforms are more susceptible to attacks (such as desktops). Using symmetric key solution in such an environment is probably not a prudent idea. In most embedded systems, attacks are harder. This means using symmetric keys is relatively safe. Using different symmetric keys for each version, or even for each distribution batch, will reduce the exposure to attacks on the key.

Regarding the reduced security of the RSA-based licensing solution, if you are not limited by the license format; it is much better (and easier) to distribute the complete signature as part of the license. The license data can contain more information, and it would be impossible to forge a license.

If your platform can support RSA calculations and you can easily distribute the complete RSA signature with the license, you are better off using the asymmetric licensing solution.

References

[1] H. Krawczyk, M. Bellare, and R. Canetti, HMAC: Keyed-Hashing for Message Authentication, Internet Engineering Task Force, Request for Comments (RFC) 2104, and February 1997.

[2] FIPS-198a The Keyed-Hash Message Authentication Code (HMAC) http://csrc.nist.gov/publications/fips/fips198/fips-198a.pdf FIPS -- Federal Information Processing Standards http://csrc.nist.gov/publications/fips/index.html

[3] FIPS-180-2 Secure Hash Standards http://csrc.nist.gov/publications/ fips/fips180-2/fips180-2.pdf

[4] B. Kaliski, J. Staddon, PKCS #1: RSA Cryptography Specifications Version 2.0, Network Working Group, Request for Comments (RFC) 2437, October 1998.

[5] FIPS-186-2 Digital Signature Standard http://csrc.nist.gov/ publications/fips/fips186-2/fips186-2-change1.pdf

[6] The WinXP licensing schema is more complex and involves an online component.

[7] Handbook of Applied Cryptography, by A. Menezes, P. van Oorschot, and S. Vanstone, CRC Press, 1996, pp 524-528, 538-540

[8] FIPS-140-2 Security requirements for Cryptographic Modules http://csrc.nist.gov/cryptval/140-2.htm

Additional Reading

[1] FIPS-196 Entity Authentication Using Public Key Cryptography http://csrc.nist.gov/publications/fips/fips196/fips196.pdf

[2] Another way to calculate a MAC described here http://www.itl.nist.gov/fipspubs/fip113.htm

About the Author

Ilan Shamir has more than 20 years of programming experience. He spent many years with Intel Corp., was a visiting scientist at MIT, and is now working for Decru Inc. that develops wire-speed encryption appliances. He welcomes comments at [email protected].

HexWeb HTML

Listing 1: HMAC using SHA-1

int hmac_sha1(unsigned char *hmac,

size_t hmac_size,

const unsigned char *msg,

size_t msg_len,

const void *key,

size_t key_len)

{

unsigned char padded_key[SHA1_BLOCK_SIZE];

unsigned char k1[SHA1_BLOCK_SIZE];

unsigned char k2[SHA1_BLOCK_SIZE];

unsigned char IPAD[SHA1_BLOCK_SIZE];

unsigned char OPAD[SHA1_BLOCK_SIZE];

unsigned char padded_msg[SHA1_BLOCK_SIZE+msg_len];

unsigned char sha1_result[SHA1_OUTPUT_LEN];

unsigned char padded_res[SHA1_BLOCK_SIZE+SHA1_OUTPUT_LEN];

assert(hmac_size <= SHA1_OUTPUT_LEN);

/* pas key with zeros */

utils_pad(padded_key, sizeof(padded_key),

key, key_len, 0x00, SHA1_BLOCK_SIZE);

/* create IPAD */

utils_pad(IPAD, sizeof(IPAD),

NULL, 0, 0x36, SHA1_BLOCK_SIZE);

/* k1 = padded_key xor IPAD */

utils_xor(k1, sizeof(k1),

padded_key, IPAD);

/* create OPAD */

utils_pad(OPAD, sizeof(OPAD),

NULL, 0, 0x5C, SHA1_BLOCK_SIZE);

/* k2 = padded_key xor OPAD */

utils_xor(k2, sizeof(k2),

padded_key, OPAD);

/* append msg to k1 */

utils_append(padded_msg, sizeof(padded_msg),

k1, sizeof(k1), msg, msg_len);

SHA1(padded_msg, sizeof(k1)+msg_len, sha1_result);

/* append previous result to k2 */

utils_append(padded_res, sizeof(padded_res),

k2, sizeof(k2),

sha1_result, sizeof(sha1_result));

SHA1(padded_res, sizeof(k2)+sizeof(sha1_result),

sha1_result);

/* copy the result */

memcpy(hmac, sha1_result, hmac_size);

return 0;

}

HexWeb HTML

Listing 2 RSA Sign and RSA Verify

#include <assert.h>

#include <openssl/err.h>

#include <openssl/evp.h>

#include "common.h"

#include "rsa.h"

int rsa_openssl_sign(unsigned char *signature,

size_t *sig_size,

const unsigned char *msg,

size_t msg_len,

RSA *key)

{

int rsa_err;

unsigned char sha1_result[SHA1_OUTPUT_LEN];

assert(key && signature && msg);

assert(msg_len > 0);

/* hash and sign the hash result */

SHA1(msg, msg_len, sha1_result);

rsa_err = RSA_sign(NID_sha1,

sha1_result, sizeof(sha1_result),

signature, sig_size,

key);

return (rsa_err == 1)? 0 : -1;

}

int rsa_openssl_verify(const unsigned char *signature,

size_t sig_size,

const unsigned char *msg,

size_t msg_len,

RSA *key,

unsigned int *isValid)

{

unsigned char sha1_result[SHA1_OUTPUT_LEN];

unsigned char sig_copy[sig_size];

assert(key && signature && msg && isValid);

assert(sig_size > 0 && msg_len > 0);

#ifdef DEBUG

ERR_load_crypto_strings();

#endif

/* hash and verify the signature matches */

SHA1(msg, msg_len, sha1_result);

memcpy(sig_copy, signature, sig_size);

*isValid = RSA_verify(NID_sha1,

sha1_result, sizeof(sha1_result),

sig_copy, sig_size,

key);

#ifdef DEBUG

{

int e;

do {

e = ERR_get_error();

fprintf(stderr, "RSA_VERIFY error = %s\n",

ERR_error_string(e, NULL));

} while (e != 0);

}

#endif

return 0;

}

HexWeb HTML

Listing 3: Symmetric key license generation and verification

int genl_symm_generate(char *license,

size_t license_size,

u64 target_id,

u16 exp_date,

u16 features,

const void *symm_key)

{

unsigned char licdata[12];

unsigned char mac[SHA1_OUTPUT_LEN];

unsigned char userlic[10];

assert(license_size > sizeof(licdata)*2);

/* copy data into place */

memcpy(licdata,

(char *)&target_id, sizeof(target_id));

memcpy(licdata + sizeof(target_id),

(char *)&exp_date, sizeof(exp_date));

memcpy(licdata + sizeof(target_id) + sizeof(exp_date),

(char *)&features, sizeof(features));

hmac_sha1(mac, sizeof(mac),

licdata, sizeof(licdata),

symm_key, sizeof(symm_key));

/* create the license string */

memcpy(userlic,

(char *)&exp_date, sizeof(exp_date));

memcpy(userlic + sizeof(exp_date),

(char *)&features, sizeof(features));

memcpy(userlic + sizeof(exp_date) + sizeof(features),

mac, sizeof(userlic) -

(sizeof(exp_date) + sizeof(features)));

/* format it nicely */

utils_bin2str(license, license_size,

userlic, sizeof(userlic));

return 0;

}

int verl_symm_verify(const char *license,

u64 target_id,

const void *symm_key,

u16 *exp_date,

u16 *features,

u8 *isValid)

{

unsigned char lic_bin[10];

size_t licdata_len;

unsigned char licdata[12];

unsigned char mac[SHA1_OUTPUT_LEN];

unsigned char userlic[10];

/* parse the license */

utils_str2bin(lic_bin, sizeof(lic_bin),

&licdata_len, license);

memcpy(exp_date, lic_bin, sizeof(*exp_date));

memcpy(features, lic_bin+sizeof(*exp_date),

sizeof(*features));

/* reconstruct the HMACed data */

memcpy(licdata,

(char *)&target_id, sizeof(target_id));

memcpy(licdata + sizeof(target_id),

(char *)exp_date, sizeof(*exp_date));

memcpy(licdata + sizeof(target_id) + sizeof(*exp_date),

(char *)features, sizeof(*features));

hmac_sha1(mac, sizeof(mac),

licdata, sizeof(licdata),

symm_key, sizeof(symm_key));

{

/* compare the leftmost bits */

int offset = sizeof(*exp_date)+sizeof(*features);

*isValid = 0;

if (memcmp(lic_bin+offset, mac,

sizeof(lic_bin) - offset) == 0)

{

*isValid = 1;

}

}

return 0;

}

HexWeb HTML

Listing 4: Asymmetric key license generation

int genl_asymm_generate(char *license,

size_t license_size,

char *partial_sig,

size_t part_sig_size,

u64 target_id,

u8 lic_features,

RSA *rsa_key)

{

unsigned char licdata[9];

unsigned char signature[128];

size_t sig_len;

unsigned char userlic[10];

/* copy data into place */

memcpy(licdata,

(char *)&target_id, sizeof(target_id));

memcpy(licdata + sizeof(target_id),

(char *)&lic_features, sizeof(lic_features));

/* sign the license */

rsa_openssl_sign(signature, &sig_len,

licdata, sizeof(licdata),

rsa_key);

/* create the license string */

memcpy(userlic,

(char *)&lic_features, sizeof(lic_features));

memcpy(userlic + sizeof(lic_features),

signature, sizeof(userlic) - sizeof(lic_features));

utils_bin2str(license, license_size,

userlic, sizeof(userlic));

/* create the part that should be shipped with the sw */

utils_bin2str(partial_sig, part_sig_size,

signature + sizeof(userlic) - sizeof(lic_features),

sig_len - sizeof(userlic) + sizeof(lic_features));

/* free the key */

keys_free_rsa_key(rsa_key);

return 0;

}

HexWeb HTML

Listing 5 Asymmetric key license verification

int verl_asymm_verify(const char* license,

const char* partial_sig,

u64 target_id,

RSA *rsa_key,

u8 *lic_features,

u8 *isValid)

{

unsigned char lic_bin[10];

size_t licdata_len;

unsigned char licdata[9];

unsigned char signature[512];

unsigned char bin_signature[128];

size_t sig_len;

/* parse the license */

utils_str2bin(lic_bin, sizeof(lic_bin),

&licdata_len, license);

memcpy(lic_features, lic_bin, sizeof(*lic_features));

/* reconstruct the signed data */

memcpy(licdata,

(char *)&target_id, sizeof(target_id));

memcpy(licdata + sizeof(target_id),

(char *)lic_features, sizeof(*lic_features));

/* reconstruct the signature */

strlcpy(signature, license + sizeof(*lic_features)*2,

sizeof(signature));

strlcat(signature, partial_sig, sizeof(signature));

utils_str2bin(bin_signature, sizeof(bin_signature),

&sig_len, signature);

/* try to verify the license */

rsa_openssl_verify(bin_signature, sig_len,

licdata, sizeof(licdata),

rsa_key,

isValid);

/* free the key */

keys_free_rsa_key(rsa_key);

return 0;

}

Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.