# Patent

## Title
System, apparatus and method for license key permutation

## Abstract

A system and method of dynamically altering the encoding, structure or other attribute of a cryptographic key, typically a license activation key, to render useless keys that have been created by illegal key generation “cracks”. An encoding/decoding engine provides a plurality of key obfuscation algorithms that may alter the structure, encoding or any other attribute of a given key. A changeable combination code is supplied to the encoding/decoding engine that specifies a subset of the algorithms to apply during the encoding or decoding phase. The encoding engine is used during key generation and the decoding engine used during key usage. The same combination code must be used during decoding as was used during encoding to recover the original key or a valid key will not be recovered. Thus, a system can be rapidly re-keyed by selecting a new combination of encoding/decoding algorithms. The selection of algorithms comprises a combination code. The new combination code will result in keys that are incompatible with any existing illegal key generators.

## Background
CROSS-REFERENCE TO RELATED PATENT APPLICATION
This application is a continuation of U.S. patent application Ser. No. 12/818,115, filed Jun. 17, 2010, which claims the benefit of U.S. provisional application Ser. No. 61/213,539, filed Jun. 18, 2009, the entire disclosures of which are hereby incorporated by reference.


FIELD OF THE INVENTION
The present application relates to the areas of software encryption, licensing and security. Particularly, the present invention provides a system, apparatus and method for altering the generation and validation of cryptographic and/or license verification keys using a configurable combination code.
BACKGROUND OF THE INVENTION
Traditionally, application software use license verification systems for controlling use of application software and other protected content employing a key or key-pair that is generated and, at some point, used in protocols whose purpose is typically, but not exclusively, to verify ownership of a software or content license.
These key-based systems are frequently compromised by illegal key generator software applications produced by software crackers. Frequently referred to as “key-gens,” these programs are capable of mimicking the methods used to create license keys. These illegal keys can then be supplied to the application during product activation resulting in theft of the software license.
Traditionally, illegal “key-gen” applications typically rely on analyzing an installation key (i.e. product key) that is either entered manually or scraped from the system. The installation key is analyzed and a correctly paired activation key is generated. These applications are dependent on reproducing the methods that a legitimate system uses to produce these key pairs.
A fundamental technological issue when combating these key-gens is that the underlying primary verification methods and protocols are embedded within application source code. Modifying application logic to thwart illegal key-gens (that is, in order to generate new valid key pairs) can take months or potentially years on larger applications.
Because the effort to design and develop new key generation and license verification protocols is greater than the effort and time to reverse engineer them, the hacker community is capable of rapidly compromising these methods and systems, typically within weeks of a new release of software.
Traditional systems are rigid, difficult and time consuming to change. Like an old iron lock that must be re-forged to change the key, once the method to generate the key has been discovered, it takes far too long to address the problem of re-securing the system.
What is needed is a system that can rapidly alter the structure and methods used to generate the keys and re-secure the system at a rate that is equivalent to or better than the rate at which illegal key generators can compromise those structures and methods.
Illustrative embodiments of the present invention address at least the drawbacks associated with conventional system and provide many advantages.
SUMMARY OF THE INVENTION
As noted above, exemplary embodiments of the present invention address at least the above problems and/or disadvantages, and provide at least the advantages described below.
Exemplary embodiments of the present invention provide a system, method and apparatus that can rapidly alter the structure and methods used to generate the keys and re-secure the system at rate that is equivalent to or better than the rate at which illegal key generators can compromise the keys.
Exemplary embodiments of the present invention provide for a method, system and apparatus for generating and/or utilizing a mangled license key for invalidating an illegally produced key in a computer license validation system by generating a combination key that utilizes a subset of key obfuscation algorithms of a master set or collection of algorithms to encode an installation key, encrypting the installation key using the combination key, thereby producing a mangled license key, and decoding the mangled license key to produce the installation key.
Exemplary embodiments of the present invention provide a system, method and apparatus for invalidating the illegal keys produced illegally by illegal key generator software application programs by altering both the structure of the keys and the methods used to generate the keys. A changeable combination code is used to select a subset of key obfuscation algorithms from a larger master-set. The original key is then processed by this subset of algorithms producing a key that is incompatible with the illegal key generator.
Exemplary embodiments of the present invention provide a system, method and apparatus for altering a license key system to invalidate a compromised key without changing the fundamental construction of the license key system.
Exemplary embodiments of the present invention provide additional benefits relating to systems that use cryptographic data other than activation/installation key pairs.
Further, exemplary embodiments of the present invention provide for a system, method and apparatus for license key permutation in the context of using installation/activation key pairs.



