I would like to come up with a MAC algorithm that is simple and provably secure.

The message and mac are OTP encrypted. For the purpose of this exercise lets say the entire plaintext is known to the adversary (they have predicted it), but the MAC for the authentic message is not known.

I'm not an expert, but it seems to me that perfect mac security can be described as follows:

For any bitflip(s) of the encrypted message, the MAC should change in a way that is completely unpredictable. That is to say the OTP encrypted mac should be equally likely to change into any value in the set of potential values.

Question 1: Is that too stict? Too lax? Or just right?

Following from the above definition, here's an extremely inefficient but (I believe) perfectly secure algorithm:

MAC is initialized with 0's. Then, for every bit of the message, n random bits from the OTP are assigned. Where n is the MAC length. If the message bit is 1, the random bits are XOR'd with the MAC. If 0, they are not.

Question 2: Is that perfectly secure?

Question 3: If it is secure, is there any way the algorithm can be changed to improve the efficiency without reducing the security?


1 Answer 1


What's discussed is not really a Message Authentication Code. It's a One-Time Message Authentication Code (or One-Time Authenticator, although the term is often used for a time-dependent authenticator), because the key/OTP can't be reused, which is required for a MAC.

Q1: The proposed condition is insufficient. Argument: the condition is met by the proposed algorithm, which is insecure, see Q2.

Q2: If we ignore this, the algorithm still is insecure, for two reasons that each break the standard notion of security# of a MAC or OTA:

  1. The empty message has all-zero authenticator, allowing a forgery with no query. That's solved by prepending a 1 bit to each message (equivalently, setting the initial value from the OTP).
  2. Appending any number of zero bits to a message leaves the authenticator unchanged, allowing forgery with one query. That's solved by restricting to fixed-size messages, or appending a 1 bit to each message (equivalently, by XORing with a value from the OTP indexed by the message size).

Q3: The above changes makes the algorithm a perfectly secure OTA: probabiblity of forgery is the same as for a random choice of authenticator. It's one that uses a very long one-time key, compared to a Carter-Wegman Authenticator. This achieves essentially the same goal with a key that can be down to as large as the authenticator (for fixed-size message up to some maximum, but the fixed part of that can be solved in the same way as issue 2). This technique is at the core of Poly1305.

# The standard notion of security of a MAC or OTA is that:

  • adversary decides if they want to propose a message of their choice and get it's authenticator
  • in MAC (not OTA) they can repeat the previous step
  • adversary submits a message and a candidate authenticator
  • adversary succeeds if that later message is different from any previous message submitted, and is accepted with probability better than for a random authenticator.
  • $\begingroup$ I don't understand how this could be exploited. If the message is known, you can bit flip it to be all zeros. You will then know the decrypted MAC will be all zeros. But you still can't forge a message because you don't (and can't) know what the MAC of the original message was. Even in the case when the known plaintext is all zeros. You can't forge a message, because changing any bit to 1 would result in a totally new mac. $\endgroup$
    – Drew
    Commented Mar 22 at 20:28
  • $\begingroup$ @Drew: I added the standard notion of security for a MAC or OTA. I do not challenge that your proposed system matches your proposed notion of security. It's different, and not so useful in real life: there is nothing to prevent an adversary from changing both the message and the authenticator to all-zero, which in your system will be accepted. This would potentially cause a denial of service, and is to be considered an exploitation. Same for adding zeros at the end of an actual message, without changing the genuine authenticator. $\endgroup$
    – fgrieu
    Commented Mar 22 at 21:18
  • $\begingroup$ The messages are short and transcribed manually (like with WW2 encryption machines), so denial of service isn't a risk. I suppose by capturing a known plaintext message and then shortening it, an attacker could compose a message with arbitrary plain text. Thanks for the insight. I will think about that. $\endgroup$
    – Drew
    Commented Mar 23 at 2:45
  • $\begingroup$ @Drew: For manual cryptography, your system makes sense. Indeed a human will not be foiled by the two attacks there are (and there are not others as long as the key is not reused). It's main drawback is the long key, and that it must remain single-use. $\endgroup$
    – fgrieu
    Commented Mar 23 at 9:53
  • 1
    $\begingroup$ @Drew: Given that goal, I guess you should add tags pen-and-paper and authentication, and read these related, found by this query. $\endgroup$
    – fgrieu
    Commented Mar 24 at 9:43

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.