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

Speed Hashing

codinghorror.com

Post reply on HN
Print view View original

131–133 of 133 posts

Re: Speed Hashing

#131

Post by emboss »

codinghorror wrote: post #46
pbsd wrote: post #26

Earlier quoted context omitted.

Secure hashes need to be fast. If you look at the ongoing SHA-3 competition, you will see an enormous focus on speed, on both software and hardware. Why do they need to be fast? They're used everywhere . Opening up notepad.exe, you'll verify a handful of digital signatures, each of which will compute a hash of the binary as first order of business. HMAC is used in virtually every secure network protocol worth using -…

I guess what I don't fully understand is just how computationally intensive (slow) a hash needs to be to produce a reliable fingerprint, that is, one that is as collision free as possible and extremely sensitive to any tiny change in the source data. I do understand that password related hashes may have arbitrary computational delays added just to make them tougher to brute force, which would be bad in many other (al…

Maybe the question is asked from the wrong perspective - it's not that designers of cryptographic hash functions ask themselves "Hmm, so how fast/slow do we want this thing to be?".

They go the other way round and set a "security parameter" that should hold for a particular instance (all the parameters fixed) of their algorithm. That "security parameter" determines how hard it should be for an arbitrary adversary to break the scheme by brute force, and in addition the scheme is only thought to be secure if there is no polynomial time algorithm that can break it in time significantly less than the brute force algorithm would take.

Given such a security parameter, the art is then typically to design the fastest primitive that upholds this same security margin. For example, if two (unbroken) algorithms would take O(2^80) for a brute force Birthday Attack, then you'd conceive the faster of the two as the "better" algorithm. ("Fast" of course can be subjective, e.g. fast in HW or fast in SW etc.)

For one thing, that's simply just because making an algorithm slower is always possible (PBKDF2), but in practice there are a lot of applications (probably more) where a hash should be as fast as possible rather than as slow as possible, as in digital signatures for example.

Re: Speed Hashing

#132

Post by nooop »

mistercow wrote: post #51
nooop wrote: post #43

Earlier quoted context omitted.

It does not allow infinite string compression, because you obviously have to store the original data. For hashes of good length and quality, the theory stands. I would even use MD5 and say the theory stands for non-critical every day uses given there is no attacker.

> It does not allow infinite string compression, because you obviously have to store the original data. Nope. Say you have a hash function `h` which guarantees a unique, 128-bit output for any input. Then `h` is a function which compress any string into 128-bits: If `y = h(x)` then it is trivial for me to write a program that will reconstruct `x` from `y`. I will simply iterate `x` through the possible input strings…

By your very own definition, "In theory" means "we have a model that makes good predictions in some circumstances."

If I let "some circumstances" be "non critical use with no attacker" and the model be "very very very very very very very very very very very very very low probability of collision when applied on pre-existing files", I don't see any problem.

The problem is that you were commenting the article using an absurdly geek point of view, interpreting each sentence as it had a very strict mathematical meaning.

In the real world, peoples sometime do misuse the language a little with the resulting sentences being easier to understand for everybody. That is generally not a call for a smart people to point out that when translated word by word (i.e. when poorly translated) using quantifiers, the statement is mathematically false. Especially when everybody on earth understand that use of "in theory" in the first place.

If Jeff wanted to make a mathematical article, he probably had written mathematical statements in the first place.

If every time you see the world "theory" you are feeling you should correct the one using it by telling him about corner cases he very probably already knows about their existence in the first place, you will loose a lot of time for a lot of non-constructive comments.

Post reply on HN