Optimized integrity verification procedures

OPTIMIZED INTEGRITY VERIFICATION PROCEDURES

TECHNICAL FIELD

The present invention relates to optimized methods for integrity verification, and constitutes a separate application from SE 0700601-8.

STATE OF THE ART

The protection of digital data transferred between computers over a network is fundamentally important for many companies today. Companies try to achieve this protection by implementing some form of Digital Rights Management (DRM) procedure. The DRM method often involves encrypting the information (eg, encrypting the binary form of the information) in order to restrict its use to those persons who have been authorized to use it.

Encryption is the traditional method of protecting digital information, such as data, during transmission over a network. In its typical application, encryption protects digital information from theft by attacking data during transmission between two parties with mutual trust. Too many digital file transfer applications today (e.g. for the transmission of audio or video information), however, the paradigm has shifted, as a party receiving the information (i.e. “the receiving party”) may try to crack DRM encryption as the party providing the information (i.e. the “transmitting party”) has applied to the information. In addition, with the proliferation of network attacks, a third party can gain access to the receiving party's computer and thus to the protected information.

In addition to encryption and decryption, digital information may need other layers of protection. Proof of authenticity is another important layer of protection. When receiving digital information, the recipient often needs to "verify" the source of the digital information. In other words, the recipient needs to verify the integrity of the digital information by making sure that the information came from an authenticated source and was not tampered with on its way to the recipient.

To date, a number of procedures for verifying the integrity of digital information have been proposed. These methods typically apply a hashing function to the text version of the information to provide a hash digest (also called a hash or a digest), which is then used to generate a signature for the information. One

535 797 fundamental property of all "hash functions" is that if two "hashes" are different then the two input data were different in some respect. When two hashes are identical for two different input data, there is a hash collision. It is important in an encryption system that the hash function has a very low collision probability.

Traditional integrity verification procedures are computationally intensive, especially for portable devices with limited computational resources. For this reason, there is a need in this art for an integrity verification method that is less computationally intensive. It would be ideal if such a process allowed a portable device to quickly verify the integrity of a digital information it receives.

SUMMARY OF THE INVENTION

Some embodiments of the invention provide a method for verifying the integrity of a digital information. In a source of the digital information, the method generates a signature for the digital information by applying a hashing function to a special part of the digital information, the special part being smaller than the total digital information. The method provides a device with the signature and the digital information. In the device, the method applies the hashing function to the special part of the digital information to verify the integrity of the transmitted signature and thereby verify the integrity of the transmitted digital information.

The special part of the digital information includes several different sections of the digital information. In some embodiments, the method configures the source and device to select a predetermined set of sections of the digital information as the particular portion of the digital information. The device includes in some embodiments a read-only memory that (1) stores code for identifying the particular part, and (2) stores the hashing function.

In some embodiments, the method generates a signature for the digital information at the source by (1) applying the hashing function to the particular part to generate a hash digest, and then (2) generating the signature from the hash digest. The method can be implemented in either an asymmetric or symmetric integrity verification procedure. In some embodiments, for example, the method applies the hashing function to the device by (1) applying the hashing function to the particular part to generate a hash digest, and (2) transferring the digest and the received signature to a signature verifying process that determines the authenticity of

535 797 signature based on the provided digest. In some embodiments, the method alternatively applies the hashing function to the device by (1) generating a second signature based on the hash digest, and (2) comparing the first and second signatures to determine the integrity of the transmitted digital information.

The source of the digital information can be different in different design examples. For example, the source may be the author of the information, distributor, etc. The device that receives the digital information may also be different in different embodiments. Examples of such a device include a portable audio / video player (eg iPod), a laptop, a mobile phone, etc. The digital information may also be different in different embodiments. The digital information can e.g. be firmware updates to the operating system of the device, third-party applications to run on the device, audio / video files to be played on the device, etc.

DESCRIPTION OF FIGURES

The new features of the invention appear from the appended claims. For a more detailed explanation, however, a number of embodiments are described in the following figures.

Figure 1 shows a system for integrity verification according to some embodiments of the invention.

Figure 2 shows another integrity verification system according to some embodiments of the invention.

Figure 3 shows a DRM system implementing the integrity verification system according to some embodiments of the invention.

