Processing sytem with a secure set of executable instructions and/or addressing scheme

Abstract

A method for securing a data processing system having a processing unit is disclosed. At least a group of N1 digital words of m1 bits is selected from among the set of M1 digital words. N1 is less than M1. These words are selected in such a way that each selected digital word differs from all the other selected digital words by a number of bits at least equal to an integer p which is at least equal to 2. The group of N1 digital words of m1 bits form at least one group of N1 executable digital instructions. The processing unit is configured to make it capable of executing each instruction of the at least one group of N1 executable digital instructions.

Claims

1. A method for securing a data processing system having a processing unit, the method comprising: generating a set of M1 digital words of m1 bits, wherein M1 and m1 are positive integer numbers; selecting, from among the set of M1 digital words, at least a group of N1 digital words of m1 bits, wherein N1 is a positive integer number and N1 is less than M1, in such a way that each selected digital word differs from all other selected digital words by a number of bits greater than or equal to an integer p, integer p being greater than or equal to 2, the group of N1 digital words of m1 bits forming at least one group of N1 executable digital instructions; and configuring the processing unit to make it capable of executing each instruction of the at least one group of N1 executable digital instructions.

2. The method according to claim 1, wherein N1 is equal to 2.sup.n1 and M1 is equal to 2.sup.m1, wherein n1 is a positive integer number and m1 is greater than n1.

3. The method according to claim 1, wherein unselected digital words are invalid instructions.

4. The method according to claim 1, wherein a set of the executable instructions comprises a plurality of groups of digital instructions, the digital instructions of the same group meeting a similarity criterion, the similarity criterion respectively associated with the groups all being different from each other; wherein the selecting comprises selecting, from among the set of M1 digital words, a plurality of groups of digital words in such a way that each selected word of a group differs from all other selected words of the group by a number of bits greater than or equal to p, the groups of digital words forming the groups of digital instructions; and wherein the method comprises configuring the processing unit to make it capable of executing each instruction of the groups of digital instructions.

5. The method according to claim 4, wherein a digital instruction of at least one rank of a group may differ by only one bit from the digital instruction of the same rank or of a different rank of another group.

6. The method according to claim 4, wherein the digital words not belonging to any group are invalid instructions.

7. The method according to claim 1, further comprising storing, in program storage unit of the data processing system, digital program instructions defining a program to be executed by the processing unit and belonging to a set of the executable instructions.

8. The method according to claim 1, further comprising operating the processing unit so that it executes one of the instructions of the at least one group of N1 executable digital instructions.

9. A method for developing a secured addressing scheme within a data processing system, the scheme being organized in address blocks and having N2 address blocks, and address words having n2 bits, wherein N2 and n2 are positive integer numbers, the method comprising: generating a set of 2.sup.m2 digital words of m2 bits, wherein m2 is a positive integer number, m2 being less than n2 and greater than or equal to 2; selecting, from among the set of 2.sup.m2 digital words, N2 digital words of m2 bits, in such a way that each selected digital word differs from all other selected digital words by a number of bits greater than or equal to an integer h, integer h being greater than or equal to 2; and assigning to the N2 address blocks address words whose m2 most significant bits are, respectively, the m2 bits of the N2 selected digital words.

10. The method according to claim 9, further comprising: for at least one of the address blocks having M address sub-blocks, generating a set of 2.sup.r digital words of r bits, M and r being positive integer numbers, r being less than or equal to n2-m2 and greater than or equal to 2; selecting, from among the set of 2.sup.r digital words, m digital words in such a way that each digital word differs from all the other selected digital words by a number of bits greater than or equal to an integer s greater than or equal to 2, wherein m is a positive integer number equal to M; and assigning to the at least one of the address blocks address words whose r bits following the m2 most significant bits are, respectively, the r bits of the m selected digital words.

11. The method according to claim 9, further comprising operating the data processing system using the secured addressing scheme.

12. A data processing system comprising: a processor capable of executing each instruction of a set of executable digital instructions of m1 bits, m1 being a positive integer number, the set of executable digital instructions including at least a group of N1 digital words of m1 bits (MNS.sub.i), wherein N1 is a positive integer number and 2.sup.m1 is greater than N1, each digital word differing from all other digital words of the group by a number of bits greater than or equal to an integer p which is greater than or equal to 2; and a storage unit configured to store program code comprising instructions of the set of executable digital instructions.

