Note: Descriptions are shown in the official language in which they were submitted.
CA 02708000 2010-06-18
SYSTEM, APPARATUS AND METHOD FOR LICENSE KEY PERMUTATION
FIELD OF THE INVENTION
[0001] 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
[0002] 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.
[0003] 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.
[0004] 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.
[0005] 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.
1
CA 02708000 2010-06-18
[0006] 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.
[0007] 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.
[0008] 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.
[0009] Illustrative embodiments of the present invention address at least the
drawbacks
associated with conventional system and provide many advantages.
SUMMARY OF THE INVENTION
[0010] 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.
[0011] 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.
[0012] 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.
[0013] 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
2
CA 02708000 2010-06-18
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.
[0014] 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.
[0015] Exemplary embodiments of the present invention provide additional
benefits
relating to systems that use cryptographic data other than
activation/installation key pairs.
[0016] 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
[0017] 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:
[0018] 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.
[0019] 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.
[0020] 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.
[0021] 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.
3
CA 02708000 2010-06-18
[0022] 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.
[0023] 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.
[0024] 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.
[0025] 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.
[0026] Throughout the drawings, like reference numerals will be understood to
refer to
like elements, features and structures.
DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS
[0027] 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.
[0028] 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
4
CA 02708000 2010-06-18
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.
[00291 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:
100301 Hashing the input using an array of bytes;
100311 Using XOR with each byte of the input or an external buffer;
100321 Reverse or jumble the bits in the key using a known pattern;
100331 Run the input through an encryption algorithm;
[00341 Hashing the input using any algorithm (i.e. MD5, SHA1, etc), among
other
obfuscation algorithms.
[00351 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.
[00361 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
CA 02708000 2010-06-18
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.
[0037] 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:
71
I r.(n-r)!
[0038] 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.
[0039] 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
6
CA 02708000 2010-06-18
decrypt and recover the original installation key. The key-server 9 then uses
the usual method to
create a correctly paired product activation key.
[0040] 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.
[0041] 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.
[0042] 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 I 1
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.
[0043] 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.
[0044] 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
7
CA 02708000 2010-06-18
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).
[0045] 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.
[0046] 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).
[0047] 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.
[0048] 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.
[0049] 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.
8
CA 02708000 2010-06-18
[00501 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.
[00511 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.
[00521 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.
100531 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
9
CA 02708000 2010-06-18
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. The media may also be a transmission
medium
such as optical or metallic lines, wave guides, and so on, including a carrier
wave transmitting
signals specifying the program instructions, data structures, and so on.
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.
100541 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.
