Re: MACs + Encryption + same Key

From: David Wagner (daw_at_taverner.cs.berkeley.edu)
Date: 10/17/04 

Date: Sun, 17 Oct 2004 06:42:24 +0000 (UTC)

Eris Pluvia wrote:
>I apologize, but English is not my mother language.

Ahh! My apologies.

I wish I was one-tenth as conversant in any second
language as you are in English.

>Thanks for your didactic explanation. So, if I understood:
>K_MAC=SHA1-HMAC(K,"MAC")
>K_encrypt =SHA1-HMAC(K,"encrypt")
>means that, in practice, "K_MAC" and "K_encrypt" are statistically
>independent (provided some conditions on SHA1, etc..)

Right. Well, to be technical, we often use the term computationally
indistinguishable (as opposed to statistically) to warn that the independence
only holds for attackers who are computationally limited (e.g., cannot
perform more than 2^80 work). But that's a very minor detail.

>But I suppose that it should be easy to extend the result of the theorem (or
>to build similar one) in order to prove the following: Given:
> K_MAC=SHA1-HMAC(K, M)
> C_i = AES(K, IV + i)
>(M = message, IV = random) then K_MAC and C_i are statistically independent.

Well, I don't know how. That doesn't guarantee it can't be done, but
I don't know of anyone who has done it.

More precisely, I don't know how to do it without very strange and
artificial-looking assumptions on AES or SHA1-HMAC. Basically, one needs
a condition that AES and SHA1-HMAC do not have any "funny interactions"
between them. That condition sounds quite plausible. However, I'm not
sure how to formalize the condition, and I don't know how to find any
reasonable-looking cryptographic assumption that implies the condition.

Frankly, the "no funny interactions" assumption sounds pretty plausible.
Taking an engineering point of view, if I had to make this assumption to
get work done, I'd happily make it. However, in this case, we don't need
this unusual assumption. My general philosophy is to minimize the number
of unproven assumptions needed to prove a scheme secure. The fewer unproven
assumptions you rely on, the less the chance that one of them turns out to
be false. In this case, we can eliminate the unproven (and somewhat
hand-wavy) assumption with a fairly simple modification to the protocol,
so I tend to consider that change worthwhile.

I don't want to leave the impression that re-using the same key for both
AES and SHA1-HMAC is a major sin. I don't mean to suggest that it will
certainly render your application insecure. It is secondary, certainly.
However, key separation is part of best practice, and re-using the same
key represents a step down from good practice.

>(I changed MD5-HMAC to SHA1-HMAC, I don't know if this fact is the kernel
>of our disagree)

Ok, that's fine. That's not core of my point. The change is fine.

Relevant Pages