Method for checking the integrity of a program or data, and apparatus for implementing this method

• US 5,442,645 A
• Filed: 10/24/1994
• Issued: 08/15/1995
• Est. Priority Date: 06/06/1989
• Status: Expired due to Term

• Current Assignee: CP8 Technologies (Thales SA)
• Original Assignee: Bull CP8 (Schlumberger NV)
• Inventors: Oisel, Andre, Ugon, Michel
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): TU, CHRISTINE TRINH LE
• Application Number:
  US08/328,963
• Time in Patent Office: 295 Days
• Field of Search: 235/380, 235/381, 235/382, 235/382.5, 380/28, 380/29, 380/30, 380/42, 371/22.4, 371/25.1, 371/54, 371/53, 364/222.5, 364/225.2
• US Class Current: 714/736
• CPC Class Codes: G06F 11/08 Error detection or correction by redundancy in data representation, e.g. by using checking codes
• CPC Class Codes: G06F 11/1004 to protect a block of data words, e.g. CRC or checksum G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00
• CPC Class Codes: G06F 12/1408 by using cryptography for digital transmission H04L9/00
• CPC Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• CPC Class Codes: G06Q 20/3552 Downloading or loading of personalisation data
• CPC Class Codes: G07F 7/1008 Active credit-cards provided with means to personalise their use, e.g. with PIN-introduction/comparison system

Abstract

The invention relates to a method and apparatus for checking the integrity of a message such as a program and/or data against an original message supposed to correspond to it.

By using an algorithm (A) on at least part of the original message, at least one signature (S1, S2, . . . Sm) of this part is calculated and memorized in a memory area (10) of a portable object (1) which also has processing circuits (11) able to implement algorithm (A). In order to check the integrity of a message, at least one signature of a message part is calculated by the processing circuits (11) of the portable object by implementing the algorithm (A) and is compared to an original message signature supposed to correspond, and memorized in memory area (10).

Claims

1. A method for verifying integrity, against an original message (M), of a subsequent message containing information, the method including the steps of:

storing the original message in an electronic portable object (1) having a processing circuit (11) and at least one non-volatile memory area (10) accessible only by said processing circuit (11);

storing a secret key (K) in the at least one non-volatile memory area (10) of the electronic portable object;

using the processing circuit (11) and the secret key (K) to apply an algorithm (A) to at least a part of the original message to calculate at least one original signature (S1, S2, . . . Sm) of the original message within the electronic portable object;

storing each original signature (S, S1, S2, . . . Sm) of the original message in said at least one non-volatile memory area (10) of the electronic portable object under control of the processing circuit (11);

verifying the integrity of the subsequent message against the original message by executing the algorithm (A) within the processing circuit (11) of the electronic portable object, the processing circuits (11) having inputs of the subsequent message and the secret key (K), to calculate at least one subsequent signature of at least one part of the subsequent message to be verified;

using the processing circuit (11) of the portable object to compare, within the electronic portable object, each subsequent signature calculated from the subsequent message with each original signature from the memory area (10) of the portable object; and

displaying to a user using a computer system external to the portable object, whether or not each subsequent signature calculated from the subsequent message is in matching relationship with a respective original signature calculated from a respective original message,

wherein algorithm (A) is a calculation algorithm which takes into account, for calculation of each original and subsequent signature, at least one secret key (K) stored in the memory area (10) of the portable object, accessible only within the electronic portable object and under control of said processing circuits (11).

2. The method according to claim 1, wherein the key (K) is used to calculate at least one original signature based upon at least part of the original message with a view to memorization of said at least one original signature,

wherein the key (K) is used to calculate at least one subsequent signature based upon a subsequent message with a view to verification of the at least one subsequent signature,

wherein the key (K) is determined at the time of calculation of said at least one original signature by the processing circuits of the portable object,

and wherein the key (K) is stored in the memory area of the portable object under control of the processing circuit (11) thereof at the same time the at least one original signature is stored in the memory area (10) of the portable object.

3. The method according to claim 1 wherein the key (K) is used when the at least one subsequent signature is memorized upon verification, the key (K) being stored in memory area ( 10 ) of the portable object such that the key (K) is accessible only under control of the processing circuits (11) of the portable object.

