I have a short message that’s exactly 128 bits of length. The message serves as a time-limited authorization token for a database. It contains a permission profile ID (64 bits) and an issue timestamp (64 bit double). The key is known only to the issuing server, but the content may actually be given to the user in plaintext (though having it hidden is preferred during transport, as an additional security measure), and in general not impossible to guess.
I intend to encrypt it using AES-128 (there is no need for IV/nonce as each timestamp is assured to be unique - by having a sub-millisecond resolution). I’m looking for a fast way to authenticate it, considering a single server would be expected to decrypt and verify up to tens of thousands of these tokens per second, with a marginal performance impact. I considered using an HMAC but looked for an alternative that’s faster and preferably relies solely on AES (AES-NI Instruction could significantly accelerate computations).
I came up with the simple idea of encrypting the plaintext twice with two different keys (either completely unrelated or derived from a master key using a salted hash or a KDF) and concatenating it to a 256 bit result, which looks like this:
E_K1(Plaintext) || E_K2(Plaintext)
As far as I can tell, this seems secure, and verification would be faster in practice than when using an HMAC - simply decrypt both and verify that both plaintexts match. Additionally, since maintaining two unrelated (or securely derived) keys would add some complexity, but would only introduce a single bit of strength, I’m also considering simply using
MasterKey and [the first 128 bits of]
SHA1(MasterKey) as the two keys.
Is this as secure as I think it is? Could this even be (marginally) more secure than using a HMAC? - since for every random guess of the first block there would exactly one corresponding second block that would decrypt to the same plaintext (i.e. no possibility of a collision since block ciphers have a one-to-one mapping between plaintexts and ciphertexts for a single block).
Note the above method works only with block ciphers and is equivalent to CBC-MAC with the special case of having only one block, so the resulting tag can be decrypted directly instead of decrypting the ciphertext and the re-encrypting the resulting plaintext with the authentication key.
Considering this further: it may actually be safe to authenticate the ciphertext itself so the second block could be an encryption of the first one. e.g.:
(not sure if a second key is needed in this case [though it seems to be a good safety measure], but some caution needs to be exercised since with some ciphers, it may be the case that
E(E(Plaintext)) = Plaintext)
Validation would be twice as fast, since only one encryption/decryption operation is needed to determine if the first block is authentic.
Although not based solely on AES (the original requirement), UMAC/VMAC, although relatively new techniques, may prove competitive or better in performance, but I'm relatively new to them so some studying is still needed. Using a GMAC (the authentication code used with GCM mode) is also an option, but I'm not sure it'll give better performance than UMAC/VMAC.
Conclusions (based on my own research and suggestions of the commenters):
MAC functions based on universal hashing (UMAC, VMAC, Poly1305) are very fast but require a nonce for every individual MAC, and GMAC requires an IV, thus these are probably not appropriate in this particular case, where having a short total length of transmitted payload is essential (it is not clear to me whether the nonce/IV can somehow be safely derived in this case, but that operation by itself would probably be quite expensive)
HMAC-SHA is currently a bit slow (as it performs two hash operations per call) but may be accelerated by sophisticated caching of its internal state - though this optimization may be difficult or time-consuming to implement in practice. A future hardware accelerated instruction set for SHA-1/SHA-256 is planned for release with the Skylake architecture, and may change the situation.
CBC-MAC (a more generalized algorithm than described by the original proposal) based on AES would be hardware accelerated and perform great, especially when it's applied to the ciphertext, so it seems like the best solution so far.