[Cryptography] A Fun Trick: The Little MAC Attack

[Jerry Leichter]

On May 9, 2015, at 9:09 PM, Ray Dillinger <bear at sonic.net> wrote:
> I have never understood, though, why ... [HMAC] is preferred
> to the more straightforward construction:
> 
>    hash(Encrypt(key, message))
> 
> .  The only reason I know why ... [HMAC] 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....
Export may have entered into it in some cases, but performance was probably a bigger issue.  We're talking about a time when "hash" was MD5, "encrypt" was DES (or maybe 3DES), and a "fast chip" was an i386.  MD5 was *much* faster.  You'd probably have trouble streaming encrypted audio - but you could manage streaming authenticated audio.  "Authenticated/integrity protected but not encrypted"  modes were common in proposals in those days.  They still remain in IPSEC (whose origins go back that far) - though there hasn't been any *technical* need for them in many years.

Most proposals of the day simply used MD5(key || message), a few might go for the "more secure" MD5(key || message || key).  You could find tons of hand-waving arguments for why this was safe.  (I started on a project that used the first form - justified with those hand-wavy arguments - in about 1995.  It took me about 10 minutes - well, maybe a bit more - to (re-)discover extension attacks against it.  The "safer" double-key mode takes more sophistication to attack, but isn't actually any good either.  BTW, this particular project was gathering data from a large number of small devices.  It was argued that (a) the actual data wasn't secret - it was observations about public information, so didn't need to be encrypted; (b) falsified information could lead you to incorrect decisions, so authentication/integrity guarantees were useful; (c) the devices were too small and weak to run DES anyway.)

HMAC at least gave you a mode that "worked" in some reasonable sense.  As a technological compromise given the realities of the era, it made sense.

                                                        -- Jerry