[CST-2] Bit of Security, for a change

[Barnaby Gray]

On Sun, May 26, 2002 at 10:38:11AM +0100, Matej Pfajfar wrote:
> > Quick security question, basically concerns 1998 paper 7 question 9.
> > Basically asks whether a digital signature on a 32bit MAC is more secure
> > than a 128 bit Hash, and why.
> I just got up so sorry if this is rubbish -
> A MAC is cryptographically secure, whereas an ordinary hash is not.
> You need to know the key to be able to generate/verify the MAC. =>
> signatures are more difficult to forge/the sender can't plausibly deny
> that he/she sent the message etc.

The key lengths used really determine the comparative security of the
MAC vs the ordinary hash. The ordinary hash will be susceptible to the
birthday attack, so for the 128-bit hash it takes the attacker 2^64
complexity to produce other 'interesting' messages that hash to the
same value and can be used for evil deeds. The MAC will avoid this in
that the attacker doesn't know the key for the MAC, but if the key
length is short then the attacker can first, given enough data, do a
brute-force attack on finding the key, then apply the birthday problem
to this too, to find two messages that produce the same MAC, which
will only be complexity 2^16!

So if the key for the MAC is > 64-bit I'd say the MAC scheme is
securer, if it is < 64-bit the hash scheme is securer.

Of course there might be other more obvious attacks on either I've
missed..

Barnaby