13. The data processing system according to claim 12, wherein N1 is equal to 2.sup.n1, n1 is a positive integer and m1 is greater than n1.

14. The data processing system according to claim 12, wherein, in the presence of a digital word other than those of the at least one group, the processor is configured to execute a special invalidity process.

15. The data processing system according to claim 12, wherein the processor is configured to execute each instruction of a set of executable digital instructions of m1 bits including a plurality of groups of digital words of m1 bits, each digital word of a group differing from all the other digital words of the group by a number of bits greater than or equal to 2, the digital instructions of a given group meeting a similarity criterion, the similarity criterion respectively associated with the groups all being different from each other.

16. The data processing system according to claim 15, wherein a digital instruction of at least one rank of a group may differ by only one bit from the digital instruction of the same rank or of a different rank of another group.

17. The data processing system according to claim 15, wherein, in the presence of a digital word not belonging to any group, the processor is configured to execute a special invalidity process.

18. The data processing system according to claim 12, wherein the processor comprises a microprocessor.

19. The data processing system according to claim 12, wherein the processor comprises a microcontroller.

20. An integrated circuit, incorporating the data processing system according to claim 12.

21. A card incorporating the integrated circuit according to claim 20.

22. A data processing system comprising: a processing unit; and elements addressable by address words of n2 bits belonging to an addressing scheme using address blocks, n2 being a positive integer number, the addressing scheme having N2 address blocks, wherein N2 is a positive integer number and the address words assigned to the N2 address blocks each include a first group of m2 most significant bits, m2 being a positive integer number less than n2 and greater than or equal to 2, each first group of an address word assigned to one of the N2 blocks differing from all the N21 other first groups of the other address words assigned to the N21 other blocks by a number of bits greater than or equal to an integer h which is greater than or equal to 2.

23. The data processing system according to claim 22, wherein elements comprise storage units and peripherals.

24. The data processing system according to claim 22, wherein at least one of the address blocks has M address sub-blocks, M being a positive integer number, and the address words assigned to the at least one of the address blocks each have, after the first group of m2 most significant bits, m2 being a positive integer number, a second group of r bits, r being a positive integer number less than or equal to n2m2 and greater than or equal to 2, each second group of an address word assigned to one of the M address sub-blocks differing from all the M1 other second groups of the other address words in the M1 other sub-blocks by a number of bits greater than or equal to an integer s which is greater than or equal to 2.

25. The data processing system according to claim 24, wherein the element associated with the at least one of the blocks is a set of peripherals and wherein the M elements associated with the M address sub-blocks are M particular types of peripheral.

26. The data processing system according to claim 22, wherein the processing unit comprises a microprocessor or a microcontroller.

27. An integrated circuit, incorporating the data processing system according to claim 22.

28. A card incorporating the integrated circuit according to claim 27, the card comprising an integrated circuit card or a smart card.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) Other advantages and features of the invention will be made clear by the detailed description of applications and embodiments, which is not limiting in any way, and the appended drawings, in which:

(2) FIGS. 1 to 12 show schematically some different applications and embodiments of the different aspects of the invention.

DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENTS

(3) In FIG. 1, the reference SYS denotes a data processing system having a processing unit UT, for example a microcontroller or a microprocessor, having a processor MT (processing means), connected via a bus BS to program storage unit MMP and to different storage units MM1, MM2, MM3 and to different peripherals PH1, PH2, PH3 . . . .

(4) At least some of these peripherals, for example the peripherals PH1 and PH2, are peripherals of the same type, for example, controllers, while the peripheral PH3 and other peripherals, not shown here for the sake of simplicity, are peripherals of another type, for example clock generation systems.

(5) The system SYS may be, as shown in FIG. 2, incorporated into an integrated circuit CI which is itself integrated into an integrated circuit card or a smart card CP.

(6) Reference will now be made in a more detailed way to FIGS. 3 to 8 in order to describe an example of the development of a set of secured executable instructions which can be executed by the processing unit UT.

(7) It is assumed here that the set of instructions executable by the processing unit comprises 2.sup.n1 executable instructions formed by words of m1 bits.

(8) In this example, a set of 2.sup.m1 digital words of m1 bits, MN.sub.i, is initially generated (step 30, FIG. 3). The variable m1 is chosen so as to be greater than n1.

