SHA-based encryption function in Python

[Richard Parker]

Paul Rubin at phr-n2002a at nightsong.com wrote on 4/24/02 8:05 PM:

> But HMAC's keys are already dependent (they're the same key xor'd with
> two different constants), so I'm not sure how concatenating something is
> really worse.  I'm back to wanting to re-read the HMAC paper, which I'll
> try to do sometime.

It is possible I am remembering the proof incorrectly, but as I recall the
security of HMAC was proved by first proving secure a construction with
independent keys and then showing that HMAC was secure with the additional
assumption that the compression function of the hash function is sufficient
to make the two derived keys indistinguishable from random.

> Currently I'm using
> 
> K1 = H('auth1' + K)
> K2 = H('auth2' + K)
> MAC = H(K1 + H(K2 + ciphertext))
> 
> which I hope is at least as good as HMAC (the keys are more
> independent) and it uses fewer interpreter operations (though more SHA
> calls).  It's speed isn't too bad, but I always like to look for
> improvements.

I like that idea.  I do, however, recommend that as a precaution you choose
values for the two constants that differ by more than one bit.  While more
expensive than HMAC in the theoretical sense, this HMAC variant looks secure
and I'm not surprised to hear that it is actually faster in Python.  I can't
see any attack that wouldn't also imply the ability to crack the hash
function, which is the same level of security offered by HMAC.  If you are
using the MAC more than once with same key you could improve performance by
only computing the values of K1 and K2 once (this optimization would also
apply to HMAC).

> Note that there's a trivial O(2**64) attack on my authentication since
> I'm truncating the MAC to 8 bytes.  So if a security difference
> between HMAC and what I'm doing needs more than O(2**64) work to
> exploit, it's not really useful to an attacker.  Is that a reasonable
> way to think of this?

Yes, it is certainly acceptable to perform that kind of analysis.  On the
other hand, I personally try hard to avoid cryptographic designs that
introduce dependencies that make it difficult to change parameters or
primitives without reanalyzing the entire design.

-Richard