Re-flash protection for flash memory

A method for storing data includes providing a memory package including an integrated circuit containing a non-volatile memory and counter circuitry. The data is written to the non-volatile memory. The counter circuitry is operated to maintain a count of write operations performed on the non-volatile memory. The data and the count from the memory package are received at a controller, separate from the memory package, and the data is authenticated in response to the count.

FIELD OF THE INVENTION

The present invention relates generally to data storage, and particularly to protection of the data stored.

BACKGROUND OF THE INVENTION

An increasingly important object of data storage is protecting the integrity of the stored data. For example, a play-counter of a digital rights management system may be used to count, and limit, the number of times a song is played. Circumventing the counter may allow unlimited playing of the song, so that protection of the counter against corruption is essential

While apparatus and methods for protection of stored data are known in the art, an improved system for the protection would be advantageous.

SUMMARY OF THE INVENTION

Various embodiments of the present invention may include an apparatus and a method for storing data in a safeguarded manner. In some embodiments the apparatus and the method typically comprise a controller package and a separate memory package, herein also referred to as a controller and a memory. The two packages may be connected by a communication bus and are typically mounted on a printed circuit board. In one embodiment the controller package may comprise a secret key and an authentication engine. In some embodiments the memory package may comprise an integrated circuit having a non-volatile memory (NVM), which is typically flash memory. The integrated circuit may also comprise write-cycle counter circuitry, which is typically implemented as a finite state machine.

In a disclosed embodiment the circuitry may provide a count of the number of write operations made to each block of the NVM, and the values of the counts may be stored in the NVM. To write data to a block of the NVM, the controller package typically initially requests a current write-cycle count of the block from the NVM. The controller may operate the authentication engine to calculate an authentication signature for the block, using the secret key and the data concatenated with an incremented write-cycle count. The controller may then send the authentication signature and the data to the NVM, wherein they are written. The write-cycle counter circuitry typically increments the write-cycle count, and the incremented value replaces the prior count stored in the NVM.

In a further disclosed embodiment, to read the data from the block, the controller may retrieve the current write-cycle count from the memory package. The controller may also retrieve the authentication signature and the data stored in the block. The controller's authentication engine calculates an assumed block signature for the block using the secret key, the data, and the write-cycle count. The controller may compare the assumed and retrieved signatures, and, if they are identical, the read data may be assumed to be correct. If the two signatures are not identical, the read data may be considered to be suspect.

By using the count of write operations to authenticate the read data, the controller is able to detect in a simple manner if unauthorized write operations have been performed on the NVM. By incorporating the counter circuitry in the memory package, there is no need to modify existing controllers, nor to use controller memory, which is typically limited and expensive, to maintain the write-cycle counts.

In an alternative embodiment of the present invention, data transferred between the controller and the memory may be encrypted during the transfer. In a further alternative embodiment, the safeguarded data is stored in an encrypted form.

In a yet further alternative embodiment, the controller may comprise a random number generator. The generator is used to provide a random number to the memory, which uses the random number to transfer the write-cycle count to the controller in a secure form. The secure form may be decoded by the controller, and typically protects the write-cycle count from being read by entities other than the controller.

There is therefore provided, according to an embodiment of the present invention, apparatus for storing data, including:

a memory package including an integrated circuit, which circuit contains a non-volatile memory to which the data is written and counter circuitry which is configured to maintain a count of write operations performed on the non-volatile memory; and

a controller, separate from the memory package, which is configured to receive the data and the count from the memory package, and to authenticate the data in response to the count.

Typically the controller is configured to receive a prior count of prior write operations from the memory package, to provide to the memory package a signature for the data in response to the prior count and the data, and to authenticate the data in response to the signature. Providing the signature to the memory package may include storing a copy of the signature in the memory package, and authenticating the data in response to the signature may include verifying that the copy and the signature are identical.

In one embodiment the controller is configured to provide a random number to the memory package, and the memory package is configured to transfer a function of the count, generated in response to the random number, to the controller. The memory package may be configured to generate a signature of the function and to transfer the signature with the function to the controller. The controller may be configured to authenticate the count in response to the signature and the function.

In a disclosed embodiment the counter circuitry is configured to store a value of the count in the non-volatile memory, the counter circuitry typically includes a finite state machine, and the non-volatile memory typically includes a flash memory.

In some embodiments the controller includes a secret key, and the controller is configured to generate a signature of the data in response to the secret key, and to authenticate the data in response to the signature.

In an alternative embodiment the controller is configured to perform encryption on the data so as to generate encrypted data, writing the data to the non-volatile memory includes storing the data in the non-volatile memory as the encrypted data, and receiving the data includes receiving the encrypted data and performing decryption on the encrypted data. The encryption and decryption may be symmetric. Alternatively, the encryption and decryption may be asymmetric.