BRIEF DESCRIPTION OF THE DRAWINGS
The above and other exemplary features, aspects and advantages of the present invention will become more apparent from the following detailed description of certain exemplary embodiments thereof when taken in conjunction with the accompanying drawings in which:
FIG. 1 is a schematic block diagram that illustrates an overview of the entire key permutation process within the context of product license activation method, system and apparatus of the present invention, according to an exemplary embodiment.
FIG. 2 is a schematic block diagram that illustrates how selection of a combination code relates to (for example, influences) the algorithms selected for employment during encoding and decoding within the context of product license activation method, system and apparatus of the present invention, according to an exemplary embodiment.
FIG. 3 is a schematic block diagram that illustrates interaction in a system using a static set of algorithms used to generate a mangled key within the context of product license activation method, system and apparatus of the present invention, according to an exemplary embodiment.
FIG. 4 is a schematic block diagram that illustrates how selection of a combination code relates to (for example, influences) the algorithms selected for employment during encoding and decoding within the context of product license activation method, system and apparatus of the present invention, according to an exemplary embodiment.
FIG. 5 is a schematic block diagram that illustrates how selection of a combination code relates to (for example, influences) the algorithms selected for employment during encoding and decoding within the context of product license activation method, system and apparatus of the present invention, according to an exemplary embodiment of the present invention.
FIG. 6 is a flow diagram that illustrates an overview of the method for utilizing a mangled installation key for invalidating an illegally produced installation key in a computer license validation system, according to an exemplary implementation of the present invention.
FIG. 7 is a schematic block diagram that illustrates an apparatus for generating a mangled license installation key for invalidating an illegally produced key, according to an exemplary embodiment of the present invention.
FIG. 8 is a schematic block diagram that illustrates a computer license validation system for generating a mangled license installation key for invalidating an illegally produced key, according to an exemplary embodiment of the present invention.



Throughout the drawings, like reference numerals will be understood to refer to like elements, features and structures.
DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS
The matters exemplified in this description are provided to assist with a comprehensive understanding of exemplary embodiments of the present invention described with reference to the accompanying drawing figures. Accordingly, those of ordinary skill in the art will recognize that various changes and modifications of the exemplary embodiments described herein can be made without departing from the scope and spirit of the present invention. Also, descriptions of well-known functions and constructions are omitted for clarity and conciseness. Likewise, certain naming conventions, labels and terms as used in the context of the present disclosure are, as would be understood by skilled artisans, non-limiting and provided only for illustrative purposes to facilitate understanding of certain exemplary implementations of the embodiments of the present invention.
FIGS. 1-8 illustrate exemplary embodiments of the present invention that provide for a method, system and apparatus for generating and/or utilizing a mangled installation key for invalidating an illegally produced installation key in a computer license validation system by generating a combination key to utilize a subset of key obfuscation algorithms to encode an installation key, encrypting the installation key in accordance with the combination key, thereby producing a mangled installation key, and then decoding the mangled installation key to produce the installation key.
FIG. 1 is a schematic block diagram that illustrates an overview of the key permutation process within the context of product license activation method, system and apparatus of the present invention, according to an exemplary embodiment. For example, when an application 1 generates an installation key 2, it passes it to the encoder 3 for processing. A “combination key” 4 is generated by passing seed data 5 (for example, seed data can be any data that is known, generated or stored by the application, such as a hardware identifier, the original activation key or installation key) through a series of obfuscation algorithms (1 . . . n). The output of each algorithm is chained to the input of the next creating a complex code path 6. An algorithm can be any algorithm such as a hashing algorithm, mathematical algorithm or any other algorithm, provided that the algorithm produces consistent results. Some exemplary obfuscation algorithms are:
Hashing the input using an array of bytes;
Using XOR with each byte of the input or an external buffer;
Reverse or jumble the bits in the key using a known pattern;
Run the input through an encryption algorithm;
Hashing the input using any algorithm (i.e. MD5, SHA1, etc), among other obfuscation algorithms.
Once generated, the combination key is used to encrypt 7 the original installation key and produce a new permutation of the key which can be referred to as a mangled key or mangled installation key 8.
According to exemplary implementations of the present invention, the obfuscation algorithms used during the combination key generation phase are a sub-set of a larger collection of algorithms, all of which are known to the decoder (e.g., decoder 11 in FIG. 1) and are all stored at a server (e.g. key server 9 in FIG. 1) to allow it to generate an activation code corresponding to the installation code when license verification is desired. This allows the selection of a sub-set of the algorithms during the key obfuscation phase using a combination code which specifies the obfuscation algorithms to employ. Alternatively, the sub-set of algorithms can be selected and then the combination code generated based on those selected algorithms. Changing the combination code changes the selection of algorithms used to create the mangled installation key resulting in an output unique to the given combination code.
FIG. 2 is a schematic block diagram that illustrates a combination selection according to an exemplary implementation of the present invention, where any number or combination of algorithms may be used, order is not important, and each algorithm may preferably only be used once within a combination, so the formula to calculate the number of possible key combinations is:




  
    ∑
    
      r
      =
      1
    
    n
  
  ⁢
  
    
  
  ⁢
  
    
      n
      !
    
    
      
        r
        !
      
      ⁢
      
        
          (
          
            n
            -
            r
          
          )
        
        !
      
    
  




