2
$\begingroup$
  1. Begin hashing (Key||Message)
  2. Encrypt the hash state (or some part of it, such as the first 128 or 256 bits), with the key.
  3. Add the encrypted hash state to the hash and return the result.

This could be roughly described as Hash(Key||Message||Encrypt(Previous hash state))

There are several properties about this:

  1. It may be faster than an HMAC in practice, especially for shorter messages (modern hardware accelerated encryption is up to 5x-10x the speed of hashing).
  2. Encrypting the hash state in stage (2) is a psuedo-random permutation, rather than just a PRF and so may have stronger security guarantees (this is the job of the more math-oriented people [i.e. you guys/girls] to try to analyze though).
  3. A practical advantage of HMAC, though, is that it could work with arbitrary “secrets”, that are not necessarily psuedo-random, but this construction would only work if the “secret” is an actual key associated with some cipher (though the “secret” could be hashed of course, to yield a key) - this may not be a significant limitation in practice though, as in most cases it is used with an actual key.

(Also consider a “weaker” version where stage (1) only performs Hash(Message), [i.e. without the key])

[Non-expert alert: I’m not a cryptographer or even a computer-scientist, so I don’t have the knowledge or capacity for the type of percise mathemtical reasoning that’s needed to analyze this. I guess that’s why I’m asking it here..]

Improve this question
$\endgroup$
3
  • $\begingroup$ If you are concerned with speed of a MAC and have hardware-accelerated AES encryption, you definitely want to consider CBC-MAC with the length of the message at start, and right-padding of the message with zeroes; this is demonstrably secure (when using a key dedicated to MAC), and even standardized as ISO/IEC 9797-1:2011 Padding Method 3. As they put it: "The [first] block consists of the binary representation of the length (in bits) of the unpadded [message], left-padded with as few (possibly none) ‘0’ bits as necessary to obtain a [128-]bit block". $\endgroup$
    – fgrieu ♦
    May 18, 2015 at 11:17
  • $\begingroup$ (continued) if for some reason the length of the message is not known at the beginning of the MAC, there's the more elaborate CMAC; or OMAC2. Do not use straight CBC-MAC with a variable-length message. $\endgroup$
    – fgrieu ♦
    May 18, 2015 at 11:24
  • $\begingroup$ Sure, I'm already using CBC-MAC! (and I'm aware that prepending the length or encrypting the last block is also secure for variable length messages). I just asked this out of curiosity.. :) $\endgroup$
    – Anon2000
    May 18, 2015 at 12:31

1 Answer 1

Reset to default
1
$\begingroup$

Security

The level of security is likely to depend on the cryptographic primitives - the actual hash function and cipher - used. It is very likely that you can construct a function that is insecure, e.g. where the cipher is used for both the hash function an encryption. So you need to prove that the hash function and the encryption primitive are not influencing the security, even though they are using the same key. It is much easier to use a single PRF or PRP and prove that secure. Using one function also greatly simplifies implementations.

Implementation issues

An implementation issue is that intermediate hash states are often not defined or clear. SHA-1 and SHA-2 do have "logical" intermediate states after a block is hashed as the hash output is basically (part of the) final state. The final state for these hash functions does not significantly differ from the intermediate state. This is not obvious for other hash functions. This is for instance the case for Keccak - the winner of the SHA-3 contest - as well as most other SHA-3 candidates. Using an intermediate hash state should therefore be avoided.

Expected properties

I'll iterate over the expected properties in order:

It may be faster than an HMAC in practice, especially for shorter messages (modern hardware accelerated encryption is up to 5x-10x the speed of hashing).

Usually performance is less of an issue for shorter messages. I would argue that it is only faster for shorter messages; the effect on larger messages will be negligible. Even then, it would require the cipher implementation to be cached (and in the case of e.g. Java, optimized) in addition to the hash function.

Encrypting the hash state in stage (2) is a psuedo-random permutation, rather than just a PRF and so may have stronger security guarantees (this is the job of the more math-oriented people [i.e. you guys/girls] to try to analyze though).

A hash function especially within HMAC already provides very good security guarantees. It remains to be seen if using a PRP would have any advantages; I would expect it to be less secure.

A practical advantage of HMAC, though, is that it could work with arbitrary “secrets”, that are not necessarily psuedo-random, but this construction would only work if the “secret” is an actual key associated with some cipher (though the “secret” could be hashed of course, to yield a key) - this may not be a significant limitation in practice though, as in most cases it is used with an actual key.

One of the more annoying aspects of CBC based MAC's is the non-variable key size. This is for instance rather annoying when using the MAC as building block for a key derivation function (KDF). So this is - in my opinion - a significant limitation.

CPU hash acceleration

Note that there are also CPU level optimizations for hash functions. Well known ones live in the Intel SHA extensions, the VIA padlock security suite, the Sun Ultra-Sparks...

Improve this answer
$\endgroup$
9
  • $\begingroup$ This should be pretty readable for a non-expert. Don't hesitate to ask if it is not. $\endgroup$
    – Maarten Bodewes ♦
    May 18, 2015 at 12:25
  • $\begingroup$ Thank for your time! It seems like there's a rather large gap between "being able to use cryptographic constructs correctly" or "being able to implement cryptographic functions" to "being able to reason and prove properties about cryptographic constructs". I guess the first or second should be sufficient for myself. Since I once worked a [Javascript] SHA-1 implementation (mostly to improve performance of an existing one) I assumed the type of hash function used would have the intermediate state that's equal or be very close to the output at that point. $\endgroup$
    – Anon2000
    May 18, 2015 at 12:57
  • 1
    $\begingroup$ @Anon2000: in crypto perhaps more than elsewhere, the devil is in the details. If you look closely at a typical SHA-1 implementation, the state has the 160-bit chaining variable so far, the length so far (usually 64-bit, could be in bits or bytes), and the message-block-not-hashed-yet (usually up to 511-bit, which length may or may not be tracked separately). If you want a portable implementation enciphering or hashing that, you need to care of all these details, including endianness and order of the various fields. If you consider only the chaining variable, you must be careful about padding. $\endgroup$
    – fgrieu ♦
    May 18, 2015 at 13:21
  • $\begingroup$ I would expect the hash function 1. to be precisely positioned at the end of a block and 2. for it to process a final block for this to work. And it could probably made to work. But the above shows that there are probably too many snags for it to become a generic scheme. Note that for Keccak you would not need the encryption at all. You could also have a look at GCM mode / GMAC for accelerated authentication. $\endgroup$
    – Maarten Bodewes ♦
    May 18, 2015 at 13:25
  • $\begingroup$ @fgrieu I didn't actually implement SHA-1 from scratch, but worked carefully on existing (correct) implementation. But anyway, the nice thing about writing software (compared say, to writing papers) is that you can implement an algorithm without a 100%, complete understanding of it. And then test it to match an existing implementation. So in this case it's being aggressively tested against OpenSSL by bit-bit comparison of the output for random inputs of various lengths. $\endgroup$
    – Anon2000
    May 18, 2015 at 13:33

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.