SHA-based encryption function in Python

[Paul Rubin]

Richard Parker <richard at electrophobia.com> writes:
> > Do the keys really need to be independent?
> 
> As I recall, it was essential to the HMAC proof of security that the keys be
> independent.  I don't know if is possible to prove HMAC secure with
> dependent keys, but it would almost certainly require stronger assumptions
> about the underlying hash function.

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.

> > How is H(K || (H || 'a' || K || X))?
> 
> I am concerned about it.  You're basically using HMAC with a weaker
> pseudorandom key derivation.  If you absolutely can not use the xor of ipad
> and opad, make sure you use a key derivation for both K1 and K2.  Perhaps
> the following:
> 
>   H(c1 || K || H(c2 || K || x))

OK, I can try that.  I'm resisting HMAC because in the perverse economics
of interpreted languages, calling the library SHA function can be faster
than xor'ing two 64-character strings in the interpreter (I'll have to
run actual timings though).  

> I strongly recommend you just use HMAC, rather than inventing your own MAC
> construction.

I'll experiment with some ways of coding HMAC to run fast in Python.
The implementation that comes with the 2.2 library is pretty slow.

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.

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?

Thanks as usual.  I've pushed new code up to my web site:

  http://www.nightsong.com/phr/crypto/p2.py