(9) Then, in step 31, a group of 2.sup.n1 digital words of m1 bits, MNS.sub.i, is selected from the set of 2.sup.m1 digital words MN.sub.i. The words MNS.sub.i are selected in such a way that each selected digital word MNS.sub.i differs from all the other selected digital words by a number of bits at least equal to an integer p which is at least equal to 2. In other words, the Hamming distance between two selected digital words is at least equal to p.

(10) The set of 2.sup.n1 selected digital words MNS.sub.i then forms the group of 2.sup.n1 executable instructions INST.sub.i.

(11) The digital words not selected in the set of 2.sup.m1 digital words MN.sub.i may then, for example, be considered as invalid instructions INSIV.sub.j.

(12) On the basis of these executable instructions INST.sub.i, a programmer may develop a program whose digital program instructions (taken from among this set of secured executable instructions INST.sub.i) may be stored in program storage unit MMP.

(13) This being the case, the processor of the microprocessor or microcontroller UT generally has a logic core including logic gates and pipeline stages. This logic core has to be configured, typically by using conventional software tools, in such a way that the microprocessor can effectively execute each of the 2.sup.n1 desired operations (addition, jump, conditional jump, subtraction, multiplication, etc.) when it receives at its input each of the 2.sup.n1 corresponding secured executable digital instructions. Once this configuration of the microprocessor is complete, it is hard-coded and associated in a one-to-one way with the 2.sup.n1 secured executable instructions.

(14) Step 32 of FIG. 3 shows the configuration of the processor MT of the microprocessor UT for making them capable of executing each of the instructions of the set of executable digital instructions which has just been generated.

(15) FIG. 4 shows an example of a set of 16 instructions (n=4) selected from a set of 256 digital words (m=8) of 8 bits each. In this example, the number p has been chosen so as to be equal to 4.

(16) Therefore, as shown in FIG. 4, the 16 selected digital words MNS.sub.1-MNS.sub.16, corresponding to the 16 8-bit instructions of the set of instructions, are such that each selected digital word MNS.sub.i differs from the other selected digital words by a number of bits at least equal to 4.

(17) Thus an attacker wishing to carry out a fault injection attack will have to be able to change 4 bits of an instruction in order to have a chance of reaching a valid executable instruction. The robustness of this set of executable instructions against a fault injection attack is therefore greatly enhanced.

(18) In the example described above, it was assumed that the set of executable instructions contained only one group of 2.sup.n1 digital instructions of m1 bits each.

(19) This being the case, it is entirely possible that the set of executable instructions may comprise a plurality of groups GR1-GRg which, in this example, each have 2.sup.n1 instructions.

(20) Therefore, as shown in FIG. 5, starting with 2.sup.m1 digital words MN.sub.i the different groups GRg of selected digital words are selected (step 51), taking the number p into account.

(21) Thus the group GR1 comprises 2.sup.n1 selected digital words MNS1.sub.i, the group GR2 comprises 2.sup.n1 selected digital words MNS2.sub.i, and the group of rank g comprises 2.sup.n1 selected digital words MNSg.sub.i.

(22) Here again, within each group, a selected digital word differs from the other selected digital words by a number of bits at least equal to p.

(23) However, it is not necessary for a digital word MNS1.sub.i to differ from a selected digital word of another group, for example the digital word MNS2.sub.i, by a number of bits at least equal to p.

(24) The different selected digital words of different groups then form, respectively, the 2.sup.n1 executable instructions of the different groups.

(25) Thus a first group GR1 is formed by the 2.sup.n1 executable instructions INST1.sub.i corresponding to the selected digital words MNS1.sub.i, while the 2.sup.n1 instructions INST2.sub.i of the group GR2 correspond to the 2.sup.n1 selected digital words MNS2.sub.i, and so on.

(26) It then becomes possible to group instructions meeting the same similarity criterion within the same group, given that the similarity criteria differ from one group to another.

(27) Thus, the instructions INST1.sub.i which have the same number of operands can be grouped in group GR1, while the instructions INST2, which perform the same type of operation (for example jumps, conditional jumps, etc.) can be grouped in group GR2, for example.

(28) Starting from these executable instructions INST1.sub.i, INST2.sub.i, INSTg.sub.i, a programmer can develop a program whose digital program instructions (taken from this set of secured executable instructions INST1.sub.i, INST2.sub.i, INSTg.sub.i) can be stored in the program storage unit MMP.