Figure 4 shows an integrity verification method performed using one or more DRM servers in some embodiments of the invention.

Figure 5 shows a method for integrity verification performed by means of a portable multimedia unit in some embodiments of the invention.

Figure 6 shows a diagram of a computer system that conceptually illustrates the components of a typical DRM server, user computer or portable device implementing some embodiments of the invention.

535 797

DETAILED DESCRIPTION OF THE INVENTION

In the following description, a number of details will be included to facilitate the explanation. However, those skilled in the art will appreciate that the invention may be practiced without the use of these particular details. In other cases, well-known structures and units are shown in the form of block diagrams so as not to burden the description of the invention with unnecessary details.

I. OVERVIEW

Some embodiments of the invention provide a method for verifying the integrity of a digital information. In a source of the digital information, the method generates a signature for the digital information by applying a hashing function to a special part of the digital information, the special part being smaller than the total digital information. The method provides a device with the signature and the digital information. In the device, the method applies the hashing function to the special part of the digital information to verify the integrity of the transmitted signature and thereby verify the integrity of the transmitted digital information.

The special part of the digital information includes several different sections of the digital information. In some embodiments, the method configures the source and device to select a predetermined set of sections of the digital information as the particular portion of the digital information. The device includes in some embodiments a read-only memory that (1) stores code for identifying the particular part, and (2) stores the hashing function.

In some embodiments, the method generates a signature for the digital information at the source by (1) applying the hashing function to the particular part to generate a hash digest, and then (2) generating the signature from the hash digest. The method can be implemented in either an asymmetric or symmetric integrity verification procedure. In some embodiments, for example, the method applies the hashing function to the device by (1) applying the hashing function to the particular part to generate a hash digest, and (2) transferring the digest and the received signature to a signature verification process that determines the authenticity of the signature based on the provided digest. In some embodiments, the method alternatively applies the hashing function to the device by (1) generating a second signature based on the hash digest, and (2) comparing the first and second signatures to determine the integrity of the transmitted digital information.

535 797

The source of the digital information can be different in different embodiments. For example, the source may be the author of the information, distributor, etc. The device that receives the digital information may also be different in different embodiments. Examples of such a device include a portable audio / video player (eg iPod), a laptop, a mobile phone, etc. The digital information may also be different in different embodiments. The digital information can e.g. be firmware updates to the operating system of the device, third-party applications to run on the device, audio / video files to be played on the device, etc.

II. SYSTEMS FOR INTEGRITY VERIFICATION ACCORDING TO SOME EMBODIMENTS

Figure 1 conceptually shows a more detailed version of an integrity verification system 100 for some embodiment of the invention. As shown in this figure, this system includes a source unit for digital information 110 and an information receiving unit 115. As shown in Figure 1, the source unit for digital information 110 transmits at least one block of digital information 105 to the information receiving unit 115. A source of information is each party involved in the creation of the information, its sale or distribution. Examples of such a party include the author of the information, the seller, the distributor, etc. The source unit for digital information 110 may consist of one or more desktop or portable devices, computers, servers, etc. As shown in Figure 1, the source unit for digital information 110 performs a hashing. procedure 120 and a signature generation procedure 130. The hashing procedure 120 applies a hash function to a portion of the digital information 105. This portion is a particular pattern of bits 125 which is shown conceptually as blackened sections of the digital information 105 in Figure 1.

In some embodiments, this bit pattern is specified in a manner that (for example, by the digital information source unit 110, by a DRM server controlling the unit 110, etc.) ensures that sufficient digital information is hashed to achieve three goals. First, the bit pattern must be specified so that manipulation of the digital information requires manipulation of one of the sections being hashed, which would reveal the manipulation because the manipulation would change the following signature. Second, the bit pattern must be specified so that two different pieces of digital information hashed by procedure 120 do not collide (that is, do not produce the same hash). Third, since the information receiving unit 115 will use the same bit pattern for its hashing procedure, the bit pattern should use the minimum number of

535 797 bits needed to fulfill the first two objectives, so that the hashing procedure will minimally utilize the computational resources of the information receiving unit 115.

The hashing procedure 120 is in some embodiments configured to select the bit pattern 125 quasi-randomly, or systematically (eg, based on an ordered pattern of bits) in other embodiments. In some embodiments, e.g. the digital information consists of object code of a program (such as the operating system of the information receiving unit 115, a third party application running on the information receiving unit 115, etc.)

