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;


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


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?


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)$.

| improve this answer | |
  • $\begingroup$ 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? $\endgroup$ – Aaron Toponce Mar 22 '16 at 12:59
  • 1
    $\begingroup$ 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. $\endgroup$ – Aaron Toponce Mar 22 '16 at 13:01
  • 1
    $\begingroup$ 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. $\endgroup$ – malexmave Mar 22 '16 at 13:01

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.