(29) Here again, an attacker wishing to replace an instruction belonging to a group with another instruction belonging to the same group would again have to modify simultaneously at least p bits, for example 4 bits if p is equal to 4.

(30) Step 52 of FIG. 5 shows the configuration of the processor MT of the microprocessor UT for making them capable of executing each of the instructions of the set of executable digital instructions INST1.sub.i, INST2.sub.i, INSTg.sub.i which has just been generated.

(31) On the other hand, if it is impossible or undesirable to divide the whole set of 2.sup.m1 digital words into groups, there may be some remaining unselected digital words belonging to no group. In this case, as shown in FIG. 5, and by analogy with what has been described above, these unselected digital words may be considered as invalid instructions INSIV.sub.j.

(32) FIG. 6 shows an example of three groups GR1, GR2, GR3 of 16 selected digital words corresponding to 16 instructions, these three groups coexisting in the initial set of 2.sup.8 digital words.

(33) In each group, each selected digital word, and therefore each instruction, has a Hamming distance greater than or equal to 4 from all the other selected digital words of the same group.

(34) It should also be noted here that, for at least some of the ranks, rank 1 for example, and for at least some of the groups, groups GR2 and GR3 for example, the digital word MNS2.sub.1 differs from the selected digital word MNS3.sub.1 by only one bit.

(35) An instruction modified by a laser beam attack may therefore result in a change of group, which is disturbing for the attacker.

(36) In this example, the group GR1 may be assigned to branching instructions, while the group GR2 may be assigned to instructions having an operand and the group 3 may be assigned to instructions having two operands.

(37) FIG. 7 shows an example of an algorithm for assigning a digital word MN from among the 2.sup.m1 digital words to a group. This algorithm can also be used to handle the generation of a plurality of groups conforming to the criteria defined above.

(38) This algorithm can easily be implemented in a microcomputer, for example a PC.

(39) This case is purely a non-limiting example.

(40) This algorithm will scan all the values MN of the digital words from 0 to 2.sup.m11. For each value MN, a parameter denoted tab is assigned, this parameter being set to 1 for all the digital words at the outset. At the end of the algorithm, the group identifier of a digital word is the value of the parameter associated with this digital word.

(41) If the group identifier has a value of 1, the corresponding digital word has no group.

(42) In step 70, a check is made as to whether the value of the digital word MN is less than 2.sup.m1. If this is the case, the group identifier, groupId, is set to 0, and a logical variable Grptrouv is set to the false state.

(43) In step 72, a test is conducted as to whether the identifier groupId is less than 2.sup.m1, and whether the variable Grptrouv is in the false state.

(44) If this is the case, a value testVal is set to 0, and a logical variable validGroup is set to the true state.

(45) In step 74, a test is conducted as to whether the variable testVal is less than 2.sup.m1, and whether the logical variable validGroup is in the true state.

(46) If this is the case, the algorithm moves to step 75, in which a test will be conducted as to whether the value of the parameter associated with the variable testVal is equal to the identifier groupId, and whether the Hamming distance between the current digital word MN and the value testVal is less than p.

(47) If this is the case, the value false is assigned to the variable validGroup (step 76), whereas, if the result of the test of step 75 is false, the variable testVal is incremented by 1 (step 77). The algorithm then returns to step 74.

(48) If the result of the test of step 74 is found to be false, the state of the logical variable validGroup is tested (step 78).

(49) If this variable is in the true state, the algorithm moves to step 79, in which the value of the variable groupId is assigned to the parameter tab associated with the digital word MN, and the true value is assigned to the logical variable Grptrouv.

(50) The algorithm then moves to step 80 in which the variable groupId is incremented by 1.

(51) On the other hand, if valid Group has the false value in step 78, the algorithm moves directly to step 80.

(52) At the end of step 80, the algorithm returns to step 72. If the test result is false in step 72, the algorithm moves to the next digital word (step 81) and returns to step 70.

(53) If the test result is false in step 70, the algorithm stops, and a group has or has not been assigned to each of the digital words, while, in each of these groups, the selected digital words meet the condition of a Hamming distance at least equal to p.

(54) FIG. 8 provides an extract from the result of the algorithm for 256 digital words, showing, for each digital word MN (only the digital words 0x00 to 0x3F are shown here), the number of the group in which it will be placed.

(55) The same concept of a minimum Hamming distance between digital words can be used, as shown in FIG. 9, to develop a secured addressing scheme within the data processing system SYS.

