I am sorry, but I need to introduce some concepts which are not directly related to cryptography to make myself clear, I hope I won't stun you with this ... (I'd rather explain it here than redirect the reader to an even more stunning external link ;) )
I am working on Flash memory devices. These devices are divided into blocks of a quite significant size (from a few kilobytes to a few megabytes). The blocks, called eraseblocks, have a major property : they wear out. Once data has been written to a specific location within an eraseblock, the whole block must be erased to overwrite this data.
This erasure operation can only be performed a finite number of times before the block becomes worn and unusable (this number varies between 103 and 105 on nowadays chips).
Multiple solutions handle this problem, by reserving some space at the beginning of each block to manage them. UBI (Unsorted Block Images) is one them and is the one I am currently using. UBI writes two header fields at the beginning of each block which contain some information about it and extra things that it needs to manage the blocks. Among these things, a few are worth to mention :
- A 32-bit long logical eraseblock number
- A 32-bit long volume ID
- A 64-bit long sequence number
UBI can divide the Flash memory in partition-like entities called volumes. Each volume has an ID (volume ID) and a size expressed in eraseblocks. The blocks of a volume are numbered from 0 to this size limit (this is the logical eraseblock number). UBI makes a difference between a logical block (LEB) and a physical block (PEB). The former is a block of a volume and the latter is the physical block on the memory device itself on which is written the logical one. For instance, the block numbered 0 of the volume numbered 0, i.e. LEB(0,0), can be stored in any PEB at a given time, say PEB(10). UBI moves these logical blocks to various physical ones for an efficient wear-out management. Since some bad things can happen, any time UBI has to map a specific LEB to a PEB (by writing the block headers in the targeted PEB) it updates a global sequence number which is integrated in one of the headers.
I want to perform on-the-fly encryption when reading or writing to the memory. I already have the pure encryption pattern. It involves AES-128 encryption on a UBI volume basis.
Now, I want to combine it with a MAC scheme in order to authenticate that the data on the flash was not forged. The thing is : how can I cook up a reliable scheme for this purpose ?
Here are my thoughts on this subject : using HMAC-SHA1 (eventually truncated for memory space constraints), I can produce a tag that authenticates a given PEB(p) < - > LEB(v, l) mapping, using the encryption key K for the volume v. The tag should be produced in this way
HMAC-SHA1(v | l | sqnum | p, K)
This pattern has some advantages :
- It is easy to compute to perform checking operations
- It prevents a malevolent user to corrupt the volume with any other method than the two following : erasing the physical block p or overwrite the physical block p (which involves erasure of the block), which can only be performed up to 105 times.
I came up with this design because I find it practical for the uses of UBI I am making, but I have no idea of the security flaws it might introduce or solve in the whole thing.
Actually, I have a few questions. First, is my design safe ? And in any case, what would you suggest ? I am aware that last one is quite an open question, but I think there might be existing patterns that could be customized to fit my use case.