WO2016071743A1

WO2016071743A1 - Integrity protection for data storage

Info

Publication number: WO2016071743A1
Application number: PCT/IB2014/065885
Authority: WO
Inventors: Michael Kenneth BOWLER
Original assignee: Elliptic Technologies Inc
Current assignee: Elliptic Technologies Inc
Priority date: 2014-11-07
Filing date: 2014-11-07
Publication date: 2016-05-12
Anticipated expiration: 2017-05-07
Also published as: CN107111730B; CN107111730A

Abstract

A system for protecting the integrity of a memory system maintains an age counter and an opportunity counter for each of multiple memory blocks; maintains an epoch counter for the memory system; writes data in a selected memory block; increases the local sequence number of the selected memory block; updates the opportunity counter for the selected memory block if the local sequence number of the selected memory block rolls over; computes a message authentication code (MAC) in the selected memory block based on a global sequence number and the local sequence number; updates the age counter and the opportunity counter for any non-selected memory blocks if the opportunity counter for the non-selected memory blocks does not match the LSB of the epoch counter for the non- selected memory blocks; and computes a new MAC for any memory block for which the updating is performed.

Description

INTEGRITY PROTECTION FOR DATA STORAGE

FIELD OF THE INVENTION

[0001] The present disclosure relates to integrity protection of data storage, memory caching and cryptography.

BRIEF SUMMARY

[0002] In accordance with one embodiment, a method is provided for protecting the integrity of a memory system divided in a plurality of memory blocks each of which has a local sequence number. The method maintains an age counter for each of the memory blocks; maintains an opportunity counter for each of the memory blocks; maintains an epoch counter for the memory system; writes data in a selected memory block; increases the local sequence number of the selected memory block; updates the opportunity counter for the selected memory block if the local sequence number of the selected memory block rolls over; computes a message authentication code (MAC) in the selected memory block based on a global sequence number and the local sequence number; updates the age counter and the opportunity counter for any non-selected memory blocks if the opportunity counter for the non-selected memory blocks does not match the LSB of the epoch counter for the non- selected memory blocks; and computes a new MAC for any memory block for which the updating is performed.

[0003] In one implementation, each of the MACs is updated opportunistically (1) after the corresponding age counter rolls over and (2) during the writing of data to the corresponding memory block.

[0004] The foregoing and additional aspects and embodiments of the present disclosure will be apparent to those of ordinary skill in the art in view of the detailed description of various embodiments and/or aspects, which is made with reference to the drawings, a brief description of which is provided next.

BRIEF DESCRIPTION OF THE DRAWINGS

[0005] The foregoing and other advantages of the disclosure will become apparent upon reading the following detailed description and upon reference to the drawings.

[0006] FIG. 1 is a diagram of a global sequence number. [0007] FIG. 2 is a flow chart of an example of the use of a local sequence number with an opportunity counter.

[0008] While the present disclosure is susceptible to various modifications and alternative forms, specific embodiments or implementations have been shown by way of example in the drawings and will be described in detail herein. It should be understood, however, that the disclosure is not intended to be limited to the particular forms disclosed. Rather, the disclosure is to cover all modifications, equivalents, and alternatives falling within the spirit and scope of an invention as defined by the appended claims.

DETAILED DESCRIPTION

[0009] Integrity protection of memory systems located on insecure devices is generally done by computing a cryptographic integrity protection value or Message Authentication Code (MAC) and storing it along with the data. Therefore an unauthorized third party cannot modify the information written in memory.

[0010] A MAC algorithm, sometimes called a keyed (cryptographic) hash function (however, a cryptographic hash function is only one of the possible ways to generate MACs), accepts as input a secret key and arbitrary-length data to be authenticated, and outputs a MAC (sometimes known as a tag). The MAC value protects the data integrity as well as its authenticity, by allowing verifiers (who also possess the secret key) to detect any changes to the data content.

[0011] When the memory is authentically updated, the MAC is recomputed. To prevent replays of previously authentic values, a unique value, such as a counter or a sequence number, is added to the authentication input.

[0012] A MAC is also used when data cache writes out cache-lines to external memory. In this case, to prevent an attacker from replaying previous segments of data, a sequence number is associated to each and every cache line in the memory. Therefore, an attacker cannot capture an image of the external memory and after the memory has been updated, replace the cache-lines within the memory with a previously captured version.