(56) In FIG. 9, the minimum Hamming distance is h, but it would obviously be possible to choose a minimum Hamming distance h which was equal to p, as in the securing of the set of executable instructions described above.

(57) In this case, the addressing scheme is organized in address blocks, and has N2 address blocks. The address words used in the addressing scheme have n2 bits in this case, for example 32 bits.

(58) A number m2, less than n2 and greater than or equal to 2, is then chosen. A set of 2m2 digital words of m2 bits MNi is then generated (step 80).

(59) Then, in step 81, N2 selected digital words MNS.sub.i are selected from among the set of 2.sup.m2 digital words, in such a way that each selected digital word differs from all the other selected digital words by a number of bits at least equal to h, the integer h representing the minimum Hamming distance.

(60) Address words are then generated (step 82) and are respectively assigned (step 83) to the N2 address blocks. More precisely, the address words MAD1.sub.j assigned to address block 1 all have m2 most significant bits, corresponding to the m2 bits of the selected digital word MNS1. The remaining n2m2 bits can be used to define a plurality of address words which all have the same most significant bits.

(61) Similarly, the address words MADN2.sub.j assigned to address block N2 all have, as their m2 most significant bits, the m2 bits of the selected digital word MNS.sub.N2.

(62) The different address blocks are then associated, in step 84, with N2 elements of the data processing system.

(63) Thus, by way of example, as shown in FIG. 10, if n2=32, m2=5 and h=3 are chosen, only four selected digital words MNS.sub.1-MNS.sub.4 are obtained, these words forming four groups of address words distinguished from each other by their most significant bits. It will be possible to assign these four groups of address words to four address blocks associated with four elements, for example the storage unit MM1, the storage unit MM2, the storage unit MM3 and the set of peripherals PH.sub.i.

(64) It then becomes particularly difficult for an attacker who wishes to carry out a fault injection attack to move from one address block to another, as this would require the simultaneous modification of 3 bits among the 5 most significant bits in order to have a chance of obtaining a valid address from another block.

(65) It is entirely possible that at least one of the address blocks has M address sub-blocks.

(66) This is the case, for example, with the address block assigned to the set of peripherals. In fact, the set of peripherals PH.sub.i can be divided into M subsets of peripherals, each subset containing peripherals of the same type.

(67) The addressing of these sub-blocks can then be secured, in the same way as that described above.

(68) More precisely, as shown in FIG. 11, a set of 2.sup.r digital words of r bits is generated, r being less than or equal to n2m2, and greater than or equal to 2. Then, in step 111, M selected digital words MRS.sub.i are selected from among the 2.sup.r digital words MR.sub.i, taking into account the minimum Hamming distance, equal to an integer s greater than or equal to 2 (here again, s represents the minimum Hamming distance and may be chosen so as to be equal to or different from h).

(69) Here again, each selected digital word MRS.sub.i differs from all the other selected digital words by a number of bits at least equal to s.

(70) Address words are then generated (step 112).

(71) More precisely, it is assumed in this example that it is address block 4 (in which all the address words have the selected digital word MNS.sub.4 as their m2 most significant bits) that has M address sub-blocks.

(72) In this case, the address words MADR1.sub.j assigned to the first address sub-block include, as regards these r bits following the m2 most significant bits, the selected digital word MRS.sub.1.

(73) The remaining n2m2r bits can be used to define a plurality of address words MADR1.sub.j, enabling the peripherals of the corresponding subset of peripherals to be assigned individually.

(74) Similarly, all the address words MADRM.sub.j have, as their m2 most significant bits, the m2 bits of the selected digital word MNS.sub.4, and then have, as the following r bits, the r bits of the selected digital word MRS.sub.M.

(75) These address words assigned to the M address sub-blocks (step 113) are then associated with the M subsets of peripherals.

(76) The selection of the different digital words and their distribution within at least one group can be carried out by using the same algorithm as that described with reference to FIG. 7.

(77) In the example described, and as shown in FIG. 12, the 32-bit address pointer PTR therefore includes 5 most significant bits in such a way that 4 address blocks with a minimum Hamming distance equal to 3 can be differentiated, and, within an address block, at least 2048 address sub-blocks can be differentiated over 17 bits with a Hamming distance at least equal to 4. The remaining 10 bits can be used for the individual addressing of peripherals, for example.