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

51–60 of 133 posts

Re: Speed Hashing

#51

Post by mistercow »

nooop wrote: post #43
mistercow wrote: post #34

>A given hash uniquely represents a file, or any arbitrary collection of data. At least in theory. It really bothers me when people misuse "in theory" like that. "In theory" means "we have a model that makes good predictions in some circumstances, but there are cases where it may fall short". But a model in which hashes uniquely represent arbitrary collections of data is a model which allows for infinite compressibil…

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 (which I can do because the set of strings is countable) until I find one that satisfies `h(x) == y`. Impractical, yes, but allowed by the theory, and that means the theory is invalid.

Re: Speed Hashing

#52

Post by pbsd »

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…

The first question is an open one. Not even theoretical cryptography people understand collision resistance very well. From a practical standpoint, though, we know that it can be pulled off reasonably fast; SHA-256 is still standing, for example, and it "only" takes 14 cycles per byte hashed. Not great, but not bad either.

The first written mention of artificially slowing down key derivation was (AFAIK) here: https://www.schneier.com/paper-low-entropy.html The rationale was that, given a key (resp. password) that gives you s bits of security, you apply some function that gives you extra t bits of security, by making bruteforcing it 2^t times more expensive.

Also note that some applications of hash functions don't care about collisions. MD5 is still OK-ish for e.g. HMAC, where what matters is second-preimage resistance.

Re: Speed Hashing

#53

Post by donpark »

Where to store the salt is that's where the real problem is.

It doesn't really matter how much encryption and hashing we throw at anything if everything is stored on the same server.

What's the point of salt if salt is in plain sight?

What's the point of asking users to verify hash of downloadable files when hash is stored along side the file itself?

What's the point of cryptography when code points straight to all that's necessary to dispell the protection?

Ultimate shame is that we still lack the necessary infrastructure for minimum level of security despite all the cloud-related hype, leaving each server to stand-alone which is no security at all.

Re: Speed Hashing

#54

Post by cperciva »

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…

Strongly collision-free hash functions are generally in the range of 5-20 clock cycles per byte of data on modern hardware. It's significantly slower than memcpy, but probably significantly faster than your network.

Re: Speed Hashing

#55

Post by randombit »

afhof wrote: post #3

One very curious thing to me is that for the upcoming SHA-3 standard, Wikipedia lists the cycle timings for each hash method. I would have thought that slower hashing speed would be a good thing, but the faster the candidate algorithm the better it appears. Perhaps the faster the hash is easier implement in hardware / less power for embedded devices?

He is referring to password hashing where brute forcing is an issue. For a cryptographic hash function, the goal is to be as fast as possible while retaining security. There is currently an intensive competition between the SHA-3 teams to produce the fastest implementations. Check out http://bench.cr.yp.to/results-sha3.html for more performance data on a range of machines.

It's not always the case that a hash that is faster in software is easier or cheaper to implement in hardware. For instance Skein is very fast on x86-64 but apparently is less competitive in low power hardware implementations.

Re: Speed Hashing

#56

Post by khafra »

eruquen wrote: post #49

Nobody mentioned pepper yet. Not the "static salt" variant which you might find while googling. That is just more security by obscurity. I'm talking about adding a random string of fixed length characters to the (salted) password that is not saved anywhere. At login, it requires a bit of brute-forcing on the server to check the hash since we have to go trough all possible pepper strings. This adds a few ms (e.g. with…

> Now, on the attacker's side the picture looks drastically different. The amount of time required to brute-force through the already salted hashes grows exponentially with the length of the pepper string.

That isn't drastically different. The amount of time required scales exponentially with the pepper string for both the attacker and the legitimate authentication server. Not really different from increasing the work factor with bcrypt; and not as cool as increasing the circuit size with scrypt.

Re: Speed Hashing

#58

Post by rmc »

lysium wrote: post #22

While long and random passwords are a good thing, there are still applications that make that very difficult to use. I'm looking at you, Apple AppStore, letting me choose a new password after only the second wrongly-entered, disallowing copy&paste on that website to enter the new password, requiring JavaScript on that website to enforce the no-copy&paste rule and then not showing me the characters I enter. That's rid…

If you are using long passwords, you don't need to use purely random text, you can use a phrase.

Re: Speed Hashing

#59

Post by judofyr »

donpark wrote: post #53

Where to store the salt is that's where the real problem is. It doesn't really matter how much encryption and hashing we throw at anything if everything is stored on the same server. What's the point of salt if salt is in plain sight? What's the point of asking users to verify hash of downloadable files when hash is stored along side the file itself? What's the point of cryptography when code points straight to all t…

> What's the point of salt if salt is in plain sight?

If you by "plain sight" mean "the same place as the hash" you're misunderstanding what the salt is for. If you want to access X servers in order to verify a password, you don't need a salt; you just split the hash in X parts and store each on different servers.

Salts are for preventing rainbow tables.

Re: Speed Hashing

#60

Post by romaniv »

What about appending a significantly long random string to all passwords? Would that slow down re-computation of hashes significantly enough to thwart brute-force attacks? I don't know enough about GPU architecture to tell for sure.
Post reply on HN