Speed Hashing • Hacker News Board

Re: Speed Hashing

#111

Post by donpark » Fri, Apr 06, 2012, 6:58 PM UTC

mistercow wrote: post #68

donpark wrote: post #62

Earlier quoted context omitted.

It doesn't matter if the hash is split into X parts and stored on X servers. We are not talking about Humpty Dumpty here and salt-specific rainbow tables can be built on-demand as long as the reward justifies the time and expense.

Of course they can, but the point is that the time and expense is massively increased. Building a rainbow table to run against each separately salted account is way more work than building a single rainbow table and cross referencing it with a giant list of hashes to find some collisions. In general "as long as the reward justifies the time and expense" can be said about any security measure. Salting has another bene…

Yes, user-specific salt does raise the cost but given the usual length and complexity of passwords in-use IRL, raise is not massive enough for high security servers.

Besides, the point of my original comment was the problem of placing everything in the same basket which includes the code used to hash passwords and files. How would you protect them?

Re: Speed Hashing

#112

Post by haberman » Fri, Apr 06, 2012, 7:05 PM UTC

cperciva wrote: post #54

codinghorror wrote: post #46

Earlier quoted context omitted.

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.

Correct me if I'm wrong, but my understanding is that cryptographic and non-cryptographic hash functions have similar avalanche properties (and therefore similar probability of accidental collision); the difference is just that cryptographic hash functions make it difficult to intentionally create a collision.

Is that right?

Re: Speed Hashing

#113

Post by cperciva » Fri, Apr 06, 2012, 8:43 PM UTC

haberman wrote: post #112

cperciva wrote: post #54

Earlier quoted context omitted.

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.

Correct me if I'm wrong, but my understanding is that cryptographic and non-cryptographic hash functions have similar avalanche properties (and therefore similar probability of accidental collision); the difference is just that cryptographic hash functions make it difficult to intentionally create a collision. Is that right?

Good non-cryptographic hash functions have "good" avalanching behaviour, but the definition of "good" depends on how randomly you expect your inputs to behave and how much a collision costs you. In hash tables, for instance, people often use quite weak -- i.e., poorly avalanching -- hashes since the cost of a collision is quite low.

Probably the best way to phrase it is that non-cryptographic hash functions cover a continuum with checksums at one extreme and cryptographic hash functions at the opposite extreme.

Re: Speed Hashing

#114

Post by romaniv » Fri, Apr 06, 2012, 8:43 PM UTC

glogla wrote: post #64

romaniv wrote: post #60

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.

Not really. The reason why longer passwords take long is not a property of the GPU or computation, it is because there are many more possible passwords as the length increases and you have to try sizable portion of them. For example, there are (to make the math simple) 10 000 four number pins (0000, 0001, ... 9999). However, if you append 4 to every pin, you have made them longer, but there are still 10 000 of them,…

I was thinking more along the lines of somehow forcing certain space complexity on every hash computation so it can't be as easily parallelized.

However, I see that my exact reasoning in the post above is not solid. Having longer strings as the final result of password comparison is irrelevant, because they are not part of the brute-force computation in the first place.

Re: Speed Hashing

#115

Post by tzs » Fri, Apr 06, 2012, 9:42 PM UTC

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…

That is indeed annoying. As a work around, if you use a browser or browser extension that lets you modify the DOM on the fly, you can disable the paste blocking. For instance, in Safari, use "Inspect Element" on the password field, find the onpaste="..." attribute, double click the onpaste and change it to something that isn't a valid event name.

You can then paste in the password field.

It should be reasonably possible to make a bookmarklet that goes through all form elements on a page and does this automatically to all that have onpaste handlers, so you don't have to bust open the inspector and dick around every time you want to log in.

Re: Speed Hashing

#116

Post by jlebar » Fri, Apr 06, 2012, 10:29 PM UTC

codinghorror wrote: post #19

judofyr wrote: post #9

Nitpicks. It seems that he's talking about password hashing: > "Hashes are designed to be tamper-proof". Wrong. Cryptographically secure hash functions are. > "Hashes, when used for security, need to be slow." Wrong. Password hashes needs this; not SHA1/MD5 etc.

Well, I'd say a hash that has no need whatsoever to be tamper-proof (no attackers, ever) and cares only about speed is a checksum -- so maybe a terminology issue. I agree there are certainly other uses for hashes, just trying to distinguish between hashes and checksums. Re-reading what I wrote, I open with "Hashes are a bit like fingerprints for data. A given hash uniquely represents a file, or any arbitrary collecti…

