[Cryptography] Perfect Integrity?

[Peter Fairbrother]

On 05/08/18 14:56, Kristian Gjøsteen wrote:
> 4. aug. 2018 kl. 21:44 skrev Peter Fairbrother <peter at tsto.co.uk>:
[...]
>> 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 ciphers, «information theoretic security» has a specific meaning that roughly translates into «an adversary with unlimited computing power does not learn anything from the ciphertext».

Ouch. I'd prefer: "information theoretic security" means that without 
information an adversary doesn't have access to he can learn nothing 
about a plaintext from its ciphertext."

The OP was talking about Perfect Integrity, not Information Theoretic 
Integrity, and while I suppose there are differences, I am not entirely 
sure what they are.

To stay with security for a moment, an OTP is said to be perfectly 
secure; an attacker can learn nothing about the plaintext from the 
ciphertext - except maybe it's length. Chtsghjydsor might possibly 
decrypt as "attack at dawn" or "retreat at dusk", but it doesn't decrypt 
as "watch it, Hannibal is crossing the Alps with elephants", as it isn't 
long enough.

Could be important if eg the General habitually sends long messages when 
about to retreat, and short ones when about to attack. Or vice-versa.

Of course you can add padding, but exactly how much padding is needed to 
make a message information-theoretic secure?

So. is a "perfect" OTP information theoretic secure? Is anything? An OTP 
hotline discloses nothing ... but it's existence.

And a "perfect" OTP is basically a stream cipher, with the disadvantages 
of stream ciphers, eg plaintext manipulation etc.


> This definition does not make sense for integrity, so information theoretic has to get a new meaning with respect to integrity.
> 
> First, the context. We have a function f that takes a key and a message and outputs a tag. There are n distinct tags. Alice sends (m,t) to Bob, where t = f(k,m) and k is a shared key. Bob receives (m’, t’) and checks if f(k,m’) == t’.
> 
> Note (as has been said, already) that - regardless of what f is - Eve has a 1/n chance of creating a valid tag by choosing t’ at random. (At this point, some people say that information theoretic security is impossible and stop. Even though we haven’t defined what information theoretic security means yet…)
> 
> There are now two possible ways to define security: (a) no adversary should have greater than 1/n chance of creating a forgeryand (b) no adversary should have greater than eps chance of creating a 
forgery, for some small eps.

There is at least a third way - c) no adversary should have greater than 
1/|m| chance of creating a forgery, where |m| is the number of possible 
messages.

> (b) is the most convenient content of «information theoretic integrity»,and we may reserve the prefix «perfect» to denote (a)

I do not understand that.

[..]
> 
> Next, an example that works: k = (a,b), f(k,m) = a*m + b. First, since b is random, Eve learns nothing about a from t. Next, suppose Eve sets m’ = m + Delta and t’ = t + Delta’. If Eve wins, then Delta’ = a*Delta. Since Delta is non-zero, the odds of that is exactly 1/n.

This is trivially insecure as written, even for a one-off-tag - unless 
the calculations are done mod a large prime p, when it becomes secure.

(one-off-tag attack scenario: Alice calculates tag t from message m, Eve 
intercepts message, prevents it's delivery, wants to forge a different 
message for Bob)

Now the maximum message size is p-1 - if larger messages are allowed it 
is trivial to create a message which equals m modulo p. Also, a and b 
should be chosen at random from 1 to p-1.

So |a| = |b| = |t| = |m|, = |p| roughly.

I may have been a bit loose in nomenclature here, using |x| both for the 
size of x and the number of possible x's, hope you follow me.

We could truncate t without giving anything away about a and b, except 
the chance of forgery would increase - so using the working example, 
there is a natural size to a MAC tag which is the same as the size of 
the message.

I think there is something more fundamental [1] going on as well; so if 
I may I will call a MAC tag like that, calculated in a (loosely, 
~information theoretic~) secure way with size equal to the message, a 
"perfect" tag.


-- Peter Fairbrother

[1] working on it..