4. The method according to claim 1 wherein calculation of at least one original signature from the original message, with a view to memorization of the at least one original signature in the memory area of the portable object, is carried out by circuits (2) external to the processing circuits (11) of the portable object, in which a circuit conversion algorithm (A) is stored.

5. The method according to claim 1 wherein the step of using the processing circuit (11) and the secret key (K) to apply an algorithm (A) further comprises the steps of dividing the original message into several modules (M1, M2, . . . Mm), calculating one signature (S1, S2, . . . Sm) of each of these modules and memorizing each of the module Signatures (S1, S2, . . . Sm) in the memory area (10) of the portable object in order to serve as references for later verifications;

and

in order to verify the integrity of a subsequent message against the original message., the processing circuits compile a given number of modules (p) in the subsequent message to be verified, then the signature of each of these (p) modules is calculated and compared with the signature of the corresponding original signature module stored in the memory area (10) of the portable object.

6. The method according to claim 5 wherein the number (p) of subsequent message modules on which verification is conducted is less than a total number (m) of modules comprising the original message in order to make subsequent message signature calculation time of the signature to be verified less than time required to calculate the signatures for all subsequent message modules;

and

the number (p) is chosen as a function of the total number (m) of subsequent message modules such that a desired probability of detecting a subsequent message alteration is provided.

7. The method according to claim 5 wherein the number (p) of subsequent message modules to be verified is calculated at the time of a subsequent message verification by the processing circuit of the portable object as a function of the total number (m) of modules contained in the original message in order to provide a desired probability of detection of subsequent message alteration when the subsequent message signatures are verified.

8. The method according to claim 5 wherein, to determine on which (p) subsequent message modules the signature verification will be made, the processing circuits of the portable object make (p) successive choices of different random numbers, each random number determining a subsequent message module to be verified.

9. The method according to claim 5 further comprising the steps of:

determining a subset of modules of the original message against which subsequent message signature verification will be made, the determining step comprising;

choosing by the processing circuit of the portable object a binary random number (a) of length (m) expressed in bits, the length of the random number directly representative of the number of modules (m) in the original message,

the random number having (p) bits of a certain binary value (1 or

     0), the remaining (m-p) bits having a complementary value, each bit of the random number being assigned a different serial number, the subsequent message modules to be signature-verified determined by the serial numbers of the (p) bits taken from the (m) bits in the random number.

10. The method according to claim 5 wherein the original message is comprised of a sequence of bits identified by position in tile original message, wherein using the processing circuits of the portable object, the several modules (M1, M2, . . . Mm) of the original message are compiled and the signature of each of the several original message modules are calculated before being memorized by the processing circuits of the portable object, each of the original message modules compiled by the steps of:

selecting a certain number of original message bits according to one of a predetermined rule and a rule created by the processing circuits of the portable object, to form an original message module, and

storing the rule used to form each module from the original message in the portable object in border to reconstitute, from a subsequent message to be verified, the modules of the subsequent message following the same rule used for forming the modules from the original message.

11. The method according to claim 5, to calculate the signature of the at least one original message module (M1, M2, . . . Mm) before memorization, and to calculate the signature of at least one subsequent message module to verify the integrity of the subsequent message consisting of binary words, further comprising the steps of:

the portable object processing circuit forming a plurality of blocks (B1, B2, . . . Bn), each block consisting of data derived from the subsequent message, each datum within each block having a unique address; and

the portable object processing circuits forming the at least one subsequent message module by using at least one bit from each of the plurality of blocks (B1, B2, . . . Bn) according to a given rule.

12. The method according to claim 11 wherein forming of the plurality of blocks is carried out by taking the data in an order in which the data appears when the subsequent message is read.

13. Apparatus for verifying integrity, against an original message (M), of a subsequent message by calculating an original signature (S) from the original message (M) using a conversion algorithm (A), and comparing the original signature (S) with a subsequent signature calculated from the subsequent message, the apparatus comprising:

at least one portable object (1) including

a processing circuit (11) for implementing the conversion algorithm (A) to calculate at least one one of the signatures from at least one message,

means (10) for memorizing within the portable object the at least one signature calculated from the at least one message by the processing circuit (11),

a secret key (K) stored within the means (10) for memorizing for use as a data input to the algorithm (A) when the at least one signature is calculated by the processing circuit (11),

