Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why you should never use hash functions for message authentication

blog.jcoglan.com

Post reply on HN
Print view View original

61–70 of 103 posts

Re: Why you should never use hash functions for message authentication

#61

Post by cbsmith »

jcoglan wrote: post #44
cbsmith wrote: post #35

This is a great essay on why you should never use a hash function for message authentication. Except not for the reason the author thinks. There are several problems here. First, with SHA-1 for example, you have 64 bytes per chunk. That means you basically get a free ride on this problem for anything Secondly, unless a message ends right on the 64 byte boundary, it is not nearly that simple. You have a bit of a probl…

Your point about padding and length bytes is spot-on. I actually left this out of the explanation, although it's interesting, because I felt it a useless diversion: something that's safe except in an easily describable subset of cases is still not fit for purpose when specially designed tools without these problems exist. Point being, although hash functions might work most of the time, their general construction doe…

> Your point about padding and length bytes is spot-on. I actually left this out of the explanation, although it's interesting, because I felt it a useless diversion: something that's safe except in an easily describable subset of cases is still not fit for purpose when specially designed tools without these problems exist.

I'm with you except for: "a useless diversion".

From the description in your article, I might think that if I have really short messages, I'm okay. I might think that if I reversed my strings, so any additional state is prepended instead of appended, I'd be okay. I might think that if I truncate my hashes (say, used the first 256 bits of SHA-512), I'd be okay. I'd be really, really wrong.

> Point being, although hash functions might work most of the time, their general construction does not make them safe for this purpose. You can't say something is 'mostly secure' because it works 'most of the time'. The times is doesn't work will affect someone, and for them the system is not secure at all.

That's the wrong point though. It's not that hash functions "might work most of the time". Uncompromised secure hash functions work all of the time for their intended purpose. For this other purpose, they work exactly none of the time.

