Perfect Deniability of a MAC Protocol

Question

I proposed an idea of Perfect Deniability of a MAC

I tried to come up with a protocol that satisfies those security requirements as well as the normal security requirements of a MAC

One-Time MAC

1. Alice and Bob pre-share a $n^2$ OTP bits, $k$ (bits that were generated the same way you would for a OTP with all the requirements met here)

2. Alice breaks $k$ into $n$ strings of length $n$, lets call them $k_1, k_2, ..., k_n$

3. For each $k_i$ Alice computes $b_i = \bigoplus_{j=0}^{n}(m \oplus k_i)$
   • Each $b_i$ is a bit computed from xoring all the bits in $m \oplus k_i$
4. Alice sends $m||b$ where $b = b_1||b_2||...||b_n$
5. Alice and Bob destroy k

Proof

One-Time MAC is a MAC since anyone not knowing the key can only modify the stream with negligible probability. If someone tried to flip bits in the message then they would need to flip some unknown bits in the MAC and visa versa. They would only guess correctly with probability $2^{-n}$.

Now for the perfect deniability part.

If Eve came to Alice with $m$ and MAC($m$) = One-Time MAC($m$) then Alice can just generate $n$ random $n$ bit strings check their $b_i$ values and reorder them so that they create a "valid" key. (Note she may need to generate more than $n$ keys if the number of $b_i = 0$ doesn't match the number of $0$'s in MAC($m$), but odds are she will not need to generate more than $2n$ random strings)

Problems and Thoughts

I feel obligated to post issues with this protocol.

• Very large key ($n^2$)
• Similar issues as OTP (key management, etc..)
• Could be used as a MAC for a OTP and give messages perfect secrecy and perfect deniability without the ability to be tampered with

Questions

• Does this satisfy the properties of a MAC?
• Does this satisfy this definition?
• Could this be done with a smaller key?
• For long messages can you break it into smaller messages and MAC each individually to use less key?
  • I would assume you would lose security since $n$ would be smaller

Answer 1

Does this satisfy the properties of a MAC?

No, it doesn't, however a tweak to it does.

The issue is that flipping a single bit of $m$ always changes either every bit of the MAC (if $n$ is odd), or none of the bits (if $n$ is even); hence it is trivial for the attacker to modify the message, and adjust the MAC.

What you really meant is $b_i = \bigoplus_{j=1}^{n}(m \wedge k_i)$ (where $\wedge$ is the bit-wise and operation. This still needs a bit of tweaking (because of the all-0 message; either include an artificial 1 bit in the message, or cheaper, do a final xor of yet another $k$ vector into the final $b$ result).

This method is equivalent to selecting a random $(n \times n)$ matrix in $GF(2)$, and then doing a matrix multiplication of the message to form the output; this is a well-known universal hash method.

Does this satisfy this definition?

With the above tweaks, yes.

Could this be done with a smaller key?

Of course. I suspect that most universal hash methods could be made to do this; here's one approach (polynomial hashing) that uses quite a small key.

Lets pick an integer $z$, and a field representation of $GF(2^z)$ (actually, any field of about this size can be made to work).

Then, for our one-time keys key, we pick two random $z$-bit values $h$ and $c$.

Then, we divide our $n$-bit message $m$ into $z$-bit sized chunks $m_{i-1}, m_{i-2}, ..., m_0$ (where $i = \lceil( n / z ) \rceil$, and we compute:

$$MAC = m_{i-1} h^{i+1} + m_{i-2} h^{i} + ... + m_0 h^2 + i h + c$$

The above computation is done in $GF(2^z)$

This is also a secure MAC (any modification to the message and tag will pass the checks with probability at most $(i+1)2^{-z}$; we can select $z$ to make this arbitrarily small), and it also meets your requirements (to fake a MAC, we can select an arbitrary $h$ and compute what the $c$ value had to be); using a total of $2z$ OTS bits per message.