Prev: Diffie-Hellman key exchange
Next: I beam formula
From: Fabrice on 10 May 2010 20:48
Hi,

I have a message M, a hash function H(), and a block cipher with
encryption function E() and decryption function D()

I calculate S=E(K, H(M)) (encrypt the hash of message with a key K)

1) Can this construct of S be called a mac of the message ?
2) Is it a good one ?

I guess one could argue that this is basically CBC-MAC of the Hash of
the message. I've read that CBC-MAC is only good for fixed length
messages. In that case the actual message are Hashes of fixed length,
so I guess that one could say this construct is as good a CBC-MAC....
would that be fair ?

As far as why try this instead of something else. The main reason is
in the way the mac is verified.

Normal CBC-MAC, you do regenerate the actual MAC and compare to the
one sent with the message. This often mean that the proper MAC is in
memory and so could be eventually spied upon, turning your MAC
checking machine into a MAC generating machine.

With this construct, the verification is done by decrypting the MAC,
then compare the hash of the Message to the result of this decryption.
So the MAC is never regenerated, and can not be stolen from memory.

(One could try to steal the key, in both case. But in some situations
it is easier to hide a key that the result of encryption)

Does this construct already has a name ?

If not, I patent it! :)



From: Scott Fluhrer on 10 May 2010 22:40

"Fabrice" <fabrice.gautier(a)gmail.com> wrote in message
news:ce19df5b-34c4-4307-b747-8b181c40d246(a)h37g2000pra.googlegroups.com...
> Hi,
>
> I have a message M, a hash function H(), and a block cipher with
> encryption function E() and decryption function D()
>
> I calculate S=E(K, H(M)) (encrypt the hash of message with a key K)
>
> 1) Can this construct of S be called a mac of the message ?
> 2) Is it a good one ?

A MAC is secure if an attacker (who doesn't know the key), given a large
series of (Mn, Sn) messages (where the attacker gets to choose the Mn
messages), cannot construct (with a nontrivial probability of success) a
(Mz, Sz) pair which he has not seen.

Now, with your construct, an attacker cannot find an Mz such that H(Mz) =
H(Mn) (with Mz!=Mn); this is the collision resistance assumption of the hash
function. Hence, we can simplify the requirement on the attacker to being
able to find a (Hz, Sz) pair, which is distinct from the (Hn, Sn) pairs he
has been given (where Hn=H(Mn) and we just assume that the attacker can find
a message Mz s.t. H(Mz)=Hz). However, if the attacker was able to predict
such a pair, that could be used as a distinguisher on E (in this
distinguisher, the attacker would ask for the encryption of all the Hn's,
from the resulting (Hn, Sn) pairs, predict a (Hz, Sz) pair, then ask for the
decryption of the Sz value and see if it comes back as Hz. As we assume no
such distinguisher exists on E, we assume we cannot predict a (Hz, Sz) pair.

Hence, assuming H is a collision resistant hash function, and E is a good
(indistinguishable from random) encryption function, then your combination
is a secure MAC.


As to whether it's good, well (IMHO) it can be improved. For example, if
you replace the collision resistant hash function with a universal hash
function ( http://en.wikipedia.org/wiki/Universal_hashing ) based on a
secret key, well, it's still a secure MAC, and its actually somewhat faster
(universal hash functions are in general faster than collision resistant
ones). Examples of existing MACs that are designed exactly like that are
GMAC and the authentication-only form of CWC. And, yes, they preserve your
below idea of verifying by decryption.

>
> I guess one could argue that this is basically CBC-MAC of the Hash of
> the message. I've read that CBC-MAC is only good for fixed length
> messages. In that case the actual message are Hashes of fixed length,
> so I guess that one could say this construct is as good a CBC-MAC....
> would that be fair ?
>
> As far as why try this instead of something else. The main reason is
> in the way the mac is verified.
>
> Normal CBC-MAC, you do regenerate the actual MAC and compare to the
> one sent with the message. This often mean that the proper MAC is in
> memory and so could be eventually spied upon, turning your MAC
> checking machine into a MAC generating machine.
>
> With this construct, the verification is done by decrypting the MAC,
> then compare the hash of the Message to the result of this decryption.
> So the MAC is never regenerated, and can not be stolen from memory.
>
> (One could try to steal the key, in both case. But in some situations
> it is easier to hide a key that the result of encryption)
>
> Does this construct already has a name ?
>
> If not, I patent it! :)
>
>
>


From: Francois Grieu on 11 May 2010 04:17
On 11/05/2010 02:48, Fabrice wrote:
>
> I have a message M, a hash function H(), and a block cipher with
> encryption function E() and decryption function D()
>
> I calculate S=E(K, H(M)) (encrypt the hash of message with a key K)
>
> 1) Can this construct of S be called a mac of the message ?
> 2) Is it a good one ?

As explained by Scott Fluhrer, yes. With one caveat: the construction
and security argument uses that the size of the plaintext for E is the
same as the size of the output of H, which is unusual with real-world
hashes and encryption primitives.

> I guess one could argue that this is basically CBC-MAC of the Hash of
> the message.

No. CBC-MAC does not use a hash, and proceed by repeatedly (XOR-ing the
previous result with a block of the message and encrypting that).

> I've read that CBC-MAC is only good for fixed length
> messages. In that case the actual message are Hashes of fixed length,
> so I guess that one could say this construct is as good a CBC-MAC....
> would that be fair ?

The similarity is remote, and IMHO limited to: with message reduced to
one block, CBC-MAC is the same as your construct with H replaced by
identity (which is a fine hash in the context, since first preimage
resistance seems a non-issue).

> As far as why try this instead of something else. The main reason is
> in the way the mac is verified.
>
> Normal CBC-MAC, you do regenerate the actual MAC and compare to the
> one sent with the message. This often mean that the proper MAC is in
> memory and so could be eventually spied upon, turning your MAC
> checking machine into a MAC generating machine.
>
> With this construct, the verification is done by decrypting the MAC,
> then compare the hash of the Message to the result of this decryption.
> So the MAC is never regenerated, and can not be stolen from memory.

Yes.

> (One could try to steal the key, in both case. But in some situations
> it is easier to hide a key that the result of encryption)

Yes.

> Does this construct already has a name ?

Google hash-then-encrypt


Fran�ois Grieu
 | 
Pages: 1
Prev: Diffie-Hellman key exchange
Next: I beam formula