In some of these embodiments, the code includes a set of op codes (i.e., instruction codes) and no or more operands (i.e., no or more data bits) for each op code. Thus, some of these embodiments apply the hash function to as much of the opcodes and operands as are needed to maximize the detection of tampering, minimize hash collisions, and minimize the use of computational resources.

In some embodiments, e.g. the information receiving unit an ARM microprocessor. In such a microprocessor, each row of object code (which includes an op code and its associated operand) is called a microprocessor operation unit (MOU), which has a statistical length of four bytes. Some embodiments therefore use the four-byte distance to identify the boundary between each line of code, and then use this information to select one or more bytes from each MOU. The selection of bytes from each MOU can be performed in different ways in different embodiments. Some embodiments include a quasi-random mixture of opcodes and operands in the bit pattern to be hashed. Other embodiments may only include op-codes (for example, most or all op-codes) in a code snippet, which is hashed and signed. Still other embodiments may select a specific byte (for example, always the first) in each instruction line. Some embodiments utilize a secret function, which for each MOU produces an integer module for the MOU length and then selects the section or sections of the MOU that correspond to that module. Other embodiments may utilize other microprocessors such as microprocessors provided by Motorola Corporation, Intel Corporation, AMD Corporation, IBM Corporation, etc.

In various embodiments, the hashing procedure applies 120 different hashing functions to the particular portion of the digital information. Examples of hashing functions such as

535 797 is used in various embodiments including MD5, SHA-1, etc. Hashing functions can be used with or without a key (i.e. hashing functions can be key hashing functions).

As mentioned above, a hashing function is a transformation that typically takes a form of data (such as a text form) and transfers it to a distorted output called digest or hash. The digest typically has a certain number of bits, which serve as a unique "fingerprint" for the original information. If the original message is changed and hashas again, a very high digest is likely to be produced. Hash functions can thus be used to detect altered and forged documents. They provide message integrity, which assures the information recipient that the information has not been altered or distorted.

As shown in Figure 1, the signature generator 130 receives digests produced by the hashing function in the hashing procedure 120. The signature generator 130 produces a signature 147 for the information 105 from the received digest 145. To produce such a signature, the generator 130 may use any of a number of known techniques such as: SHA-1, MD5 MAC.

In the system 100, the digital information 105 and the generated signature 147 are transmitted to the information receiving unit 115, as shown in Fig. 1. Different embodiments transmit this data to the receiving unit 115 in different ways. Some embodiments distribute this data, for example, via a communication network such as a LAN, WAN or a network of networks (for example, the Internet). In addition, the information receiving unit 115 may receive this data via a network directly from the author, seller or distributor of the information or indirectly via one or more interconnected servers, such as one or more DRM servers, information caching servers, etc.

An information recipient is any paid person involved in the use or distribution of the information. Examples of such a party include the information user, distributor, etc. The information receiving unit 115 may be a stationary or portable unit, computer, server, audio / video player, a communication unit (for example telephone, pager, text messenger, etc.), pocket computer , etc.

In the system 100, the source unit for digital information 110 and the information receiving unit 115 use an asymmetric method for

535 797 privacy verification. Thus, the information receiving unit 115 performs two methods, a hashing procedure 135 and a signature verifying procedure 140. The hashing procedure 135 applies the same hash function to the same sections of the digital information 105 as the hashing procedure 120 in the digital information source unit 110. . In particular, in some embodiments, the hashing procedure 135 in the receiving unit 115 is configured to select the same bit pattern in the digital information 105 as the hashing procedure 120 in the digital information source unit 110. Figure 1 illustrates this conceptually by showing that the hashing procedures 120 and 135 utilizes identical blackened bit patterns 125 in the digital information 105. The selection in the hashing procedure 135 of the same bit pattern 125 can be made in a quasi-random or systematic manner which leads to the selection of the same bit pattern as in the hashing procedure 120.

The application of the hashing function in the hashing procedure 135 to the information 105 produces a digest 149. This digest should be identical to the digest 150 generated by the hashing function in the hashing procedure 120 when the digital information received by the procedures 120 and 135 is the same. since both procedures select the same set of sections in the digital information.

