Why you should never use hash functions for message authentication

This is a great essay on why you should never use a hash function for message authentication.<p>Except not for the reason the author thinks.<p>There are several problems here.<p>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 &#60; 64 bytes. A lot of "application state" fits pretty well in 64 bytes.<p>Secondly, unless a message ends right on the 64 byte boundary, it is not nearly that simple. You have a bit of a problem, because the hash is padded, and when you add extra characters to your original string, that padding gets <i>replaced</i> with those values. So, it's no longer simple to just "keep going" from where you stopped.<p>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 <i>before</i> those bytes, so not only did you change those 8 bytes, but you shifted them down a byte.<p>So, no, it isn't nearly that easy to crack a SHA-1 based authentication, and yet, it is easy enough that you should totally NOT use them for authentication and instead use HMAC ; they <i>are</i> vulnerable to extension attacks, 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.<p>It just turns out that cryptography is way more complicated, and even in terms of understanding weaknesses that arise from doing things wrong, you are going to get it wrong. Trust the experts, when they say it is a bad idea, but don't assume <i>why</i> it is a bad idea can be explained in a short blog article like this.<p><i>UPDATED</i>: Added an explanation as to why it might be dangerous to just take this article at its word.

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.<p>Here's what their documentation says:<p>Language Standard Syntax for Generating MD5 Hash Java import org.apache.commons.codec.digest.*; hash = DigestUtils.md5Hex(string1+string2+string3...); PHP $hash = md5($string1.$string2.$string3...); Ruby require 'digest/md5' hash = Digest::MD5.hexdigest(string1+string2+string3...) Python import md5 hash = md5.new(string1+string2+string3...)

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

&#62; Finally, you should make sure your application does not exit early if the tag is invalid. You should do all the data processing you would normally do, just short of modifying the database, and check the tag last. If you return early you risk another timing attack.<p>What kind of timing attack is that? In order for there to be a timing attack, there has to be a difference in the timings.<p>1. You can either process the data, check the authentication code, then commit.<p>2. Or you can check the authentication code, process the data, then commit.<p>I don't see any attacks on #2 that couldn't also work on #1.

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

The title is sort of linkbait, as in fact what it should be is "Never use hash functions vulnerable to extension attacks"... (And most common ones are) With that said, this stuff is pretty cool and after reading that the author learned all this in the Coursera Cryptography class I decided to sign up for it. (Starts June 11th)

&#62;&#62; This fact means that an attacker can determine the first correct character of the tag by submitting requests to a signed URL with a different first character in the tag each time, and stopping when the request takes a little longer than usual. After guessing the first character they can move onto the second, and so on until they’ve guessed the whole correct tag.<p>Wouldn't this attack be eliminated by using iptables rate limiting to reduce the attack window of opportunity?

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?

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

Stupid question: Whenever I've used GPG to sign an email, it includes a line saying "Hash: SHA1". Does this imply PGP-signed messages are vulnerable to this, or does PGP/GPG do something different/smarter?

One thing I'm slightly confused about here.<p>The article says:<p><i>"This sequence is then folded using a compression function h(). The details of the h() depend on the hashing function, but the only thing that concerns us here is that the compression function takes two message blocks and returns another block of the same size."</i><p>So if the chunks in a SHA-1 hash are 512 bits each then surely the output of the hash function would be 512 bits rather than the 160 bit digest?<p>Edit: the IV is 160 bits , so "another block of the same size" means each derivative block is the size of the IV <i>not</i> of the actual data.

RFC 2104 specifies how you should do it, see e.g. <a href="http://de.wikipedia.org/wiki/Keyed-Hash_Message_Authentication_Code" rel="nofollow">http://de.wikipedia.org/wiki/Keyed-Hash_Message_Authenticati...</a><p>The Handbook of Applied Cryptography, Chapter 9 (free online: <a href="http://cacr.uwaterloo.ca/hac/" rel="nofollow">http://cacr.uwaterloo.ca/hac/</a>) nicely explains the reasons.

In order for an extension attack, wouldn't the blocks have to align perfectly? Like suppose I hash [abcd][efgh][k]<p>How would you extend that?

tptacek or others with domain knowledge-<p>Is the timing attack hardening suggested in the blog post a standard approach?<p>If I was trying to attack a system and knew loosely that they did what he suggested (hashing then comparing vs comparing with timing exposed) , my untrained instinct would be that this is the weakest part. In other words I think this just makes the timing attack a little more difficult, but still possible, by producing specific hashes that carry out the timing attack.<p>When I've needed to harden comparisons against timing attacks, I've always just used constant time comparison functions, such as these -&#62;<p><a href="http://codahale.com/a-lesson-in-timing-attacks/" rel="nofollow">http://codahale.com/a-lesson-in-timing-attacks/</a> <a href="http://rdist.root.org/2010/01/07/timing-independent-array-comparison/" rel="nofollow">http://rdist.root.org/2010/01/07/timing-independent-array-co...</a>

Also, HMAC is just one MAC (message authentication code). OMAC and is another good one; it has the interesting property of being built on top of a block cipher instead of a hash function, which can reduce the number of "moving parts" in a system if you're using a block cipher of some sort anyway.

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?

what's wrong with hashing (message + secret) instead?

This seems to me like a variant of "do not trust the client." Good info though. I have learned a lot more about how hash algorythms work. I do wonder though if fixed-param hashes are relatively safe due to the inability to add suffixes.

If I remember correctly this was the same issue that Flickr had with their API calls at one point in time!