How to design a practical and secure MAC scheme? 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 ;) )

UBI Properties

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.

Encryption concerns

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) &lt; - > 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.
There are many ways to authenticate the contents of the disk.  The way you have described is reasonable, if you have a way to store the global sequence number in an authentic way (so it cannot be tampered with).

Another general approach is to look at the data structure that is maintained by the UBI to map from logical block numbers LEV($v,l$) to physical block numbers PEB($p$).  Then, add a MAC on all entries of that data structure, and when you read the data structure, verify the MAC.

Also it might help to use tweakable encryption to encrypt each block, with the tweak set based upon the block numbers.

Broader comment: I think you should start by reading about full disk encryption (FDE) in general.  I don't see anything here that is terribly different from the issues facing FDE on magnetic hard disks.  Here are some good starting references:


Disk encryption theory, particularly its discussion of tweakable encryption.
IEEE P1619/D16 - Standard for Cryptographic Protection of Data on
Block-Oriented Storage Devices
And, these three research papers on disk encryption
Do Flash memory (SSD) architecture impacts encryption techniques?


Do note that many full disk encryption schemes provide only confidentiality, not authenticity, so you'll need to go beyond what those schemes offer.

P.S. One last comment: you are forming the input to your MAC by concatenation.  This is fine if all of the fields are fixed-length values, but if they are variable-length, you may be at risk of a concatenation attack.