[0013] Generally, to avoid long delays when writing new data to memory, the memory is segmented into memory blocks, and a MAC is stored along with each memory block. A block can be one cache line or a larger memory space. Therefore, the authentication algorithm only needs to be performed over an individual, smaller memory block. However, a separate sequence number needs to be maintained for every memory block. The sequence number needs to be sufficiently large to prevent it from expiring (rolling over) too often. When a sequence number expires, the cryptographic integrity algorithm needs to be re-keyed, which results in re-computing the MAC for all data blocks. During the refresh process, the memory system is not accessible, leading to access delays. Large sequence numbers are therefore preferable, but with a large number of blocks, a substantial amount of sequence number data needs to be stored and maintained.

[0014] An existing solution is to maintain a small local sequence number per memory block and a global epoch counter. The epoch counter and the local sequence number are concatenated to form the sequence number applied to the integrity algorithm. However, any time the epoch counter is updated, each MAC needs to be updated. The memory system is not accessible during the refresh process.

[0015] There is a need to reduce the storage requirements to maintain the sequence numbers while minimizing refresh events and access delays. There is a need to update MAC opportunistically during normal data updates or in the background such that the memory is still accessible when the epoch counter is updated.

[0016] In one embodiment, referring to FIG. 1, a global sequence number 100 comprises a local sequence number 101 and a global epoch counter 102. The local sequence number 101 is subdivided into two fields: an opportunity counter 110 and an age counter 115. An instance of the local sequence number 101 is maintained for every external cache line or memory block. All local sequence numbers reset to zero on key initialization.

[0017] The global epoch counter 102 is a counter global to all blocks. The opportunity counter 110 allows the MAC to be updated opportunistically after the age counter 115 rolls over, during normal updates (writes) of the data block. It also allows the MAC to be refreshed to new epoch values off-line.

[0018] The width of the age, opportunity, and epoch counters can be tuned to tradeoff the frequency of epoch update, off-line integrity check refresh to new epoch values, and opportunistic epoch updates versus memory storage requirements for the counter values.

[0019] As an example, a 32-bit global sequence number can include a 4-bit age counter and a 2-bit opportunity counter.

[0020] The epoch counter 102 and the age counter are concatenated to form the full sequence number used in computing the integrity protection value. The Least Significant Bits (LSB) of the epoch counter are inferred by comparing the global epoch counter 102 to the local opportunity counter 110.

[0021] Every time a cache line is written to external memory, the opportunity counter 110 is compared to the LSB of the epoch counter 102. If they match, the age counter is incremented by 1. If the age counter wraps (carries into the opportunity counter), the epoch counter is incremented by 1. When the epoch counter increments, all local sequence numbers need to be checked, and every line that has an opportunity counter matching the LSB of the new epoch, needs to immediately have its MAC recomputed with the new sequence number.

[0022] The opportunity counter allows an offline update or refresh of the MAC when the epoch counter changes. A background process or thread may update the local sequence numbers so that the opportunity counters are in sync with the current epoch. This can occur when the cache is not busy, i.e., on a low priority process. Whenever a MAC refresh operation is performed, the age counter resets to zero, to minimize the need for epoch updates. When a line is to be written back into memory, and the opportunity counter does not match the current epoch, the opportunity counter is set to match prior to computing the MAC, and the age counter is reset to zero. The MAC corresponding to the line is therefore refreshed opportunistically.

[0023] The refresh process of an external cache line MAC value is performed by reading in the cache-line and validating the MAC. The new MAC is computed using the updated global sequence number.

[0024] As the epoch counter exceeds predetermined thresholds, interrupts are optionally generated to the processor at various thresholds to prompt a proactive rekey operation before the counter expires.