where n is the number of algorithms and r is the number selected. With modest obfuscation algorithms such as 16 algorithms, 65535 unique combinations are possible. Because the combination key is generated dynamically, it is not possible to use static analysis to determine how the installation key was encrypted (e.g., mangled) to thwart hackers from illegally obtaining and using the installation key. Furthermore, because the combination code is actually specifying the algorithms to employ, it forces the process of key generation through a path of execution unique to the given code. This, in turn, means that for any new combination, a software cracker would be forced to do an active re-analysis of the key generation process in order to produce an illegal key-gen for that code. This makes it difficult for the cracker to reverse engineer but easy for a legitimate system because all that is required is a change to the combination code.
With continued reference to FIG. 1, when a key-server 9 needs to generate a key pair, it passes the mangled key 10 to the decoder 11 along with the combination code 12. The decoder parses the combination code 12 to determine which algorithms were used to generate the combination key. The combination code may be supplied through various sources such as via an end user 13, an external system 14 or by obfuscation 15 (for example, embedded in the application code), or passing it with the mangled key. The combination code is then used to decrypt and recover the original installation key. The key-server 9 then uses the usual method to create a correctly paired product activation key.
According to exemplary embodiments of the present invention, the key encoder may work in a static, dynamic or hybrid implementation employing both static and dynamic encoding.
According to an exemplary embodiment of the present invention, in a static implementation, the encoder is compiled using a hard coded sub-set of algorithms. The combination code in this case could be a static value well-known by the decoder. This has the advantage that there is no need to transmit the combination code and only a sub-set of the algorithms need to be exposed on a target system, making it impossible to perform any local analysis on the entire set of the collection of algorithms used by the server 9.
FIG. 3 is a schematic block diagram that illustrates a static encoder which comprises a fixed set of obfuscation algorithms 16 (e.g., a subset of the collection of algorithms used by the server 9) that are hard-coded and compiled into the application code, according to an exemplary embodiment of the present invention. These algorithms generate the combination key 17 that is used to encrypt 18 the original key 19 producing a mangled key 20. The decoder 11 must be supplied a combination code that matches the hard-coded algorithms employed in the static encoder. If an illegal key-gen program is discovered, a new version of the static encoder must be released that implements a different combination of all or some of the subset of hard-coded obfuscation algorithms 16 compiled into the application code.
According to an exemplary embodiment of the present invention, in a dynamic implementation, the encoder can implement preferably the entire set of the collection of obfuscation algorithms used by the server 9. These algorithms are selected dynamically based on a given combination code. This method has the advantage that new combinations can be created without a software release (e.g., the combination can be communicated a different way to the decoder than compiled, for example, in the application code) but at the cost of exposing more of the system for analysis by a hostile party.
FIG. 4 is a schematic block diagram that illustrates a dynamic encoder implementing a richer set of obfuscation algorithms 21 than a static encoder (e.g., in FIG. 3), according to an exemplary embodiment of the present invention. During the encoding phase, a combination code 22 is supplied that specifies the algorithms to employ (23) when generating the combination key (24). The combination key (24) is used to encrypt (26) the given original key (27) producing a mangled key (28) that is unique to the given combination code (22).
According to an exemplary embodiment of the present invention, a hybrid implementation can use a combination of hard-coded algorithms and a dynamically selected set. This may provide the best balance between security and flexibility.
According to an exemplary embodiment of the present invention, if an illegal key-gen program is discovered, a different combination code is supplied to force the creation of an incompatible mangled key (28).
According to an exemplary embodiment of the present invention, FIG. 5 illustrates that, at some point, the original key is recovered so it can be used during a normal process of key-pair generation, encryption, verification or other key use typical of a cryptographic or secure system. There may be multiple versions of static and dynamic encoders that have been built for different usage scenarios or to combat illegal key-gens. The decoder includes every obfuscation algorithm (30) that is employed in these encoders.
Every algorithm in use has a unique identifier that is encoded in the combination code (31). This allows the decoder to determine which specific set of obfuscation algorithms (30) were employed in the generation of the mangled key (32). The correct set of algorithms is selected based on information from the combination code (31) and a combination key (33) is generated. The combination key (33) is used to decrypt (34) the mangled key (32) and recover the original key (35). Once the original key has been recovered, the system may use it normally in any cryptographic or other secure process.
FIG. 6 illustrates an exemplary embodiment of the present invention providing a method 600 for utilizing a mangled installation key for invalidating an illegally produced key in a computer license validation system, the method comprising the steps of obtaining an installation key 601, selecting a subset of key obfuscation algorithms from a master set of key obfuscation algorithms based on a combination code 602, generating a combination key by processing seed data with the subset of key obfuscation algorithms 603, and generating the mangled installation key by processing the installation key with the combination key 604, wherein the mangled installation key is different than the illegally produced key, and wherein the method is computer-implemented.
FIG. 7 illustrates an exemplary embodiment of the present invention providing a computer 706, 707 implemented apparatus 700 generating a mangled installation key for invalidating an illegally produced key, the apparatus comprising an application unit for generating or obtaining an installation key 701, a key server for generating a product activation key and installation key pair 702, an encoding unit for generating a combination key by selecting a subset of key obfuscation algorithms from a master set of key obfuscation algorithms based on a combination code 703, an encryption unit for encrypting the installation key using the combination key and thereby, producing a mangled installation key 704, and a decoding unit for decoding the mangled installation key, thereby producing a result installation key, and further comprising selecting the subset of key obfuscation algorithms from the master set of key obfuscation algorithms provided at the decoding unit, based on the combination code 705, wherein the mangled installation key is a varied permutation of the installation key.
FIG. 8 illustrates an exemplary embodiment of the present invention providing a computer license validation system 800 for generating a mangled installation key for invalidating an illegally produced key, the system comprising an encoder for encoding and producing the mangled installation key by processing an installation key with a subset of key obfuscation algorithms selected from a master set of key obfuscation algorithms based on a combination code 801, and a decoder for decoding the mangled installation key by processing the mangled installation key with a subset of key obfuscation algorithms selected from a master set of key obfuscation algorithms provided at the decoder based on a combination code, thereby producing a result installation key 802.
Further, FIG. 8 illustrates an exemplary embodiment of the present invention providing a system 800 comprising a computer processor 803 for executing a computer program embodied on a computer readable storage medium, the computer program executing instructions for generating a mangled installation key for invalidating an illegally produced key.
The above-described exemplary embodiments of an apparatus, system and method in computer-readable media include program instructions to implement various operations embodied by a computer. The media may also include, alone or in combination with the program instructions, data files, data structures, and the like. The media and program instructions may be those specially designed and constructed for the purposes of the present invention, or they may be of the kind well-known and available to those having skill in the computer software arts. Examples of computer-readable media include magnetic media such as hard disks, floppy disks, and magnetic tape; optical media such as CD ROM disks and DVD; magneto-optical media such as optical disks; and hardware devices that are specially configured to store and perform program instructions, such as read-only memory (ROM), random access memory (RAM), flash memory, and the like. Examples of program instructions include both machine code, such as produced by a compiler, and files containing higher level code that may be executed by the computer using an interpreter. The described hardware devices may be configured to act as one or more software modules in order to perform the operations of the above-described embodiments of the present invention.
Although exemplary embodiments of the present invention have been disclosed for illustrative purposes, those skilled in the art will appreciate that various modifications, additions, and substitutions are possible, without departing from the scope of the present invention. Therefore, the present invention is not limited to the above-described embodiments, but is defined by the following claims, along with their full scope of equivalents.