As shown in Figure 1, the signature generator 140 receives the digest 149 produced by the hashing function in the hashing procedure 135. The signature verifier 140 also receives the signature 147 generated by the signature generator 130 in the source unit for digital information 110. The verifier 140 then determines if the received signature 147 is the correct signature for the received digital information 105 by determining if the signature 147 is correct for the digest 149. To determine if the signature 147 is correct for the digest 149, the verifier 140 may use any of a number of known techniques, such as SHA-1 or MD5.

Based on the comparison between the digest 149 and the signature 147, the verifier 140 then delivers an integrity check value 151. This value specifies whether the received signature 147 is the correct signature for the received digital information 105.1 some embodiments are e.g. the privacy check value is a Boolean value, which is true when the integrity of the digital information has been verified (that is, the received signature corresponds to the received digital information), and is false when the integrity of the digital information has not been verified. In other embodiments, the integrity check value is any other type of binary value, with a value indicating that the integrity of the digital information has been verified and the other value

535 797 indicating that the integrity of the digital information has not been verified. The integrity check will specify that the integrity of the information is not verified when one or more portions of the digital information are manipulated after the signature 147 has been generated and these portions include one or more information sections used to generate the hash digests 145 and 149.

Other embodiments may be implemented in other integrity verification systems. Figure 2 shows, for example, an embodiment of the invention in a symmetric integrity verification system 200. The system 200 is similar to the system 100 except that its information receiving unit 115 does not include the asymmetric signature verifier 140 but includes a signature generator 240 and a symmetric signature verifier 250.

Like the signature generator 130 in the digital information source unit 110, the signature generator 240 generates a signature 253 from the hash digest 149, which it receives. The generated signature 253 is then transferred to the signature verifier 250 together with the received signature 147. The verifier 250 then compares the two signatures to specify the integrity check value 151. The integrity check value 151 indicates that the received digital information has not been manipulated as the two signatures 147 and 253 correspond to each other. Since these two signatures do not correspond to each other, the integrity check value indicates that the information has been tampered with (i.e., the received signature 147 does not correspond to the received digital information).

To conceptually illustrate that different parts of the digital information can be hashed in different embodiments or for different parts of the information, Figure 2 shows a different black bit pattern 225 in the information 105 than the pattern shown in Figure 1. The blackened sections in Figure 2 have different lengths to conceptually illustrate that sections of different sizes can be hashed in some embodiments of the invention.

III. DRM SYSTEM IMPLEMENTING SYSTEM FOR INTEGRITY VERIFICATION ACCORDING TO SOME EMBODIMENTS The integrity verification system according to some embodiments is implemented in a DRM system, which distributes information in a way that ensures the legal use of the information. As shown in Figure 3, the DRM system 300 includes a set of DRM servers 310 that distribute information to a set of N user computers 315. The set of servers 310 is connected to the user computers 315 via a computer network 320, such as a LAN, WAN, a network of networks

535 797 (for example, Internet), etc. Each user computer 315 is connected to a set of one or more portable multimedia devices 330.

Through the network connection, the user computers 315 communicate with the set of DRM servers 310 to purchase, obtain a license for, update or otherwise receive information in certain embodiments. Thus, in some embodiments, the set of DRM servers 310 thus sells or licenses information to the user computers, this set does not sell or license the information in other embodiments. In some embodiments, the set of DRM servers 310 only performs the distribution of information to authorized computers without any financial interest.

In some embodiments, the set of DRM servers 310 includes an information caching server that delivers encrypted information to a user computer 310 via the network 320 after another DRM server 310 has determined that the computer 310 is entitled to the information. In some embodiments, the system 300 utilizes a number of caching servers to store information at various locations in the network to increase the speed and efficiency of downloading information over the network.

As mentioned above, a user computer 315 communicates with the set of DRM servers 310 to purchase, obtain a license for, update or otherwise receive information over the network. user computer 315, the signature being generated by hashing only a portion of the information, according to some embodiments of the invention.

Figure 3 shows in particular a user computer 315a which sends a request for an amount of information "A" to the set of DRM servers 310. This request may be a request for purchase, to obtain a license for, or otherwise access the information. Alternatively, when the information is an application or operating system running on the user computer or one of its associated multimedia devices 330, the request may be a request for an update to the application or operating system. This request may be an explicit request or an implicit request in an update check procedure performed on the user computer 315, which with or without user intervention checks for updates to the application or operating system.

