Suppose we have a tweakable block cipher ($E(K, T, X)$ and $D(K, T, X)$) that is used in a scheme where the tweak, either in whole or in part, is used as a counter to make each block encrypt to a distinct ciphertext. If we XOR all of the blocks together and then encrypt the result, do we have a secure tag?


It is not secure if you use the $E(K, T, X)$ values as the exposed ciphertext; it is secure if you're using this scheme as a MAC (and use an independent scheme to encrypt).

If you send the $C_i = E(K, T_i, X_i)$ as the ciphertext (and send $E(K, 0, \bigoplus C_i)$ as the tag, then what the attacker could do is flip the same bit on two different $C_i$ values. The resulting $\bigoplus C_i$ will remain the same, and so the tag would validate (and the decrypted plaintext would be incorrect).

On the other hand, if you keep all the $C_i$ values internal, then this system can be viewed as a Carter-Wegman MAC. All you need to show is that $\bigoplus C_i$ is an almost universal hash function (which is fairly easy to do, assuming you get the message padding right), and the standard CW proofs apply.

  • $\begingroup$ Ah. I see why this scheme isn't used. Each ciphertext block needs to be transformed again with a keyed function before XORing them all together and encrypting the result. Is there a limit to the length of a message that can be authenticated securely under such a scheme and how does it compare to a chained MAC like HMAC or CBC-MAC? $\endgroup$ – Melab Jan 8 '18 at 20:40
  • $\begingroup$ @Melab: no, there wouldn't be any particular length limitations (at least until you hit the birthday bound); the CW argument above shows that $\bigoplus C_i$ remains universal up until then (and it probably is beyond that as well, i don't have an immediate proof of that) $\endgroup$ – poncho Jan 8 '18 at 21:00
  • $\begingroup$ Right, the birthday bound. That's what I was talking about. I didn't know if it applied to XOR MACs. I've seen claims that schemes like Bernstein's "protected counter sum" have beyond birthday bound security. $\endgroup$ – Melab Jan 8 '18 at 21:02
  • $\begingroup$ Are XOR MACs a variant of Carter-Wegman MACs? $\endgroup$ – Melab Jan 8 '18 at 21:03
  • $\begingroup$ Yes (actually, not a 'variant', rather a 'type of CW MAC'); however your MAC is different than what is commonly termed an "XOR MAC" $\endgroup$ – poncho Jan 8 '18 at 21:12

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.