## Claims

1. A method for utilizing a mangled installation key for invalidating an illegally produced key in a computer license validation system having an encoder and decoder, the method comprising the steps of:
storing a master set comprising a plurality of predetermined key obfuscation algorithms on a non-transitory computer-readable medium in the computer license validation system;
designating a combination code that specifies selected ones of the predetermined key obfuscation algorithms stored in the master set to be included in a subset and providing the combination code to the encoder and the decoder before any installation key is obtained, the key obfuscation algorithms in the subset being selected from among the predetermined key obfuscation algorithms in the stored master set and not including all of the predetermined key obfuscation algorithms of the master set;
obtaining an installation key;
generating, by a microprocessor functionally executing the encoder, a combination key by processing seed data with the subset of key obfuscation algorithms specified by the combination code;
generating the mangled installation key by processing the installation key with the combination key; and
decoding, by a second microprocessor functionally executing the decoder, the mangled installation key by processing the mangled installation key with the algorithms specified by the combination code.

2. The method of claim 1, wherein the installation key is entered by a user or obtained by the system.

3. The method of claim 1, wherein designating the combination code and the key obfuscation algorithms in the subset comprises generating the combination code based on the selected ones of the predetermined key obfuscation algorithms.

4. The method of claim 1, wherein the seed data comprises data that is retained, stored or generated by the system.

