[Cryptography] Perfect Integrity?

[Peter Fairbrother]

On 05/08/18 10:01, Peter Gutmann wrote:
> Peter Fairbrother <peter at tsto.co.uk> writes:
> 
>> A one-bit W-C MAC will give an attacker no advantage in guessing the bit -
>> but he will still have a 50% chance of guessing right.
>>
>> For information-theoretic security the MAC has to be as long as the message.
>> I think.
> 
> Depends on the circumstances.  Lets say the MAC is being used as part of an
> alarm circuit, where a keepalive is sent across the circuit every 50ms, with a
> 1-bit MAC attached.  The attacker would have to guess the bit, then 50ms later
> guess the next bit, then 50ms later guess the next one, etc.  Get a single bit
> wrong and you trigger the alarm.

I don't know of a definition of perfect integrity, which is why I added 
"I think".

If you have a 20-bit message with a 1-bit MAC, the attacker has a 1/2 
chance of successfully forging a MAC by guessing.

If you have a 20-bit message with a 20-bit secure MAC, then the chances 
are 1 in 2^20.

Hmmm, if you have a 20-bit message with a 200-bit secure MAC, an 
attacker's chance of forgery by guessing are 1 in 2^200 ...


So maybe perfect integrity is impossible, as a perfectly unguessably 
secure MAC would have to be infinitely long.

Or maybe a 20-bit MAC is enough. I suppose it depends on how you define 
perfect integrity; you pays your money ...


Peter Fairbrother