> Well, I'd say a hash that has no need whatsoever to be tamper-proof (no attackers, ever) and cares only about speed is a checksum -- so maybe a terminology issue.

Cityhash, spookyhash, and murmurhash are three modern non-cryptographic hash functions which explicitly don't call themselves "checksums".

Indeed, we say "hashtable", not "checksumtable".

Re: Speed Hashing

#117

Post by dpark » Sat, Apr 07, 2012, 12:32 AM UTC

donpark wrote: post #110

dpark wrote: post #76

Earlier quoted context omitted.

> What's the point of salt if salt is in plain sight? To prevent rainbow tables and to increase attack complexity. And to prevent someone who sees a hash from being able to drop it into a search engine and get the password (works for unsalted common passwords). The point of salt has never been secrecy. > What's the point of asking users to verify hash of downloadable files when hash is stored along side the file itse…

Your answers make sense in the context of servers for websites with low security needs, where privacy is of higher concern than security. They do not make sense for servers with high security needs.

I'm sorry, but you are simply incorrect. Salt is not a piece of secret data. Period. That was never the intention of salt, and it still is not. Secrecy of the salt does not improve its usefulness.

As for the download hash, this has nothing to do with security at all, as I already said.

Re: Speed Hashing

#118

Post by donpark » Sat, Apr 07, 2012, 2:36 AM UTC

dpark wrote: post #117

donpark wrote: post #110

Earlier quoted context omitted.

Your answers make sense in the context of servers for websites with low security needs, where privacy is of higher concern than security. They do not make sense for servers with high security needs.

I'm sorry, but you are simply incorrect. Salt is not a piece of secret data. Period. That was never the intention of salt, and it still is not. Secrecy of the salt does not improve its usefulness. As for the download hash, this has nothing to do with security at all, as I already said.

Re salt, please see project-rainbowcrack.com as an example of CUDA-driven hash cracking.

Re download hash, I think we disagree on what data integrity means. By data integrity, I mean trustworthiness which implies security, meaning file content hasn't been modified in-storage or in-transit. I'm guessing you are using those words to mean protection against transport-errors or typos (credit card entry) for which checksum is commonly used.

Given that HTTP is still the most common transport for file download and it's a reliable transport, file-hashing for transport-errors detection is I think meaningless. I know some browsers failed to report errors but comparing length is typically suffice to catch this.

That leaves only file-hashing as protection against tempering in-storage or in-transit which is why I am saying it's security-related. Keyed-hashing can mediate but, unfortunately, is not commonly used as it requires PKI.

Re: Speed Hashing

#119

Post by dpark » Sat, Apr 07, 2012, 2:56 AM UTC

donpark wrote: post #118

dpark wrote: post #117

Earlier quoted context omitted.

I'm sorry, but you are simply incorrect. Salt is not a piece of secret data. Period. That was never the intention of salt, and it still is not. Secrecy of the salt does not improve its usefulness. As for the download hash, this has nothing to do with security at all, as I already said.

Re salt, please see project-rainbowcrack.com as an example of CUDA-driven hash cracking. Re download hash, I think we disagree on what data integrity means. By data integrity, I mean trustworthiness which implies security, meaning file content hasn't been modified in-storage or in-transit. I'm guessing you are using those words to mean protection against transport-errors or typos (credit card entry) for which checksu…

How does pointing to rainbow tables indicate that salt should be secret? That's one of the things that salt prevents, and it does it without being secret. A 32-char random salt could be publicly published for each of your users and it would still do its job. Secrecy doesn't matter.

Data integrity is not trustworthiness. Data integrity means I got what you said I should get, not that you are trustworthy (and therefore I can trust what I got from you). If you want secure assurance that you got what I really sent, then you need secure assurance that I am who I say I am, and no hash will get that. You need a signed file (or hash). A hash by itself is indeed nothing but a robust a checksum in this case.

There's no point in arguing about the md5 for downloads. You're assuming that it's for security, and it's really not. It's primarily for people who are paranoid about corruption. It is also useful for validating when downloading from a mirror, though.

Re: Speed Hashing

#120

Post by tptacek » Sat, Apr 07, 2012, 3:06 AM UTC

cperciva wrote: post #103

tptacek wrote: post #99

Earlier quoted context omitted.

Since there are good password hashes that are also bad KDFs, I'm not sure I agree with the equivalence.

There are?

... I think so?

They don't all work this way but this is one of those disagreements where you're more likely to be right than me.