[Cryptography] Perfect Integrity?

[Jerry Leichter]

> The integrity equivalent to a One Time Pad is to keep a copy of the data itself as evidence of integrity. Like an OTP, perfectly secure and perfectly useless.
That depends on what security requirement you think "integrity" actually corresponds to.

I've been thinking about this from a slightly different point of view.  Suppose we fix the message size at n bits.  What's the strongest possible cipher on n bits with a k-bit key?  The answer is pretty clear:  From the space of all 1-1 functions from n bits to n bits, choose 2^k distinct functions f_i at random, numbering them from 0 to k-1.  To encrypt with key K, apply function f_K.

These are immensely strong (in a completely meaningless, from any practical point of view, sense) ciphers.  The limit, when k is n, includes all the one-time pads as a tiny fraction, where the chosen f_i are not just 1-1 but are actual Cartesian products of n 1-bit 1-1 functions (of which, of course, there are exactly two:  Identity and complement).

Speaking loosely, we describe block encryption functions as "looking like they were chosen at random" - but again it's not from the space of all 1-1 functions, but of those that are Cartesian products of 1-1 functions on 2^b bits, where b is the block size (and, of course, not even *all* such 1-1 functions).

The "strongest possible encryptions" are way stronger than they need to be because they focus on the wrong thing, the functions.  Perfect security for the encryption of an N bit message means exactly that given an encrypted message E, for any n-bit message P, the probability that a key sends P to E is the same across all keys.  One-time pads already achieve this, of course, so there's "no need to go further".

So what would the equivalent for authentication?  Authentication requires some additional redundant information along with the message.  Suppose in addition to the n bits of message, we send a bits of authentication.  The strongest possible such authentication is then produced by choosing, at random, a function Auth from the set of all functions from n bits to a bits; the pair (M,A) is then considered authentic if Auth(M) = A.

Clearly some choices of Auth are bad - e.g., constants.  As a start, let's restrict the space of functions from which we chose to include only onto functions - an nice dual to the restriction to 1-1 functions for encryption.

In the limit, when n=a, we then have just the permutations.

Now let's consider the strongest possible authentication requirement:  It should be "as difficult as possible" for an attacker to construct a pair (M,A) which will be seen as authentic.  (We can actually state this in a way that's similar to the condition for encryption, though it doesn't quite capture what's happening:  Given M, across all choices of possible Auth's, any A is equally likely.)

In this framework, Mr. Hallam-Baker's idea of sending along a copy second copy - i.e., setting a=n and Auth the identity - is insufficient:  It's trivial to forge any "genuine" message M as (M, Auth(M)) == (M, M)!

Unlike the case with encryption, where there's nothing to be gained by a key longer than the message, here a larger than n actually makes sense (though you need to replace "onto" with some appropriate condition):  If I construct a random (M, A) pair, the chances that it will appear authentic is 1/2^a, regardless of n.  (This was exactly (Matt Blaze's?) attack that showed the pointlessness of Clipper's key escrow mechanism.)

This kind of attacker is easier because the "existential forgery" attacker has much more freedom.  The corresponding attack against encryption would be the ability of an attacker to find P, E, and K such that E=Enc(P,K).  This isn't an interesting attack because K is the secret and we consider the encryption function public.  In the authentication case, Auth itself is the secret.

Now, if we look at *keyed* authentication, things are different - though it's interesting to note that a cryptosystem secure against that "existential attack" would inherently provide both secrecy and authentication.

                                                        -- Jerry

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20180804/dd97cef2/attachment.html>