115
`United States Patent
`5,935,246
`[11] Patent Number:
`[45] Date of Patent:
`Benson
`Aug, 10, 1999
`
`US005935246A
`
`[54] ELECTRONIC COPY PROTECTION
`MECHANISM USING CHALLENGE AND
`RESPONSE TO PREVENT UNAUTHORIZED
`EXECUTION OF SOFTWARE
`
`[75]
`
`Inventor: Glenn Stuart Benson, Munich,
`Germany
`
`[73] Assignee:
`
`International Computers Limited,
`London, United Kingdom
`
`[21] Appl. No.: 08/838,620
`
`[22] Tiled:
`
`Apr. 11, 1997
`
`Foreign Application Priority Data
`[30]
`Apr. 26, 1996
`[GB]
`United Kingdom ....... 9608696
`
`
`eeeecccccsccesennnnmmeeeseseseessennent GO6F 12/14
`Tint, C0
`[SD]
`sesseesseeeee 713/200; 713/201; 713/202
`[52] U.S. Cl. ...
`[58] Field of Search 0.0 395/186, 387,
`395/860, 187.01; 380/25, 4, 21, 23, 30;
`713/200
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`5,568,552 10/1996 Davis occ
`5,724,425
`3/1998 Changetal. ......
`FOREIGN PATENT DOCUMENTS
`
`
`seve 380/4
`
`we 380/25
`
`WO 88/05941
`
`8/1988 WIPO.
`
`OTHER PUBLICATIONS
`
`Davis, “Cryptographic Randomnes From Air Turbulence In
`Disk Driver”, Advances in Cryptology, Conference 14, Aug.
`21, 1994, pp. 114-120.
`
`Primary Examiner—Hassan Kizou
`Assistant Examiner—Rijue Mai
`Attorney, Agent, or Firm—Lee, Mann, Smith, McWilliams,
`Sweeney & Ohlson
`
`[57]
`
`ABSTRACT
`
`A copy protection mechanism for protecting software
`against copying, consists of a challenge mechanism embed-
`ded in each protected item of software. The challenge
`mechanism has no access to the customer’s private keying
`material. In operation,
`the challenge mechanism sends a
`random challenge to the customer’s signature server. ‘The
`signature server signs the challenge, using the customer’s
`private keying material and thenreturns the signed challenge
`to the challenge mechanism. The challenge mechanism then
`verifies the signed challenge, using the customer’s public
`keying material, and prohibits the customer from using some
`or all of the protected item of software unless the verification
`is successful. The mechanism permits every customer to
`receive an identical copy of the copy protected program with
`the embedded challenge mechanism.
`
`25 Claims, 3 Drawing Sheets
`
`12/1985 Arnoldet al.
`4,558,176
`5/1990 Chuam .....
`4,926,480
`8/1990 Chaum .....
`4,947,430
`4/1992 Comerford et al.
`5,109,413
`9/1992 Nolan, Jr.
`.....
`5,146,575
`6/1993 Gasseret al.
`5,224,163
`5/1994 Abadi et al.
`5,315,657
`5,371,794 12/1994 Diffie et al.
`5,436,972
`7/1995) Vischer .....eeeeeeeeeeees 380/25
`
`
`
`
`seeee 178/22.08
`380/23
`+. 380/25
`we. 380/4
`395/425
`« 380/30
`380/25
`
`.
`
`20\
`
`
`SIGNATURE
`SERVER
`
`
` 24
`
`CHALLENGE
`
`MECHANISM
` 23
`
`COPY-
`
`PROTECTED
`
`SOFTWARE
`
`
`Roku EX1043
`Roku v. Ancora
`
`IPR2021-01406
`
`Roku EX1043
`Roku v. Ancora
`IPR2021-01406
`
`

