1
$\begingroup$

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?

$\endgroup$
5
  • 2
    $\begingroup$ 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. $\endgroup$ Sep 17 '17 at 23:23
  • $\begingroup$ That's $2^{130} - 5$ above—misplaced a closing brace! $\endgroup$ Sep 17 '17 at 23:38
  • $\begingroup$ @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. $\endgroup$
    – Melab
    Sep 20 '17 at 20:34
  • $\begingroup$ 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. $\endgroup$ Sep 27 '17 at 19:34
  • $\begingroup$ My comment above was apparently premised on $a$ and $c$ being secret and chosen uniformly at random, not being standard parameters. $\endgroup$ Mar 7 '19 at 22:18
1
$\begingroup$

Would it be too slow to make for a good authentication mode?

No, it would be too insecure for a good authentication mode.

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.

$\endgroup$
6
  • $\begingroup$ How does it differ from GCM or Chaskey to make that the case? Remember, the tag is encrypted at the end. $\endgroup$
    – Melab
    Jan 2 '18 at 18:53
  • $\begingroup$ @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" $\endgroup$
    – poncho
    Jan 2 '18 at 19:16
  • $\begingroup$ @Melab: typo: I meant GMAC, not GHASH in the previous comment... $\endgroup$
    – poncho
    Jan 2 '18 at 19:34
  • $\begingroup$ Using a secret initial value doesn't make it secure? $\endgroup$
    – Melab
    Jan 30 '18 at 7:24
  • $\begingroup$ @Melab: no, a secret initial value doesn't make it secure; it doesn't change how it processes related messages... $\endgroup$
    – poncho
    Jan 30 '18 at 13:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.