4
$\begingroup$

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) < - > 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.

Improve this question
$\endgroup$
1
  • $\begingroup$ This might get better responses on security.stackexchange.com (since it is not about how to invent a new crypto primitive, but rather how to use existing tools in a particular domain). You can click the "flag" button to ask that it be moved there. $\endgroup$
    – D.W.
    Commented Mar 27, 2013 at 20:45

1 Answer 1

Reset to default
2
$\begingroup$

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:

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ The fields involved in my HMAC scheme are fixed length, I even mentioned their respective length ;). I have read somewhere that the same key should not be used to produce several different tags. Should I use key derivation techniques instead of keeping on using the raw K ? $\endgroup$
    – Rerito
    Commented Mar 28, 2013 at 8:29
  • $\begingroup$ If the only thing you use the key $K$ for is for MACing the combination $v | l | seqnum | p$, you're good: you don't need to worry about doing anything more. If you also use the same key $K$ to MAC other things (in a different format), then you have to worry about it (you don't want a MAC on a record with different semantics to be replayable as a $v | l | seqnum | p$ record ... if you follow my drift). $\endgroup$
    – D.W.
    Commented Mar 28, 2013 at 8:51
  • $\begingroup$ The scheme I described only authenticates a $PEB(p) \leftrightarrow LEB(v,l)$ mapping, not the actual content of the block. I might add also add tags to authenticate the data written in the block. Could you explain more precisely the flaw induced by the use of $K$ for both tags ? $\endgroup$
    – Rerito
    Commented Mar 28, 2013 at 9:09
  • 2
    $\begingroup$ Say you use HMAC$_K(v|l|s|p)$ for a $PEB \leftrightarrow LEB$ mapping, and HMAC$_K(x)$ for some other purpose (say, authenticating the hash of the volume name). Note that both $v|l|s|p$ and $x$ are exactly 160 bits long. Therefore, given an $x$ that is the hash of a volume name, the attacker can parse $x$ as $x=(v|l|s|p)$, and then the attacker knows a valid MAC on a $PEB(p) \leftrightarrow LEB(v,l)$ mapping that doesn't actually exist -- a security violation. For a slightly different perspective on this, see this answer. $\endgroup$
    – D.W.
    Commented Mar 28, 2013 at 9:22
  • 1
    $\begingroup$ Every day I get more impressed by what crypto people can think of ... That's brilliant. The paper about cold boot attacks you linked is also very impressive ! I suggest you edit your answer to append that last comment since it is a witty advice. $\endgroup$
    – Rerito
    Commented Mar 28, 2013 at 9:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.