In a further alternative embodiment the controller is configured to generate a signature of the data, and the memory package is configured as blocks of memory, and is configured to store the data and the signature in one block of the non-volatile memory.

Alternatively, the controller is configured to generate a signature of the data, and the memory package is configured as blocks of memory, and is configured to store the data and the signature in different blocks of the non-volatile memory.

At least one of the data and the count may be transferred between the controller and the memory package in a secure, typically encrypted, form.

There is further provided, according to an embodiment of the present invention, a method for storing data, including:

providing a memory package including an integrated circuit containing a non-volatile memory and counter circuitry;

writing the data to the non-volatile memory;

operating the counter circuitry to maintain a count of write operations performed on the non-volatile memory;

receiving at a controller, separate from the memory package, the data and the count from the memory package; and

authenticating the data in response to the count.

The present invention will be more fully understood from the following detailed description of the embodiments thereof, taken together with the drawings, a brief description of which follows.

DETAILED DESCRIPTION OF EMBODIMENTS

Overview

A data storage system, typically formed on a printed circuit board (PCB), comprises two separate components: a controller package and a memory package. The two components are coupled by a communication bus.

The memory package comprises an integrated circuit containing a non-volatile memory (NVM), which is herein by way of example assumed to comprise a flash memory. However, embodiments of the present invention may use any convenient non-volatile memory. Data which is to be safeguarded is stored in blocks of the NVM. The integrated circuit also contains counter circuitry, typically a finite state machine, which maintains a count of the number of write operations performed on each block of the NVM.

In order to write data to the NVM, the controller package generates a signature for the data that is a function of the data, and of the count of write operations performed on the block where the data is to be stored. (The count has been previously written to the NVM.) The signature and the data are written to the NVM, and the stored value of the count is incremented.

To read data from the NVM, the stored data, the signature of the data, and the current count value are transferred to the controller package. The controller package calculates an assumed signature from the received data and the received count. The assumed signature is compared with the received signature, and if the two signatures are identical, the received data is assumed to be trustworthy.

Typically, data is stored in an encrypted form, and may be transferred between the controller and memory packages in the encrypted form. In some embodiments, the count is also transferred in a secure form.

System Description

Reference is now made toFIG. 1, which is a schematic block diagram of data storage apparatus20, according to an embodiment of the present invention. Apparatus20comprises a memory package22, also herein termed a memory, and a controller package24, also herein termed a controller. The two packages are typically mounted on a printed circuit board (PCB)21and are coupled by a communication bus36comprised in the PCB.

Controller24is typically formed as an integrated circuit (IC)25. The controller comprises a central processing unit (CPU)30which, as described below, performs functions to read data from and write data to memory22, and which controls the operation of apparatus20. Controller24comprises a general purpose random access memory (RAM)32which, inter alia, is used to store instructions accessed by the CPU, as a data buffer, and to store a secret key33.

Controller24also comprises an authentication engine26, which operates an algorithm to generate a message authentication code (MAC). The MAC is used as a signature for data that is transferred with the MAC, and acts to authenticate and safeguard the validity of the transferred data. For data X, the algorithm generates a signature S, and the relation between S and X is written herein as S=MAC(X). The authentication engine may be implemented in hardware (H/W), software (S/W) wherein code is stored in RAM32, or a mixture of hardware and software, and may be configured to be operated by, or independently of, the CPU. The algorithm may be any MAC algorithm known in the art, such as a one-key MAC (OMAC) algorithm, or a keyed-hash MAC (HMAC) algorithm.

Controller24optionally includes a cipher block28, which, as for the authentication engine, may be implemented in H/W, S/W, or a mixture of the two. Hereinbelow, unless otherwise stated, apparatus20is assumed to include and operate cipher block28. Cipher block28is used to encrypt and decrypt data transferred between controller24and memory22. The optional property of cipher block28, and of uses of the block, are indicated in the diagrams of the present application using broken perimeters around blocks referring to encryption and decryption.

Controller24includes an interface34, which acts as a buffer and is used to transfer data between RAM32and bus36.

Memory22comprises an IC23. IC23in turn comprises non-volatile memory (NVM)44, which may be any convenient type of non-volatile memory. Hereinbelow, by way of example, NVM44is assumed to comprise flash memory. Typically data written to the NVM is in different forms, including data47that is to be safeguarded and that is assumed to be written into blocks49of the NVM. Other data written to NVM44includes signatures45of the safeguarded data, and counts43of the number of times each block of the NVM having safeguarded data is written to. There is a respective signature45for each block of safeguarded data. There is also a respective count43for each block of NVM44to which safeguarded data is written. Typically, at the manufacturing stage of apparatus20, the counts for all blocks are set to zero. For clarity, in the present application a suffix may be added to the identifiers of blocks49, data47, signatures45and counts43to identify specific blocks, data, signatures, and counts. Thus, a block49A may be assumed to have data47A, having a signature45A, written to the block, and the number of write operations performed on block49A is count43A.