535 797

II

As shown in Figure 3, the set of DRM servers 310 receives the information request A from the user computer 315a. One or more of the DRM computers then performs the procedure 400 illustrated in Figure 4 to generate a signature for the requested information A. As shown in Figure 4, the procedure 400 initially generates (at 405) a digest by applying a hash function. on only part of the requested information A. Application of a hash function to only a part of an amount of information has been described in sections I and II above. As mentioned above and further described below, the procedure 400 applies the hash function to the same part of the information A as the hashing functions of the user computer 315a and its associated multimedia unit 330a.

After applying the hashing function at 405, the procedure 410 (at 410) generates a signature based on the hash digest generated at 405. Generation of a signature based on the hash digest has been described above in sections I and II. After generating the signature at 410, the procedure transmits the requested information A and its associated signature to the user computer 315a, and then terminates.

In some embodiments, the user computer 315a uses the transmitted signature to verify the integrity of the received information A. To do this, the user computer 315a generates a hash digest for the information A by applying the hashing function to the same part of the information A as the hashing function in the set. of DRM servers 310. It then uses this digest to verify the integrity of the signature by using an asymmetric signature verifying method (as shown in Figure 1) or a symmetric signature verifying method (as shown in Figure 2).

In some embodiments, a multimedia device 330a connected to the user computer 315a also receives the information A and the signature A of this information when it is synchronized with the computer 315a. Thus, when the information A is information intended for the multimedia unit 330a, in some embodiments the user computer 315a (for example in a data memory) registers the need to download the information A and its signature to the unit 330a when the unit 330a next synchronizes with the computer 315a.

In the same way as the user computer 315a, the multimedia unit 330a generates a hash digest for the information A by applying the hashing function to the same part of the information A as the hashing function in the set of DRM servers 310. It then uses this hash digest to verify the integrity of the information through

535 797 to utilize an asymmetric signature verifying method (such as that shown in Figure 1) or a symmetric signature verifying method (such as that shown in Figure 2). Figure 5 illustrates a more detailed example of the integrity verification method.500 performed by the multimedia unit 330a in some embodiments. This procedure is performed during a synchronization operation that loads executable information (that is, code for updating the operating system, for updating existing applications, for new applications, etc.) on the multimedia device 330a. As shown in this figure, to wave with the procedure 500 (at 505) receives executable information and signature for this information during a synchronization operation which ensures that the device has all the information which the user computer indicates it should have.

After synchronization, the procedure restarts (at 510), because in some embodiments the integrity verification procedure forms part of the boot sequence at startup. In particular, in some embodiments, the boot sequence at startup performs an integrity verification procedure for each part of recently received code, although in the example shown in Figure 5, it is assumed that only one set of information is downloaded to the device at 505.1. including the integrity verification method) stored in a permanent read-only memory in the unit 315a. This ensures that the privacy verification procedure can not be manipulated after the sale of the device.

Thus, the procedure 500 (at 515) during the boot sequence at startup generates a hash digest for the retrieved information by applying the hashing function to the same part of the information as the hashing function in the set of DRM servers 310. It then uses (at 520) this hash-digest to verify the integrity of the signature. For example, the procedure 500 may use an asymmetric signature verifying method (such as that shown in Figure 1) or a symmetric signature verifying method (such as that shown in Figure 2).

When the procedure cannot verify (at 520) the integrity of the just received code (i.e. when the recently received signature does not correspond to the digest generated by the unit of the recently received information) the procedure stops without specifying that the information can be loaded into the executable memory. Alternatively, when the procedure verifies (at 520) the integrity of the just received code, the procedure specifies (at 525) that the code is executable. In some embodiments, the procedure (at 525) loads the code into an executable memory and executes the code. The DRM system 300 of Figure 3 has more than one user computer that receives digital information and signatures for such information according to the integrity verification methods in some embodiments of the invention.

535 797

In particular, Figure 3 shows a user computer 315n requesting an amount of information (i.e., the amount B) from the set of DRM servers 310. As shown in this figure, the user computer 315n receives the requested information B and a signature for this information from the set of DRM servers. 310. According to the invention, the signature of the information B is generated by hashing only a part of the information B. The user computer 315n and its associated set of portable devices 330 then verify the integrity of the information B by hashing the same portion of the information B as the set of DRM servers in much the same manner as described above for the user computer 315a and its associated devices 330a.

