Beware the hash reset attack

re: Beware the hash reset attack

Nick Parker — Wed, 19 May 2004 15:28:00 GMT

Very interesting, I wonder how often people check the file size along with the hash result to confirm the validity of their document.

re: Beware the hash reset attack

Keith Moore [exmsft] — Wed, 19 May 2004 15:38:00 GMT

MD5 (and most other hash algorithms I've studied) pads the message to an integral number of blocks. This padding includes the length of the original message, so I really don't see how this attack could possibly work.

re: Beware the hash reset attack

Keith Moore [exmsft] — Wed, 19 May 2004 15:40:00 GMT

{Replying to my own post...}

If len(alternate) + len(reset garbage) was exactly 2^64 (bits), then the reset could work, but I think people would notice this extra data.

re: Beware the hash reset attack

Raymond Chen — Wed, 19 May 2004 15:52:00 GMT

If the length is just encoded in the padding, then just act as if the original message were pre-padded with its original length (so MD5 won't add its own padding). Pad your replacement message, and (due to the block nature) the garbage will necessarily be a multiple of the block size, so no padding necessary there.

re: Beware the hash reset attack

Keith Moore [exmsft] — Wed, 19 May 2004 16:07:00 GMT

Hmmm... I don't think this would work. MD5 *always* pads, and *always* includes the message bit length in the padding, even if the message is already a multiple of the block length.

You're trying to reset MD5 back to its initial state. Part of that state is the bit length of the message (stored in a 64-bit integer).

re: Beware the hash reset attack

Eric Lippert — Wed, 19 May 2004 16:13:00 GMT

Here are some interesting notes on MD5.

http://www.rsasecurity.com/rsalabs/node.asp?id=2253

To my knowledge, no MD5 collisions have been found yet. Apparently in 1994 researchers estimated that brute-forcing a hash collision would take $10 million dollars of equipment 24 days. Assuming Moore's law, and inflation that would be about $200000 worth of equipment today -- and that's to find A collision, not a particular collision that has evil properties.

But of course, that's conjecture, not proof. When I did the hashing algorithm for code signing on Windows Script Files I included the length of the file in the hash -- it's the right thing to do, because we don't know for SURE whether the algorithm is effectively unbreakable.

re: Beware the hash reset attack

Raymond Chen — Wed, 19 May 2004 16:18:00 GMT

Ah, you're right, Keith; I missed that the size is *always* appended.

re: Beware the hash reset attack

Keith Moore [exmsft] — Wed, 19 May 2004 16:28:00 GMT

The reset is still possible (in theory) -- it would require 2 exabytes of data to do it.

re: Beware the hash reset attack

Jim Davis — Wed, 19 May 2004 17:02:00 GMT

I'd like to think that would be noticable.

"Say... this Half-Life mod is **HUGE**."

re: Beware the hash reset attack

Cooney — Wed, 19 May 2004 17:55:00 GMT

> Heck, maybe what really happened was that somebody on the deployment got their MR2 into a car accident...

Not that hard to do in Seattle - midengine car + rain + some more rain = hours of fun.

re: Beware the hash reset attack

josh — Wed, 19 May 2004 22:35:00 GMT

istm that the possibility of something in the datastream causing the hash to reset would be a major flaw in the code. The only case where that might be reasonable is if you had multiple files in one stream, and then you'd get two files and two hash values out, which defeats the point of this attack. Presumably whatever else you're operating on the stream with will "reset" at this point too, or you have a bug there.

So how can this possibly happen?

re: Beware the hash reset attack

Raymond Chen — Wed, 19 May 2004 22:52:00 GMT

True, resettability would be a flaw in the algorithm, but algorithms have been known to be found flawed years after their development. My point is that with a tiny amount of additional work, you can significantly reduce your exposure if such a flaw were to be found.

re: Beware the hash reset attack

asdf — Wed, 19 May 2004 23:10:00 GMT

Are you saying to store the file length as part of the stream (so the algorithm hashes it also), to store the original file length in addition to the hash, or to do something else with the hash and file length?

re: Beware the hash reset attack

Raymond Chen — Wed, 19 May 2004 23:24:00 GMT

Save both the hash and the original file size.

re: Beware the hash reset attack

Shawn — Thu, 20 May 2004 01:28:00 GMT

I wrote a bit about this back in March (http://blogs.msdn.com/shawnfa/archive/2004/03/05/84799.aspx) -- its an interesting attack, but as you pointed out, its very easily mitigated by simply knowing anything else about the data being hashed.

re: Beware the hash reset attack

Raymond Chen — Thu, 20 May 2004 01:51:00 GMT

Oops, sorry, Shawn. Looks like my article is pretty much identical to yours!

re: Beware the hash reset attack

Jeremy Hilliker — Thu, 20 May 2004 18:13:00 GMT

> Next, generate the bytes necessary to "reset" the engine.

Finding these bytes is as dificult as finding a message which will match the original.

Start with hash algorithm that is preimage, and second preimage resistant, otherwise it isn't useful in the first place. Given this, you want to find a string that will "reset" the algorithm to its initial state. Assume that you can do this, then you have found a message which will hash to the algorithm's initial state. IE, you have found a message which hashes to an given hash value. IE, your algorithm is not preimage resistant, which contradicts the initial statement. Therefore your assumption is false. Therefore you cannot find the string that will "reset" the algorithm.

I only see this attack as being usefull against an algorithm that is not already preimage resistant -- which means that it was broken in the first place.

Am I missing something here? Or are you allowing for broken implementations of the algorithm which can be reset?

re: Beware the hash reset attack

Michael Grier [MSFT] — Mon, 24 May 2004 06:13:00 GMT

The original context of the internal discussion was around proper use of hash functions and what you should and shouldn't use them for.

The secure hash functions in use were designed to ensure that messages could not be easily tampered in transmission.

One of the big differentiating factors between the secure hashes and other digest methods like checksums and CRCs is that they're intended to be "cryptographically hard" to "break". I'll leave "cryptographically hard" mostly undefined as some sort of reference to an NP-complete type of problem like curve fitting or factoring. Specifically, it's easy to stay ahead of the brute-force solutions by extending sizes. I will define "break" as the ability to, with little or no effort, product another byte stream with the same hash value.

Checksums, parity, CRCs and simple hashing algorithms like the ones you could find in any textbook are /insecure/ hashes. Meaning that they vary sufficiently for a typical data set but they also explicitly don't attempt to make "breaking" the hash difficult. My personal favorite string hash function { hash = 0; for (i=0; i<l; i++) hash = (hash * prime) + string[i]; return hash; } is trivially breakable.

Back to the original topic, there are a lot of people who want to have a pseudokey/hash where they can use it in a searching algorithm /instead/ of actually comparing the data. Well it's true that if the hash values are different there's no possible way that the bytestreams are equal, but that in no way implies that the pseudokeys being equal means that the bytestreams are equal.

Which then comes back to the point. What are you going to do with this? I personally feel that this falls into the category of "if it doesn't actually have to work right, I can make it as fast as you like".

Secure hashes are great for their intended use. Given a message which must conform to some syntactic requriements (readable English, XML, ASN.1, whatever), it is computationally difficult to construct a message which still fits the syntactic requirements, has the same hash value and is different from the original message /in a useful way/.

If you can change the message from "send the troops through the northern pass" to "send the troops via the southern river valley" easily, man, you're in trouble. If the end result looks more like "send the troops via the southern river valley <big honking string of unreadable text>send the troops through the northern pass", well, it's pretty obvious that there was tampering and the hash has accomplished its task.

Expecting these algorithms to stand for arbitrary unformatted data is actually not reasonable in the long run. The birthday effect is likely to show its head before too long.

Expecting these algorithms to give you a unique enough number that you don't have to worry about collisions in a context which requires correctness is also unreasonable.

Which then leads me to the point that if all you want is statistical uniqueness in order to decrease the number of times you have to compare byte streams that are different, you can use a significantly (computationally)
cheaper hashing algorithm than one of the secure hash algorithms.