# Is there a companion algorithm for OTP to ensure integrity and/or authentication?

One-Time Padding is (theoretically) perfect encryption algorithm. Let's assume that these problems are solved:

• Fast generation of independent and identically distributed random variables
• Perfect key distribution system
• Key only used once.
• Key destroyed after use, without side channels that would allow any non-trusted third party to attain any key bits.

However, for modern information exchange, it is not sufficient to encrypt information (this is against Eve). In addition to encryption, it is necessary to also protect

• integrity (this is against broken phone or cable) and
• message authenticity (this is against Mallory).

Some recommendations in cryptography recommend to use security level similar for encryption keys and message authenticity keys (i.e. use 128-bit encryption key and 128-bit MAC key). For MAC tag, it is common convention for HMAC or to use at most half of the MAC key length as the output length. Some other algorithms use full block length of the function.

For information theoretic authentication tag security, I would expect that in order to transfer message with length $N$ bits, I would need at least another $N$ bits to transfer "authentication tag" matching with the message.

Choices for Integrity or Authentication

Here are some of example schemes:

1. Double the bits. I.e. when instead of 0110, process plaintext 00111100 with OTP. This'll eat twice as much key material than OTP, but will protect against any single bit errors, and many of other errors, because it is easy to check at the recipient. (If only worrying about integrity.)
2. Process concatenation of $P$ (plaintext) and $T$ (mac tag) via OTP. There is problem how to calculate $T$. My first idea would be to use some operation on binary Galois Fields $GF(2^n)$, such as multiplication $C * C$ and use OTP to send that "checksum". (Only for integrity, but detects integrity problems with larger probability than option 1.)

Any suggestions how to efficiently calculate $T$? Are there any schemes which would provide usual security without key length $K=2N$? Are some of preconditions incorrect?

For authenticity it would appear that these are valid options:

3. encrypt-then-mac with an information-theoretically secure mac.

4. mac-then-encrypt with an information-theoretically secure mac.

What would be suitable information-theoretically secure mac for implementing alternative 3? Alternative 4 uses more key material than alternative 3. Are there any situations where alternative 4 would be profitable over alternative 3?

You could think of this question as sort of add-on question to:
"Having 4096 bit keys and short (< 256 byte) messages, can I simply use the key as OTP?"

• 3. $\:$ encrypt-then-mac with an information-theoretically secure mac. $\;\;\;$ – user991 Oct 23 '13 at 18:15
• "another half of key for coefficients of polynomial over GF(2^k)" would be a huge waste, $\hspace{.91 in}$ since it would use up way too much key material. $\;$ – user991 Oct 23 '13 at 19:25
• @user4982 "Current recommendations in cryptography often recommend to use security level similar for encryption and message authenticity (i.e. use 128-bit encryption and 128-bit MAC)." I don't know where you've heard that, but I don't know anyone that uses a 256-bit MAC to go with their 256-bit encryption. – orlp Oct 23 '13 at 19:45
• @RickyDemer Your suggestion '3. encrypt-then-mac with an information-theoretically secure mac.' is pretty much was I intended to ask in the first place. I've now clarified the question for this part. I have some concern over practical aspects (like performance). OTP is just XOR but mathematics on $GF(p)$ or $GF(2n)$ are more work to compute. BTW, would you want to write an answer. This far your comments make up for one very fine answer. – user4982 Oct 25 '13 at 12:17
• It is wasteful because it uses part of the key for encrypting the MAC tag. $\:$ Using UMAC for this would require either an unconditionally secure stateless encryption algorithm (which, as far as I know, would need a lot more key material) or would require that the verifier know the message number even if the MAC was just used for authentication of non-encrypted messages. $\;\;\;$ – user991 Nov 22 '13 at 9:34

One can efficiently obtain a $\:GF\left(2^n\hspace{-0.02 in}\right)\:$ either by

$\;$ looking up the simplest binary irreducible polynomial of
$\;$ degree $n$ here and verifying that it is in fact irreducible
$\;\;\;$ or
$\;$ using this unconditional and deterministic algorithm to compute such a polynomial

.

