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?

Improve this question
$\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$
    – Squeamish Ossifrage
    Commented Sep 17, 2017 at 23:23
  • $\begingroup$ That's $2^{130} - 5$ above—misplaced a closing brace! $\endgroup$
    – Squeamish Ossifrage
    Commented Sep 17, 2017 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
    Commented Sep 20, 2017 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$
    – Squeamish Ossifrage
    Commented Sep 27, 2017 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$
    – Squeamish Ossifrage
    Commented Mar 7, 2019 at 22:18

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented Jan 2, 2018 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
    Commented Jan 2, 2018 at 19:16
  • $\begingroup$ @Melab: typo: I meant GMAC, not GHASH in the previous comment... $\endgroup$
    – poncho
    Commented Jan 2, 2018 at 19:34
  • $\begingroup$ Using a secret initial value doesn't make it secure? $\endgroup$
    – Melab
    Commented Jan 30, 2018 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
    Commented Jan 30, 2018 at 13:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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