5
$\begingroup$

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

E_K1(Plaintext)||E_K2(Ciphertext)

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

Improve this question
$\endgroup$
17
  • $\begingroup$ SHA1(MasterKey) has a different length from AES keys. $\;$ $\endgroup$
    – user991
    May 15, 2015 at 10:20
  • $\begingroup$ Of course, I meant, to truncate it to the first 128 bits (at least that what was implied, I'll fix it). $\endgroup$
    – Anon2000
    May 15, 2015 at 10:26
  • $\begingroup$ If you have any accelerated hashing functions, I'd check to see if using one of those with the HMAC construction is faster than using AES as a MAC. Note that you can pre-compute both the inner and outer padded hashes in the HMAC and copy those (e.g. the hash context) rather than re-process the HMAC key each time (I'm assuming you can restore a state even with hardware accelerated hashing). $\endgroup$
    – Steve Peltz
    May 15, 2015 at 18:47
  • $\begingroup$ If you are validating tens of thousands of these per second, are you certain your assumption holds that sub-millisecond resolution is good enough to guarantee uniqueness? $\endgroup$
    – Stephen Touset
    May 15, 2015 at 19:48
  • 2
    $\begingroup$ It sounds to me that CBC-MAC is a perfect fit for you. No need for special constructs. CMAC is safe for variable length messages but it is more complex; it should not be needed for these messages. $\endgroup$
    – Maarten Bodewes ♦
    May 16, 2015 at 0:54

1 Answer 1

Reset to default
3
$\begingroup$

Your scheme is secure under the assumption that AES is a pseudo-random permutation (PRP): In fact, message authentication codes (MACs) are theoretically modelled as pseudo-random functions (PRFs), and any PRP is also a PRF. Therefore, your usage of single-block AES essentially is a MAC.

In the case that only a very small subset of the possible blocks is "valid" (for instance, when you check that a timestamp is no older than a few minutes or so), you may even drop the second encrypted block: If the probability that an attacker guesses the ciphertext corresponding to a valid block is already negligible, an additional MAC is not needed. Note that this depends strongly on your specific use case and is not a general security recommendation.

Improve this answer
$\endgroup$
9
  • $\begingroup$ I considered using only a single block, but eventually decided against it. Most of the entropy would actually derive from the permission ID (about 44 bits for a million possible valid values). Timestamps, however, could be set to the future, or the allowed range could be very long. I had an exact calculation (that takes FP accuracy in consideration), based on a 100 year time range yielded about 7.158 bits of entropy. $\endgroup$
    – Anon2000
    May 15, 2015 at 10:50
  • $\begingroup$ I'm also realizing this may only work with a block cipher. As in a stream cipher it would be possible to make very slight modifications to one of the blocks (for example, tamper with an existing token to modify its content in some way). And relatively easy to guess matches on the second blocks. As for multi-block approach like CBC I haven't really considered it (I'm not by any means a cryptographer!) $\endgroup$
    – Anon2000
    May 15, 2015 at 10:58
  • $\begingroup$ Yes, this would absolutely not work with a stream cipher, as flipping the same bit in both halves would result in the same plaintext output. $\endgroup$
    – Stephen Touset
    May 15, 2015 at 19:48
  • $\begingroup$ Any ideas about using this with CBC? could this work for [two copies] of several chained blocks? I haven't really spent much time considering that.. (I'm not sure though whether in this case it would actually have as many practical benefits though..). $\endgroup$
    – Anon2000
    May 15, 2015 at 20:53
  • $\begingroup$ You could use this with a streaming cipher as the first encryption only. If you're going to encrypt multiple blocks, the case for using a MAC instead of encrypting the blocks a second time is much stronger from a speed standpoint. $\endgroup$
    – Steve Peltz
    May 15, 2015 at 23:11

Your Answer

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

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