3 ms·

I disagree: it is insecure even if you use a perfect hash function. This is because the construction itself is vulnerable to collisions, whereas HMAC requires 2

I disagree: it is insecure even if you use a perfect hash function. This is because the construction itself is vulnerable to collisions, whereas HMAC requires 2nd-preimage attacks (as far as we know today, modulo any advances in the multicollision work of Joux and Kelsey for long messages, YMMV). In other words, if you use a secure 128-bit hash algorithm (not MD5!) with HMAC, you get approximately 128-bit security. If you use the same hash with "secret suffix", you get 64-bit security. Quite a loss of security for no gain. Additionally, hashes often fall to collision attacks long before 2nd-preimage attacks. So you've maximally exposed yourself to the leading edge of attacks. Not a good plan. In summary, today the following MAC approaches for short messages (say, cookies) have approximately this level of security: SHA256-HMAC: 2^256 SHA256-SecretSuffix: 2^128 SHA1-HMAC: 2^160 SHA1-SecretSuffix: 2^53 (versus 2^80 originally) MD5-HMAC: 2^128 MD5-SecretSuffix: 30 seconds on a laptop

cperciva 17y ago
I wrote: If you use a non-broken hash ... then the attacks Nate describes are harmless. You wrote: the construction itself is vulnerable to collisions. These two statements do not contradict each other. A hash function for which it is feasible to find collisions is considered by the cryptographic community to be broken. hashes often fall to collision attacks long before 2nd-preimage attacks. So you've maximally exposed yourself to the leading edge of attacks As I said -- H(m || k) is insecure with a broken hash function, while HMAC(k, m) remains secure unless the underlying hash fails catastrophically. Someone who uses SHA256(m || k) as a MAC is taking an unnecessary risk, but it's not an immediate security flaw.
- NateLawson 17y ago
  To be clear, we are using the cryptographic definition of "broken": a cipher or construction with known attacks faster than the best theoretical strength We both agree that the highest theoretical strength for collision resistance in a hash function is the birthday paradox, which takes sqrt(2^n) work. So if a collision attack is found that is faster, the hash algorithm is considered "broken". But the H(m || k) construction is broken compared to HMAC by the same definition, no matter how secure the underlying hash function. Out of the gate with a perfect hash, you're reducing the strength from 2^n to 2^(n/2). If a 2nd-preimage attack was discovered for SHA256 that reduced the effort from 2^256 to 2^128, we would both agree that it is broken for use with HMAC (among other things). This, of course, says nothing about the practicality of a 2^128 search, but cryptographically, SHA256-HMAC would be broken. So why would you call a construction that always has the same effect as such a momentous discovery not "broken"?
  - cperciva 17y ago
    So why would you call a construction that always has the same effect as such a momentous discovery not "broken"? I didn't say that H(m || k) wasn't broken. I said that it wasn't necessarily insecure. :-)
  - NateLawson 17y ago
    Ok, I think we agree on that: "broken" doesn't necessarily mean it is feasible to attack. Another example I thought of is truncated HMAC. This is where the output of an HMAC is truncated to meet some space constraint. For example, you might have an embedded device that is now using SHA256-HMAC but you have a legacy need to store the result in 160 bits (due to a hard-coded packet size designed originally for SHA-1). Let's compare this to SHA256-SecretSuffix with no truncation. Comparison of space used in packet versus the work required to attack each approach: SHA256-HMAC-Truncated160: 160 bits, 2^160 SHA256-SecretSuffix: 256 bits, 2^128 Thus even though it uses less space, a truncated SHA256-HMAC is more secure than a full size SHA256-SecretSuffix authenticator. I think this also illustrates that SHA256-SecretSuffix as a construction is broken.
    - cperciva 17y ago
      There's lots of good reasons to not use H(m || k) -- I'm not going to argue with you there. I just don't want people to say "oh my god, Nate says that what I'm doing is insecure, I'd better fix it ASAP" -- and possibly introduce far worse problems in their panic -- if what they're doing is dumb but not necessarily insecure... hence my pointing out that the insecurity of H(m || k) depends on whether the hash function is broken.
      - tptacek 17y ago
        So basically you're saying that if they're using SHA-256 H(m||k), they shouldn't worry, and you want to make that clear. I'll tell you what: I bet you $50 that we can find 5 examples of H(m || k) MACs on Google code search, and that none of them will use an "acceptably" secure hash function. I'd really like to bet that you simply will - not - be - able - to - find an H(m || k) MAC that uses a hash function that is survivable in that configuration, but proving that would take too long. I think I can win that other bet inside of an hour. If there are no real-world systems that could possibly be secure in the H(m || k) configuration, I'm left wondering why you're sticking up for it, other than to be pedantic. Being pedantic about security on Hacker News is my job, Colin, not yours. I know you feel like you're just being academically precise in this conversation, but what you're really doing is creating a subtext that SHA1 is survivable in H(m || k) configurations, and that this is really just an example of "how broken MD5 is".