`

`U.S. Patent
`
`Aug.10, 1999
`
`Sheet 1 of 3
`
`5,935,246
`
`STEP 1
`
`|VENDOR
`
`CUSTOMER
`
`PROTECTED
`SOFTWARE
`
`STEP 2
`
`|VENDOR
`
`REGISTRATION
`PACKAGE
`
`CUSTOMER
`
`STEP 3
`
`|VENDOR
`
`CUSTOMER
`
`KEYFILE
`
`i F
`
`FIG. 1
`
`20\
`
`SIGNATURE
`SERVER
`
`94.|
`
`|CHALLENGE
`MECHANISM
`
`IG. 2
`
`

`

`U.S. Patent
`
`Aug.10, 1999
`
`Sheet 2 of 3
`
`5,935,246
`
`GENERATES NONCE&
`SENDS IT TO SIGNATURE SERVER
`
` CHALLENGE MECHANISM
` 34
`
`
`
`
`
`SIGNATURE SERVER SIGNS NONCE,
`USING CUSTOMER'S PRIVATE KEY &
`
`RETURNS SIGNED NONCE
`TO CHALLENGE MECHANISM
`
`32
`
`
`
`
`aWARNING: INVALID SIGNATURE-----------
`
`33
`
`CHALLENGE MECHANISM
`VALIDATES SIGNATURE
`
`FIG. 3
`
`we ceceneeeeWARNING: INVALID SIGNATURE -----------
`
`42c02fd3ca73f38e1f1e--- WARNING: INVALID SIGNATURE-
`--eead/7d9d5001
`
`FIG. 4
`
`

`

`U.S. Patent
`
`Aug. 10, 1999
`
`Sheet 3 of 3
`
`5,935,246
`
`THREAD1
`
`VALUE_LIST.=EMPTY
`
`o1
`
`
`COUNTER:=0
`
`DONE_TEST:=FALSE
`
`
`EXECUTE THREAD2
`
`INCREMENT COUNTER
`
`DONE_TEST=TRUE?
`
`YES
`
`
`
`
`
`
`
`
`
`
`
`TERMINATE THREAD2.
`
`SAVE COUNTER IN
`
`VALUE_LIST
`
`
`
`NUM_BITS:=
`
`STATSTEST(VALUE_LIST)
`
`
`
`
`HAVE ENOUGH RANDOM
`BITS BEEN GENERATED?
`
`YES
`EXTRACT NUM_BITS LOW-
`ORDER BITS FROM EACH
`SAVED COUNTER VALUE
`
`
`
`
`
`’
`
`FIG. 5
`
`RETURN
`
`