The aspects I described that might make you think SHA-1 actually has this covered except for a few corner cases are trivial challenges for an attacker to overcome, as are all of the above "remedies" I mentioned (all of which resemble idiot moves that have in fact been made by naive developers who thought they could be clever and save themselves... I don't know.. maybe some CPU time?).

I do think the post was some great writing that illustrated an idea quite clearly. I think it could be quite informative for a lot of people. I just think what you wrote would benefit from being framed appropriately. I'd suggest a preface... something like, "HMAC's were invented to address the fact that you can't just use a hash for authentication. Somehow people miss this point, possibly because HMAC's seem like a trivial layer on top of a secure hash. In practice, there are a surprising variety of issues. To give you an idea of the kinds of problems you might run in to, and hopefully a sense that you can't just naively tweak your use of a hash to address them, I'm going to simplify a common problem with using secure hashes for authentication that has probably never occurred to you. I assure you that this problem is actually more complex, and there are many more problems."

Re: Why you should never use hash functions for message authentication

#62

Post by reitzensteinm »

tptacek wrote: post #13
spicyj wrote: post #10

> The easiest way to defeat this attack is, instead of directly comparing two strings, compare their mappings under a collision-resistant hash function. Is this really the best way to compare strings without giving away timing info?

No. It's A way to do it, but not the fastest or the simplest. An easier, faster way to do it is what Rails does (after Nate Lawson via Coda Hale told them how): accumulate the XORs of each offset of both strings and then verify that they add up to zero.

What's wrong with simply doing a traditional compare, but not exiting early when it's found the two strings don't match?

I see how the xor method works, but not why it's superior.

Also, it would seem that you'd be leaking information about the size of the other string with either method (whether you exit early or not when you run past the length of one of the strings) - not a problem when comparing hashes presumably, but is it never a concern?

I don't think you'd be leaking that information if you hashed both strings and compared the hash, because it wouldn't stop getting faster when the shorter string gets shorter.

Re: Why you should never use hash functions for message authentication

#63

Post by gchpaco »

reitzensteinm wrote: post #62
tptacek wrote: post #13

Earlier quoted context omitted.

No. It's A way to do it, but not the fastest or the simplest. An easier, faster way to do it is what Rails does (after Nate Lawson via Coda Hale told them how): accumulate the XORs of each offset of both strings and then verify that they add up to zero.

What's wrong with simply doing a traditional compare, but not exiting early when it's found the two strings don't match? I see how the xor method works, but not why it's superior. Also, it would seem that you'd be leaking information about the size of the other string with either method (whether you exit early or not when you run past the length of one of the strings) - not a problem when comparing hashes presumably,…

Compiler optimizations, CPU pipeline and branch prediction would be my guess, although I'm sure someone else can jump in with more detail. XOR is basically immune to optimized tricks.

Re: Why you should never use hash functions for message authentication

#64

Post by tptacek »

cbsmith wrote: post #59
tptacek wrote: post #47

Earlier quoted context omitted.

In practice, attackers just guess the bit length of the message by writing the Ruby script that generates the 100 candidate messages at different expected bit lengths and feeding them to their fuzzer. The bit length issue is not a real one in practice. In practice, length-extendable SHA-1 MAC functions are mechanically exploitable; they'll be discovered quickly by competent attackers who don't even have access to you…

There seems to be some kind of impedance. I'm not suggesting you can avoid using an HMAC and get away with just a hash. Let's be clear about what an HMAC is. It's pretty much what this article describes, but executed with a specific protocol that avoids exploitable weaknesses in naive approaches. It is literally: first_pad = a_constant_block ^ key second_pad = another_constant_block ^ key hash(second_pad + hash(first…

It's fine that you want to tell the thread what HMAC was, or point out that the exploit for this problem isn't literally 100 words of blog post long.

But the reality is that this is an exploit that everyone on our team, and I assume all our real competitors teams, are expected to be able to bust out on demand. It's not hard. It comes up a couple times a year in web apps, we spot it, and we exploit it. It's really not one of the more interesting or involved crypto flaws to exploit.

You wrote:

Still, you can see how that leaves a distinct subset of cases where you'd be exposed. SHA-1, along with most secure hash functions, appends the length of the message the end of the source text before performing the hash function. That means that if you add even one byte to the string, you have now changed the last 8 bytes that were fed in to the "original" hash function. Oh, and your extra byte goes in before those bytes, so not only did you change those 8 bytes, but you shifted them down a byte.

Well, respectfully, no shit. Was it your understanding that the Flickr team screwed their MAC up so badly that you didn't even have to guess glue padding to pull the attack off? You wrote this paragraph without context; you even followed it with a sentence about how you might be safer if you could fit your application state in a SHA1 message block because I forget why that could possibly matter?

Next time, when you want to point out how deceptive the apparent simplicity of a crypto concept is, choose one of the defender's problems. The attacker's problems are mostly deceptive in the opposite direction.

Re: Why you should never use hash functions for message authentication

#65

Post by tptacek »

quotemstr wrote: post #58
tptacek wrote: post #46

Earlier quoted context omitted.

No, there's a lot wrong with _Applied Cryptography_, and those things have very little to do with the fact that AC writes about IDEA and not AES. If you read _Practical Cryptography_, you don't need to read _Applied Cryptography_. AC is a book full of trivia, and of encyclopedia-style descriptions of random block ciphers with minimal attention given to the actual real-world attacks on implementations of those ciphers…

Paging through my copy of AC, I think you're right. I'd been a while since I read it. PC is indeed the better book.

Even Schneier has somewhat acknowledged how toxic AC turned out to be.

Re: Why you should never use hash functions for message authentication

#66

Post by tptacek »

cjg wrote: post #36
Mithrandir wrote: post #3

Number one thing I learned from the Coursera class: don't build your own crypto.

I've heard this said many times before and I agree. However, using crypto libraries does not solve the problem of vulnerabilities through cryptography misuse. For example, keys must be stored correctly, algorithms often need initialising in the correct mode for your specific application, IVs must not be repeated, and, as shown in this article, hashes should be used in specific ways to work correctly. There are many w…

This is the entire point of high-level crypto libraries, like Guttman's libcrypt and Google's Keyczar. So, yeah, don't use OpenSSL or javax::crypto or whatever .NET calls it; but, do consider using something like Keyczar, or, better yet, just use PGP/GPG to store data at rest, TLS for data in motion, and be done with it.

Re: Why you should never use hash functions for message authentication

#67

Post by tptacek »

ma2rten wrote: post #60

I was wondering about that timing attack. Is that really possible? How many requests would you have to make until you can get reliable statistics over the timing of a string comparison, when you have network delays, other requests and all kinds of stuff that influence timing?

It's very difficult, but possible. It's a plausible enough threat, especially if you're cloud hosted now or ever might be, that you should take steps to avoid it.

Jitter and confounding are problems that can be addressed simply by repeated measurements.

The rule-of-thumb from Crosby & Wallach's paper on remote timing attacks is, assume tens-to-hundreds of nanoseconds precision if you can colocate the attacker at the same provider, and tens of microseconds if you have to do it over the Internet.

Re: Why you should never use hash functions for message authentication

#68

Post by cbsmith »

tptacek wrote: post #64
cbsmith wrote: post #59

Earlier quoted context omitted.

There seems to be some kind of impedance. I'm not suggesting you can avoid using an HMAC and get away with just a hash. Let's be clear about what an HMAC is. It's pretty much what this article describes, but executed with a specific protocol that avoids exploitable weaknesses in naive approaches. It is literally: first_pad = a_constant_block ^ key second_pad = another_constant_block ^ key hash(second_pad + hash(first…

It's fine that you want to tell the thread what HMAC was, or point out that the exploit for this problem isn't literally 100 words of blog post long. But the reality is that this is an exploit that everyone on our team, and I assume all our real competitors teams, are expected to be able to bust out on demand. It's not hard. It comes up a couple times a year in web apps, we spot it, and we exploit it. It's really not…

I think I was pretty clear that extension attacks work. I was clear that they work despite features of a hash algorithm that would appear to address the issues highlighted in the article. I was also very clear that it is the defender's problems that are deceptively hard.

In a couple of cases I probably should have said "simple" instead of "easy". "Easy" implies more about effort than complexity. At some points I meant "little effort" and other points I meant "little complexity", but I used the same word for both, so that's bad.

Still, I don't get how you inferred the above from this, which to me reads as "any efforts you might make to address this problem your own way will almost certainly fail miserably":

It's just not nearly as easy as this article suggests, and conclusions one might draw from this article (like you can solve this problem by feeding all source text in to the hash algorithm backwards) are likely ill founded.

Re: Why you should never use hash functions for message authentication

#69

Post by tptacek »

cbsmith wrote: post #68
tptacek wrote: post #64

Earlier quoted context omitted.

It's fine that you want to tell the thread what HMAC was, or point out that the exploit for this problem isn't literally 100 words of blog post long. But the reality is that this is an exploit that everyone on our team, and I assume all our real competitors teams, are expected to be able to bust out on demand. It's not hard. It comes up a couple times a year in web apps, we spot it, and we exploit it. It's really not…

I think I was pretty clear that extension attacks work. I was clear that they work despite features of a hash algorithm that would appear to address the issues highlighted in the article. I was also very clear that it is the defender's problems that are deceptively hard. In a couple of cases I probably should have said "simple" instead of "easy". "Easy" implies more about effort than complexity. At some points I mean…

I think your comments have been misleading, so I corrected them. Nothing personal.

Re: Why you should never use hash functions for message authentication

#70

Post by cbsmith »

pbsd wrote: post #50
cbsmith wrote: post #35

This is a great essay on why you should never use a hash function for message authentication. Except not for the reason the author thinks. There are several problems here. First, with SHA-1 for example, you have 64 bytes per chunk. That means you basically get a free ride on this problem for anything Secondly, unless a message ends right on the 64 byte boundary, it is not nearly that simple. You have a bit of a probl…

"Never use a hash function for message authentication" is such a simplistic view. The author takes a common hash function design (Merkle-Damgard), and somehow extrapolates that hash functions should be simply ruled out for authentication. First, this may send the wrong message to the less-focused reader: "what, I should use block ciphers instead?". Luckily, HMAC is eventually brought up, which is a fine solution. HMA…

> Certain applications may find the overhead to be prohibitively high. With non-broken hash functions (e.g., any of the SHA-3 finalists), we can use the so-called envelope authenticator: A = H(K||M||K), with some padding to separate K from M to keep security proofs happy.

I think it is safe to say that you are suggesting a very narrow context. If invoking a hash twice is prohibitive and you are looking at choosing amongst SHA-3 finalists as an alternative (particularly given that many of them are slower than SHA-2, and I believe they are all slower than SHA-1 on low cost CPU's where you might expect this constraint), you are already talking about a very narrow performance window (literally one iteration of Moore's Law covers the gap). You then throw in that people are making refined selection of hash algorithms taking in to account various security nuances, and I think you are dealing not only with a narrow context, but a degree of cryptographic expertise that you don't have to worry that anyone solving it would be consulting this blog or Hacker News in general. ;-)

Post reply on HN