Abstract:
A method of maintaining the integrity of software stored in memory, the method comprising: storing an indicator associated with the memory; calculating a reference value from the stored indicator; storing the reference value; modifying the indicator when the software in the memory is modified; storing the modified indicator; recalculating the reference value from the modified indicator; storing the recalculated reference value; and verifying the integrity of the software by: retrieving the modified indicator; calculating an expected value from the modified indicator; and comparing the expected value with the recalculated reference value. Preferably the integrity of the software is verified without calculating an expected value from the software. The reference and expected values are typically calculated in accordance with a secret key.

Description:
FIELD OF THE INVENTION 
       [0001]    The present invention relates to a method and apparatus for maintaining software integrity. The invention can be employed typically, although not exclusively, in a mobile computing environment. 
       BACKGROUND OF THE INVENTION 
       [0002]    In the modem mobile computing environment the security of the execution environment and of the data stored on the mobile device is becoming ever more important. 
         [0003]    A GSM handset typically stores a unique identifier (known as the IMEI). This identifier must be immutable once the handset has been produced. The challenge for handset makers is to achieve this and also to protect the integrity of all the executable software which accesses the IMEI. There is no point in having the IMEI stored securely if the software can be modified never to access the stored value but to use another one. The challenge is therefore to protect the integrity of this software. 
         [0004]    One approach would be to store the software in a region of read-only memory (ROM) where its integrity is guaranteed. However in practice this solution is not viable. This is because of the increasing complexity of the software which means that it is increasingly necessary to provide mechanisms which allow this software to be updated to fix problems. This may be achieved either via a physical connection typically at a service centre or over the wireless network using an over the air update mechanism. 
         [0005]    The effect of this is that the software components are stored in modifiable storage, usually based on flash technology (although other mechanisms can be used). The important point however is that the contents of such devices can be modified and it becomes necessary to check the integrity of software stored in such devices when the device is booted and ideally before each execution of critical areas of functionality. 
         [0006]    A standard mechanism to perform integrity checks is based on the use of secure mapping algorithms which uniquely (or at least substantially uniquely) map the software to generate check data. Examples of such algorithms are the hashing algorithms SHA-1 (FIPS 180-2) or HMAC (FIPS 198) which generate outputs known as checksums. To calculate any of these checksums it is necessary to read the whole of the software which is to be checked into memory and perform a significant amount of computation on the values. On a mobile device with limited CPU power and battery life this is a significant burden which will only increase as the size of the software running on such devices increases. A worse problem is that the time taken for this validation can significantly increase the time taken to boot the device. 
         [0007]    This problem of the requirement for significant computation, power and worst of all boot time affects all mobile devices which must implement secure operation including devices such as MP3 players. In many cases the security level is even higher when Digital Rights Management (DRM) software is in use and the content decryption mechanisms must be protected. 
         [0008]    Flash devices such as those used in most mobile equipment store data within them in a non-volatile manner. This storage is then presented to the processor either as an area of virtual memory allowing full virtual memory access or via a device interface which also allows random access to the contents. 
         [0009]    A. Murat Fiskiran, Ruby B. Lee, “Runtime Execution Monitoring (REM) to Detect and Prevent Malicious Code Execution,” iccd, pp. 452-457, 2004 IEEE International Conference on Computer Design (ICCD&#39;04), 2004 (hereinafter referred to as “Fiskiran et al”) describes a Memory Hashing (MH) process in which a memory is structured as a tree with the program data placed at the leaves. Every node of the tree contains the hash of the nodes (or leaves) below it. At the root of the tree is a root hash which is permanently kept in secure memory. The integrity of an incoming data block is checked by recursively verifying its hash and all the hashes of its parent nodes, up to the root hash. 
       SUMMARY OF THE INVENTION 
       [0010]    A first aspect of the invention provides a method of maintaining the integrity of software stored in memory, the method comprising:
       a. storing an indicator associated with the memory;   b. calculating a reference value from the stored indicator;   c. storing the reference value;   d. modifying the indicator when the software in the memory is modified;   e. storing the modified indicator;   f. recalculating the reference value from the modified indicator;   g. storing the recalculated reference value; and   h. verifying the integrity of the software by:
           i. retrieving the modified indicator;   ii. calculating an expected value from the modified indicator; and   iii. comparing the expected value with the recalculated reference value,
 
wherein the integrity of the software is verified in step h. without calculating an expected value from the software.
   
               
 
         [0022]    The method of the first aspect of the invention reduces the time taken to verify the integrity of the software in step h., since it is not necessary to calculate the expected value from the software. Instead, the expected value is calculated from the modified indicator, which will involve less computation. This can be contrasted with Fiskiran et al in which the integrity-check process starts with the step of calculating hash values from the program data in the leaves. 
         [0023]    A second aspect of the invention provides a method of maintaining the integrity of software stored in two or more memory sectors, the method comprising:
       a. storing two or more indicators, each indicator associated with one of the memory sectors;   b. calculating a reference global value from the stored indicators;   c. storing the reference global value;   d. modifying the stored indicators when the software in their associated memory sector is modified;   e. storing the modified indicators;   f. recalculating a reference global value from the modified indicators;   g. storing the reference global value; and   h. verifying the integrity of the software by:
           i. retrieving the stored indicators;   ii. calculating an expected global value from the retrieved indicators; and   iii. comparing the expected global value with the reference global value.   
               
 
         [0035]    The second aspect of the invention extends the principle of the first aspect of the invention to a memory with multiple memory sectors, each having an associated indicator. The second aspect of the invention provides a further reduction in computation by calculating a single global value in steps b., f. and h.ii. from multiple indicators, instead of calculating a separate value from each indicator. Preferably the integrity of the software is verified in step h. without calculating an expected value from the software. 
         [0036]    The reference and expected values may be calculated in steps b., f. and h.ii. in accordance with a secret key, for instance by hashing or some other mapping algorithm. This makes it more difficult for an unauthorised party (without access to the secret key) to calculate the values. 
         [0037]    A third aspect of the invention provides a method of maintaining the integrity of software stored in memory, the method comprising:
       a. storing an indicator associated with the memory;   b. calculating a reference value from the stored indicator in accordance with a secret key;   c. storing the reference value;   d. modifying the indicator when the software in the memory is modified;   e. storing the modified indicator;   f. recalculating the reference value from the modified indicator in accordance with a secret key;   g. storing the recalculated reference value; and   h. verifying the integrity of the software by:
           i. retrieving the modified indicator;   ii. calculating an expected value from the modified indicator in accordance with a secret key; and   iii. comparing the expected value with the recalculated reference value.   
               
 
         [0049]    The method of the third aspect of the invention calculates the reference and expected values in accordance with a secret key. This can be contrasted with Fiskiran et al which ensures integrity by storing the root hash in secure memory. 
         [0050]    The following comments apply to all aspects of the invention. 
         [0051]    The or each indicator may be a counter which may be incremented or decremented in step d., or modified in some other way (for instance by counting the number of words of the software that have been modified). Alternatively the or each indicator may be a checksum which is modified in step d. by mapping from the modified software in accordance with a mapping algorithm, the mapping being substantially unique. 
         [0052]    If the comparison step h.iii. results in a match between the expected and reference values then various actions may be taken, depending on the context in which the software is being verified. For instance if the software is executable code, then the code may be executed if there is a match. Alternatively the output of step h. may simply be an indication of whether there is a match. 
         [0053]    The methods of the present invention may be implemented in software or dedicated hardware, typically on a device with limited processing power such as a mobile device. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS  
         [0054]    Embodiments of the invention will now be described with reference to the accompanying drawings, in which: 
           [0055]      FIG. 1  is a schematic diagram of a mobile computing device; 
           [0056]      FIG. 2  shows a first mechanism for maintaining checksum values; 
           [0057]      FIG. 3  shows a second mechanism for maintaining checksum values; 
           [0058]      FIG. 4  shows a third mechanism for maintaining checksum values; 
           [0059]      FIG. 5  shows a fourth mechanism for maintaining checksum values; 
           [0060]      FIG. 6  shows a fifth mechanism for maintaining checksum values; 
           [0061]      FIG. 7  shows a boot procedure; 
           [0062]      FIG. 8  shows a mechanism for maintaining sector counter values; and 
           [0063]      FIG. 9  shows a boot procedure using the sector counter values. 
       
    
    
     DETAILED DESCRIPTION OF EMBODIMENTS 
       [0064]    A mobile computing device  1  (such as a mobile phone handset) is shown in  FIG. 1 . The device includes a Central Processing Unit (CPU)  10 , a Boot ROM  11 , a flash chip  12  and an antenna  13 . The flash chip  12  includes a processor  20 , and a memory  21  which is divided up into a number of sectors  22 . These sectors correspond loosely with the areas (also often called sectors) which are used in conventional flash chips. 
         [0065]    The sectors  22  include integrity-protected sectors and non-integrity-protected sectors. The integrity-protected sectors store software such as:
       executable code which enables the CPU  20  to retrieve an IMEI which is stored securely on the device, either on the flash chip or some other storage element;   other executable code;   calibration data determining how the antenna operates;   other data.       
 
         [0070]    The integrity-protected sectors may be write protected. This protection merely makes it impossible to write to such sectors by accident since a determined attacker can disable the write protection, make his modifications, and enable the write protection. The flash chip also maintains a sector checksum value or counter for each integrity-protected sector. 
         [0071]    The non-integrity-protected sectors store software such as phonebook data or SMS data. The non-integrity-protected sectors may or may not be write protected, and may or may not have associated sector checksum values or counters. 
         [0072]    Examples of five mechanisms for maintaining checksum values are given below in  FIGS. 2-6 . 
         [0073]    A first mechanism is shown in  FIG. 2 . In a first step  30  (during manufacture), data is written to all sectors by the CPU  10 . In a second step  31  (also during manufacture), sector checksums are calculated and stored for all sectors containing integrity-protected data. The sector checksums may be calculated by any mapping algorithm which uniquely (or at least substantially uniquely) maps the software to the checksum. That is, it is highly unlikely that different software will map to the same sector checksum. Examples of such mapping algorithms are the hashing algorithms SHA-1 (FIPS 180-2) or HMAC (FIPS 198). 
         [0074]    The sector checksums can be stored on the flash chip in a variety of ways. For instance they can be stored as part of virtual memory, or in dedicated registers. The important point is that the flash chip is configured to release the stored checksums to make them available outside the chip. 
         [0075]    The CPU  10  has within it one time programmable storage  14  (such as a series of fuses) which stores a secret key entered at production time. In a third step  32  (also during manufacture), the CPU  10  uses this key with a mapping algorithm such as HMAC with SHA-1 to compute a reference global checksum of all of the sector checksums which have been calculated in the step  31 . As with the sector checksums, the reference global checksum may be calculated by any mapping algorithm which uniquely (or at least substantially uniquely) maps the key and the sector checksums to the reference global checksum. The reference global checksum is then stored in the flash chip, in such a way that the CPU can retrieve the reference global checksum later. 
         [0076]    During use of the handset, it may be desirable to legitimately modify one or more sectors containing integrity-protected data. Such a process of authorised modification is shown on the right hand side of  FIG. 2 . In step  33  the CPU  10  requests the processor  20  to disable the write protection. In response to this disable command the processor  20  automatically adds 1 to the sector checksum of each sector to be modified (or makes some other simple modification of the sector checksum(s)). The processor then writes to the sector(s) in step  34  and enables the write protection in step  35 . The CPU  10  then issues a special command to the processor  20  which causes the processor  20  to recalculate and store all of the sector checksums for the sector(s) which have been modified in step  36 . The CPU  10  recalculates and stores the global reference checksum in step  37  based on the new sector checksums and the secret key. In step  38  the process ends. 
         [0077]    This authorised process can be contrasted with an unauthorised process shown on the left-hand side of  FIG. 2 . In this case steps  39 - 41  correspond with steps  34 - 36 , but the unauthorised party is unable to perform step  37  since they do not have the secret key. The global reference checksum will therefore be incorrect. 
         [0078]    In a second mechanism shown in  FIG. 3 , the flash chip does not support sector write protection, but the processor  20  is configured to modify the sector checksum whenever software within a sector is written to. Steps  30 ,  31 ,  32 ,  36 ,  37  and  41  are as in  FIG. 2 . In steps  50  and  51  the processor  20  automatically modifies the checksum(s) as part of the write step  34 . This can be contrasted with  FIG. 2  in which the modification is performed as part of the write protection disable step  33 . 
         [0079]    In a third mechanism shown in  FIG. 4 , the processor  20  supports sector write protection but does not have a special command to recalculate the sector checksum(s). Instead the sector checksum(s) are recalculated and stored by the processor  20  automatically as part of the write protection enable step  60 . 
         [0080]    In a fourth mechanism shown in  FIG. 5 , the flash chip supports sector write protection and the processor  20  is configured to re-calculate the sector checksum(s) whenever any software within the sector(s) is updated. Thus the checksum(s) are automatically re-calculated as part of the write step  65 . 
         [0081]    The mechanism of  FIG. 6  is the same as the mechanism of  FIG. 5 , except it omits steps  33 ,  35  and  40 . 
         [0082]    The mechanisms described above ensure that sector checksums are maintained by the flash chip itself and cannot be bypassed: i.e. the contents of the flash chip cannot be modified without the corresponding sector checksum(s) being modified. Implementation within the flash chip rules out interference short of direct modification of the flash contents using out-of-band mechanisms such as ion beams. 
         [0083]    The flash chip  10  is configured to enable the reference global and sector checksums to be retrieved by the CPU  10  during a secure boot procedure which will now be described with reference to  FIG. 7 . 
         [0084]    In step  70 , the CPU  10  is started and it starts execution using software from the Boot ROM  11 . This software causes the CPU  10  to retrieve all of the sector checksums associated with integrity protected sectors from the flash chip  12  in step  71 . As described above, the sector checksums are maintained by the flash chip, so this requires no major computation by the CPU  10 . 
         [0085]    In step  72  the boot software in the ROM causes the CPU to calculate an expected global checksum from the sector checksums retrieved in step  71 , using the same mapping algorithm that was used to calculate the reference global checksum. In step  73  the CPU retrieves the reference global checksum stored on the flash chip. In step  74  the CPU compares the global checksums from steps  72  and  73 . If they match, then the integrity of the sector checksums is positively verified and the boot procedure continues as normal in step  75  (that is, the CPU retrieves and executes the executable software on the flash chip). If a third party has modified an integrity-protected sector by the method shown in  FIG. 3 , then the global checksums will not match and the boot procedure aborts in step  76  and/or an error message is output. 
         [0086]    This approach is as secure as the secret key within the CPU  10  since without that key it is impossible for an unauthorised party to recalculate the correct reference global checksum to store in the flash chip after some modification is made. Many other implementations for the global value check are possible. 
         [0087]    The methods of  FIGS. 1-5  change the sector checksum twice during an authorised write procedure: first the sector checksum is modified by adding one, then the sector checksum is recalculated from the new software that has been written to the sector. By contrast, the method of  FIG. 6  only changes the sector checksum once when it is recalculated in step  65 . 
         [0088]    The methods of  FIGS. 1-6  all include the step of recalculating the sector checksum after a sector has been modified. This is done in order to ensure that the sector checksums always map correctly to their associated sector. This enables the CPU  10  or flash processor  20  to periodically perform a check for corrupted software by recalculating the sector checksums, and comparing them with the stored sector checksums. However this recalculation of sector checksums during each sector write procedure does consume processing power. 
         [0089]    Therefore in a first set of alternative embodiments, the step of recalculating the sector checksum(s) is omitted, and the reference global checksum is recalculated based on the modified checksums (that is, the checksum that has been modified by adding 1). Thus the sector checksums are first calculated in step  31 , then simply become counters which are incremented during each subsequent write procedure. 
         [0090]    A method of maintaining software integrity without requiring the calculation of sector checksums at any time is shown in  FIG. 8 . Steps  30 , 34 , 35 , 38 , 39  and  40  correspond with the equivalent steps in  FIG. 2 . However in the case of  FIG. 8 , instead of maintaining a sector checksum for each sector, the processor  20  maintains a sector counter for each sector. In step  80  the sector counters are all initialised. They can be initialised to any value. In step  81  the CPU  10  calculates a reference global checksum based on the sector counters and the secret key. During an authorised write procedure, write protection is disabled in step  82  and 1 is added to the sector counter of each sector to be modified. In step  83  the reference global checksum is recalculated based on the sector counters (including the new sector counter(s)) and the secret key. The method of  FIG. 8  is particularly simple since no sector checksums need to be calculated at any point. However the sector counter can still act as an indicator that a modification has been made to the software (although in contrast with the sector checksum, there is no mapping between the content of the software and the indicator). 
         [0091]      FIG. 8  corresponds in general with  FIG. 2 . In alternative embodiments of the invention, methods corresponding to  FIGS. 3-6  (using sector counters instead of sector checksums) may also be provided. 
         [0092]    Instead of incrementing the sector counter whenever a sector is modified, the sector counter may be modified in some other way, for instance by decrementing, or by counting the number of words that have ever been written to that sector. 
         [0093]    The size of the sector counter is chosen to be sufficiently large (for instance 32 bits or larger) to remove the ability of an unauthorised party to reset it to the original value by continually enabling and disabling write protect. 
         [0094]      FIG. 9  shows a boot procedure using the sector counters maintained by the method of  FIG. 8 . Steps  70 , and  73 - 76  correspond with the equivalent steps in  FIG. 7 . The difference is that step  91  retrieves the sector counters (instead of sector checksums) and step  92  calculates the expected global checksum based on the retrieved sector counters (instead of retrieved sector checksums). 
         [0095]    The boot procedures described above in  FIGS. 7 and 9  can securely verify the integrity of a large volume of software without requiring a large amount of computation or power. This is because the expected global checksums are calculated (in steps  72  and  92 ) by performing a mapping algorithm on the sector checksums (in the case of  FIG. 7 ) or the sector counters (in the case of  FIG. 9 ), which is computationally easier than performing the mapping algorithm on the software stored in the memory sectors  12 . In other words, the integrity of the software is verified without calculating an expected value from the software. The device&#39;s boot time is therefore greatly decreased. This is achieved by ensuring that the flash storage device carries out some of this load before the boot procedure is executed. 
         [0096]    All the embodiments described above are specified in terms of the use of a flash chip but they can be applied to any form of non-volatile data storage. 
         [0097]    Although the invention has been described above with reference to one or more preferred embodiments, it will be appreciated that various changes or modifications may be made without departing from the scope of the invention as defined in the appended claims.