IC23includes an interface38, which is generally similar in function and implementation to interface34.

IC23also comprises write-cycle counter circuitry40, which is typically implemented as a finite state machine. Circuitry40counts the number of times each block of NVM44is written to, and the counts are stored as block counts43in NVM44. When a particular block is written to, the circuitry performs the count for the block by retrieving the value of the count for the block from counts43, incrementing the value of the count, and replacing the value of the count with the incremented value in counts43. Typically circuitry40is implemented in a physical location of IC23that is separate from the memory elements of NVM44, and the elements of the counter circuitry are typically formed from elements that are different from those of the memory elements.

FIG. 2is a schematic timing diagram60of steps performed by controller24and memory22, according to an embodiment of the present invention. Diagram60shows the steps performed when the controller writes data, herein also written as DATA, to a given block49A of NVM44.

In a first set62of steps the controller transmits to memory22a request for the write cycle count, WNum, of given block49A. The value WNum for the given block is received from counts43, and is transferred to controller24, via interfaces38and36, and bus36, for temporary storage in RAM32.

In a second set64of steps CPU30increments WNum. The incrementation may be by any convenient value, or function, that is used by the CPU and circuitry40. Herein the incrementation is assumed, by way of example, to be 1, so that WNum increments to (WNum+1). The CPU concatenates DATA with (WNum+1), forming concatenated data ((WNum+1)∥DATA). Engine26calculates a signature H1=MAC((WNum+1)∥DATA) for the concatenated data, by operating the engine's algorithm using secret key33. In addition, CPU30encrypts DATA to form enc(DATA), using cipher block28.

In a final set66of steps the controller transmits signature H1and enc(DATA) to memory22. A copy of signature H1is written as a signature45A into signatures45, and encrypted data enc(DATA) is written as data47A into block49A of the NVM. In addition, circuitry40increments count WNum to (WNum+1), and the incremented count for the given block is stored as a count43A in counts43.

FIG. 3is a schematic timing diagram80of steps performed by controller24and memory22, according to an embodiment of the present invention. Diagram60shows the steps performed when the controller reads data from a block of NVM44. The data to be read is assumed to have been stored as encrypted data enc(DATA) in block49A, as described above with reference toFIG. 2.

In a first set82of steps, substantially the same as set62, a current value of WNum, i.e., count43A, for block49A is transferred to RAM32in controller24.

In a second set84of steps the signature H1for block49A is retrieved from signature45A in signatures45. The encrypted data enc(DATA) stored in the block is also retrieved. Signature H1and encrypted data enc(DATA) transfer to controller24for temporary storage in RAM32.

In a final set86of steps CPU30decrypts the encrypted data, using cipher block28, to generate DATA. The CPU concatenates DATA with the value WNum, forming concatenated data ((WNum)∥DATA). Engine26uses the concatenated data and key33to calculate an assumed signature H2=MAC((WNum)∥DATA) for the concatenated data. CPU30then verifies that H1and H2are identical by comparing H1(temporarily stored in RAM32) with the calculated value H2. If the two values are identically equal, the CPU assumes that DATA is correct, and can be trusted. If H1and H2are not identically equal, the CPU assumes that DATA is not correct, and that a fault exists.

The following scenario assumes that apparatus20is used as an e-cash balance card, and describes a typical case where a fault may exist. A hacker reads enc(DATA) from memory22and stores the value for future use. The hacker uses the card, depleting the cash balance of the card, which is written to memory22as enc(DATA)′. The hacker then uses the stored value of enc(DATA) to overwrite enc(DATA)′ with enc(DATA), intending to be able to use the card with its original cash balance. The action of writing causes circuitry40to increment the value of WNum, as described above in final set66of steps (FIG. 2). However, the value of H1corresponds to the non-incremented value of WNum, so that when CPU30calculates H2in final set86of steps (FIG. 3), it finds that H2and H1are not identical. Thus, circuitry40acts to safeguard the integrity of enc(DATA)′. enc(DATA)′ in this case corresponds to the correct value of the balance in the e-cash card.

FIG. 4is a schematic block diagram of data storage apparatus100, according to an embodiment of the present invention. Apart from the differences described below, the operation of apparatus100is generally similar to that of apparatus20(FIGS. 1,2, and3), and elements indicated by the same reference numerals in apparatus20and apparatus100are generally similar in construction and in operation.

In apparatus100controller24includes a random number generator102. At the manufacturing stage of apparatus100, a secret key104, which is identical in value to secret key33, is written to NVM44of IC23. Alternatively, secret key104may be transferred into NVM44on initialization of apparatus100. In apparatus100IC23also comprises an authentication engine106, which may be implemented generally as engine26, and which performs generally similar functions. Engines26and106perform generally the same function of generating a signature, but it will be understood that the methods of implementation of engine26in apparatus20, and of engines26and106in apparatus100, may be completely different. As is described below, incorporation of generator102, key104, and engine106into apparatus100eliminates the possibility that a hacker may determine the correct value of WNum.

