# Desirability of chaining an LCG in an authentication scheme

Suppose that:

• $E(k, x)$ is the encryption of data block $x$ with key $k$ using a block cipher.
• $L_{Key}$ is the key size of the block cipher in bits.
• $L_{Block}$ is the block size of the block cipher in bits.
• $F(x) = (a \cdot x + c) \mbox{ mod } m$, so it's a linear congruential generator.
• $m = 2^{L_{Block}}$ is the modulus to be used in $F$.
• $a$ and $c$ are such that $F$ has a full period.
• $K \leftarrow \{0, 1\}^{L_{Key}}$ is a secret key to be used with the block cipher.
• $J \leftarrow \{0, 1\}^{L_{Block}}$ is a value that is derived in some way from $K$, perhaps through using $E$ and a constant.
• $T \leftarrow \{0, 1\}^{L_{Block}}$ is an authentication tag.
• $i$ is a one-based index.
• $x_{i} \leftarrow \{0, 1\}^{L_{Block}}$ is the $i$th block in a stream of data to be verified.
• $s$ is the number of data blocks.
• $y_{i} = x_{i} \oplus J$.
• $t$ is an intermediate value that is calculated prior to $T$. It is first calculated as $t = F(y_{1})$, after which it is recalculated as $t = F(y_{i} \oplus t)$.
• $T = E(K, t)$.

Seems secure enough to me (I know that isn't a good assurance, but I know jack about cryptanalysis), assuming the block cipher is secure. Block ciphers typically invoke one or more modular addition operations, so I don't think computing $b \boxplus c$ (where $b = m \cdot x$) is going to be a slow operation. I have no clue as to how much slower the multiplication would be. Would it be too slow to make for a good authentication mode?

Update #1: If $a = 65537$, then computing $a \cdot x$ would only require shifting $x$ to the left by four places and then adding $x$ to the result, which would be much faster than if $a$ had a larger Hamming weight. How much of an improvement in speed would this provide over GCM?

• Use $m = 2^{130 - 5}$, use $t = F(y_i + t)$ instead of $t = F(y_i \oplus t)$, and set $c = 0$, and you'll have a state-of-the-art MAC built out of Poly1305. Use $\operatorname{GF}(2^{128})$ instead of $\mathbb Z/(2^{130} - 5)\mathbb Z$, and you'll have a state-of-the-art MAC built out of GHASH or POLYVAL like AES-GCM-SIV uses it. Sep 17 '17 at 23:23
• That's $2^{130} - 5$ above—misplaced a closing brace! Sep 17 '17 at 23:38
• @SqueamishOssifrage That's nice, but I was hoping for commentary on the scheme I proposed. What is the POLYVAL function? I have not seen it before. Sep 20 '17 at 20:34
• POLYVAL is the same as GHASH but with different bit order, and in the proposed AES-GCM-SIV AEAD. As for analyzing the specific scheme: (a) that's why I posted a comment instead of a reply, (b) this isn't really the venue for requests for analysis of specific new cryptosystems, and (c) simplified versions of your scheme, with $c = 0$ and only tiny variations, are already widespread. Sep 27 '17 at 19:34
• My comment above was apparently premised on $a$ and $c$ being secret and chosen uniformly at random, not being standard parameters. Mar 7 '19 at 22:18

In particular, given any message $M$ that's at least two blocks long, it's trivial to find a second message $M' \ne M$ that has the same tag (no matter what the key is); and hence one could be substituted for the other without detection.
• @Melab: there's quite a few differences between what you have and GCM (more properly, GHASH); GHASH works in the field $GF(2^{128})$ using a secret multiplier; you're working in the ring $\mathbb{Z}/2^{L}$ (mostly, you xor in the message) using a public multiplier and a secret initial value. As for Chaskey, well, about the only thing that's similar between your approach and Chaskey's is the reliance on a secret initial value. I suspect the moral is "don't blindly tweak crypto if you don't know what you're doing" Jan 2 '18 at 19:16