connecting means for connecting said processing circuit (11) to an external device (2) for execution of the subsequent message by the device (2), and

comparing means in electrical communication with the processing circuit ( 11 ) and the means for memorizing for comparing the original signature (S) calculated by the processing circuit (11) with the subsequent message signature calculated by the processing circuit (11); and

means for informing a system user via the external device (2) of a result generated by the portable object comparing means, the processing circuit (11) of the portable object calculating at least one subsequent signature of a subsequent message presented thereto for integrity verification, and the comparing means comparing the subsequent signature calculated for verification with an original signature memorized in the portable object means (10) for memorizing.

14. The apparatus according to claim 13 wherein the means (10) for memorizing of the portable object include means for memorizing rules by which each original and subsequent signature is created from a respective original and subsequent message by the processing circuit within the portable object.

15. The apparatus according to claim 13 wherein each subsequent signature corresponds to one of several original signatures memorized inside the means (10) for memorizing of the portable object, and the portable object includes means for determining correspondence between one of the several original signatures and a subsequent signature.

16. The apparatus according to claim 13 wherein the means (10) for memorizing of the portable object includes an erasable reprogrammable memory under control of the processing circuits of the portable object so that, when an intentional modification of an original message occurs, at least one signature after the intentional modification is memorized in the means (10) for memorizing of the portable object.

17. A method for verifying integrity, against an original message (M), of a subsequent message containing information, the method including the steps of:

dividing the original message into a total number (m) of modules (M1, M1, . . . Mm);

using processing means to apply an algorithm A to each module of the original message to calculate a respective signature (S1, S2, . . . Sm) of each module;

using an electronic portable object having a processing circuit (11) and memory means including one non-volatile protected memory area (10) accessible only by said processing circuit, and storing said signatures in said protected memory area and said algorithm in said memory means;

and verifying the subsequent message in the portable object by;

selecting, in the subsequent message, a partial number (p) of modules less than said total number (m) of modules, said partial number being such that the a probability of detecting an alteration in the subsequent message, by considering only said partial number of modules, has a predetermined value;

using said processing circuit to apply said algorithm to each selected module to calculate a respective signature;

selecting in said protected memory area the signatures of those modules of the original message which correspond to the selected modules of the subsequent message and comparing said signatures of the original message with the signatures of the subsequent message; and

let the portable object send an output signal indicating whether or not integrity between original and subsequent messages is met depending on whether or not said signatures of the original message are in matching relationship with the respective signatures of the subsequent message.

18. The method according to claim 17 further comprising the step of determining which (p) modules of the subsequent message on which the signature verification will be made by successive choices of different random numbers, each random number determining which module is to be verified.

19. The method according to claim 18 further comprising the steps of:

determining which modules of the message that the signature verification will be made, selecting the modules from the (m) modules contained in the original message,

choosing a binary (a) of length (m) expressed in bits such that the length of a random number chosen is directly representative of the number of modules in the original message;

wherein the random number is from a code (p) out of the (m) bits contained in the random number, bits of the code (p) that have a certain binary value (1 or

     0) while the remaining (m-p) bits have a complementary value;

each bit of the random number being marked with a different serial number; and

the number of modules to be signature-verified being determined by the serial number of the (p) bits taken from the (m) bits in the random number.

20. The method of claim 17 wherein a message is composed of a sequence of bits labelled by their addresses according to positions said bits occupy in the message, and the modules (M1, M2, . . . Mm) are created from the original message in order to calculate the signature of each of these modules before it is memorized by the portable object, as follows:

each module is formed by;

taking a certain number of message bits according to a predetermined rule; and

storing the rule used to form each module from the original message in the portable object in order to reconstitute, from a message to be verified, the modules of the message following the same rule used for forming the modules from the original message.

21. The method according to claim 17 wherein the message is organized in the form of binary words, and, in order to form said original message modules and said subsequent message modules;

forming a plurality of blocks (B1, B2, . . . Bn), each block containing data such that each datum contained in a block is indexed according to the positions of the bits of which this datum is composed; and

for forming a given module, taking at least one bit from each of the blocks according to a given rule.

22. The method according to claim 21 wherein grouping of the data to form blocks is carried out by taking the data in the order in which they appear when the message is read.