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

41–50 of 133 posts

Re: Speed Hashing

#41

Post by ralph »

nadam wrote: post #24
codinghorror wrote: post #19

Earlier quoted context omitted.

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…

I am afraid the terminology you use is not canonical. A hash (function) is any function that maps a big variable-length data structure to a smaller (fixed-length) data structure. A checksum is a special hash (function) which has the purpose of detecting accidental errors during transmission or storage. (This makes them different from hash functions used for example in hash tables. For example relevant question: minim…

I have hash functions that work on less bytes than the length of the hash they produce.

Re: Speed Hashing

#42

Post by codinghorror »

cperciva wrote: post #36

Using "hash" to mean "strongly collision-free function" is a valid terminological choice; in a wide-readership piece like this it should ideally be pointed out in order to avoid confusion, but there are many fields where that definition would be assumed without statement. Getting confused between hash functions and password-based key derivation functions , on the other hand, is absolutely inexcusable; that very confu…

Good point. Isn't the only PBKDF requirement artificial and technically unnecessary computational delays? I mean far beyond what is necessary to actually produce a strongly collision free function.

Re: Speed Hashing

#43

Post by nooop »

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.

Re: Speed Hashing

#44

Post by parenthephobia »

scott_s wrote: post #30
codinghorror wrote: post #17

Earlier quoted context omitted.

terminology issue, I guess, I'd call those checksums -- where speed is the overriding concern and you're not worried about attackers changing the data underneath you. (And you actually need to uniquely identify the data in a reliable way..)

Sure, it's a terminology issue, but as several others have pointed out, you're the only one using your terminology. So expect people to be confused when you try to explain these things using your definitions.

In the case of TCP/IP, everyone calls the checksum a checksum, and nobody calls it a hash.

Re: Speed Hashing

#45

Post by arethuza »

ralph wrote: post #41
nadam wrote: post #24

Earlier quoted context omitted.

I am afraid the terminology you use is not canonical. A hash (function) is any function that maps a big variable-length data structure to a smaller (fixed-length) data structure. A checksum is a special hash (function) which has the purpose of detecting accidental errors during transmission or storage. (This makes them different from hash functions used for example in hash tables. For example relevant question: minim…

I have hash functions that work on less bytes than the length of the hash they produce.

Won't that be fairly common? Java's hashCode and the .Net GetHashCode both return 4 byte ints and there are presumably a lot of HashMap and Dictionary objects out there using short strings as keys.

Re: Speed Hashing

#46

Post by codinghorror »

pbsd wrote: post #26
codinghorror wrote: post #19

Earlier quoted context omitted.

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…

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 (all other?) situations?

Re: Speed Hashing

#48

Post by cperciva »

codinghorror wrote: post #42
cperciva wrote: post #36

Using "hash" to mean "strongly collision-free function" is a valid terminological choice; in a wide-readership piece like this it should ideally be pointed out in order to avoid confusion, but there are many fields where that definition would be assumed without statement. Getting confused between hash functions and password-based key derivation functions , on the other hand, is absolutely inexcusable; that very confu…

Good point. Isn't the only PBKDF requirement artificial and technically unnecessary computational delays? I mean far beyond what is necessary to actually produce a strongly collision free function.

The key requirement for a password-based key derivation function is that performing a brute force search is expensive. The PBKDF2 and bcrypt functions approximate this by scaling the amount of computation required; but this is imperfect since they can both be implemented on small circuits, making highly parallel attacks using GPUs/FPGAs/ASICs feasible. The scrypt function scales the amount of RAM required -- and thus the circuit size -- as well, making it far more expensive to attack since you can't use the same sort of cheap highly-parallel crunching.

The best reference for this analysis is the scrypt paper: http://www.tarsnap.com/scrypt/scrypt.pdf

Re: Speed Hashing

#49

Post by eruquen »

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 a random string of length 4).

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. If it takes a few days to crack the whole database without pepper, it might take a few years to do it with pepper. There is absolutely nothing the attacker can do about it. No access to any part of your system will help him or her.

Re: Speed Hashing

#50

Post by bonzoesc »

Misiek wrote: post #39
bonzoesc wrote: post #32

Earlier quoted context omitted.

Because sha1 is still super fast on a GPU. Why aren't you using bcrypt?

I thought that hashing password with two types of salt (one of them is unique for every user) and two places to storage salts is secure enough.

Salts don't slow a GPU down: http://codahale.com/how-to-safely-store-a-password/
Post reply on HN