For any such $\:GF\left(2^n\hspace{-0.02 in}\right)\:$, $\:$ $\:\left(GF\left(2^n\hspace{-0.02 in}\right)\right)^{\hspace{-0.02 in}*}\:$ is the set of finite tuples of elements of $\:GF\left(2^n\hspace{-0.02 in}\right)\:$, $\:$ and I define
$\operatorname{f}\hspace{-0.03 in}\operatorname{hash} \: : \: GF\left(2^n\hspace{-0.02 in}\right) \times \left(GF\left(2^n\hspace{-0.02 in}\right)\right)^{\hspace{-0.02 in}*} \: \to \: GF\left(2^n\hspace{-0.02 in}\right) \;\;\;$ by $\;\;\; \operatorname{f}\hspace{-0.03 in}\operatorname{hash}(x,\langle c_{\hspace{.02 in}0},...,c_L\rangle) \: = \: \displaystyle\sum_{i=0}^L \left(c_i \cdot x^i\right) \:\:\:$.

(Note that one can store $x^i$ from each term to easily compute $x^{i+1}$ for the next term.)
Since non-constant polynomials of degree $L$ have at most $L$ roots, $\:\operatorname{f}\hspace{-0.03 in}\operatorname{hash}\:$ is
"somewhat universal", that is, for all $(L\hspace{-0.04 in}+\hspace{-0.06 in}1)$-tuples $a$ and $b$ of elements of $\:GF\left(2^n\hspace{-0.02 in}\right)\:$,
the probability for a random choice of $x$ that $\: \operatorname{f}\hspace{-0.03 in}\operatorname{hash}(x,a) = \operatorname{f}\hspace{-0.03 in}\operatorname{hash}(x,b) \:$ is at most $\:\frac{L}{2^n}\;$.
$\{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^*$ is the set of finite binary strings. $\;\;\;$ Define $\: \operatorname{str2f} : \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^* \to GF\left(2^n\hspace{-0.02 in}\right)$
by letting $\operatorname{str2ft}(s)$ be the result of padding $s$ with a single $1$ bit followed by however
many $0$ bits are needed to make the padded string's length a multiple of $n$ and then
splitting the padded string into $n$-bit blocks and interpreting those as field elements.
Define $\: \operatorname{shash} : GF\left(2^n\hspace{-0.02 in}\right) \to \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^* \:$ by $\: \operatorname{shash}(x,s) = \operatorname{f}\hspace{-0.03 in}\operatorname{hash}(x,\hspace{-0.02 in}\operatorname{str2ft}(s)) \:$.
Since $\:\operatorname{str2ft}\:$ is injective, $\:\operatorname{shash}\:$ is such that for all binary strings $a$ and $b$
whose lengths are (strictly) less than $\:(L\hspace{-0.04 in}+\hspace{-0.06 in}1) \cdot n\:$, $\:$ the probability for a
random choice of $x$ that $\: \operatorname{shash}(x,a) = \operatorname{fshash}(x,b) \:$ is at most $\:\frac{L}{2^n}\;$.

However, the universality property does not imply security as a MAC.
A simple way to deal with that issue is to let $\:||\:$ denote string concatenation and
and then define $\;\; \operatorname{weakmac} : GF\left(2^n\hspace{-0.02 in}\right) \times \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^n \times \left(GF\left(2^n\hspace{-0.02 in}\right)\right)^{\hspace{-0.02 in}*} \: \to \: GF\left(2^n\hspace{-0.02 in}\right) \;\;$ by $\operatorname{weakmac}(\langle x,y\rangle,s) = \operatorname{shash}(x,\operatorname{str2ft}(\hspace{.03 in}y\hspace{.02 in}||\hspace{.03 in}s))\;$. $\;\;\;$ Let $\mathbf{0}$ be the string of $n$ zeros.
Since expanding $\:\operatorname{weakmac}$'s$\:$ definition shows that $\;\; \operatorname{weakmac}(\langle x,y\rangle,s) \: = \: \operatorname{shash}(x,\mathbf{0}\hspace{.01 in}||\hspace{.02 in}s) \:\text{xor}\: y \;\;$,
it follows that for a randomly chosen $y$, the probability of successfully predicting $\operatorname{weakmac}(\langle x,y\rangle,s)$ without previously seeing any of its values is exactly $\frac1{2^n}$, and that seeing only one of its values perfectly hides $x$. $\;\;\;\;$ Thus, in the case of a single-chosen-plaintext forgery attack, we may assume without
loss of generality that the two messages are both chosen independently of $x$. $\;\;\;$ That means the
inputs to $\:\operatorname{shash}\:$ will be independent of $x$ and exactly $n$ bits longer than the inputs to $\:\operatorname{weakmac}\;$.
Therefore the success probability of an exactly-one-chosen-message forgery of $\:\operatorname{weakmac}\:$ in which
both the original and the substituted messages are (strictly) less than $\:L\hspace{-0.03 in}\cdot\hspace{-0.04 in}n\:$ bits long is at most $\:\frac{L}{2^n}\;$.

If one will be authenticating lots of messages, then that will use more key material than necessary.
If either the sender might authenticate a very long message or the verifier might
be willing to accept a very long message, then that probability might be too high.
One could get a much-closer-to-universal hash family by replacing $n$ with $m$ in $\:\operatorname{f}\hspace{-0.03 in}\operatorname{hash}$
for some $m$ such that $\:m< n\:$, $\:$ running the output of the modified $\:\operatorname{shash}\:$ through an
actual universal hash family, and then applying a random degree $d$ polynomial to that output.
That will give a mac such that, for $\:q\leq d\:$, $\:$ the success probability of a
$q$-chosen-message forgery on it in which all chosen messages and the
attempted forged message have length (strictly) less than $\:L\hspace{-0.03 in}\cdot\hspace{-0.04 in}m\:$ bits, is at most
$(1/(2^n))+((L\cdot \hspace{.03 in}$choose$(q\hspace{-0.04 in}+\hspace{-0.05 in}1,2))/(2^m)\:\:$, $\:\:$ and equality holds if and only if $\hspace{.045 in}q=0\hspace{.06 in}$.

The restriction of $\:\operatorname{f}\hspace{-0.03 in}\operatorname{hash}\:$ to $\; GF\left(2^n\hspace{-0.02 in}\right) \times \left(GF\left(2^n\hspace{-0.02 in}\right)\right)^2 \;$ is an actual universal hash from $\:(2\hspace{-0.04 in}\cdot\hspace{-0.03 in}n)$-bit$\:$ strings to $n$-bit strings. $\;\;\;$ If the construction outlined in the previous paragraph is used with that universal
hash family, then it would use $\;(d\hspace{-0.04 in}+\hspace{-0.04 in}4)\cdot n\;$ bits of key material to authenticate up to $d$ messages.
On the other hand, the "simple way" uses $\:2\hspace{-0.04 in}\cdot\hspace{-0.04 in}n\:$ bits of key material to authenticate each message.

• Thank you. I like the part that helps understanding difference between universality and security as MAC. – user4982 Oct 26 '13 at 10:00

You can construct a one-time MAC that has similar properties to the OTP. Better still, it uses a fixed number of bits for each message.

Here's how it works. Choose the closest prime to your message block size. Let's say you plan to process 128-bit chunks of your message. Let's say there are $$L$$ such blocks.

The first job is to pick the first prime larger than $$2^{128}$$ which is $$2^{128}+51$$. Call this value $$q$$.

The key has two pieces. Let's call these $$x$$ and $$y$$ and choose these at random from the range $$1$$ to $$q-1$$.

$$mac(m, x, y) = m_L\times x^L + m_{L-1} \times x^{L-1} + ... + m_{1} \times x + y \mod q$$
You basically evaluate a polynomial with a term for each block of the message. The co-efficient is the message block and this is multiplied by the key raised to the power of the current block number. All operations are done mod $$q$$.
Provided $$x$$ and $$y$$ and are used precisely once, this MAC is secure against all adversaries.
• Actually, the same trick works with $GF(2^n)$; $n=128$ is actually pretty close to GCM (with replacing AES with OTP contents). – poncho Oct 24 '13 at 21:25
• One should not rely on a heuristic that there is always a prime only slightly above a given power of 2, since one can provably always construct $GF(2^n)$. $\:$ One should index the blocks from zero and choose $x$ and $y$ at random from the whole binary field, so that after applying the padding I describe in my next comment, the forgery probability will be smaller. $\;\;\;\;$ – user991 Oct 24 '13 at 22:09
• One should start computing the mac from index zero, so that one can compute the mac in a streaming manner. $\:$ At the end of the message, one needs to apply padding like is done for CBC mode. $\hspace{.71 in}$ – user991 Oct 24 '13 at 22:12
• @user4982 - you only need 128 bit tags because with the construction that Simon Johnson outlined the odds of any adversary being able to forge a message is $1/2^t$, where $t$ is the tag length. So 128 bits is more than enough ( or "secure" as Simon put it). Also, this bound holds even against information theoretic opponents. Search for "Carter Wegman universal hash" if you want to read more. – J.D. Oct 24 '13 at 22:26