# Is it worth applying a MAC on data in a HSM?

I'm building a basic HSM out of an Arduino, and am using the following scheme to store data:

• Master symmetric key $k_m$ stored in firmware (secure bit set to prevent trivial extraction).
• Secondary symmetric keys $k_s$ stored as plaintext in web application database, one per user.
• HSM record key $k_r$ generated by xor'ing the two keys together computing $AES(k_s, k_m)$, using AES-128-ECB. This means that both the HSM and application server would have to be compromised in order to reveal the key.
• AES-128-CBC used to encrypt the data, using a unique pseudo-random IV and the record key.
• Each record on the HSM consists of a plaintext record ID, the IV, and a data block.

Is it worth applying a HMAC-SHA1 hash over this data to provide integrity and authenticity checking? If so, what should I use as key material?

-
For experimentation and learning, right? :) –  SteveS Apr 30 '13 at 23:50
Mainly. Ultimately I'll be using it in a site that isn't security critical - just a game. The HSM will be handling password reset questions and "select 3 letters from your secret word" type authentication, as additional defense against remote attackers. –  Polynomial May 1 '13 at 0:03
Will there really be only one "HSM record key"? $\:$ –  Ricky Demer May 1 '13 at 1:21
@RickyDemer Per record, yes. Does that sound odd to you? –  Polynomial May 1 '13 at 7:07
You wrote the expression for $k_r$ differently in your comment and your post; $k_m$ should be the block $\hspace{.4 in}$ cipher key. $\:$ It would take slightly more space and time, but you might use SIV mode instead, $\hspace{.5 in}$ where one of the headers is the record ID. $\:$ (www.cs.ucdavis.edu/~rogaway/papers/siv.pdf) $\;\;$ –  Ricky Demer May 1 '13 at 16:36

Designing an HSM or other secure device is relatively easy; making it reliable even in the absence of adversary requires careful engineering; making it safe against adversaries with some level of physical access is hard; demonstrating that it is safe (for some definition of that) is even harder.

One thing to worry about is integrity of stored data (including keys) w.r.t. to both accidental events and deliberate attacks. One should consider problems often neglected in other embedded developments:

• memory writes during power loss, which can leave a data block partially erased or written, in manners depending heavily on technology:
• for RAM, it is easy to observe a data block left partially written, with e.g. low addresses holding new data, high address still holding old data;
• sometime it can be observed that in between, a word is garbled apparently randomly;
• for EEPROM and Flash, the physical erasure before write (typically, with alignment to some page boundary) is often apparent;
• with EEPROM or Flash, it might be observable that some memory cells are left in an unstable state where the content read (until another erase or write) will vary randomly, or/and as a function of operating temperature (if you do not trust me on this one, ask the IC vendor to put in writing what it guarantees about what's read in memory that was being written or erased at time of power loss, with rationale at the physical level to support that);
• non-deterministic CPU operation, which itself can occurs when operating conditions (e.g. power supply) are non-nominal, and there is no adequate (e.g. voltage) sensors to block operation in these conditions;
• cosmic rays; incidence vary enormously with memory technology, capacity, altitude, solar activity, location on surface of earth, and (metaphorically) phase of the moon; search Single Event Upset RAM for references;
• deliberate fault attacks trying to cause or simulate some of the above.

Carefully designed and tested measures (software and/or hardware) to deal with at least power loss is a must. Some kind of integrity protection on top of that is a good idea. One option is to substitute AES-128-CBC with AES-GCM; another is to use a separate MAC, e.g. HMAC-SHA1 (if we neglect side-channel leakage issues, it is fine to do this on the plaintext, and probably fine to use $k_r$ as the HMAC-SHA1 key, though $\operatorname{AES}(\operatorname{key}=k'_m,\operatorname{data}=k_s)$ would be more academic and work with any MAC). If that's tolerable from a functional standpoint, moving the HSM to a zeroized state in case of error is the safest from a security standpoint (but zeroization itself requires care; something like "on error detected erase $k_s$", where that erasure is performed in two halves, potentially leaves open to an attack halving the effective key size).

-

I recommend you read a bit more about cryptographic design before getting into design of a HSM. Designing a HSM is basically designing a cryptographic protocol.

For instance, using AES-128-CBC is a bad idea, as it does not provide message authentication; instead, you should use authenticated encryption.

Similarly, rather than deriving a derived key in some funny way from two pieces, I would recommend that you compute it as the hash of the two pieces (unless you really want one piece to be reconstructable from the derived key plus another piece -- that doesn't seem desirable to me). If I understand correctly, someone who learns a record key $k_r$ and learns the secondary key $k_s$ can derive the master key. That doesn't sound like a desirable property from what I can see.

There are a bunch of good papers on analysis of HSMs from the University of Cambridge (Ross Anderson and collaborators). Those papers show many security flaws in deployed HSMs, because they were ignorant of design principles for strong cryptographic protocols. I recommmend you take a look at those papers and learn from others' mistakes.

-
That's only if the OP's ordering of the inputs to AES(.,.) is the same as I think me and you would use. –  Ricky Demer May 1 '13 at 22:03
@Ricky Demer: thanks for pointing an earlier inversion of $k_s$ and $k_m$ in my text. –  fgrieu May 1 '13 at 22:19
+1 for pointing the difficulty at defining the right protocol to be implemented by the HSM. Also: indeed, $k_r=\operatorname{Hash}(k_s||k_m)$, or $k_r=\operatorname{HMAC}(\operatorname{key}=k_m,\operatorname{message}=k_s)$ can help. –  fgrieu May 1 '13 at 22:22
I'd have gone for EAX mode or GCM immediately if possible, but I'm using a pre-written AES library that doesn't offer such modes, and I've already eaten up half of my program space with libraries without even implementing the storage or request processing code. Adding EAX or GCM would be tricky to get right, and there might not be space. I'll take your advice on the hash, though. –  Polynomial May 2 '13 at 7:41
@Rick Demer: $k_r=\operatorname{Hash}(k_s||k_m)$ is in D.W.'s answer. $k_r=\operatorname{HMAC}(\operatorname{key}=k_m,\operatorname{message}=k_s)$ is my attempt to slightly strengthen that under the assumption that pairs $(k_s,k_r)$ leak (as hypothesized by D.W.). I do not see how that is worse than $k_r=\operatorname{AES}(\operatorname{key}=k_m,\operatorname{data}=k_s)$, except if $\operatorname{HMAC}$ was more vulnerable than $\operatorname{AES}$ to side channel attacks. In the attack model, $k_r$ and $k_m$ are both equally secret, thus everything envisonned for $k_r$ (except XOR) is fine. –  fgrieu May 2 '13 at 20:11