Abstract:
A microprocessor including random cache line refill ordering to lessen side channel leakage in a cache line and thus thwart cryptanalysis attacks such as timing attacks, power analysis attacks, and probe attacks. A random sequence generator is used to randomize the order in which memory locations are read when filling a cache line.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application is a continuation of U.S. application Ser. No. 10/141,926, filed May 10, 2002, which claims the benefit of U.S. Provisional Application No. 60/294,605, filed Jun. 1, 2001, each of which is hereby incorporated by reference in its entirety. 
     
    
     TECHNICAL FIELD 
       [0002]    This invention relates to a technique for increasing processor security, and more particularly to a technique for using random word order on cache line refill to reduce the possibility of an attacker being able to reveal code or data in a system. 
       BACKGROUND 
       [0003]    Traditional cryptanalysis has focused predominantly on exploiting underlying algorithms and/or protocols used to encrypt data. Even though an encryption scheme may be theoretically secure, it still may be possible to decrypt data using information obtained regarding the execution of a cryptographic algorithm. Information obtained from the operation of a cryptographic device, such as a computer or smart card, that may be used to identify and/or deduce secret information is called side-channel leakage. 
         [0004]    Many different techniques have been developed to obtain and exploit side-channel leakage including timing attacks, power attacks, and fault generation; however, side-channel information may also be obtained through more direct means. For example, probe attacks may be used to read secret information on the bus of a processor by attaching conductors to circuits of the processor. When a cryptographic algorithm is using a secret key to perform an operation, that secret key (e.g., a personal identification number (PIN)) may be loaded into a data cache. An attacker could use probes to either passively or actively determine the secret key as the data is loaded into the cache. Using knowledge about the underlying cryptographic algorithm, a probe attack may be used to identify secret information by identifying instructions and/or data loaded into a cache. 
         [0005]    A smart card may contain confidential information (e.g., social security number, credit card numbers, account numbers, date of birth) and may even contain stored value that resembles cash. The data stored on the smart card can be protected by a PIN using standard cryptographic methods. An attacker, using knowledge of the underlying cryptographic algorithms, may be able to exploit that knowledge and view the confidential information by watching data cross the bus as the data is loaded from memory into the cache. Additionally, data obtained using a probe attack may be combined with timing and power analysis data to effectively defeat the security of the smart card. 
         [0006]    By exploiting side-channel leakage, an attacker may be able to compromise the security of cryptographic devices even though the underlying algorithms and protocols used by these devices are theoretically secure. 
       SUMMARY 
       [0007]    In one general aspect, a microprocessor supporting random cache line refill ordering is provided. The microprocessor includes multiple memory addresses and at least one cache controlled by a cache controller and having multiple cache lines for storing the contents of memory addresses. Random cache line refill order logic is provided to translate a burst read request made by the cache controller into a randomly-ordered sequence of read requests based on one or more random values that are generated by a random number generator. 
         [0008]    In some implementations, the random cache line refill order logic is controlled by a random cache line refill order signal such that random cache line refill order logic is enabled when the random cache line refill order signal is asserted. 
         [0009]    Implementations of random cache line refill ordering may be provided for data caches, instruction caches, and any combination thereof. Random cache line refill ordering may be used with any cache structure including a direct-mapped cache and a four-way set-associative cache. 
         [0010]    In some implementations, random cache line refill order logic includes a random sequence generator such that the random cache line refill order logic is operable to translate a burst read request made by the cache controller into a randomly ordered sequence of read requests using the random sequence generator. The random sequence generator may randomize a sequence of n elements by successively choosing one of the n random elements and, if the element has previously been chosen, then instead choosing the first unchosen element in the sequence. Some microprocessors may include a bus interface unit to provide an interface to the memory. 
         [0011]    The details of one or more implementations are set forth in the accompanying drawings and the description below. Other features and advantages will be apparent from the description and drawings, and from the claims. 
     
    
     
       DESCRIPTION OF DRAWINGS 
         [0012]      FIG. 1  is a timing diagram of an exemplary five-stage pipeline that may be used in a RISC architecture. 
           [0013]      FIG. 2  is a block diagram of a processor core including an instruction cache and a data cache. 
           [0014]      FIG. 3  is a diagram of an exemplary direct-mapped cache that may be used as an instruction cache or a data cache. 
           [0015]      FIG. 4  is a function used to randomly determine a sequence of memory reads in response to a burst read request. 
           [0016]      FIG. 5  is a block diagram of a random cache line refill order system that can be used to randomize a burst read request. 
           [0017]      FIG. 6  is a flowchart of a process for translating a burst read request into a random sequence of separate read requests. 
           [0018]      FIG. 7  is a diagram of a simplified random cache line refill order in a direct-mapped cache with four words per cache line. 
       
    
    
     DETAILED DESCRIPTION 
       [0019]    If the order in which data and instructions are loaded into a cache is entirely deterministic, then an attacker may be able to extract secret information by reading instructions and/or data as they are loaded into a cache. For example, a direct-mapped cache may store four words per cache line. When a cache miss occurs, the system determines which cache line to refill and then loads new words into that cache line. Randomizing the load sequence of a cache line refill increases the security of a processor by making it more difficult for an attacker to obtain secret information by reading data and/or instructions as they are loaded into a cache. 
         [0020]    Referring to  FIG. 1 , an exemplary microprocessor architecture that may implement random cache line refill order includes a five-stage pipeline in which each instruction is executed in a fixed amount of time, such as, for example, five clock cycles. The execution of each instruction is divided into five stages: instruction fetch (I) stage  1001 , execution (E) stage  1002 , memory fetch (M) stage  1003 , align/accumulate (A) stage  1004 , and writeback (W) stage  1005 . In the I stage  1001 , a specified instruction is fetched from an instruction cache. A portion of the fetched instruction may be used to specify source registers that may be used in executing the instruction. In the E stage  1002 , the system fetches the contents of the specified source registers. These fetched values may be used to perform arithmetic or logical operations. The processor also uses the E stage to begin performing multiply/divide operations and arithmetic logic unit (ALU) operations. 
         [0021]    In the M stage  1003 , ALU operations complete and an executing instruction may cause memory to be read from a data cache. In the A stage  1004 , loaded data is aligned with word boundaries and multiplier accumulations and carry propagations are performed. Finally, in the W stage  1005 , values obtained by the execution of the instruction may be written back to a register. 
         [0022]    In the I stage  1001 , the processor attempts to fetch an instruction from an instruction cache (I-cache). If a cache miss occurs, the system loads the instruction from memory and stores it in the I-cache. Likewise, in the M stage  1003 , the system attempts to fetch data from a data cache (D-cache). If a cache miss occurs, the system loads the data from memory and stores it in the D-cache. 
         [0023]    Referring to  FIG. 2 , a processor core  2000  includes execution core  2010 , memory management unit  2020 , translation lookaside buffer  2030 , cache controller  2040 , instruction cache  2050 , data cache  2060 , and bus interface unit  2070 . Execution unit  2010  implements a load-store architecture with single-cycle arithmetic logic unit (ALU) operations. The core includes thirty two 32-bit general-purpose registers used for scalar integer operations and address calculation. The register file, which may include two read ports and one write port, may be fully bypassed to minimize operation latency in the pipeline. When execution core  2010  needs to fetch an instruction or access data that is not stored in a register, the execution core  2010  makes a request using memory management unit  2020 . 
         [0024]    Memory management unit  2020  uses translation lookaside buffer  2030  to provide an interface between execution core  2010  and cache controller  2040 . Translation lookaside buffer  2030  acts as a cache for translations of virtual memory addresses to physical memory addresses. Using the translation lookaside buffer  2030 , the memory management unit  2020  handles address translations, faults, virtual paging, and/or various other functions. When the memory management unit  2020  receives a request to read an instruction or data, it makes a request to cache controller  2040 . 
         [0025]    Cache controller  2040  provides an interface to instruction cache  2050  and data cache  2060 . Each of these caches may be implemented using any cache technology. For example, each may be implemented as a 16 Kbyte cache that is virtually indexed and physically tagged, allowing virtual-to-physical address translation to occur in parallel with the cache access rather than having to wait for physical address translation. The tag holds, for example, 22 bits of the physical address, a valid bit, and a lock bit. In some implementations, the caches support cache locking on a per-line basis. 
         [0026]    Bus interface unit  2070  controls the external interface signals. Additionally, the bus interface unit  2070  may include a write buffer, such as a 32-byte collapsing write buffer, to hold and combine write transactions before issuing them to the external interface. If the data caches follow a write-through cache policy, a write buffer may significantly reduce the number of write transactions on the external interface, and may reduce the amount of stalling in the core due to issuance of multiple writes in a short period of time. 
         [0027]    Thus, for example, the execution core  2010  may fetch an instruction by sending a request to memory management unit  2020  which performs virtual to physical address translations. The memory management unit  2020  then sends a request to cache controller  2040 . The cache controller  2040  looks up the instruction&#39;s address using instruction cache  2050 . If the instruction is available in cache  2050 , then it is returned to the execution core  2010 . Otherwise, a cache miss occurs and a request sends through bus interface unit  2070  to refill a cache line to load the instruction into instruction cache  2050 . To exploit temporal and spatial locality of instruction execution, it is often beneficial to load multiple instructions at one time. Thus, the bus interface unit  2070  is sent a burst read request to retrieve multiple instructions, which then are loaded into the cache. If an attacker is able to probe the system&#39;s bus, the data loaded into the cache and the order in which the data is loaded may yield significant information about the operations being executed. 
         [0028]    In a typical direct-mapped cache, the cache line is refilled in linear wrapping order. The word causing the cache miss is the critical word. In linear wrapping order, the critical word is first loaded, and then each consecutive word in the cache line is loaded, wrapping to the beginning until the entire cache line has been filled. For example, in a four-word cache line including words  0 - 3 , if word  1  is the critical word, then the cache is refilled in linear wrapping order as follows: word  1 , word  2 , word  3 , word  0 . 
         [0029]    Referring to  FIG. 3 , a direct-mapped cache  3000  may be used as instruction cache  2050  or data cache  2060 . The cache  3000  provides the ability to look up a central processing unit (CPU) address  3010  which, for purposes of the cache, is logically divided into a tag, an index, and an offset. The index is used to identify a particular line  3020  within the cache  3000  where the information may be stored. A cache line  3020  includes various flags that are used to manage the cache line (i.e., whether the data in the cache location remains valid), a tag, and data. In this example, four words are stored in each cache line and the offset is used to select the appropriate word within the cache line. Comparator  3030  is used to determine if the data is located within the cache  3000 . 
         [0030]    If the tag of CPU address  3010  and the tag of the appropriate cache line  3020  match and the cache line  3020  valid bits indicate that the data is still valid, then a cache hit occurs and the appropriate data is selected by multiplexer  3040  using the offset of CPU address  3010 . If the tags do not match, or if the data is no longer valid, then a cache miss occurs and the appropriate cache line  3020  is refilled, reloading each word in the relevant cache line  3020 . 
         [0031]    The level of security in the system may be increased by randomizing the order in which cache line  3020  is refilled. In the example discussed above with respect to  FIG. 3 , a burst read request issued to refill the cache line results in four reads. It is desirable to randomize the sequence in which these reads are performed. It should be understood that the architecture discussed above is given for purposes of example only. Those of skill in the art will appreciate that random cacheline refilling may be implemented in any computer architecture incorporating a cache. 
         [0032]    A sequence generator may be used to create sequences of any length based on a stream of numbers from a random number generator. For example, a random sequence of length four may be generated using a stream of 2-bit numbers from a pseudo random number generator. In this example, the sequence must contain each number ( 0 - 3 ) exactly once. 
         [0033]    A random sequence generator may be implemented using the function shown in  FIG. 4 , where 
         [0034]    rand n =“Random number”, n=[0,3]; 
         [0035]    sel n =f(rand n , mask n ), n=[0,3]; 
         [0036]    mask 0 =0000; 
         [0037]    mask n+1 =mask n |sel n , n=[0,2]; 
         [0038]    and rand n  and sel n  are 4-bit one-hot encoded values in the range 0-3, sel n  is the n&#39;th value in the sequence, and mask n  indicates which numbers have been in the sequence before the n&#39;th value. 
         [0039]    The function ƒ(rand n , mask n ) shown in  FIG. 4  is used to compute successive values of sel n  based on the previous numbers (mask n ) and a random value (rand n ). An example of how the algorithm works is given in Table 1. 
         [0000]    
       
         
               
               
               
               
               
             
           
               
                   
                 TABLE 1 
               
               
                   
                   
               
               
                   
                 n 
                 rand 
                 mask 
                 sel 
               
               
                   
                   
               
             
             
               
                   
                 0 
                 1000 
                 0000 
                 1000 
               
               
                   
                 1 
                 0010 
                 1000 
                 0010 
               
               
                   
                 2 
                 0010 
                 1010 
                 0100 
               
               
                   
                 3 
                 1000 
                 1110 
                 0001 
               
               
                   
                   
               
             
          
         
       
     
         [0040]    In this example, we begin with random number “1000” and a mask of “0000”. The function ƒ(rand n , mask n ) shown in  FIG. 4  returns “1000”, identifying the first selection in the sequence. The mask is set to the logical OR of the previous mask and the selection (i.e., “1000”) and the process continues. The next random number is “0010”. Function ƒ(rand 1 , mask 1 ) identifies the next selection in the sequence, “0010” and the mask is updated accordingly to “1010”. In the next step, the random number is again “0010”. Because the third selection has already been made, it can not be made again. Function ƒ(rand 2 , mask 2 ) returns “0100” and the mask is updated to “1110”. Finally, the remaining selection of “0001” is made based on the random number “1000”. 
         [0041]    Referring to  FIG. 5 , random cache line refill ordering is implemented when the cache controller  2040  issues a burst read request to the bus interface unit  2070 . When random cache line refill order is enabled, the bus interface unit translates a burst read into four single memory reads in a pseudo-random sequence. Referring to  FIG. 5 , random cache line refill order (RCLRO) logic  5010  may be used to implement the random sequence generation described above. When a RCLRO signal  5020  is asserted and a burst read request is made by cache controller  2040  to refill instruction cache  2050  or data cache  2060 , the RCLRO logic  5010  uses random number generator  5030  to translate the burst request into individual randomly-ordered read requests that are sent to bus interface  2070 . Then, bus interface  2070  reads the requested addresses from memory  5040  so that they can be loaded into the appropriate cache ( 2050  or  2060 ). 
         [0042]    Referring to  FIG. 6 , random cache line refill order may be performed by first receiving a burst read request (step  6000 ) from a cache controller  2040 . If random cache line refill ordering is enabled (step  6010 ), the system translates the burst read request into separate read requests in random sequence (step  6020 ). If random cache line refill ordering is not enabled, then the burst read requests are sent to the bus interface unit  2070 . The bus interface unit  2070  then reads the requested memory locations and returns the data to the cache controller  2040  to refill the cache. 
         [0043]    Referring to  FIG. 7 , cache  7000  is a simplified example of random cache line refill ordering in a direct-mapped cache. In this example, the cache includes only two lines and holds four words per cache line. This cache is far too simple to be used in most applications; however, the principles described with reference to this example are applicable to any size cache in any configuration. 
         [0044]    The cache shown in  FIG. 7  is a direct-mapped cache with each cache line holding four words of data. A portion of each CPU word address is designated as an offset to select one of the four words within a cache line. In this example, the two low-order bits are chosen as the offset. Additionally, a portion of each CPU word address is designated as an index to identify the cache line where the address would be stored in the cache. In this example, the third low-order bit is used as the index. 
         [0045]    CPU word address  7010  is “011001011”. The low-order bits “ 11 ” are used as the offset to specify which word within the appropriate cache line may contain the address. The third low-order bit “ 0 ” is the index. Thus, the offset of “11” specifies that word  3  would contain the address and the index “0” indicates that the addresses would be contained in the first line of the cache. Because the tag stored at this location, “011001” matches and the entry is marked valid, a cache hit occurs and the data “1001” is returned. 
         [0046]    CPU word address  7020  includes an offset of “01” and an index of “1”. This identifies word  1 , line  1  of the cache having a tag “100100”. Because the tag does not match the tag of CPU word address  7020 , “101100”, a cache miss occurs. In response to a cache miss, a burst read request is made to read memory addresses “101100100”, “101100101”, “101100110”, and “101100111” from memory. If random cache line refill order is selected, the request is translated into a random sequence of read requests. Data is then loaded in the generated random sequence order and stored in the cache line being refilled. For example, the random sequence may be as follows: word  2 , word  1 , word  3 , word  0 . If random cache line refill order is not selected, then the cache may be loaded in linear wrapping order beginning with the critical word as follows: word  1 , word  2 , word  3 , word  0 . 
         [0047]    The techniques described above may be used with any cache structure. A processor&#39;s security may be improved by enabling random cache line refill order; however, the added security may come at a cost if the processor takes longer to refill a cache line in random word order. 
         [0048]    In addition to random cache line refill order implementations using hardware, (e.g., within a microprocessor or microcontroller) implementations also may be embodied in software disposed, for example, in a computer usable (e.g., readable) medium configured to store the software (i.e., a computer readable program code). The program code causes the enablement of the functions or fabrication, or both, of the systems and techniques disclosed herein. For example, this can be accomplished through the use of general programming languages (e.g., C, C++), hardware description languages (HDL) including Verilog HDL, VHDL, AHDL (Altera HDL) and so on, or other available programming and/or circuit (i.e., schematic) capture tools. The program code can be disposed in any known computer usable medium including semiconductor, magnetic disk, optical disk (e.g., CD-ROM, DVD-ROM) and as a computer data signal embodied in a computer usable (e.g., readable) transmission medium (e.g., carrier wave or any other medium including digital, optical, or analog-based medium). As such, the code can be transmitted over communication networks including the Internet and intranets. 
         [0049]    It is understood that the functions accomplished and/or structure provided by the systems and techniques described above can be represented in a core (e.g., a microprocessor core) that is embodied in program code and may be transformed to hardware as part of the production of integrated circuits. Also, the systems and techniques may be embodied as a combination of hardware and software. Accordingly, other implementations are within the scope of the following claim.