[0025] Optionally, a background process checks the opportunity counters and updates the MAC for any opportunity counter that is about to expire (for example the memory blocks that are 1 bit away from the LSB of the epoch. During the background process any memory block MAC can be updated based on a pre-determined policy. This maximizes the time a cache-line can be opportunistically updated before getting hit with a refresh, and still allows the refresh to run as a background process.

[0026] FIG. 2 shows an example flow chart of an embodiment when an authentication code is updated for a memory block i is initiated at step 201. If step 203 determines that the opportunity counter for block i is different from the LSB of the epoch counter at step 203, the local sequence number is from a different epoch, then step 205 sets the opportunity counter for block i to the LSB of the epoch counter and resets the age counter for block i to zero. Otherwise, the local sequence number is in the current epoch, and step 207 increments the age counter for block i is incremented. If the age does not roll (i.e., there is no carry) at step 209, the memory block i is updated with the new sequence number at step 211. If the age rolls (i.e. resets to zero) at step 209, the epoch counter needs to be updated at step 213, the opportunity counter for block i is set to the LSB of the epoch counter and the age is reset to 0. The memory block i is updated accordingly. All memory blocks j are checked at step 219 except for the one that was just updated at step 213 which is skipped by the If step 215. If the opportunity counter for block j is equal to the LSB of the epoch counter at step 219, then the opportunity counter has fallen behind by a number of epochs represented by the number of bits in the opportunity counter (in this example, four epochs, because the opportunity counter is 2 bits), and the MAC of memory block j needs to be refreshed at step 221. If the opportunity counter for block j is not equal to the LSB of the epoch counter at step 219, then no update is necessary for block j, and the next block is checked by incrementing the value of j at step 217.

[0027] The above embodiment can also be used for encrypted memory systems.

[0028] Although the algorithms described above including those with reference to the foregoing flow charts have been described separately, it should be understood that any two or more of the algorithms disclosed herein can be combined in any combination. Any of the methods, algorithms, implementations, or procedures described herein can include machine- readable instructions for execution by: (a) a processor, (b) a controller, and/or (c) any other suitable processing device. Any algorithm, software, or method disclosed herein can be embodied in software stored on a non-transitory tangible medium such as, for example, a flash memory, a CD-ROM, a floppy disk, a hard drive, a digital versatile disk (DVD), or other memory devices, but persons of ordinary skill in the art will readily appreciate that the entire algorithm and/or parts thereof could alternatively be executed by a device other than a controller and/or embodied in firmware or dedicated hardware in a well-known manner (e.g., it may be implemented by an application specific integrated circuit (ASIC), a programmable logic device (PLD), a field programmable logic device (FPLD), discrete logic, etc.). Also, some or all of the machine-readable instructions represented in any flowchart depicted herein can be implemented manually as opposed to automatically by a controller, processor, or similar computing device or machine. Further, although specific algorithms are described with reference to flowcharts depicted herein, persons of ordinary skill in the art will readily appreciate that many other methods of implementing the example machine readable instructions may alternatively be used. For example, the order of execution of the blocks may be changed, and/or some of the blocks described may be changed, eliminated, or combined.

[0029] It should be noted that the algorithms illustrated and discussed herein as having various modules which perform particular functions and interact with one another. It should be understood that these modules are merely segregated based on their function for the sake of description and represent computer hardware and/or executable software code which is stored on a computer-readable medium for execution on appropriate computing hardware. The various functions of the different modules and units can be combined or segregated as hardware and/or software stored on a non-transitory computer-readable medium as above as modules in any manner, and can be used separately or in combination.

[0030] While particular implementations and applications of the present disclosure have been illustrated and described, it is to be understood that the present disclosure is not limited to the precise construction and compositions disclosed herein and that various modifications, changes, and variations can be apparent from the foregoing descriptions without departing from the spirit and scope of an invention as defined in the appended claims.

Claims

WHAT IS CLAIMED IS:

1. A method of protecting the integrity of a memory system divided in a plurality of memory blocks each of which has a local sequence number, said method comprising: maintaining an age counter for each of said memory blocks;

maintaining an opportunity counter for each of said memory blocks;

maintaining an epoch counter for the memory system;

writing data in a selected memory block;

increasing said local sequence number of said selected memory block;

updating said opportunity counter for said selected memory block if said local sequence number of said selected memory block rolls over;

computing a message authentication code (MAC) in said selected memory blocks based on a global sequence number and said local sequence number;

updating said age counter and said opportunity counter for any non-selected memory blocks if the opportunity counter for said non-selected memory blocks does not match the LSB of the epoch counter for said non-selected memory blocks; and

computing a new MAC for any memory block for which said updating is performed.

2. The method of claim 1 in which each of said MACs is updated opportunistically (1) after the corresponding age counter rolls over and (2) during the writing of data to the corresponding memory block.

3. The method of claim 1 in which all local sequence numbers are reset to zero on key initialization.

4. The method of claim 1 which includes updating said epoch counter while said memory system remains accessible.

5. The method of claim 1 in which said local sequence number for a memory block includes the values of the opportunity counter and the age counter associated with that memory block.

6. The method of claim 1 in which said MACs are refreshed to new epoch values off-line.

7. The method of claim 1 in which the epoch counter and the age counter for a selected memory block are concatenated to form a sequence number.

8. The method of claim 1 which includes comparing the value of the opportunity counter with the least significant bits of the epoch counter, and incrementing the age counter if they are equal.

9. The method of claim 1 which includes updating or refreshing a MAC when the corresponding epoch counter changes.

10. The method of claim 1 which includes updating the local sequence number so that the corresponding opportunity counters are synchronized with the corresponding epoch counters.

11. The method of claim 1 which includes refreshing a MAC when the corresponding age counter resets to zero.