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

51–60 of 103 posts

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

#51

Post by more_original »

tomp wrote: post #45
more_original wrote: post #43

Earlier quoted context omitted.

Well, if you have an internal collision hash(m1)=hash(m2) and both messages m1 and m2 are of the same size, then it seems that one would also get hash(m1|key|size) = hash(m2|key|size). So, I cannot really see how appending the size will help. (All subject to optimistic assumptions about block sizes, etc.)

In this sense, every hash function is equally unsafe, even HMAC.

Please substantiate. An attacker knowing an internal collision of the hash algorithm for m1 and m2 (of the same size...) can construct HMAC(m2,key) from HMAC(m1,key) without knowing the key?

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

#52

Post by simondlr »

Ralz wrote: post #42

I e-mailed visa about something similar with their new upcoming V.me service. They suggest that you use md5 to generate the tag which is known to be weaker than SHA-1. I was a little surprised that a company like Visa would mess up on crypto and not know to use HMAC instead of just a simple hash. Never heard a response from them either. Here's what their documentation says: Language Standard Syntax for Generating MD5…

The link: https://developer.v.me/docs/get_credentials

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

#53

Post by threedaymonk »

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…

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.

If the reader can't be bothered to read the article to the end, I hardly think it reflects on the author. Whilst it might indeed be a more concise article if it just said "don't use a hash function for message authentication, use HMAC", it would still miss the important final point about timing attacks, not to mention the journey of explanation about why you shouldn't just use a hash function.

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

#54

Post by pbsd »

threedaymonk wrote: post #53
pbsd wrote: post #50

Earlier quoted context omitted.

"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…

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. If the reader can't be bothered to read the article to the end, I hardly think it reflects on the author. Whilst it might indeed be a more concise article if it just said "don't use a hash function for message authentication, use HMAC", it wo…

You are correct, I shouldn't have tried to argue poor readership, that's just sloppy.

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

#55

Post by marshray »

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.

> accumulate the XORs of each offset of both strings and then verify that they add up to zero

If you do that in a language with an optimizing compiler or JIT runtime you'd better look at the generated code and/or do your own timing measurements. A sufficiently-smart optimizer could recognize that the first difference encountered allows for early loop termination.

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

#56

Post by ch0wn »

loeg wrote: post #4

Tl;dr: Use HMAC for Hash-based Message Authentication Codes and hash functions for hash functions. Don't use them the other way around. PS, maybe more developers should take an intro course on crypto.

+ don't compare secret strings in a manner that makes it possible to draw conclusions about the position of the inequality.

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

#57

Post by doomslice »

bemmu wrote: post #5

For the string comparison, could you really use that in a timing attack. Wouldn't the difference between comparison taking one char longer be measured in nanoseconds, while the overall network lag would be milliseconds?

This is just a guess on how you would do it... but it would involve making many many many requests until you could establish a mean against a given confidence level. Then you could compare that mean for each starting character (once again, many many many requests for each character). If the mean of any of them (or heck, even the distribution of the timings) differ than the others, then you know you you hit the right mark.

This assumes that 1: you can reliably measure at that small of a time difference and 2: you can submit enough requests without being detected.

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

#58

Post by quotemstr »

tptacek wrote: post #46
quotemstr wrote: post #34

Earlier quoted context omitted.

There's nothing wrong with Applied Cryptography so long as you _understand_ it. If you blindly apply outdated algorithms, yes, you lose. Everyone should read both Applied Cryptography _and_ the other books you mentioned, and keep up on the literature besides.

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.

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

#59

Post by cbsmith »

tptacek wrote: post #47
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…

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_pad + message))
It's that similar. The biggest non-security consequence is that you have to call your hash function twice. If that is a problem, you have bigger problems. If you are using a secure hash to authenticate a message, you should always use HMAC.

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

You're closer to addressing the real complexity involved in cracking it than the original article. I agree that in principle it isn't hard to break a naive hash-based digest authentication. I'm merely pointing out that it isn't simple.

Also... not sure why they'd have to use Ruby or why that is relevant...

> It is a very, very bad idea to put off fixing a problem like this because you've been led to believe by someone on a message board that MD padding is going to be an obstacle to attackers.

No. It's a very, very bad idea to ever go down this road in the first place. Start with a MAC. If you think you can be more clever than the collective expertise of the field, study cryptography and prove it, but until you've finished studying it, do what they say. History is littered with people who thought they knew just enough about cryptography that they could do things their own way without consequences (WEP anyone?).

In general I'm all for encouraging amateurs to compete with the pros, but cryptography is definitely one of those fields where it can appear deceptively simple to achieve your goals, and it totally, totally, totally is not.

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

#60

Post by ma2rten »

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?
Post reply on HN