5. The method of claim 1 further comprising decoding the mangled installation key by processing the mangled installation key with the combination code for producing a result installation key.

6. The method of claim 5, wherein the result installation key is equivalent to the installation key.

7. The method of claim 5, wherein the decoding further comprises accessing a subset of key obfuscation algorithms from a copy of the master set of key obfuscation algorithms provided at the decoder based on the combination code to process the mangled installation key with the subset of key obfuscation algorithms used to produce the result installation key.

8. The apparatus of claim 1, wherein the encoder and decoder are implemented by a programmed processing device.

9. A computer license validation system for generating a mangled installation key for invalidating an illegally produced key, the system comprising:
a non-transitory computer-readable storage medium configured to store a master set comprising a plurality of predetermined key obfuscation algorithms;
a microprocessor functionally executing an encoder;
an encryption unit; and
a second microprocessor functionally executing a decoder;
wherein the encoder is configured to designate a combination code that specifies selected ones of the predetermined key obfuscation algorithms stored in the master set to be included in a subset, the key obfuscation algorithms in the subset being selected from among the predetermined key obfuscation algorithms in the stored master set and not including all of the predetermined key obfuscation algorithms of the master set;
wherein the encoder and the decoder are provided with the combination code before any installation key is obtained;
the encoder generates a combination key by processing seed data with the subset of key obfuscation algorithms specified by the combination code;
wherein the encryption unit generates a mangled installation key by processing an installation key with the combination key; and
wherein the decoder decodes the mangled installation key by processing the mangled installation key with the algorithms specified by the combination code to obtain the installation key.

10. The apparatus of claim 9, further comprising a key server for generating a key pair comprising the installation key and an activation key.

11. The apparatus of claim 9, wherein the installation key is received from a user, received from an application and/or determined by the license validation system.

12. The apparatus of claim 9, wherein the encoder, encryption unit and decoder are implemented by a programmed processing device.