IV. SYSTEM DIAGRAM

Figure 6 shows a diagram of a computer system that conceptually illustrates the components of a typical DRM server, user computer or portable device implementing some embodiments of the invention. The computer system 600 includes a bus 605, a processor 610, a system memory 615, a read-only memory 620, a permanent memory 625, input units 630 and output units 3035,

The bus 605 collectively represents all system, peripheral and chipset buses that handle the communication between internal units in the computer system 600. For example, the bus 605 communicatively connects the processor 610 with the read-only memory 620, the system memory 615 and the permanent storage unit 625. From these different memory units retrieve processor 610 to execute instructions and process data to execute the procedure of the invention. The Read-only memory (ROM) 620 stores static data and instructions needed for the processor 610 and other modules in the computer system. In the case of a portable device implementing the invention, the read-only memory stores the boot sequence and the hashing procedure in some embodiments, as mentioned above.

The permanent storage unit 625, on the other hand, is a read-and-write memory unit. This unit is a permanent memory unit, which stores instructions and data even when the computer system is not in operation. Some embodiments of the invention utilize a mass memory device (such as a magnetic or optical disk with associated disk drive) as the permanent memory device 625. Other embodiments utilize an external memory device (such as a memory card or memory stick) as a permanent memory device.

Like the permanent storage unit 625, the system memory 615 is a read-and-write memory unit. However, unlike the storage unit 625, the system memory is one

535 797 volatile read-and-write memory, as a random access memory. The system memory stores some of the instructions and data that the processor needs while operating. In some embodiments, the procedures of the invention are stored in the system memory 615, the permanent storage unit 625, and / or the read-only memory 620.

The bus 605 is also connected to the input and output units 630 and 635. The input units enable the user to transmit information and select commands for the computer system. The input units 630 include alphanumeric keyboards and pointer controllers. The output devices 635 display images generated by the computer system. The output devices include printers and display devices such as cathode ray tube (CRT) or liquid crystal display (LCD) devices. Finally, as shown in Figure 6, some configurations of the computer 600 also include a network adapter 640 connected to the bus 605. Via the network adapter 640, the computer may be part of a network of computers (such as a local area network ("LAN"), an extensive network (“WAN”) or an Intranet) or a network of networks (such as the Internet). Any or all of the components of the computer system 600 may be used in conjunction with the invention. However, those skilled in the art will appreciate that any other system configuration may also be used in conjunction with the invention.

V. BENEFITS

Those skilled in the art will appreciate that the integrity verification procedures described above have several advantages. When downloading new executable code to a device, for example, it is important to verify the integrity of the code as such code provides an appropriate opportunity to subject the device to an attack. The integrity procedures, as described above, provide an easy way to check the integrity of the code even on portable devices with limited computing resources.

Some embodiments also incorporate the integrity verification procedures during the boot sequence at boot of the device to minimize the possibility of manipulating the integrity procedure. To further minimize this possibility, some embodiments have the integrity procedures stored in a read-only memory in the device.

Although the invention has been described with reference to a large number of specific details, those skilled in the art will recognize that the invention may be embodied in other specific forms without departing from the spirit of the invention. As mentioned above, for example, some embodiments may utilize a key hashing function. If a key is used, both symmetric (single secret key) and asymmetric keys (public / private) can be used

535 797 key pairs) are used. An example of a keyed hash function is a keyed MD5 technology. A transmitter adds a randomly generated key at the end of a message and then hashes the message-key combination using an MD5 hash to effect a digest. The key is then removed from the message and encrypted with the sender's private key. The message, the message digest and the encrypted key are sent to the recipient who opens the key with the sender's public key (validating in such a way that the message is actually from the sender). The receiver then adds the key to the message and applies the same hash as the sender. The message digest should correspond to the message digest sent with the message.

Several of the embodiments described above also select bit patterns in the object code format for an information. Other embodiments may select other patterns of sections as the information has a different format (for example, is in source code or XML15 format). The person skilled in the art will thus realize that the invention is not limited by the illustrative details described but should instead be defined by the appended claims.