[Cryptography] A Fun Trick: The Little MAC Attack

[Phillip Hallam-Baker]

On Sat, May 9, 2015 at 9:09 PM, Ray Dillinger <bear at sonic.net> wrote:
>
>
> On 05/08/2015 07:37 PM, Phillip Hallam-Baker wrote:
>> On Thu, May 7, 2015 at 8:14 PM, Dan Kaminsky <dan at doxpara.com> wrote:
>>> Practical HMAC-MD5 Collisions!
>>>
>>> Not that they should ever matter...
>>>
>>> http://dankaminsky.com/2015/05/07/the-little-mac-attack/
>>
>> There is actually a mode where they could matter. There exist
>> applications where a MAC is used as the digest for a signature. This
>> enables a mode where the signature can only be verified by someone who
>> knows the secret without the loss of non-repudiation that a straight
>> HMAC entails.
>
>
> So this common construction for message authentication codes,
> which with vector2 = 0x363636... and vector1= 0x5c5c5c....
> constitutes the usual definition of HMAC:
>
>    hash(key XOR vector1) XOR hash(key XOR vector2 XOR message)
>
> allows the ability to create collisions in the hash to be extended
> to the ability to create collisions in the MAC, when the attacker
> knows the key.
>
> I don't see any significant damage here; if the attacker knows
> the key, the point of a MAC function (particularly a symmetric
> MAC function in which knowledge of the same key needed to verify
> the MAC is the requirement for generating a bogus MAC) is hosed
> anyway.
>
> I have never understood, though, why the above form is preferred
> to the more straightforward construction:
>
>     hash(Encrypt(key, message))
>
> .  The only reason I know why the first form was EVER preferred
> has to do with crypto export regulations back in the bad old
> days when, in certain contexts, certain authorities permitted
> hash functions to be part of exportable software but not
> encryption functions.

At the time HMAC was proposed we did not have AES. In fact we didn't
have any encryption scheme that was satisfactory. The best was 3DES
which was a hopeless performance suck.

As a matter of principle, I dislike your scheme because it will go
belly up if the same key is used for authentication and encryption.

A better approach would be :

hash(key + Encrypt(key, message) )

Of course at this point we are into the realm of authenticated
encryption and we might as well use a construction that is provable.