# Alternatives to HMAC + CBC?

I'm looking at using HMAC + CBC. The combination looks like this:

ciphertext = AES256(text, k1)
data = HMAC-SHA256(iv | ciphertext, k2) | iv | ciphertext


Where:

k1 = 32 byte key - Randomly generated, once
k2 = 32 byte key - Randomly generated, once
iv = 16 bytes - Randomly generated, for every message


The purpose is for storing sensitive information in a database.

Is the above approach cryptographically secure for sensitive information? Would there be any reason to consider a stream-cipher mode verses a block-cipher mode like CBC?

Would an AEAD mode like OCB or CCM be more appropriate?

If an AEAD mode is not available for the platform we are using (specifically Go), is it worth the effort trying to implement these modes?

-
I imagine things would be easier if you moved the HMAC to the end. $\:$ – Ricky Demer May 18 '13 at 2:48

Yes, this is fine, at the record level. (What you've built would be classified as a "Encrypt-then-Authenticate" scheme in the literature, and there are standard provable security results for such schemes.) Well done on constructing a solid, well-engineered cryptographic scheme.

An AEAD mode would spare you from having to invent such a scheme, but what you've got is fine, and there's no reason why you need to change.

There's no reason to switch to a stream-cipher mode of operation.

As others have mentioned in the comments, this would be more secure if you included an identifier in the input to HMAC that identifies the table, row, and column where this appears, so that a ciphertext cannot be replayed from one position to another. There will still be the risk of rollback attacks, as fgrieu explains; that is more challenging to defend against, so if you need to stop them, you might want to elaborate on the specific application situation.

-
One issue I can see is how this database is structured. For instance, if he is encrypting a single field, then an attacker could forge data by copying the value of one field to another. So, I think (if this is the case) there should be a row-unique identifier included in the authenticated data, probably the auto_inc column for the table. Also, the scheme is vulnerable to "replay" attacks, is it not...? – Reid May 18 '13 at 2:51
Indeed, the scheme is solid at the record level. I second @Reid's comment: each record's integrity is protected, but the database's integrity is not. Adding an identifier of the record's location in the HMAC helps, by preventing moving records, but it still allows rolling back each record of the database to an earlier state. Even if we link the update of records in some way, the database as a whole can still be rolled back. – fgrieu May 18 '13 at 5:16
Is there some reference material I can look at about these replay issues? The database is not accessed directly. If the attacker has direct access to the database, wouldn't he also have access to the ids? Also is there any benefit from separating the signature out into a separate column, or is it better to keep it mixed in with the ciphertext? – Luke May 18 '13 at 5:34
Also, in the database context: while the confidentiality of each record is protected, the location of updated records is not. And the atomicity of the updates of multiple related records (e.g. update of accounts in a manner preserving the overall balance) is not protected. – fgrieu May 18 '13 at 5:36
It doesn't matter whether you separate out the signature into a separate column or not. – D.W. May 18 '13 at 5:45