cperciva 17y ago

I wrote: If you use a non-broken hash ... then the attacks Nate describes are harmless. You wrote: the construction itself is vulnerable to collisions. These two statements do not contradict each other. A hash function for which it is feasible to find collisions is considered by the cryptographic community to be broken. hashes often fall to collision attacks long before 2nd-preimage attacks. So you've maximally exposed yourself to the leading edge of attacks As I said -- H(m || k) is insecure with a broken hash function, while HMAC(k, m) remains secure unless the underlying hash fails catastrophically. Someone who uses SHA256(m || k) as a MAC is taking an unnecessary risk, but it's not an immediate security flaw.

NateLawson 17y ago
To be clear, we are using the cryptographic definition of "broken": a cipher or construction with known attacks faster than the best theoretical strength We both agree that the highest theoretical strength for collision resistance in a hash function is the birthday paradox, which takes sqrt(2^n) work. So if a collision attack is found that is faster, the hash algorithm is considered "broken". But the H(m || k) construction is broken compared to HMAC by the same definition, no matter how secure the underlying hash function. Out of the gate with a perfect hash, you're reducing the strength from 2^n to 2^(n/2). If a 2nd-preimage attack was discovered for SHA256 that reduced the effort from 2^256 to 2^128, we would both agree that it is broken for use with HMAC (among other things). This, of course, says nothing about the practicality of a 2^128 search, but cryptographically, SHA256-HMAC would be broken. So why would you call a construction that always has the same effect as such a momentous discovery not "broken"?
- cperciva 17y ago
  So why would you call a construction that always has the same effect as such a momentous discovery not "broken"? I didn't say that H(m || k) wasn't broken. I said that it wasn't necessarily insecure. :-)
- NateLawson 17y ago
  Ok, I think we agree on that: "broken" doesn't necessarily mean it is feasible to attack. Another example I thought of is truncated HMAC. This is where the output of an HMAC is truncated to meet some space constraint. For example, you might have an embedded device that is now using SHA256-HMAC but you have a legacy need to store the result in 160 bits (due to a hard-coded packet size designed originally for SHA-1). Let's compare this to SHA256-SecretSuffix with no truncation. Comparison of space used in packet versus the work required to attack each approach: SHA256-HMAC-Truncated160: 160 bits, 2^160 SHA256-SecretSuffix: 256 bits, 2^128 Thus even though it uses less space, a truncated SHA256-HMAC is more secure than a full size SHA256-SecretSuffix authenticator. I think this also illustrates that SHA256-SecretSuffix as a construction is broken.
  - cperciva 17y ago
    There's lots of good reasons to not use H(m || k) -- I'm not going to argue with you there. I just don't want people to say "oh my god, Nate says that what I'm doing is insecure, I'd better fix it ASAP" -- and possibly introduce far worse problems in their panic -- if what they're doing is dumb but not necessarily insecure... hence my pointing out that the insecurity of H(m || k) depends on whether the hash function is broken.
    - tptacek 17y ago
      So basically you're saying that if they're using SHA-256 H(m||k), they shouldn't worry, and you want to make that clear. I'll tell you what: I bet you $50 that we can find 5 examples of H(m || k) MACs on Google code search, and that none of them will use an "acceptably" secure hash function. I'd really like to bet that you simply will - not - be - able - to - find an H(m || k) MAC that uses a hash function that is survivable in that configuration, but proving that would take too long. I think I can win that other bet inside of an hour. If there are no real-world systems that could possibly be secure in the H(m || k) configuration, I'm left wondering why you're sticking up for it, other than to be pedantic. Being pedantic about security on Hacker News is my job, Colin, not yours. I know you feel like you're just being academically precise in this conversation, but what you're really doing is creating a subtext that SHA1 is survivable in H(m || k) configurations, and that this is really just an example of "how broken MD5 is".