# What security flaw exists in MAC authentication scenario?

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.

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.

-
I'm not sure I understand what you want to accomplish. Do A and B only communicate with each other? Something like Alice telling Bob which product she offers him to buy and Bob answering whether he wants it or not? In this scenario only Alice and Bob need to verify each others messages and no one else is involved. Or do want to build something like an signature verification server where everyone has Bob's public key, but only Bob has Alice's public key? That would not involve MACs though. –  Perseids Aug 14 '13 at 21:09
Thanks for asking. (A)lice communicates with many (B)obs - they are all clones. (B)ob listens to the world and wants to authenticate messages to see if they originated from A. 'B' does not talk to 'A'. No need for 'A' to verify anything. 'B' only talks to himself. No public keys involved, just private keys that A & B hold secret for the MAC. Goal: as posted. –  chux Aug 14 '13 at 21:41
@chux: "Confidentiality" is the goal of encryption, aka, to keep the contents of the message secret. "Authenticity" is the goal of MACs and digital signatures, aka, to prove who sent it. I believe you meant "authenticity" instead of "confidentiality" in your last paragraph. –  B-Con Aug 14 '13 at 21:42
So if all Bobs are clones, they all share the same secret key with A? –  Perseids Aug 14 '13 at 21:46
@Perseids Yes, all Bobs are clones and share the same secret keys with A. –  chux Aug 14 '13 at 21:48

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.

-
You have a good point. The idea, though not stated clearly enough, is that $A$ & $B(s)$ are cooperative and "$A$ and $B$ keep their keys secret." and in a later comment "B only talks to himself". Given your good idea, if B ever talks to himself via a public message, a different MAC key/clone should be used. But as you suggest, if A or one of the clone B is compromised, the gig is up - which really the same as the "secret" key being comprised. I'll ponder this more. –  chux Aug 14 '13 at 22:17

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.

-
An order caveat - The message order, as it turns out is not significantly important. This was unstated, but then I didn't consider it until you provided it (and a solution). –  chux Aug 14 '13 at 22:27
@chux: What about selectively blocking messages? Without the associated counter B will never know if one message in-between two others was not transmitted. –  Perseids Aug 14 '13 at 22:31
Selectively blocking - (you keep finding these Swiss holes in my cheese.) The messages are complete unto themselves and a missed one is irrelevant. This also was unstated, but then I didn't consider it either. –  chux Aug 14 '13 at 22:36
@chux Cryptography and IT-Security in general is a subtle field :) If these are not problematic for you then it seems fine. Depending on the use case though B-Con is right that asymmetric might be a better choice. –  Perseids Aug 14 '13 at 22:49
I concur a digital signature (asymmetric keys) would be better than a MAC were it not for 3 things: A and B are cooperative, thus B would not forge a message, non-repudiation is not needed & the DS is about 2x as long as a MAC. I'll expand more in the Post. –  chux Aug 15 '13 at 2:13