FIG. 5is a schematic timing diagram120of steps performed by controller24and memory22, according to an embodiment of the present invention. Diagram120shows the steps performed when the controller writes DATA, in an encrypted form, to a block49B, also identified as BNum, of NVM44.

In a first set122of steps, CPU30uses random number generator102to generate a random number C1. The CPU temporarily stores C1in RAM32. CPU sends C1, and a request for the write cycle count43B, also written herein as WNum, of block BNum to memory22.

In memory22the value of WNum is retrieved from counts43, and the memory forms a function M1of parameters C1, BNum, and WNum. Hereinbelow, by way of example, M1is assumed to comprise a concatenation of C1, BNum, and WNum, i.e., M1=(C1∥BNum∥WNum). However, M1may comprise any other convenient function of C1, BNum, and WNum which is separable into its constituent parameters. Authentication engine106generates a signature S1for M1, using secret key104and the algorithm incorporated in the engine: S1=MAC(M1).

The values of S1and M1are then transferred to controller24. In one embodiment M1is encrypted before transference, and decrypted by the controller.

In a step124CPU30uses engine26to calculate a signature S2for the received value of M1, using secret key33, i.e., engine26determines S2=MAC(M1). The CPU also recovers values C1′, BNum′, and WNum from M1, and checks if S2==S1, C1′==C1, and BNum′==BNum. If the three identities are valid, CPU30assumes that the value WNum is correct. If any of the identities are not valid, the CPU assumes that there is an error and does not proceed with the write process.

A set of steps126is generally similar to set64of steps described with reference toFIG. 2, so that set126concludes by CPU30transferring the signature H1of block BNum, and the encrypted data enc(DATA), to memory22.

In a final set of steps128, generally similar to set66described above, a copy of signature H1is written as signature45B into signatures45and enc(DATA) is written into block49B (BNum) as data47B. In addition, in counts43, WNum for block BNum is incremented to (WNum+1) and the incremented value is stored as count43B.

Comparison of timing diagram60with timing diagram120shows that, unlike in the former timing diagram, in the latter timing diagram there is no transfer of WNum, in a readable form, between controller24and memory22.

FIG. 6is a schematic timing diagram140of steps performed by controller24and memory22, according to an embodiment of the present invention. Diagram140shows the steps performed when the controller reads enc(DATA) from a block of NVM44. The data to be read is assumed to have been stored in block49B, BNum, as described above with reference toFIG. 5.

A first set of steps142is substantially similar to set of steps122, beginning with the generation of a random number C1, and concluding with the transfer of M1and S1from memory

A step144is generally similar to step124, so that three identities S2==S1, C1′==C1, and BNum′==BNum are checked for validity. As for step124, if the three identities are all valid, the read process proceeds. If any of the identities are not valid, CPU30assumes there is an error and does not continue with the read process.

A set of steps146is generally similar to set of steps84(FIG. 3). Thus, the signature H1of block49B is retrieved from signature45B in signatures45, and the encrypted data enc(DATA) stored in the block is also retrieved. The encrypted data and the signature transfer to controller24.

A final set of steps148is generally similar to set of steps86. Thus, after decrypting enc(DATA) to form DATA, CPU30concatenates DATA with WNum. Engine26calculates an assumed signature H2, MAC((WNum)∥DATA), and compares H2with H1. If H2is identical with H1, the CPU assumes that DATA is correct, and can be trusted. If H1and H2are not identically equal, the CPU assumes that DATA is not correct, and that a fault exists.

Consideration of timing diagrams120and140shows that circuitry40, by incorporating a count of write operations performed on memory22, acts to safeguard the integrity of data stored in the memory. In addition, since the value of the count is not transferred in a readable form between the memory and controller24, the count value is only available to the memory and the controller, and the integrity of the stored data can not be compromised.

The description above provides one example of how signatures are generated using a secret key. It will be understood that other forms of signature generation, and/or of encryption of data, may be used. Such other forms include, but are not limited to, simple encryption and asymmetric data encryption. The signatures formed may be stored in NVM44together with, or separately from, their respective data. Thus, a signature and its data may be stored in the same block of NVM44, or alternatively in different blocks of the NVM. Typically, for backward compatibility with existing controller packages, it may be advantageous to store the signatures separately.

Secure transfer of data including the value of the write cycle count, between controller24and memory22, may be effected by forms other than those described above. For example, in apparatus100, rather than transferring M1with a signature S1from the memory to the controller (FIGS. 5 and 6), M1may be encrypted at the memory, then transferred to and decrypted by the controller, without forming or transferring S1.