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