# How could I make a MAC two time secure?

Let us assume that a MAC is calculated as $t = a m + b$ with $a,b,m \in \mathbb{Z}_p$, $p$ prime. $a$ and $b$ denote the private generation keys, $m$ refers to the message.

This MAC is then one time secure, but not two time secure. One time secure means that an attacker who learns of one message-mac pair has only a small chance to find a separate message with a valid mac. Two time insecure means that as he learns two pairs, he is then easily able to solve the resulting system of linear equations for the secret $a$ and $b$.

How could the MAC generation scheme be changed to make it two time secure?

I understand that the $am$ and $b$ components are independently and evenly distributed in $[0..p-1]$, as $p$ is prime. Given that, I thought I could add a third component, derived from a newly added part $c$ of the private key, which again is independent and evenly distributed. But I could not figure out how.

First off, obviously, simply using something like $t = a m + b + c$ or $t = a m + b + c m$ does not work, as the new component can be combined with either $a$ or $b$, thus not providing any effective benefit.

Something like $t = a m + b + c m^2$ does not seem to work, as $m^2$ is not evenly distributed in $\mathbb{Z}_p$. (Am I missing something?)

Another idea might be to add a counter to the generation: $t = a m + b + c i$ where $i$ is a message counter. This appears to be two time secure for $p > 2$, but only given that the attacker cannot simply use $p$-apart messages, which obviously share the same $c i$ component. This requirement seem too high to me, so I'm not a fan of this idea.

• "It is well known that a MAC is one time secure, but not two time secure. ". This goes maybe for your specific MAC that relies on number theory, but I'm pretty sure that e.g. CMAC or HMAC do not possess this property. – Maarten Bodewes Nov 19 '16 at 15:49
• @MaartenBodewes Thanks, I'll try to fix this in the question. – mafu Nov 19 '16 at 15:50

Something like $t = a m + b + c m^2$ does not seem to work, as $m^2$ is not evenly distributed in $\mathbb{Z}_p$. (Am I missing something?)
You are missing something. Given two solutions $(m_0, t_0), (m_1, t_1)$ to the equation $t = cm^2 + am + b$ (for unknown $a, b, c$), any third solution $(m_2, t_2)$ will hold with probability $1/p$ (assuming $m_2 \ne m_0, m_1$); if $p$ is large, this exactly satisfies the criteria you're looking for. You can see that by fixing $m_2$ and considering the possible $t_2$ values between $0$ and $p-1$; for each such $t_2$ value, there is a unique set of $a, b, c$ values that make all three equations work, and as $a, b, c$ were generated randomly (so any no set has any higher probability than any other), this means that all possible $t_2$ values are equiprobable.
It doesn't matter that $m^2$ isn't equally distributed. If it really bothers you, you can perform the operations in $GF(2^n)$ rather than $GF(p)$. In $GF(2^n)$, $m^2$ is evenly distributed (but, as above, it's not actually a concern).