`

`5,935,246
`
`1
`ELECTRONIC COPY PROTECTION
`MECHANISM USING CHALLENGE AND
`RESPONSE TO PREVENT UNAUTHORIZED
`EXECUTION OF SOFTWARE
`
`BACKGROUND TO THE INVVENTION
`
`This invention relates to electronic copy protection
`mechanisms for protecting software against unauthorized
`copying.
`The Business Software Alliance estimates the 1995 finan-
`cial lossesattributed to software piracy as US$8.1 Billion for
`business application software and US$15.2 Billion for all
`software. Solutions have been proposed in two areas: (i)
`improvedIntellectual Property Rights (IPR) legislation, and
`(ii) enhanced electronic copy protection (ECP) mechanisms.
`IPR legislation and enforcement are improving in many
`countries, but there are still significant difficulties in other
`parts of the world. As a result, some vendors are currently
`reassessing ECP.
`It is desirable for any ECP mechanism to satisfy the
`following requirements.
`The ECP mechanism should prohibit unauthorized users
`from executing copy protected software.
`The ECP mechanism should not prohibit the user from
`making backups.
`The ECP mechanism should make only standard hard-
`ware and software assumptions. For example, although
`hardware dongles provide excellent copy protection
`services, many vendors do not wish to limit the sale of
`the software to the collection of users who ownorare
`
`willing to install a dongle.
`The ECP mechanism should have minimal impact upon
`the user interface. The visible impact should be limited
`to the customer’s initial login to the operating system
`and/or smart card. Subsequent impact upon the user
`interface should be relegated to relatively minor per-
`formance concerns.
`The ECP mechanism should not limit execution of the
`
`copy protected software to a limited collection of
`machines. When a customer legitimately purchases
`software, the customer should be able to execute the
`software on any machine regardless of ownership. The
`customer should optionally be able to authorize simul-
`taneous execution of the software on multiple
`machines.
`
`The ECP mechanism should have no required network
`dependencies in order to execute an already purchased
`copy protected program.
`The vendor should be permitted to distribute an identical
`version of the copy protected software to all users. This
`requirement permits the copy protected software to be
`distributed through normal channels such as,
`for
`example, CD-ROMs,floppy disks, or network bulletin
`boards.
`
`It should be excessively difficult and/or computationally
`infeasible for a potential software pirate to circumvent
`the copy protection mechanism without modifying the
`copy protected program. This requirement serves as an
`important virus-protection measure because a digital
`signature supplied by the vendor would not validate if
`a pirate distributes a modified version of the original
`program.
`The ECP mechanism should not compromise any of the
`customer’s private keying material. In particular, the
`ECP mechanism should not disclose the customer’s
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`private keying material to the vendor, any program
`produced by the vendor, or any simple Trojan horse
`program. While the primary functionality of copy pro-
`tection is to protect the software vendor, one must not
`do so at the expense of the customer.
`The ECP mechanism should be available in either a
`software-only version or a hardware-assisted (smart
`card) version, to assure widespread market acceptance.
`The least time consuming attack by a potential software
`pirate should be byte-code disassembly of the copy
`protected software. In order to thwart the copy protec-
`tion mechanism,the pirate must remove or change the
`ECP. Choudhuryetal. [“Copyright Protection for Elec-
`tronic Publishing over Computer Networks”, available
`as at Mar. 27, 1996 on Word Wide Web at http://
`ftp.research.att.com/dist/anoncc/copyright.epub.ps.Z]
`propose a mechanism in which a protected document
`can be viewed only via a specially configured viewer
`program, which allows a user to view the document
`only if the user supplies the viewer with the user’s
`private keying material. This deters the user from
`distributing unauthorized copies of the viewer program,
`since that would require the user to divulge his or her
`private keying material to others. However, because
`Choudhury’s mechanism requires that the viewer pro-
`gram obtain access to the customer’s private keying
`material, it breaks one of the requirements listed above.
`Furthermore, Choudhury’s mechanism maynotbe used
`in conjunction with a smart card that is configured to
`avoid releasing private keying material.
`The object of the present
`invention is to provide an
`improved ECP mechanism thatis able to satisfy the above
`requirements.
`The ECP mechanism of the present invention makes use
`of asymmetric cryptography, also known as public key
`cryptography. In asymmetric cryptography, each user has
`public keying material and private keying material. Each
`user may posthis or her public keying material to a publicly
`accessed directory without compromising the corresponding
`private keying material. Normally,
`the user guards the
`private keying material as a close secret. Using the RSA
`asymmetric encryption algorithm, for example, a pair of
`users may encrypt and then subsequently decrypt a message
`using either of two methods: (i) encrypt using the public
`keying material and decrypt using the private keying mate-
`rial; or (ii) encrypt using the private keying material and
`decrypt using the public keying material. Two examples are
`presented below.
`Secret message: A user, Alice, posts her public keying
`material
`to a well-known directory or bulletin board. A
`second user, Bob, wishes to send a confidential message to
`Alice. Bob encrypts the message using Alice’s public keying
`material and sends the encrypted message to Alice. Since
`Alice is the only user with access to the corresponding
`private keying material, only Alice may decrypt the message
`to discover its original content.
`Digital signature: A digital signature is an electronic
`analog of a handwritten signature. After posting her public
`keying material, Alice encrypts a message using the private
`keying material. Since anyone mayaccess the public keying
`material, there is no message secrecy. However, since Alice
`is the only user with access to the private keying material,
`no one else can “forge Alice’s signature” by performing the
`encryption. Any user may validate Alice’s signature using
`the public keying material.
`Both examples depend upon the fact that Alice closely
`guards her private keying material. Otherwise, the crypto-
`
`

`

`5,935,246
`
`3
`graphic system may neither guarantee secrecy nor ensure
`signature validity. The best known mechanism for protecting
`one’s private keying material is through the use of a smart
`card. In this case, the smart card is a device with no interface
`for releasing private keying material
`(in a non-
`cryptographically protected form).
`Although smart cards provide the best protection, social
`factors of electronic commerce may providea role in ensur-
`ing private keying material protection. One of the significant
`difficulties associated with asymmetric encryption services
`is authentication. For example, if Alice posts her public
`keying material to a public directory, then how does Bob
`assess validity? That is, a pirate may attempt to masquerade
`as Alice but post the pirate’s keying material. Some com-
`mercial organizations are beginning to provide solutions to
`this problem byacting as Certification Authorities (CA). For
`(possibly) a fee, the CA solicits identifying material from
`potential customers such as a driver’s license or passport.
`After validating the identifying material, the CA posts the
`customer’s public keying material to a public directory, and
`the CA signs a certificate that holds the customer’s public
`keying material. Standardized services, for example, X.500
`may be adopted to help facilitate the use of directories that
`contain public keying material.
`Oncea user posts his or her public keying material to the
`CA,
`the user will probably make an extensive effort
`to
`protect his or her private keying material. In this case, if the
`user’s private keying material were to become unknowingly
`compromised, then the user would have causefor significant
`concern because networked vendors may authorize elec-
`tronic commerce transactions based on the information
`found in the public directory.
`SUMMARYOF THE INVENTION
`
`According to the invention there is provided a computer
`system comprising a copy protection mechanism for pro-
`tecting software against copying,
`the copy protection
`mechanism comprising challenge means associated with a
`protected item of software, and response means in which a
`customer’s private keying material
`is securely stored,
`wherein:
`
`(a) the challenge means has no access to the customer’s
`private keying material;
`(b) the response means comprises means for signing infor-
`mation using the customer’s private keying material and
`then returning the signed information to the challenge
`means, and
`(c) the challenge means comprises meansfor verifying said
`signed information, using the customer’s public keying
`material, and for prohibiting the customer from using
`someorall of said item of software unless said verifica-
`tion is successful.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a flow diagram of a purchasing protocol used
`when a customer wishes to purchase software that is pro-
`tected by an ECP mechanism in accordance with the inven-
`tion.
`
`FIG. 2 is a block diagram showing the software compo-
`nents that are required to be installed in the customer’s
`machine to enable the customer to run the copy protected
`software.
`
`FIG. 3 is a flow diagram showingthe operation of the ECP
`mechanism in the protected software.
`FIG. 4 shows the format of a nonce (random number
`expressed in hexadecimal form) generated by the ECP
`mechanism.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`FIG. 5 is a flowchart showing the operation of a random
`number generator used to generate nonces.
`DESCRIPTION OF AN EMBODIMENT OF THE
`INVENTION
`One ECP mechanism in accordance with the invention
`
`will now be described by way of example with reference to
`the accompanying drawings.
`Purchasing Protocol
`FIG. 1 shows a purchasing protocol used when a customer
`wishes to purchase software that is protected by an ECP
`mechanism in accordance with the invention. It is assumed
`that each party (i.e. the vendor and each potential customer)
`has its own public and private keying material. Each party
`makes its public keying material available to other parties,
`but keeps its private keying material secret.
`In step 1, the customer obtains the protected software
`from a vendor. The customer may get the software, for
`example, on a floppy disk or CD-ROM at a PC store.
`Alternatively,
`the customer may download the software
`from a network bulletin board. A challenge mechanism,to
`be described later, is embedded in protected software in such
`a way that a potential attacker cannot easily separate the
`challenge mechanism from the protected program. The
`attacker would need to disassemble the code and to manu-
`
`ally remove the challenge mechanism. The challenge
`mechanism has the vendor’s public keying material embed-
`ded in it. As will be described, the challenge mechanism
`prevents the user from running the software at this stage.
`In step 2, the customer sendsa registration packageto the
`software vendor, for example by electronic mail. This reg-
`istration package contains a reference to a public directory
`that holds the customer’s public keying material.
`In step 3,
`the software vendor embeds the customer’s
`public keying material into a keyfile and sendsthe keyfile to
`the customer, for example by electronic mail. Once the
`customer installs the keyfile, the ECP mechanism permits
`the customer to execute the software.
`
`The creation of the keyfile by the vendoris performed by
`a keyfile generator, which is a program that executes at the
`vendor’s facility. The vendor must take care to guard this
`program because it accesses the vendor’s private keying
`material. In use of the keyfile generator, an operator enters
`the following information:
`Vendor name: The nameof the vendor’s company.
`Vendor password: The password that unlocks the vendor
`company’s private keying material (decrypt the private
`keying material using the password). Company
`employees who do not know the password cannot
`generate keyfiles.
`Customer name: The name of a customer for whom to
`
`generate a keyfile. The name indexes into a database of
`public keying material.
`Keyfile name: The name of a new keyfile.
`After obtaining this information,
`the keyfile generator
`builds a keyfile, containing the customer’s public key. The
`keyfile appears to the customer as a completely random
`sequence of values. Building of the keyfile involves the
`following operations. First, the keyfile generator creates a
`file and inserts the customer’s public keying material into
`the file, along with thousands of decoy bits. In the present
`example, each keyfile contains approximately 480,000
`decoy bits. This number of bits represents a significant
`amount of decoy material, and can fit into a standard e-mail
`message.
`Each keyfile stores the customer’s public keying material
`in a different
`location. Additionally, each keyfile has
`
`

`

`5,935,246
`
`5
`encrypted customer information embedded in it without
`disclosing the required encryption key. This encrypted cus-
`tomer information permits a software vendor to easily
`identify the owner of a keyfile in the event that the keyfile
`appears in a public location such as a bulletin board. The
`keyfile generator then encrypts and re-encrypts the keyfile
`multiple times, using different algorithms. Finally, the key-
`file generator signs the keyfile using the vendor’s private
`keying material.
`Customer Software
`
`10
`
`15
`
`20
`
`25
`
`6
`fying the challenge mechanism. Vendors may optionally
`augmentthis protection using additional proprietary lines of
`defence. If the keyfile has been modified,
`the challenge
`mechanism hangs the program.
`Assuming the signatureis validated, the challenge mecha-
`nism then parses the keyfile, using a proprietary, vendor-
`specific algorithm, to locate the customer’s public keying
`material
`in the keyfile, and extracts this public keying
`material. The challenge mechanism then calls its signature
`validation function,
`to validate the digital signature com-
`puted over the nonce using the customer’s public keying
`FIG. 2 shows the software components that are required
`material. If the signature is not valid, the challenge mecha-
`to be installed in the customer’s machine (computer) to
`nism hangs the program. Thus,
`it can be seen that
`the
`enable the customer to run the copy protected software.
`software continues executing if and only if the customer
`These consist of a signature server 20, and a cryptographic
`possesses the proper keyfile.
`Nonce Generator
`engine 21. Also shown are the keyfile 22 and the copy
`protected software 23. As mentioned above, the copy pro-
`Generation of a nonce is performed by a nonce generator
`tected software includes a challenge mechanism 24.
`included in the challenge mechanism. Operation of the
`The signature server is a program that the customertrusts,
`nonce generator is as follows. First, the nonce generator
`which the customer executes when the system initially
`queries a large number of system parameters, e.g.,
`the
`system time, the amount of space remainingfree in the page
`boots. The customer enables the system byinserting a floppy
`table, the number of logical disk drives, the names of the
`disk that contains an encrypted copy of the customer’s
`files in the operating system’s directory, etc.
`private keying material. The signature server then prompts
`Next, the nonce generator builds a random number, using
`the customer for a pass phrase used to decrypt the floppy.
`a random numbergenerator. The random number generator
`The signature server then executes in the background wait-
`consists of two process threads, referred to herein as Thread
`ing for signature requests.
`1 and Thread 2. FIG. 5 showsthe operation of Thread 1,
`It should be noted that the signature server neverreleases
`which is the main thread of the random numbergenerator.
`the customer’s private keying material out of its process
`(Box 51) Thread 1 first creates a data structure value_list,
`boundary. The signature server relies on operating system
`
`protections to ensure its own integrity. The signature server for holdingalist of counter values. Thelistis initially empty.
`30
`(Box 52) Thread 1 sets a current counter value to zero, and
`executes in its own address space and communicates with
`sets a done_test flag to FALSE. (Box 53) Thread 1 then
`external processes. The signature server stores the custom-
`er’s password in wired memory (images of the memory
`forks Thread 2. Thread 2 posts an asynchronousdisk access,
`never appear in swap space).
`and then sleeps until the disk access is complete. When the
`The cryptographic engine is a dynamic linked library
`disk access is complete, Thread 2 sets the done__test flag to
`35
`TRUE. Note that Thread 1 and Thread 2 share the done_test
`(DLL) available in both the customer’s and the vendor’s
`home country, that performs cryptographic services. The
`flag.
`(Box 54) Thread 1 increments the counter value by one.
`signature server links with the cryptographic engine. Ser-
`(Box 55) Thread 1 then tests whether the done_test flag
`vices provided by the cryptographic engine include asym-
`metric and symmetric encryption and a one-way hash func-
`is now TRUE,indicating that the disk access initiated by
`tion.
`Thread 2 is complete. If done_test is FALSE, the process
`returns to box 54. Thusit can be seen that, while waiting for
`the disk access to complete, Thread 1 continually increments
`the counter value.
`(Box 56) When done_test is TRUE, Thread 1 terminates
`Thread 2, and saves the counter value in the first free
`location in value__list.
`(Box 57) Thread 1 then calls a Statstest function, which
`estimates the degree of randomness of the counter values
`saved on value__list. This function may use, for example, the
`Chi-Square, Kolmogorov-Smimov, and Serial Correlation
`Tests. (The Serial Correlation Test is described in D. Knuth,
`The Art of Computer Programming, Addison-Wesley Pub-
`lishing Co, Reading Mass., 2nd Edition, 1981). The Statstest
`function may be optimized to ensure that complicated cal-
`culations are not repeated for each disk access. Statstest
`returns a value which indicates how many low-orderbits of
`each saved counter value should be considered random.
`(Box 58) Thread 1 compares the value returned by Stat-
`stest when combined with the length of the value__list with
`a predetermined threshold value,
`to determine whether
`enough random bits have now been generated. If not enough
`random bits have been generated, the process returns to box
`52 above, so as to generate and save another counter value.
`(Box 59) When the required number of random bits has
`been generated, Thread 1 extracts the specified number of
`low-order bits from each counter value in the list, and
`returns this sequence of bits as the output random number.
`
`Operation of ECP Mechanism
`FIG. 3 shows the operation of the ECP mechanism. This
`is performed whenthe userinitially attempts to execute the
`protected software, and is also repeated periodically during
`execution.
`(Box 31) The challenge mechanism of the protected
`software generates an unguessable nonce (random number)
`and passes the nonceto the signature server with a signature
`request.
`(Box 32) Whenit receives the nonce, the signature server
`first checks that
`the nonce presented to it corresponds
`exactly to the format FIG. 4, with the exception of the 32
`random-appearing characters. If it does not, the signature
`server denies the signature request. Assuming that the nonce
`is in the correct format,
`the signature server uses the
`cryptographic engine to sign the nonce using the customer’s
`private keying material. The signature server then returns the
`signed nonce to the challenge mechanism in the protected
`software.
`(Box 33) Whenit receives the signed nonce, the challenge
`mechanism accesses the keyfile associated with the pro-
`tected software and calls a signature validation function in
`the challenge mechanism to validate the vendor’s signature
`of the keyfile, using the vendor’s public keying material that
`is embeddedin the challenge mechanism. This validation of
`the keyfile signature ensures that an attacker cannot modify
`the keyfile or its digital signature without additionally modi-
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`

`

`5,935,246
`
`7
`the random number
`it can be seen that
`In summary,
`generator exploits the unpredictability in the timing of a
`series of disk accesses as a source of randomness in the
`generation of nonces. (See P. Fenstermacheret al., “Cryp-
`tographic randomness from air turbulence in disk drives”,
`Advances in Cryptology: Crypto °94, pages 114-120,
`Springer-Verlag, 1994). By forking new threads on each disk
`access, the random numbergenerator also exploits unpre-
`dictabilities in the operation of the operating system’s sched-
`uler as a second source of randomness.
`The analysis performed by the Statstest function permits
`the random number generator to self-tune for any speed
`processor and disk, by computing the number of low-order
`bits of each saved counter value to return. For example, a
`system with a high-variance disk access time will generate
`more random bits per-disk access than a system with a
`low-variance disk access time. For example, for a Quantum
`1080s disk (6 ms average write time), and a 486 66MHz
`processor, the system generates approximately 45 bits per
`second. Alternatively, one may hard code the numberofbits
`per-disk access and use a de-skewing technique to ensure a
`good degree of randomness.
`The nonce generator also queries the operating system to
`ensure that it posts each disk access to an actual disk. The
`final output nonce is formed by combining the output
`random numberfrom the random number generator with the
`result of querying the system parameters as described above.
`The nonce generator described above works best when
`executing on an operating system that provides direct access
`to the disk, e.g., Windows 95 or Windows NT. In such an
`operating system, special operating system calls available to
`programs executing in user space permit a program to
`bypass the operating system’s in tern a | buffering mecha-
`nism and write directly to the disk. Most programs do not
`take advantage of these special operating system calls
`because they may be relatively inefficient and difficult to
`use. On Windows 95 and Windows NT, for example, a
`program may only use the se special calls if the program
`accesses data that is a multiple of the disk’s sector size. The
`program may discover the sector size by querying the
`operating system.
`If the operating system does not provide direct access to
`the disk, then the challenge mechanism could still use the
`disk timing random number generator. However,
`in this
`case,
`the quality of the generated values would have a
`greater reliance upon unpredictabilities in the operating
`system’s scheduler as opposedto the variance inherentto the
`disk access time.
`
`The example of the invention described above assumes
`that the operating system permits a program to fork multiple
`threads within a single address space. Additionally,
`the
`example of the invention assumesthat the operating system
`permits the threads to access synchronization variables such
`as semaphores. Most modern operating systems (including
`Windows 95 and Windows NT) provide these services. The
`example of the invention uses multiple threads to implement
`a mechanism which quantifies each disk access time.
`However, if an implementation of the invention were to
`execute on a system that does not provide multiple threads
`or synchronization variables, then the nonce generator could
`substitute other mechanisms,e.g. querying a physical clock.
`Attacks and Defences
`The ECP mechanism described aboveis robust becauseit
`protects itself against attack as described below.
`1) Disclosed Private Keying Material
`In this form of attack, a pirate legitimately purchases the
`software and then discloses both the software and the
`
`pirate’s private keying material to an unauthorised user.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`8
`The ECP mechanism deters this form of attack because
`the electronic commerce market provides many incentives
`for guarding one’s private keying material.
`In order to
`ensure that a pirate does not generate keying material for the
`exclusive use of copy protection, the software vendor should
`consult a CA to ensure that each customer has pre-
`authorized his or her private keying material to be used for
`multiple purposes.
`The ECP mechanism does not prohibit a customer from
`maintaining multiple asymmetric key pairs. However, at
`least one key pair could be used in multiple ways. Perhaps,
`for example, a software vendor may choose to use the same
`public keying material both (i) to validate a customer’s
`signature of the electronic transaction used to purchase the
`software and (ii) to build the customer’s keyfile.
`2) Certificate Revocation
`immediately after receiving a
`In this form of attack,
`keyfile from the vendor, the pirate issues a certificate revo-
`cation package (CRP). The purpose of the CRP is to
`announce publicly that the pirate’s private keying material
`has been compromised. Subsequently,
`the CAs add the
`pirate’s CRP to their certificate revocation lists. The infra-
`structure encourages electronic commerce participants to
`disregard any certificate mentioned in a certificate revoca-
`tion list. At this point the pirate freely distributes his or her
`private keying material in order to thwart the copy protec-
`tion mechanism.
`The ECP mechanism deters this form of attack because a
`
`pirate who wishes to generate a significant profit from
`breaking ECPhaslittle incentive to mount a CRPattack. The
`problem is that the pirate probably wishes to remain anony-
`mousin order to avoid legal prosecution. Althoughthe pirate
`may plead innocence by claiming that someonestole his or
`her private keying material, the pirate should assumethat he
`or she may be a prime suspect
`in a potential criminal
`investigation launched by a law enforcement agency.
`A law enforcement investigation might not be a primary
`concern to a pirate who wishes to generate only a minor
`profit. However, we hope that the time, trouble, and expense,
`associated with issuing a CRP outweighs the benefit of
`circumventing the copy protection for the benefit of only a
`few close friends.
`3) Clandestine Keyfile
`In this form of attack, the pirate generates a new public/
`private keying material pair. Next,
`the pirate creates a
`clandestine keyfile that contains the new public keying
`material. Alternatively, the pirate modifies an original key-
`file by substituting the new public keying material. The
`pirate distributes the copy protected software, the clandes-
`tine keyfile, and the new keying material.
`The ECP mechanism protects against this type of attack
`using three lines of defence. Thefirst line of defence is the
`digital signature of the keyfile, described above. The digital
`signature ensures that, if a pirate modifies the keyfile, the
`challenge mechanism does not validate the signature. The
`pirate may potentially thwart this line of defence by chang-
`ing the implementation of the challenge mechanism, by
`substituting a new embedded public key. Such a change to
`the challenge mechanism breaks an important virus-
`protection measure that may be used by a legitimate
`vendor—signing the program in order to ensure that the
`program is not modified in the distribution process. Note that
`a vendor does not release its private keying material. This
`line of defence provides significant keyfile protection
`because it requiresa pirate to disassemble the copy protected
`program in order to locate the vendor’s public keying
`material.
`
`

`

`5,935,246
`
`9
`The secondline of defence is the decoy bits in the keyfile.
`Although the keyfile stores no confidential information, the
`vendor-specific algorithm for parsing a keyfile is a secret.
`However, a pirate may potentially learn the secret by dis-
`assembling the challenge mechanism’s executable image.
`The third line of defence is the multiple encryption of the
`keyfile. If one assumes that the pirate cannot break the
`encryption algorithms themselves,
`the pirate must disas-
`semble the copy protected program in order to determine the
`required cryptographic algorithms.
`Of course, no two vendors should use the three lines of
`defence in exactly the same way. So, if a pirate were able to
`generate clandestine keyfiles for one version of a program,
`then the pirate’s keyfile-generator would not generate clan-
`destine keyfiles for other vendor’s program versions.
`4) Repeated Nonces
`the pirate forces the challenge
`In this form of attack,
`mechanism