# A simple keyed message authentication code using XOR

Suppose I have a key that is at least 32 characters in length and provides at least 128-bits of entropy. If I picked from the character set of [a-hjkmnp-z2-9-], then I know that each unambiguous character provides exactly 5 bits of entropy if built from a CSPRNG, such as /dev/urandom. Thus, a 32-character string would meet my requirements by providing 160-bits of entropy. Something like amjgg6d3e9v7makwad2y544qtz-wxu9x. Suppose also I have a 16-character base64 salt. Something like BGTH8iPYi16nJCCh.

Now, suppose I hash the concatenated password and salt with SHA-256(salt||password), giving hex string H1;

3b1a89849599a9a2b8ebfa34fb4f9ef7fc26093980fb49901d6670329fcc8da8


And suppose I hash the message "foo bar baz" with SHA-256 as well, giving hex string H2:

dbd318c1c462aee872f41109a4dfd3048871a03dedd0fe0e757ced57dad6f2d7


My question is this: Aside from the cryptographic strength resting on the entropy of the provided key, and the cryptographic strength of the hashing function, what is cryptographically weak with the MAC construction of H1 XOR H2, which provides the following as a hexadecimal string as a MAC?

e0c9914551fb074aca1feb3d5f904df37457a9046d2bb79e681a9d65451a7f7f


Assuming your authenticated message is public (which is reasonable), this scheme seems insecure for the following reason:

Your authentication tag $t$ over message $m$ is computes as

$$t=sha256(salt||key) \oplus sha256(m)$$

This means that any adversary knowing $m$ can compute a new authentication tag $t'$ for a message $m'$ in the following way:

$$t' = t \oplus sha256(m) \oplus sha256(m')$$

This will result in

$$t' = sha256(salt||key) \oplus sha256(m) \oplus sha256(m) \oplus sha256(m') = sha256(salt||key) \oplus sha256(m')$$

This is, by your definition, a valid authentication tag for $m'$.

You need to incorporate the message into the authentication tag in a non-reversible way. For example, HMAC does $h(k \oplus opad || h((k \oplus ipad) || m))$. This way, a new authentication token cannot be created without inverting the hash function $h$. (opad and ipad are fixed values that are used to ensure the keys are different at both positions)

Additionally, you would have to distribute your salt to the recipient somehow, and ensure that the adversary cannot change it. Otherwise, authentication will be impossible because the recipient cannot compute $sha256(salt||key)$.

• Hmm. Shouldn't it follow that a different tag, "t-prime" be valid for a different message "m-prime", regardless of the private key? I don't understand how your solution demonstrates a weakness in the construction. If "t-prime" distinct from "t" was a valid tag for the original message "m", then I would understand the problem. But I don't understand how a different tag for a different message is a weakness. I guess I'm missing something? – Aaron Toponce Mar 22 '16 at 12:59
• Nevermind. After working it through in my head further, I see the problem. A valid tag is created for a different message without knowledge of the key. Thanks. – Aaron Toponce Mar 22 '16 at 13:01
• Your authentication system should also authenticate who the message is from. The adversary is not interested in finding a second tag for your message, but a new one for his own. If your message is "pay 100 USD", an attacker could change it to "pay 1000 USD" and compute a valid authentication tag over the new message. To the recipient, this would be indistinguishable from you sending that 1000 USD message. – malexmave Mar 22 '16 at 13:01