`[11] Patent Number:
`[19]
`United States Patent
`
`Earnest
`.
`[45] Date of Patent:
`Dec. 19, 1989
`
`................................ .. 178/22.08
`3/1984 Best
`4.465.901
`9/1984 Donald et al.
`........ .. 380/4
`4,471,l63
`6/1986 Piekholtz . . . . , .
`. . . , . . ,. 330/25
`4,593,353
`3/193? Pailen er al.
`.. 364/200
`4,652,990
`1/1938 Weiss .......... ..
`380/23
`4,120,860
`4,123,234 2/1933 Munck eta]. .
`330/25
`4,759,062
`7/1983 Traub et a1.
`380/25
`
`
`
`[54] MODULAR SOFTWARE SECURITY
`
`'
`Lester 0- Earnest. L08 Aitos Hflls.
`Calif.
`
`[75]
`
`Inventor:
`
`.
`.
`[73] ASS‘gnee‘ OMS! I'm" MOb‘le' Ala'
`[21] AWL No; 394,035
`
`[22] Filed:
`
`Aug. 7. 1986
`
`'
`
`OTHER PUBLICATIONS
`
`I
`
`[63]
`
`_
`_
`Related U.S. Appllcatlon Data
`Continuation of Ser. No. 725.254, Apr. 19, 1935, aban»
`cloned.
`
`Deming, Cypragmphy and Data Security, 9. 25; (Ad-
`dison—Wesley, 1982).
`“Cipher Systems" by Beker and Piper, p. 180, 233—235,
`1982.
`
`Examiner—Stephen C_ Bucmki
`Assists”; Emmfflgr_gemm Ear} Gregory
`Attorney, Agent, or Firm—Webb, Burden, Ziesenheim &
`web},
`
`[57]
`
`ABSTRACT
`
`Disclosed is a. computer method and apparatus that
`permits identical copies of encrypted cornputer soft-
`were (including a number of software elements) to be
`distributed to many users while retaining central con—
`trol over which elements are "unlocked", that is, are
`_ a“th°md f0” “5'3 by 33°11 “35"-
`
`13 Claims, 1 Drawing Sheet
`
`[52]
`
`Int. CL‘ mu...u..u..u......................-......
`13.5. CI. .......................................... 330/4; 380/25;
`340/325-1513 340325-34
`[53} Field of Search ............... 123/2203, 22.09, 22.10,
`128/2114; 380/23—25, 23, 3, 4; 364/200, 900
`.
`References Cited
`
`[56]
`
`US PATENT DOCUMENTS
`3,962.539
`6/1976 Ehxsam et al.
`413502.310 11/1931 BOIII'iCius at 31-
`fi’igg'ggg
`'3‘ 31'
`211934 Best
`4:433:20?
`4.439,330 3/1934 Chueh ..... .
`4,446,519
`5/1939 Thomas
`
`
`
`ITS/22.07
`------- 354/200
`83:12:02,3:
`173122.09
`1:... 364/200
`330/25
`
`
`
`
`
`
`
` CRACKER
`NOVRAM 12-]
`
`
`
`CAPABILITY
`
`COUNT
`
`DIRECTORY
`
`FLOPPY
`DISC
`
`PMC Exhibit 2141
`
`Apple v. PMC
`|PR2016-01520
`
`Page 1
`
`COMPUTER
`(MC 68000)
`
`SERIAL NO.
`
`mn-
`
`'
`
`PMC Exhibit 2141
`Apple v. PMC
`IPR2016-01520
`Page 1
`
`
`
`
`
`US. Patent
`
`Dec. 19,1939
`
`4,888,798
`
`COMPUTER
`(MC SBOOOI
`
` KEY
`
`FILE
`
`
`
`
`
`SERIAL N0.
`
`
`
`
` TICATION KEY
`
`
`
`
`' MATCH ACCESS KEYS -
`IN FILES WITH "0"
`
`CAPABILITY KEYS.
`IF MATCHED,ENTER
`CAPABILITY KEY
`IN DIRECTORY
`
`
`
`
`COMPUTE CONTROL
`WORDS FORM
`SERIAL NO.
`
`
`INCREMENT
`CRACKER
`
`COUNT
`
`
`
`TRANSFORM
`CAPABILITY KEY
`
`INTO AUTHEN-
`
`TICATION BI
`
`PERFORM
`EXCESS
`
`ACCESS KEYS
`CRACKER
`CRACKER
`
`COgNT
`COUNTER MEASURES
`
`
`
`I FIg. 2
`
`PMC Exhibit 2141
`
`Apple v. PMC
`|PR2016-01520
`
`Page 2
`
`
`
`PMC Exhibit 2141
`Apple v. PMC
`IPR2016-01520
`Page 2
`
`
`
`
`
`ll]
`
`15
`
`20
`
`This application is a continuation of application
`06/125,254. filed Apr. 19. 1985. now abandoned.
`The present invention relates to computers and cryp-
`tosystems for use with computer software to prevent
`unauthorized use of the software on computers.
`Frequently, a computer system is capable of receiv-
`ing software which includes a number of different ele-
`ments (sometimes called til. hinotions. modules. capa-
`bilities or options). Each element (file) may be segre-
`gated from the other elements so that the elements may
`be priced separately or othenvise separately controlled.
`The software distributor needs to deliver to each com-
`puter user those elements for which the computer user
`pays or is otherwise authorized. The software distribu-
`tor wishes to prevent unauthorized users from having
`access to the elents for which the users have not paid
`or are otherwise unauthorized. Also. the distributor
`does not wish the user to be able to cOpy or otherwise
`share the software with other unauthorized users.
`The ease with which computer software can be cop-
`ied is both a great operational convenience and a great
`commercial weakness. Once a copy of sofiware for
`standard computers has been delivered to a user in some
`form. it is usually a simple matter for the user to repli-
`cate and redistribute the software to other users
`_whether or not the other users are authorized. Legal
`barriers. such as software licensing agreements and
`copyrights. offer some protection against unauthorized
`use. particularly for expensive software that has a lim-
`ited number of users. Legal barriers offer less practical
`protection for low-priced software that runs on many
`machines such as personal computers.
`In the environment where the software distributor
`also controls the design of the computer hardware on
`which the software will run. it is possible to erect barri-
`ers to unauthorized use by using encrypted software.
`For example. each computer may have an assigned
`identity key (typically, a unique serial number) that is
`accessible to the computer program and may have a
`built—in decryptiOn mechanism which utilizes’the iden-
`tity ltcy as a decryption key. When encrypted software
`is loaded into the computer. the software is automati-
`cally decrypted using the assigned computer identity
`key as the decryption key. In such a eryptosystem, any
`attempt to load encrypted software created for a differ-
`ent computer will fail because of the inability to decrypt
`the sofiware. Key stream crypting in a cryptosystem is
`executed typically as follows.
`Key-stream encryden uses the same process to ei-
`ther encrypt an unencrypted software element (file) or
`to decrypt an encrypted software element (file) to re-
`store the encrypted element (file) to its original unen-
`crypted form. The source data from the unencrypted
`software element (file) is treated as a data stream (that
`is. as a string of bits). Typically. the encryption process
`performs an "exclusive-or” operation between each bit
`of the source data stream and a corresponding bit from
`a key data stream. The key data stream is typically a
`random or pseudo-random sequence of bits. The result
`of this encryption operation is an encrypted data stream
`in which 0‘s and 1‘s occur with approiiimately equal
`probability.
`.
`_
`Decryption of the encrypted data stream is accom-
`plished by performing exactly the same “exclusive-or"
`
`
`
`1
`
`4,888,798
`
`MODULAR SOFTWARE SECURITY
`
`BACKGROUND OF THE INVENTION
`
`5
`
`2
`operation on the encrypted data stream, using the same
`key data stream as was used during encryption. The
`second “exclusive-or" operation utilizing the same key
`data stream restores the encrypted data stream to its
`original unencrypted source data stream form. In other
`words. the "exclusive or" operation is its own inverse.
`In order for this key-stream cryptosystem to work. it is
`necessary to use identical key data streams in both the
`encryption and decryption prosesses.
`By using key-stream crypting on software elements
`(files) stored on floppy disk or other media. the contents
`of those elements (files) are rendered unintelligible in
`the sense that a static analysis yields no information
`since the stored data looks like random bit patterns.
`Pseudorandom number generators can be made to
`synthesize suitable key data streams. They have the nice
`property that they can generate a wide variety of such
`key streams under parametric control. In one system.
`for example. a simple additive process is used to gener-
`ate the irey-stream. Beginning with a “seed key" {a
`starting value for the “old key”). a “new key” is gener-
`ated using 32-bit words by the following calculation of
`Eq.(1).
`
`25
`
`30
`
`35
`
`45
`
`55
`
`65
`
`"new key"=(“seed key"+"code")rnndulo 32
`
`mm
`
`In Eq.(1). the "code" is a constant in any given software
`version. By choosing different values of the “seed key"
`and “code” for differt software versions. Eq.(l) gen-
`erates a series of quite different "new keys".
`Many other simple or elaborate key-stream generaa
`tors are possible and have been described in well-known
`literature under the category “pseudo-random number
`generators."
`While the above key-stream cryptosystem makes
`unauthorized use of software difficult, the cryptosystem
`creates a serious problem for the software distributor
`since the cryptosystem requires that the software be
`specifically encrypted for each machine on which it is
`to be run based on the identity key of that machine.
`Therefore. the software to be distributed is different for
`each computer so that the distributor must treat every
`user’s computer differently and such treatment is obvi-
`ously inefficient and expensive;
`In view of the above limitations, there is a need for
`impmved software cryptosystems which do not require
`a different encrypting of the software for each com-
`puter authorized to use the software.
`SUMMARY OF THE INVENTION
`
`The present invention is a computer method and
`apparatus that permits identical cepies of encrypted
`computer software (including a number of software
`elements) to be distributéd to many users while retain-
`ing central control over which elements are "un-
`locked". that is. are authorized for use by each user.
`The computer software after distribution to a user is
`stored udthin the user’s computer and may include both
`authorized and unauthorized elements. The user may
`“unlock” any one or more of the authorized elements by
`entering corresponding encrypted capability keys. usu-
`ally one ltey for each authorised element. Each of the
`capability keys typically is a short string of alphanu-
`meric characters entered through a keyboard or equiva-
`lent input device. While the capability keys may be
`different for each computer.
`the computer software
`including the encrypted elements are the same for all
`
`PMC Exhibit 2141
`
`Apple v. PMC
`|PR2016-01520
`
`Page 3
`
`PMC Exhibit 2141
`Apple v. PMC
`IPR2016-01520
`Page 3
`
`
`
`4.888.798
`
`3
`computers so that the software can be copied and dis-
`seminated by a distributor without concern about
`whether or not use of any particular element is autho-
`rized.
`The user’s computer syst has interlocks that per-
`mit only those elements that have been "unlocked" by
`entry of a capability key to function in the computer. At
`the time of the
`delivery of the'software. the user
`is given capability keys for only those elements that the
`user has purchased or for which the user is otherwise
`authorized. If the user later obtains additional capability
`keys corresponding to newly authorized elements. the
`user is then able to access the corresponding newly
`authorized elements. Typically, the newly authorized
`elements are already stored in the user’s computer so
`that there is no need for the user to again receive the
`newly authorized software elements. The user need
`only receive the capability keys for those elements.
`The computer software is typically distributed in
`different versions where each version has a different
`key-stream generator and encrypts software elements
`differently.
`The present invention ofl‘ers a substantial barrier to
`casual software piracy while facilitating software up-
`dates. Key-stream crypting (encryption and decryption)
`is used in the security system as a "first line of defense"
`together with capability keys which provide modular
`control of access to software elements.
`In one embodiment. the number of uses of a software
`element authorized by a capability key is limited. When
`the limit for one capability key is reached. a user is
`required to enter another capability key to obtain autho-
`rization for additional uses of the same software ele-
`ment.
`
`lo
`
`15
`
`20
`
`25
`
`30
`
`35
`
`In a specific embodiment. the modular sofiware secu-
`rity system permits modular control of access to soft—
`ware elements using specific "keys". including a “capa-
`bility” key. an “identity” key. and a “stor
`" key.
`The stored key is a key which is identical to the trans-
`formed key resulting from the transform of the capabil-
`ity key and the identity key. In one typical system, the
`stored key has two components. namely. an “authenti-
`cation" key and an "access" key.
`'
`When .the user is authorized to use a particular soft—
`ware element, as evidenced by the user having the cor-
`responding capability key. the user enters the capability
`key into the user's computer system. The user’s com-
`puter system transforms the capability key using the
`identity key to form a transformed key. The trans-
`formed key is then compared with the stored key and if
`a match occurs. that match indicates that access to the
`protected software element is authorized. Each “capa-
`bility” key is provided to the user by the software dis-
`tributor and controls access to a particular software
`elemt.
`The "identity" key is a number for identifying a par-
`ticular computer. user or other thing. When used to
`identify a computer, the identity key is permanently
`stored in the user's computer and is unique to the user's
`computer and therefore can function to assure that the
`authorized software element is authorized only for the
`computer having the proper identity key. The identity
`key transforms the capability key.
`The “authentication” key is an arbitrary number that
`is compiled into the firmware of the computer system.
`The authentication key is used to check the validity of
`capability keys that are entered. All systems that use a'
`given firmware version typically have the same authen-
`
`
`
`4
`tication key. but the authentication key may be changed
`between versions.
`Each software element in the system has an associ-
`ated “accem” key which must be matched with a por-
`tion of the transformed capability key to obtain permis-
`sion to access the file. Typically, the access key is inter-
`leaved with the file data stored in the software element
`in a way that depends on the firmware version.
`At the time of delivery of the computer system, the
`system has a stored key including an authentication key
`(software version dependent) an access key (one for
`each element).'and a machine identity key (different for
`each computer). When the computer system is started.
`the system decrypts and downloads the computer soft-
`ware including certain main operating programs from
`the floppy disk or other program source using the same
`key-stream decryption process for all software. The
`cornputer software on the disk has a directory element
`that associates software element names with disk ad-
`dresses and capability keys. Generally,
`there is one
`capability key per software element. Each software
`element stores an access key. generally in a number of
`distributed locations that are software version-depend-
`ent. Any elements with access keys of “0" are consid-
`ered to be “unprotected” and no capability key is
`needed to access them.
`In its
`configuration (before entry of any capa-
`bility keys). the capability keys of all elements are set to
`a pre-establish value. for example. "0". No element with
`a capability key “0" can be accessed until a non-zero
`capability key has been computed and stored in the
`corresponding capability key field of the element direc-
`tory except for unprotected elements which, as indi-
`cated by a “0" access key. require no capability key.
`Initially, therefore. before entry of any capability key,
`only the unprotected elements are accessible. Addi-
`tional software elements having non-zero access keys
`can be “unlock " by a capability key unlocking pro-
`C55.
`
`
`
`the system and to unlock a pro-
`In order to
`tected element using the unlocking process. a capability
`key for the protected element is entered into the system.
`The entered capability key is transformed with the sys—
`tem identity key to form a transformed key- The trans-
`formed key is compared with the stored key. Typically.
`a portion of the transformed key is compared with the
`authentication key stored in firmware to verify the
`entered capability key’s authenticity. If an authentica-
`tion match occurs. the match resulting from entry of the
`correct capability key is used to "unlock" protected
`elements provided also that access is authorized. If an
`'
`'
`a special
`
`d5
`
`50
`
`55
`
`60
`
`65
`
`formed.
`If the authentication key is matched correctly. each
`element that has a “0" in its capability key field in the
`element directory is examined to determine which ele-
`ments also have an access key matching another portion
`of the transformed capability key. Wherever an access
`key match is found. the capability key (not the trans-
`formed capability key) is stored into the capability key
`field of that element in the element directory. When the
`capability key is thus stored in the directory. the pro-
`tected element has been unlocked and is available for
`use. In order to access the protected element. however.
`the capability key must be entered before each access.
`Thereafter. whenever access to a software element is '
`requested. the capability key stored (if any) in the ele-
`
`PMC Exhibit 2141
`
`Apple v. PMC
`|PR2016-01520
`
`Page 4
`
`PMC Exhibit 2141
`Apple v. PMC
`IPR2016-01520
`Page 4
`
`
`
`4,838,793
`
`6
`Software file storage 17 is employed for storing soft-
`ware elements in encrypted form. Storage l’l‘ typically
`includes a floppy disk which stores programs (including
`a number of protected software elements such as font
`files), other data, and an element directory in encrypted
`form.
`.
`Key-stream crypting is used to render all software
`elements stored in storage 17 unintelligible until key-
`Stream decrypting is performed. The key-stream crypt-
`ing is the same for all software elements of a particular
`version ofthe software and is the same for all computers
`(printers) of a particular release; but the crypting may
`be different for other versions of the software and other
`releases of the cornputer. The function of the key-
`stream cryptosystem is to make static analysis of soft-
`ware elements difficult, but such a key-Stream cryp-
`tosystem is not necessary for the "unlocking" of pro-
`tected software elements by use of capability keys. The
`unlocking of protected software elements employs ca-
`pability keys and requires that the capability keys be
`transformed. One couvenient capability-key transfor-
`mation that will be used in one embodiment of the sys-
`tem is now described.
`The computer system‘s identity key, Is. {for example,
`a 32-bit serial number} is read {mm the system firmware
`stored in PROM memory 14 of FIG. 1. The identity
`key. 13;, is then transformed with the capability key. Cr,
`entered through keyboard 12 to form a transformed
`capability key, Ti, as follows:
`
`It' Car-1T2
`
`liq-(1}
`
`the symbol “"" designates a reversible
`in Eq.(2},
`transform which typically is performed in a number of
`steps. First, the serial number identity key. It, is trans»
`formed by one or more arithmetic or logical Operations
`into two 32-bit centrol numbers, BI and 82. Typically.
`theSe transformations of 1;; are version-dependent. For
`example, the transformations consist of multiplying It
`by two different constants, ll and 11 (where .l] and I;
`may be different for different versions), as follows:
`
`if}
`
`15
`
`20
`
`25
`
`30
`
`35
`
`5
`meat directory for that element is transformed in the
`same way as when the capability key was entered into
`the system. Portions of the transformed key derived
`from the stored capability key are compared with the
`stored authentication key and the stored access key.
`If either the stored authentication key or the stored
`access key does not match the corresponding portion of
`the transformed key, the failure to match indicates that
`access to the element is unauthorized. Access is unau-
`thorized, for example, if the element has been repro-
`duced from a system with a different version of the
`firmware or if a floppy disk storing the element has been
`moved from another system to the present system. In
`either case, the system typically resets all capability key
`fields in the element directory to “0". The user must
`then reenter non-zero capability keys into the system in
`order to gain access to any protected element.
`The transformation of the capability key can be done
`in many different ways. The important criterion is that
`the capability key transformation be reversible so that,
`given a stored key (typically including an authentica-
`tion key and an access key) and a system identity key. a
`capability key can be computed having the property
`that. when transformed, it will match these keys.
`Additional objects and feaer of the invention will
`appear from the following description in which the
`preferred embodiments of the invention have been set
`forth in detail in conjunction with the drawings.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 depicts a cryptosystem for use in connection
`with or a computer.
`FIG. 2 depicts a flow chart which represents the
`operation of the FIG. 1 cryptosystem in order to enter
`a capability key.
`DETAILED DESCRIPTION
`
`Encrypted Capability Keys
`
`A practical realization of the modular capability-key
`cryptosystem embodied in a printing system is shown in
`FIG. 1. The printing system employs a general purpose
`processor and a number of different computer software
`elements which represent different capabilities of the
`system. Typical hardware elements used in the printing
`system are as follows.
`A general purpose computer 10 with integral ran-
`dom-access memory (RAM) 11 to store computer soft-
`ware (including a number of protected and/or unpro-
`tected software elements) and to store data is employed.
`A Motorola MCGBOOO microcomputer with 256k bytes
`of MOS RAM memory is Suitable for computer 10.
`An input device 12 for entering an alphanumeric
`string representing the capability key is employed. A
`display terminal 12-2 and keyboard 12-1 connected to
`standard RSZJZC port 13 of computer 10 is suitable for
`input device It).
`A permanent, machine-readable memory device 14 is
`employed to Store the serial number identity key and
`other firmware. A PROM {programmable read-only
`memory} physically and electronically attached to a
`backplane 15 of the computer 10 is suitable for perma—
`nent memory device 14.
`A small amount of permanent, alterable memory 16 is
`employed to keep track ofthe "cracker count" which is
`the total number of erroneous capability keys that have
`been entered. NOVRAM (non-volitile RAM) storage
`associated with the computer is suitable for memory 16.
`
`
`
`flkX-lll=31
`
`flkXle=Bt
`
`45
`
`Eqw
`
`3114)
`
`The transformation of the capability key, Ci, then
`further proceeds in two steps. The first control number.
`131, is transformed with the numeric capability key, Ck.
`to yield another 32-bit number, called the intermediate
`transform. Xi, as follows:
`
`31' Ct=Xs
`
`Eta-(5}
`
`SS
`
`the transform is typically an EXCLU-
`In Eq.(5).
`SIVE-OR operation as follows:
`
`BIEBCk=Xi
`
`54(6)
`
`The EXCLUSIVEOR operation indicated by the
`symbol "6;" in Eq.(6) is bit-bysbit between each pair of
`correspondings bits of BI and Ck and yields for corre-
`sponding" bits of Xka "i" if the corresporiding hits ofB1
`and Ck are different and “0" if they are the same.
`The second control number, 32, is used to transform
`the intermediate transform. Xi. of Eq.(6) to form the
`transformed capability key, Tk, as follows:
`
`65
`
`51' X3=Tg
`
`EqI-n
`
`PMC Exhibit 2141
`
`Apple v. PMC
`|PR2016-01520
`
`Page 5
`
`
`
`PMC Exhibit 2141
`Apple v. PMC
`IPR2016-01520
`Page 5
`
`
`
`7
`
`4,888,798
`
`In E40). the transform indicated by the symbol-
`is typically a bisecting permutation indicated by the
`symbol
`
`u."
`
`5'2 (3,)“ - Tk
`
`Ext-(3}
`
`The bisecting permutation of Eq.{3) is performed
`typically in a number of steps as follows. In Eq.(8}. if the
`high«order bit of the control number. B}, is "l". swap
`the left and right 16-bit groups of the X1. transform to
`form the first permuted value. Xi“. Lfthe next bit to the
`right in B1 is “1", swap the leftmost two 8-bit groups of
`X.“ to form the left half of the next permuted value,
`Kn. If the next bit to the right in B; is "l", swap the
`rightmost two 8-bit groups of the X“ value to form the
`right half of Kn. Use one at a time the next four hits of
`B1 to control swapping of the left and right halves of
`each of the four 3-bit groups of Xe.
`Each 8-bit group of Xu will swap a 4-bit left and a
`4-bit right half as a function of one corresponding bit in
`B1. When each of the four 3-bit groups of Xkl is
`swapped or not as determined respectively by four bits
`of B1, the result is the next permutted value. X5. The
`value Xi; censists of eight 4«bit groups. each 4-bit group
`having 2-bit left and right halves. The next eight bits of
`B; control swapping of the left and right halves of the
`eight 4-bit groups of X14 and the result formed is the
`next permutted value Kim. The value Xka consists of
`sixteen 2-bit'groups. each group having a left bit and
`right bit. The next sixteen bits of B} are used to control
`the swapping of the left and right bits of the respective
`sixteen groups of Xe; to form the next permuted value
`Xu which is the final value. Tk.
`Note that this bisecting transform of Eq.(8) is revers-
`ible since given a desired transformed ltey. Tic, the sys-
`tem serial number identity key. Ir. and knowledge of the
`transform process. the process can be executed "in re-
`verse" so as to compute a corresponding capability key.
`Ck.
`After the capability key. Ck. has been transformed by
`ll; to form the transformed capability key. Tic. the trans-
`formed capability key. Tk.
`is compared with a stored
`key. Sic. if Tic matches Sic. then the software element
`associated with Si. is unlocked and ready to be accessed
`by the system. Typically. Si is formed of two parts,
`namely. an authentication lteyI Vic, and an access key,
`At. The stored key. 51;. should be identical to the trans-
`formed key, 51.. After the capability key transformation
`is completed to form Tk. the 16-bit left half. TL, okais
`compared with the authentication key. Vk. for this sys-
`tem. If T; does not match Vic.
`the failure to match
`indicates that use is not authorized and a special
`"cracker countermeasure" procedure is entered.
`If the authentication code. Va, matches '1'; correcrly.
`each element that still has “0" in its capability key field
`in the element directory is examined to determine
`which ones have an access key. At. matching the 16-bit
`right half. T3. of the transformed capability key, Ta.
`
`10
`
`IS
`
`20
`
`25
`
`30
`
`35
`
`4O
`
`45
`
`50
`
`55
`
`65
`
`
`
`8
`Wherever a match is found between Arc and T3, the
`capability key. Ci, (not the transformed capability key.
`Tr) is stored in that elements capability key field of the
`element directory. Storing die capability key. Ck, into
`the directory constitutes entry of the capability key into
`the system and the "unlocking" of the corresponding
`protected software element.
`It is important that the transformation of Eq.(2) used
`with the capability key effectively permutes the bits. If
`only key-stream encryption were used. a clever soft-
`ware user who had obtained authorization for several
`capabilities for a given computer system might compare
`them and deduce which elements made up the authenti-
`cation key. Given that information. the security systems
`on all machines could be attacked without fear of coun-
`termeasures. Using a cryptosystem which pcrmutes the
`bits in a system-dependent way avoids this problem.
`File Ace-est: Control
`
`Whenever file access is requested to obtain access to
`a protected software element. the non-zero capability
`key (if any) stored in the capability key field of the
`element directory for that software element is trans-
`formed in the same way as when the capability was
`initially entered into the system to unlock the protected
`software element. After the stored capability key. Ck,
`from the element directory is transformed to form the
`transformed capability key. Tic. the left half. '1'; is com-
`pared with a stored authentication key. Vt. and if a
`match results. the right half. T3.
`is compared with a
`stored access key. At. If At. matches TR. the protected
`software element is released for use by the system.
`If either the authentication key. Vt. or the access key.
`Ar. does not match '1'; and TR, respectively. the failure
`to match indicates that
`the corresponding protected
`software element has been copied from a system with a
`different firmware version or the floppy disk (or a copy)
`has been maved into the computer system from another
`syStem. In either case. the system sets all capability keys
`fields in the software element directory to "0". The user
`must then re-enter capability keys in the capability key
`fields of the element directory for the system in order to
`gain access to the various protected software elements.
`The access key is stored within the data of a software
`element in locations which are distributed throughout
`the data, for example. two bytes of the access key in
`every 36th and 37th byte location of the data. The loca-
`tion of the access key within the data can change with
`every software version.
`Using the modular security system described above.
`standard and identical copies of software (including
`many software elements whether authorized or not) can
`be disseminated to many different users. Authorized
`software elements can be unlocked at each user's com-
`puter by having the user enter a capability key for those
`elements for which the particular user is authorized.
`Although each user may have all or many software
`elements whether authorized for use or not. the user
`only obtains access to those particular elements for
`which the user is authorized.
`Note that by storing the encrypted capability key. Ck.
`in the element directory of the system and decrypting
`and rechecking each capability key each time an at-
`tempt to access an element is made. the system is pro-
`tected against having elements "unlocked" on one sys-
`tem then moved to another system. Inasmuch as the
`capability keys are machine-identity dependent. know- '
`ing the keys for a particular system is of no value to
`
`PMC Exhibit 2141
`
`Apple v. PMC
`|PR2016-01520
`
`Page 6
`
`
`
`PMC Exhibit 2141
`Apple v. PMC
`IPR2016-01520
`Page 6
`
`
`
`
`
`9
`users of a different system. It is. of course. msential to
`keep the key transform confidential and to change the
`transform if the transform becomes known in some way.
`While the protection scheme described above should
`adequately defend against casual software piracy,
`it
`cannot protect against certain kinds of sophisticated
`attack. In particular, if the attacker is given physical
`access to a machine together with logic analyzers and
`other high-speed digital
`recording devices.
`then
`through an extensive analysis of recordings the attacker
`can deduce how the decryption prooess is carried out
`and thereafter create user keys for any given capability
`of any machine for which the identity is known. If a
`successful attack of this sort is known to have Occurred.
`a readily available defense is to change the decryption l5
`algOrithm (the transform of Eq.(2))i.n newer versions of
`the software.
`
`5
`
`10
`
`I 4,383,198
`
`10
`in Eq.(1l}. the value of Ti. equals St which has a left
`half and a right half given by the authentication key,
`We. and the access key, At. respectively. which are
`inputs to the capability key generator.
`Using the value of the intermediate transform. Xi,
`determined in accordance with Eq.(ll) the reverse of
`the transform of Eq.(5] is appLied to produce the capa-
`bility key. Ct, as follows:
`
`31‘ Xguck
`
`E51111)
`
`In the particular example described. the reverse trans-
`form of Eq.(12) is performed as the reverse of the EX-
`CLUSIVE-OR transform of Eq.(6) as follows:
`
`Bltbxt=Ct
`
`55M”)
`
`EXAMPLE
`
`25
`
`A concrete example of how the encrypted capability '10
`key cryptosystem works is presented here. The stored
`transformed capability key. St. has two components,
`namely the authentication key. Vi and the access key,
`Ag. Assume that the authentication key, Vt. for a cur-
`rent version of system software has been set arbitrarily
`to 64.34519 and that the access key. At. for a certain
`element having a name E (such as a printer font file) is
`34.46610. The base for all numbers is indicated by a
`subscript. Assume a user purchases or otherwise is an-
`thorized to access the element E for a certain machine
`where that machine has a serial number identity key. It.
`12.43210.
`The particular values of the keys Vic. A5; and It are
`supplied by the software distributor. together with the
`constants .11 and 11. to the distributor's capability key
`generator. The generator processes the keys Vt, Air and
`I}; and forms the capability key, Ck, which for the par-
`ticular values described is defeElcfm. The capability
`key generator can be a special program that is kept
`under the software distributor’s control or can be any
`manual or other conventional means for forming a capa-
`bility key based upon the transforms employed.
`In order for the capability key generator to generate
`the capability key, the capability key generator per—
`forms the reverse transformation of Eq.(2) as given by 45
`the following Eq.(9):
`
`30
`
`35
`
`U? Tia-Ct:
`
`Eq.(9)
`
`The transform of Eq.(9) is carried out in a number of 50
`steps analogOus to the steps of Eq.(3) through (8} above.
`Initially,
`the capability key generator must have the
`values B] and 32. In order to obtain these values, the
`constants J; and