What security flaw exists in MAC authentication scenario?

Question

What security flaw exists (if any) in the solution of this non-encrypted authentication scenario?

An unencrypted message passes one-way from computer A to B. Its transmission is viewable by the public. The message does not need to be kept secret. Both A & B have already securely exchanged any needed keys. A and B keep their keys secret.

Goal:

1. B needs to authenticate that the message (10s to 1000s bytes) originated from A.
2. Prevent others from creating a message (other than a copy that A originated) that B would mistake for an authentic message.

Solution (MAC)

• A appends a MAC to the message and sends it. B receives purported message and MAC.
• B authenticates (or not) the message/MAC. MAC size: about 256 to 512 bits.

---

Looked over other Q&A, but authentication is so often tied with confidentiality that I failed to find posts that addressed authenticity without a secrecy requirement.

[Edit]

I selected the answer (1 of 2 good answers) that presented the original scenario’s biggest problem: Via comments, it came out that $B$ is really a set of clone $B$s and thus a MAC does not authenticate that the message came from $A$ as it could come from another $B$. Thus warranting a Digital Signature.

---

The following points shift the nature of the question but do align with the realities of my particular situation. There are mentioned here should additional answers wish to address the modifications - which I will review and likely up vote. I should post a new more clarified question later.

A1. My 1st goal s/b “$B$ needs to authenticate that the message (10s to 1000s bytes) originated from $A$ or from another $B$.” Thus a MAC appears still OK.

A2. Non-repudiation of a message is not needed.

A3. Each message is complete and is not part of a larger message set (ordering or selective blocking not an issue.)

A4. The size of the MAC (or alternatives) is limited.

Details: There is no wired network. The messages & MAC are contained in RFID tags. The message describes a product attached to an RFID tag. These messages are generated by $A$ "the factory" and distributed, via public means, to various $B$s. A given machine $B$ may alter the message either with the original MAC or with a new MAC unique to that $B$ machine - TBD. The product need not move between the clone $B$s. All this does not authenticate a valid product exists (the product and RFID tag could be separated or the RFID is spoofed). It does authenticate that a valid product’s message exists.

Answer 1

Digital signatures are used to solve this type of problem. That is, a way for $A$ to sign the message for $B$ so that $B$ is highly confident that $A$ signed the message in question. There are lots of signature schemes out there, such as RSA signing, DSA, and others.

A MAC is not strictly a digital signature, but has a subset of that functionality and may meet your stated goals. It meets the requirement that an attacker won't be able to forge a new MAC without the key, which was the second point listed. (See this tangentially related question about HMAC.)

However, a MAC doesn't strictly meet the first stated goal. The problem is that MACs are based on symmetric keys, which means that everyone with the key can "MAC-sign" a message. When verifying a MAC, all the receiver ($B$) knows is that one of the parties with the symmetric key "signed" the message, but it don't know which one did. A copy of $B$ may send MAC-signed messages to other copies of $B$ and nothing distinguishes those MAC-signings from $A$'s MAC-signings. Practically speaking, this means, at a minimum, the attack surface of which compromised hosts can impersonate $A$ is widened. You no longer have to trick $A$ into signing malicious plaintext in order to forge $A$'s MAC-signature (such as by hacking it), using copy of $B$ will suffice.

This can have horrible implications if messages from $A$ are audited later and need to be verified as originating $A$ under the assumption of foul play on the network. (Maybe a legal court audit, perhaps just verifying that data collected was collected at $A$, etc.) Since any $B$ can forge a message on $A$'s behalf, you can't prove $A$ sent the messages. However, this may or may not be a concern for you.

Answer 2

Yes, this looks fine.

I assume $A$ and $B_i$ are trusted parties. The protocol as I understand it looks like this:

1. $A$, $B_1$,…,$B_n$ agree on a secret key k.
2. $A$ broadcasts messages ($m_1$,MAC($m_1$,$k$)), … , ($m_j$,MAC($m_j$,$k$) which $B_1$,…,$B_n$ receive and authenticate.

I assume $A$ and $B_i$ are trusted parties, so no $B_i$ will itself publicise any MACs, i.e. forge messages from $A$.

This follows the definition of a MAC pretty closely: $f_k$ is called a MAC if for a random $k$ an attacker who can first choose arbitrary $m_i$ and get the images $f_k(m_i)$ can then only create a pair $(\widetilde{m},t)$ with $\widetilde{m}\neq m_i\forall i$ and $t=f_k(\widetilde{m})$ with negligible probability.

There is caveat though: An attacker can manipulate which messages $B_i$ will receive and in which order. To prevent this you need to add a counter to every message: Send ($i|m_i$,MAC($i|m_i$,$k$)) instead of ($m_i$,MAC($m_i$,$k$) and at the end $A$ needs to send the overall count of messages along with a MAC: ($j$,MAC($j$,$k$)). Note that the key cannot be reused afterwards.