Abstract:
A method and a circuit for protecting the execution of a program, including initializing at least one counter, carrying on with the normal program execution, interrupting this execution when the counter reaches a given value, and executing at least one integrity check of the calculation after this interrupt.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS k  
       [0001]     Cross Reference To Related Applications  
         [0002]     This application is a continuation of U.S. application Ser. No. 11/407,382, filed Apr. 18, 2006 entitled PROTECTION OF THE EXECUTION OF A PROGRAM EXECUTED BY AN INTEGRATED CIRCUIT, which application is incorporated herein by reference in its entirety. 
     
    
     BACKGROUND OF THE INVENTION  
       [0003]     1. Field of the Invention  
         [0004]     The present invention generally relates to electronic circuits and, more specifically, to the protection of data contained in an integrated circuit against an extraction thereof after fault injections in the circuit operation. The present invention more specifically relates to the protection against a possible attempt to disturb a calculation handling data that should not be communicated outside the circuit.  
         [0005]     2. Discussion of the Related Art  
         [0006]      FIG. 1  is a schematic block diagram illustrating an example of a simplified architecture of an integrated circuit  1 , for example a smart card, of the type to which the present invention applies. Circuit  1  comprises a central processing unit  11  (CPU) associated with one or several memories  12  (MEM) among which generally at least one element for storing in non-volatile fashion a digital amount (for example, a confidential code) and an input/output circuit (I/O) enabling data exchange with the outside of circuit  13 . The different elements communicate via several internal data, address, and control buses  14 .  
         [0007]     Among possible attacks performed by persons attempting to fraudulently obtain confidential data from chip  1 , the present invention applies to so-called fault-injection attacks which consist of disturbing the operation of component  1 , for example, by means of radiation (laser, infrared, X-rays, etc.) or by other means (for example, by acting on the component supply).  
         [0008]     The data provided (output) by the component on its input/output ports  13  are exploited by the person attempting to fraud to discover secret elements of the chip (algorithm, secret key, etc.) or to elude a security mechanism (authentication, identification, ciphering, etc.).  
         [0009]     Some integrated circuits comprise tools for detecting fraud attempts by checking that a program has properly executed. For example, the same instructions of a calculation are executed twice and it is checked that they lead to the same result, or a signature calculation is performed on data extracted from memory  12 . In case a fraud attempt is detected, the component is generally off, that is, it does not provide the required result on its input/output ports  13 .  
         [0010]      FIG. 2  schematically shows an example of sequencing of a calculation with an integrity check of the type to which the present invention applies. This sequencing may correspond to a portion of a program executed by a smart card and only the portion subject to an integrity check, that is, a checking of the absence of errors on the calculation having involved the critical digital quantity, will be discussed.  
         [0011]     It is generally desired to check the calculation (be it by double execution or by a signature calculation) before outputting the result from circuit  1 . This means that an execution (block  21 , COMPUT) of the calculation, the integrity of which is desired to be checked, is followed in time with a checking (block  22 , CHECK) before allowing the carrying on of the program flow (block  23 , FLOW) and especially the provision of a result to the outside of the circuit.  
         [0012]     The object of checking  22  is to detect a possible disturbance by fault injection on execution of calculation  21 .  
         [0013]     A problem is that if a person attempting to fraud knows how to disturb (derail) a calculation, he also knows a priori how to disturb checking  22  of this calculation, in particular, if this disturbance consists of forcing a jump of the program in the flow thereof, there is a risk for the integrity check not to be brought to its end, without this preventing the program from carrying on, and thus the output of a result.  
         [0014]     A conventional solution to attempt solving this problem is illustrated in Fig.  2 . It consists of spacing calculation  21  in time from its integrity check  22  by interposing, between the two (block  24 , WAIT), either false operations, or a wait loop, that is, a wait sequence between the execution of the calculation and its checking.  
         [0015]     A disadvantage of such a solution is that the introduction of such a wait sequence  24  aversely affects the general rapidity of execution of the programs in the integrated circuit.  
         [0016]     Another disadvantage is that, to be effective, wait sequence  24  must be relatively long to guarantee that a second attack intended to disturb checking  22  actually falls in wait sequence  24 .  
         [0017]     Another disadvantage is that wait sequence  24  may itself be disturbed by a fault injection, which then risks enabling the program to start back off in its normal flow (block  23 ).  
       SUMMARY OF THE INVENTION  
       [0018]     The present invention aims at overcoming all or part of the disadvantages of known methods and systems for checking the integrity of calculations executed by an integrated circuit.  
         [0019]     The present invention more specifically aims at avoiding use of wait time sequences to space the execution of a calculation to be protected from its integrity check.  
         [0020]     The present invention also aims at providing a solution requiring no structural modification of the integrated circuits executing algorithms involving digital quantities to be protected.  
         [0021]     The present invention also aims at providing a versatile and adaptable solution, whatever the type of executed calculation.  
         [0022]     To achieve all or part of these objects, as well as others, the present invention provides a method for protecting the execution of a program by checking the integrity of a calculation executed by an integrated circuit, comprising:  
         [0023]     initializing at least one counter;  
         [0024]     carrying on with the program execution;  
         [0025]     interrupting this normal execution when the counter reaches a given value; and  
         [0026]     executing at least one integrity check of the calculation after this interrupt.  
         [0027]     According to an embodiment of the present invention, said given value is randomly selected from a range of values.  
         [0028]     According to an embodiment of the present invention, an upper limit of said range is selected according to the normal execution of the program so that no instruction prejudicial from the point of view of data security occurs before the integrity check of the calculation can be executed.  
         [0029]     According to an embodiment of the present invention, a lower limit of said range is selected to result in a time longer than the time required for the integrity check.  
         [0030]     According to an embodiment of the present invention, said counter is a time counter.  
         [0031]     According to an embodiment of the present invention, said counter is an instruction counter.  
         [0032]     According to an embodiment of the present invention, said counter is a counter of a signal available in the integrated circuit in relation with the calculation time.  
         [0033]     According to an embodiment of the present invention, several integrity checks are performed on intermediary results of the calculation with, each time, initializations of the counter to different values.  
         [0034]     The present invention also provides an integrated circuit comprising at least a central processing unit, a memory, an input/output circuit, and means for implementing the protection method.  
         [0035]     The present invention also provides a smart card comprising such a circuit.  
         [0036]     The foregoing and other objects, features, and advantages of the present invention will be discussed in detail in the following non-limiting description of specific embodiments in connection with the accompanying drawings. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0037]      FIG. 1 , previously described, partially and schematically shows an example of an integrated circuit of the type to which the present invention applies;  
         [0038]      FIG. 2  illustrates a conventional example of the flow of an integrity check program of the type to which the present invention applies;  
         [0039]      FIG. 3  schematically illustrates in the form of blocks a first embodiment of a method for protecting the flow of a program according to the present invention; and  
         [0040]      FIG. 4  schematically illustrates in the form of blocks a second embodiment of a method for protecting the flow of a program according to the present invention. 
     
    
     DETAILED DESCRIPTION  
       [0041]     The same elements have been designated with the same reference numerals in the different drawings. For clarity, only those method steps and circuit elements which are useful to the understanding of the present invention have been shown in the drawings and will be described hereafter. In particular, the details constitutive of the calculations, the integrity of which is desired to be checked have not been discussed, the present invention being compatible with any conventional digital quantity handling algorithm. Further, the actual integrity check programs, be they multiple calculations, signature calculations, or others have not been described in detail since the present invention is compatible with any conventional integrity check mechanism.  
         [0042]     A feature of an embodiment of the present invention is to replace the initial steps performed in the wait sequence between the integrity check and the actual calculation (block  24 ,  FIG. 2 ) with steps of the normal program flow, subsequent to the calculation to be protected.  
         [0043]     Another feature of an embodiment of the present invention is to interrupt this normal flow of the program at at least one time, randomly selected, to check the integrity (at least partially) of the calculation.  
         [0044]      FIG. 3  very schematically illustrates in the form of blocks, in a view to be compared with that of  FIG. 2 , a first embodiment of the present invention. This drawing shows the time flow of a program implementing a calculation to be protected.  
         [0045]     As previously, at a time of the program flow, said program executes (block  21 , COMPUT) a calculation, the integrity of which is desired to be checked.  
         [0046]     According to this embodiment of the present invention, at the end of the calculation, the program initializes (block  35 , T INIT) a counter  36  (TIMER). This counter is, for example, a time counter generally available in any central processing unit (block  11 ,  FIG. 1 ). It may also be a counter of instructions or of any available signal (for example, the state of a variable) likely to be put in relation with the execution time of the calculation. Counter  36  is used to generate, at the end of its counting, preferably randomly selected from a determined range, an interrupt (IT).  
         [0047]     This interrupt is, according to this embodiment of the present invention, taken advantage of to interrupt the flow (block  23 ′, FLOW) of the program which has carried on normally after initialization  35  of the counter.  
         [0048]     An integrity check calculation (block  22 , CHECK) conventional per se is executed by the central processing unit after interrupt IT.  
         [0049]     Once the integrity check has been performed, the program flow (block  23 ′, FLOW) carries on unless implementing, if need be, the required steps (circuit blocking, memory clearing, etc.) in case of a lack of integrity.  
         [0050]     According to a preferred embodiment of the present invention, counter  36  is initialized to count or count down a time interval, randomly selected between two values which are selected according to the normal program steps likely to execute (block  23 ′) before the integrity check. These values are selected to avoid for a prejudicial action from the point of view of security to intervene before the integrity check can be performed.  
         [0051]     The minimum limit for example corresponds to the minimum duration required to separate a calculation from its integrity check so that the delay is sufficient to avoid having a second disturbance cause a problem with the integrity check. For example, this minimum time corresponds to the maximum duration of the integrity check program.  
         [0052]     The maximum limit is preferably selected according to instructions  23  of the program which follow the calculation to be protected so that interrupt IT intervenes before output of a result from the circuit.  
         [0053]      FIG. 4  very schematically illustrates in the form of blocks a second embodiment of the present invention. This drawing shows the time flow of a program implementing a calculation to be protected.  
         [0054]     As compared with the embodiment of  FIG. 3 , the integrity control comprises several checks (CHECK 1 ),  222  (CHECK 2 ), etc. triggered by successive interrupts IT 1 , IT 2 , etc. which follow successive initializations  351  (T 1  INIT),  352  (T 2  INIT),  353  (T 3  INIT), etc. of counter  36  (or of separate counters). The program flow carries on (blocks FLOW  231 ,  232 ,  233 ) between each check. Each counting duration (or number of instructions) T 1 , T 2 , T 3  is randomly selected. Such an embodiment more specifically applies to checks of intermediary results of a calculation.  
         [0055]     An advantage of the present invention is that it reduces or minimizes the time loss linked to the integrity check and, more specifically, to the time separation between the integrity check and the calculation to be checked. The only time cost generated by the present invention corresponds to the interrupt management, which is in practice negligible as compared with the duration of an integrity check.  
         [0056]     Another advantage of the present invention is that it respects the random character of the time separation between the calculation to be checked and the integrity check.  
         [0057]     Another advantage of the present invention is that it is easy to implement by exploiting the central processing unit usually present to perform the involved calculation.  
         [0058]     According to an alternative embodiment, counter  36  is initialized during the main calculation (block  21 ).  
         [0059]     According to another variation, counter  36  is initialized at the beginning of the calculation to be protected. According to a preferred embodiment of this alternative, the lower limit of the counter is then selected according to the content of the calculation to be checked, to be longer than the execution time of a given number of instructions of the algorithm (for example, a number of turns of a DES-type algorithm).  
         [0060]     An advantage then is that, according to the time when the interrupt occurs, one or the other of the partial results is checked. Information about the time of the interrupt as well as a possibility to provide several interrupts are available ( FIG. 4 ).  
         [0061]     Another advantage is that this also protects from a program trap by imposing a first check close to the beginning of the algorithm.  
         [0062]     Of course, the present invention is likely to have various alterations, improvements, and modifications which will readily occur to those skilled in the art. In particular, although the present invention has been described in relation with an integrated circuit of smart card type, it more generally applies to a calculation integrity check aiming at protecting a desired secret digital quantity from a possible reading by a person attempting to fraud.  
         [0063]     Further, the practical implementation of the present invention is within the abilities of those skilled in the art based on the functional indications given hereabove and by using conventional tools. In particular, the selection of the range of durations (or of numbers of instructions) according to the calculation to be protected, as well as the initialization time (before, during, or after the calculation) are within the abilities of those skilled in the art according to the application.  
         [0064]     Such alterations, modifications, and improvements are intended to be part of this disclosure, and are intended to be within the spirit and the scope of the present invention. Accordingly, the foregoing description is by way of example only and is not intended to be limiting. The present invention is limited only as defined in the following claims and the equivalents thereto.