Abstract:
A method for monitoring memory integrity comprising, receiving a data read access request, updating a data read history register responsive to receiving a data read access request, the update comprising storing a first register value, wherein the first register value is defined by a previous register value and a first symmetric key encryption function, updating a data write history register in further response to receiving the data read access request, the update comprising storing a second register value, wherein the second register value is defined by a previous register value and a second symmetric key encryption function, receiving a data write access request, updating the data read history register responsive to receiving a data write access request, the update comprising storing the first register value, and updating the data write history register in further response to receiving the data write access request, the update comprising storing the second register value.

Description:
BACKGROUND OF THE INVENTION 
       [0001]    1. Field of the Invention 
         [0002]    This invention relates generally to computer storage media and, more specifically, to a method and system for checking the integrity of computer memory. 
         [0003]    2. Description of Background 
         [0004]    In existing methods, such as those described in U.S. Patent Application Number 20060161773, a processor updates a read/write history register (R/W) is after each read and write memory access (Eqs. 1, 2, and 3). When the processor updates the write history register (Eq. 2), a counter value storing the number of writes to a memory is encrypted and used as a new counter value (Eq. 3) in order to make a future counter value unpredictable for attackers. 
         [0000]        R   t   :=R   t-1   ⊕E   k ( d, c   r   , a ),   (1) 
         [0000]        W   t   :=W   t-1   ⊕E   k ( d, c   w   , a ),   (2) 
         [0000]      where  c   w   =c   r   +E   c ( c   r ).   (3) 
         [0005]    Wherein R t  and W t  are stored values in the R/W register for a transaction t, E k  is an encryption function using an encryption key k, d is data, c is a counter value, a is a data address, and E c  is an encryption function using c as an encryption key. 
         [0006]    The method requires an encryption circuit for encrypting the counter value and a large adder that handles multiple bits. Furthermore, the encryption processing occupies about half the latency of the entire integrity check. 
       SUMMARY OF THE INVENTION 
       [0007]    The shortcomings of the prior art are overcome and additional advantages are achieved through an exemplary method for monitoring memory integrity, the method comprising, receiving a data read access request, updating a data read history register responsive to receiving a data read access request, the update comprising storing a first register value, wherein the first register value is defined by a previous register value and a first function R t :=R t-1 ⊕E k (d, r, a), wherein t is a transaction number, d represents stored data, r is a random number, a is an address of the data, E k  is a symmetric key encryption function, and k is a key of the symmetric key encryption function, updating a data write history register in further response to receiving the data read access request, the update comprising storing a second register value, wherein the second register value is defined by a previous register value and a second function W t :=W t-1 ⊕E k (d, r, a), receiving a data write access request, updating the data read history register responsive to receiving a data write access request, the update comprising storing the first register value, and updating the data write history register in further response to receiving the data write access request, the update comprising storing the second register value. 
         [0008]    Additional features and advantages are realized through the techniques of the present invention. Other embodiments and aspects of the invention are described in detail herein and are considered a part of the claimed invention. For a better understanding of the invention with advantages and features, refer to the description and to the drawings. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0009]    The subject matter that is regarded as the invention is particularly pointed out and distinctly claimed in the claims at the conclusion of the specification. The foregoing and other aspects, features, and advantages of the invention are apparent from the following detailed description taken in conjunction with the accompanying drawings in which: 
           [0010]      FIG. 1  illustrates a block diagram of an example of a prior art memory controller. 
           [0011]      FIG. 2  illustrates a block diagram of an exemplary embodiment of a memory controller. 
           [0012]      FIG. 3  illustrates a flow chart of an exemplary method involving checking memory integrity. 
       
    
    
       [0013]    The detailed description explains the preferred embodiments of the invention, together with advantages and features, by way of example with reference to the drawings. 
       DETAILED DESCRIPTION OF THE INVENTION 
       [0014]    Systems and methods involving checking memory integrity are provided. Several exemplary embodiments are described. 
         [0015]    Memory integrity ensures that a set of read data is the last data written by a memory controller such as, for example, a processor. To ensure memory integrity, previous methods generate read access and write access in pairs and verify the transactions. For example, when a cache memory controller issues a read access request, an external memory controller makes a write access after the read access. When a write access request is issued, the external memory controller makes the write access after a read access. This may be expressed in the equation below, transactions t, that is, read data and write data d, their addresses a and the order c of the transactions on the reading channel are the same as those on the write channel. 
         [0000]      Σ a   t   w   {d   a   , a, c}=Σ   a   t   r   {d   a   , a, c}   
         [0016]    To achieve this, read/write history registers are provided on the write and read channels to store the history of transactions. Each of the registers is updated after each memory access. The update is made by using exclusive OR. However, the same history can be held for different transaction sequences if calculated as: 
         [0000]    
       
      
       R=⊕ 
       a 
       t{d 
       a 
       , a, c}, W=⊕ 
       a 
       t{d 
       a 
       , a, c} 
      
     
         [0017]    Therefore, transactions are scrambled using a hash function H before storing. 
         [0000]        R=⊕   a   H ( t{d   a   , a, c }),  W=⊕   a   H ( t{d   a   , a, c }) 
         [0018]    If only the simple hash function is used, malicious attackers can generate collisions. Therefore, a symmetric key cryptography function E k  is used. The key k is hidden within the processor and therefore is not observable by an attacker. 
         [0000]        R=⊕   a   E   k ( t{d   a   , a, c }),  W=⊕   a   E   k ( t{d   a   , a, c }) 
         [0019]    However, the encryption cannot prevent an attack that forces the processor to read even numbers of the same transaction, because of the property of exclusive OR. For example: 
         [0000]        E   k ( t   0 )⊕ E   k ( t   1 )= E   k ( t   0 )⊕ E   k ( t   1 )⊕ E   k ( t   2 )⊕ E   k ( t   2 ) 
         [0020]    Therefore, a global counter register g is provided that counts a number of memory accesses within the processor. A number of write accesses to each memory address is compared with the total count of the counter c (g=Σc). Thus, such attack can be detected. 
         [0021]    An attack that replaces transactions themselves cannot be prevented also because of the property of exclusive OR. For example 
         [0000]        E   k ( t   0 )⊕ E   k ( t   1 )= E   k ( t   1 )⊕ E   k ( t   0 )       that is,         
         [0000]        E   k ( t   0   {d   0   , a   0   , c   0 })⊕ E   k ( t   1   {d   1   , a   1   , c   1 })= E   k ( t   1   {d   1   , a   1   , c   1 })⊕ E   k ( t   0   {d   0   , a   0   , c   0 }) 
         [0023]    The replacement attack is still possible because a future counter value can be predicted if the order (counter) c of transactions t{d a , a, c} is incremented after every memory access. In order to prevent a future counter value from being predicted, a new counter c w  is generated by encrypting a read transaction t r  and a read counter c r . The global counter is also updated accordingly. 
         [0000]        c   w   =c   r   +E   c ( c   r ) 
         [0000]        g+=E   c ( c   r ) 
         [0024]    Updating the counter in this way makes it difficult to predict future counter values and therefore can prevent the replacement attack. A block diagram of an example of a memory controller using the above-described previous method is illustrated in  FIG. 1 . 
         [0025]      FIG. 2  illustrates a block diagram of an exemplary embodiment of a memory controller. The illustrated exemplary embodiment includes a secure processor  202  that includes a central processing unit (CPU)  204  communicatively linked to a cache memory  206 . A verification module  208  is communicatively linked to the cache memory  206  and an external memory  210 . The verification module  208  may be, for example, a processor that includes a read buffer  201 , a write buffer  203 , a first function box  205 , a second function box  207 , a random number generator (RNG)  209 , a read history register  211 , and a write history register  213 . 
         [0026]    In operation, the exemplary embodiment of the verification module  208  ensures memory integrity by ensuring that the read data is the last data written by the cache memory  206 . The verification module  208  generates read access and write access always in pairs, and verifies the transactions t that is, read data and write data d, their addresses a and the unpredictable random number r of the transactions on the reading channel are the same as those on the write channel. 
         [0000]      Σ a   t   w   {d, r, a}=Σ   a   t   r   {d, r, a}   
         [0027]    The verification module  208  includes the read/write history registers  211  and  213  that are provided on write and read channels to store the history of the transactions. Each of the registers  211  and  213  is updated after each memory access. The update is made by using exclusive OR. However, the same history can be held for different transaction sequences (R=W) if calculated as: 
         [0000]    
       
      
       R=⊕ 
       a 
       t{d, r, a}, W=⊕ 
       a 
       t{d, r, a} 
      
     
         [0028]    Therefore, transactions are scrambled using a hash function H before storing. 
         [0000]        R=⊕   a   H ( t{d, r, a }),  W=⊕   a   H ( t{d, r, a }) 
         [0029]    If only the simple hash function is used, malicious attackers can generate collisions. Therefore, a symmetric key cryptography function E k  is used. The key k is hidden within the processor and therefore is not observable by an attacker. 
         [0000]        R=⊕   a   E   k ( t{d, r, a }),  W=⊕   a   E   k ( t{d, r, a }) 
         [0030]    However, the encryption cannot prevent an attack that forces the processor to read even numbers of the same transaction, because of the property of exclusive OR. For example: 
         [0000]        E   k ( t   0 )⊕ E   k ( t   1 )= E   k ( t   0 )⊕ E   k ( t   1 )⊕ E   k ( t   2 )⊕ E   k ( t   2 ) 
         [0031]    Using the random number enables the verification module  208  to verify the integrity of the data without using a global counter register update that uses encryption for integrity or multiple multi-bit adder circuits. This is illustrated by the equations: 
         [0000]        R   t   :=R   t-1   ⊕E   k ( d, r, a ), 
         [0000]        W   t   :=W   t-1   ⊕E   k ( d, r, a ) 
         [0000]    where the RNG  209  generates r, and r is an unpredictable random number that varies at each memory access. The use of r allows the verification module  208  to not encrypt a counter and maintain memory integrity. 
         [0032]    As discussed above regarding the previous method, an attacker may attempt to perform a replacement attack when the attack repeats the same transaction an even number of times because of the property of exclusive OR. To perform a replacement attack, pairs (t 1 , r 1 ) and (t 2 , r 2 ) must be replaced as follows. A transaction in the following description represents data and its address (t:={d a , a}). 
         [0000]        W=E   k ( t   0   , r   0 )⊕ E   k ( t   1   , r   1 )⊕ E   k ( t   2   , r   2 )⊕ E   k ( t   3   , r   3 ) 
         [0000]        R=E   k ( t   0   , r   0 )⊕ E   k ( t   2   , r   2 )⊕ E   k ( t   1   , r   1 )⊕ E   k ( t   3   , r   3 ) 
         [0033]    When write access to t 1  is made, t 2  and r 2  must be read. However, even if t 2  is known, r 2  is an unpredictable random number that will be generated in the future and therefore cannot be replaced. Thus, the replacement attack fails. 
         [0034]    Using another method of attack, an attacker may attempt to force the processor to read even numbers of the same transaction 
         [0000]        W=E   k ( t   0   , r   0 )⊕ E   k ( t   1   , r   1 )⊕ E   k ( t   1   , r   1 )⊕ E   k ( t   3   , r   3 )= E   k ( t   0   , r   0 )⊕ E   k ( t   3   , r   3 ) 
         [0000]        W=E   k ( t   0   , r   0 )⊕ E   k ( t   m   , r   m )⊕ E   k ( t   m   , r   m )⊕ E   k ( t   3   , r   3 )= E   k ( t   0   , r   0 )⊕i E k ( t   3   , r   3 ) 
         [0000]      W═R 
         [0035]    However, since the random number r is changed at every memory access, r 1  cannot be written twice. Therefore 
         [0000]        W=E   k ( t   0   , r   0 )⊕ E   k ( t   1   , r   1 )⊕ E   k ( t   1   , r   2 )⊕ E   k ( t   3   , r   3 )= E   k ( t   0   , r   0 )⊕ E   k ( t   3   , r   3 ) 
         [0000]    showing that 
         [0000]      W≠R 
         [0000]    Therefore, the attack can be also detected. 
         [0036]      FIG. 3  illustrates a flow diagram of an exemplary method of checking memory integrity. In this regard, referring to block  301  if a data read access request, the data read history register is updated in block  303  by storing R t  where R t :=R t-1 ⊕E k (d, r, a). In block  305  the data write history register is updated by storing W t  where W t :=W t-1 ⊕E k (d, r, a). If a data write access request is received in block  307  the data read history register is updated in block  309  by storing R t  where R t :=R t-1 ⊕E k (d, r, a), and the data write history register is updated by storing W t  where W t :=W t-1 ⊕E k (d, r, a) in block  311 . 
         [0037]    The above-described embodiment reduces the circuit size and latency. The latency required for integrity check at every memory access can be reduced by about half because the processor does not encrypt the counter and encryption of only the read/write history registers is performed. 
         [0038]    While the preferred embodiment to the invention has been described, it will be understood that those skilled in the art, both now and in the future, may make various improvements and enhancements which fall within the scope of the claims which follow. These claims should be construed to maintain the proper protection for the invention first described.