Comment by Wowfunhappy | Hacker News Reader

Comment by Wowfunhappy | Hacker News Reader

This happens to include a nice two-paragraph summary of how password hashing works, that I think a non-technical person could easily understand. It's a shame they used the term "string", but it reads fine in context. I should save for future use...

-----

> If you have a Google account, Google’s core sign-in system is designed not to know your password. How, then, can we verify your password when you sign in to your Google account again? The answer lies in a bit of cryptography: when you set your password, instead of remembering the exact characters of the password, we scramble it with a “hash function”, so it becomes something like “72i32hedgqw23328”, and that’s what we store with your username. Both are then also encrypted before being saved to disk. The next time you try to sign in, we again scramble your password the same way. If it matches the stored string then you must have typed the correct password, so your sign-in can proceed.

> The effectiveness of the hash function lies in its one-way nature: it is simple to scramble your password, but nearly impossible to unscramble it. So, if someone should obtain the scrambled password, they won’t be able to recover your real password. The downside of password hashing is that if you forget your password, we cannot show you what it was; there’s nothing we can do other than reset it to a temporary password (valid one time only) and then require you to pick a new one.

Doesn't really explain that the "scrambling" is deterministic which is an important feature. In colloquial use "scramble" means to randomize, for example "scramble the code to your gym locker."

When you scramble your locker combo, is really is random. When you scramble your password with a hash function, it may look random, but it's really not.

Also just for fun, here's a creative stab at my own explanation.

As every dog knows, each dog has a unique smell. If you have smelled the dog before, then you can use its smell to recognize who it is, but without that past experience, nothing in the smell itself tells you who it might be.

The hash function creates the smell from your password, which is the dog. A website does't save a photo of your dog, just the smell. So if a hacker breaks in, they might smell your password but they can't see it. And when you login to the website, it makes sure your password smells right before it lets you in.

It’s sort of implied when they explained they do the same hashing and ensure the hashes match though.

It says that it scrambles it "the same way" when it checks it. Isn't that clear enough?

The scrambling is modulated by a random nonce which is stored together with the hash. So you are scrambling the original randomly; you then scramble the password-to-be-checked the same "way" (ie. with the same nonce) to compare hashes.

I can’t believe you think “scrambles the same way” is misleading and “smells right” isn’t.

> Also just for fun, here's a creative stab at my own explanation.

I know you said "just for fun", but I really think we need to do better than these types of explanations.

I remember many years ago, I was wondering what the heck hyper-threading was, and I came across a video that compared it to a bowl of cereal. Even though you only have one mouth, you'll be able to eat the cereal more quickly if you use both your hands, instead of just one.

I watched this video, and felt gratified, and closed the browser window... and then suddenly realized that I still had no idea what hyper-threading was, only that I should use both my hands if I'm ever in a cereal-eating competition.

A better explanation would have gone something like, "CPUs solve math problems more quickly than we can give them problems to solve. Hyper-threading queues up additional sets of problems that the CPU can switch to when it would otherwise be doing nothing."

Analogies are useful tools, but usually only after we have some understanding of the real version.

Analogies are great to memorize the content. They don't explain the content because they're not 1:1 translatable.

Does that mean that analogies themselves are an analogy of hash functions?

(not serious; hope it is not against the guidelines)

More seriously analogies are better for a bigger picture of a complex system, as they effectively describe mode of interactions. The dog/smell analogy was not bad but you have to also add a role for the other actor in the system (here I would say: the third party, and the database)

I fully understand password hashing and I still had trouble following your analogy. I think the key is using as little jargon as possible and explaining the actual concepts plainly.

>"Hashing" a password is a method of scrambling it that will produce the same scramble every time you do so. However two different passwords will never produce the same scramble.

Could be better, but emphasizes the deterministic nature of hashing but also avoids tangential details and gotchas like collisions which aren't relevant here.

I don't think explaining determinism is necessary or even helpful here. I showed the post to my girlfriend and it made perfect sense to her. Explaining that sometimes doing the same thing in the same way results on different results unless you're careful only muddies the message.

The explanation is clear that they scramble the password in the same way to get the same result.

The other thing they could address is that more than one password can map to the same hash. But it would not improve the explanation.

There’s no need to confuse things with metaphors as anyone with elementary understanding of maths should be able to understand it:

A cryptographic hash function is an algorithm that:

Given an input, it returns a very large number.

Given a bit-for-bit identical input it returns exactly the same number.

If the input changes by one bit, it _should_ give an extremely different number, so different that it appears to be random.

The probability of two different inputs producing the same output is extremely low, and the better the hash function, the lower this probability is.

Funny thing, human scrambling is not actually random (it's a shuffle not a randomization) and neither is a coin toss. When asked to produce a random password, people gravitate towards nonrepetition and that dependent on medium they use to type the password in. This results in a highly skewed blue noise statistics.

People aren't random even when they try to be.

Wait, a coin toss isn’t random?

It's nearly impossible to unscramble the hash if it is random.

It's trivial to unscramble hashed dictionary words with 123! or 2019! appended to the end.

Google should somehow note that distinction as it is important.

Technically, you're guessing the password, you're not unscrambling it (which, afaik is not just "nearly impossible", but it is impossible by design for modern hash functions).

Being able to make millions (or hundreds of millions or even billions) of guesses each second makes successful guessing more feasible.

It's worth pointing out that while modern hash functions are believed to be infeasible to unscramble (technically, to require exponential time), none have been proven so. In fact, proving the mere existence of such a function would prove P!=NP.

Wouldn’t it prove the opposite namely that P equals NP?

I think you mean... P = NP. Which is very unlikely as we could do away with mathematicians if that were true.

Seems unlikely, but not proven. That's the point. I dunno about 'do away with mathematicians'.

Yeah, I just thought that showing how to solve a best-case exponential function in polynomial kind was the sort of thing that would prove P = NP (I dictated this before, so NP came out as MP)

No, if you can prove that a secure hash function exists, then you have proved that P != NP. (This is what alexbecker said.)

If you can prove P = NP, then you have proved that no secure hash functions exist. (This is the contrapositive.)

For convenient definitions of "secure" :-). "Unscrambling" a particular function could be in P but still effectively intractable.

(For a fun angle not related to complexity, the algorithm itself could be so large that it wouldn't fit in the observable universe without breaking the Bekenstein bound.)

And it has been a long time since I did proof theory, but is there the possibility of a non-constructive proof but no actual examples no matter how long you keep enumerating algorithms? Or a non-constructive proof, but no constructive proof? In that case there could be a "perfect heuristic"...

Oops, this is what I get for not reading carefully :) But this is interesting: it implies, if I'm not mistaken, it implies that we haven't ever proven that a function takes exponential time, just that we haven't found any algorithms for certain problems faster than exponential time. I hadn't considered P != NP this way before...

No, we know that P != EXP_TIME, by the time hierarchy theorem - i.e. we know some problems (and we do have concrete examples) take exponential time. What we don't know is that there exists a problem that requires exponential time (or otherwise greater than polynomial) where we can create a proof that a answer is correct which is checkable in polynomial time.

https://en.wikipedia.org/wiki/Time_hierarchy_theorem

There's one thing I've never understood about this "guessing" technique to find the plain text of a known hash value. Wouldn't the sticker also need to know exactly what hashing function had been used as well as how many times applied (i.e. what the "stretching" factor was)?

Because without that knowledge what would the attacker run their guesses through? And wouldn't that information be hard to get unless you had the full source code along with all relevant configuration?

You can make a few simplifying guesses. 1. Google uses a lot of go so its likely they use bcrypt, so try that first. 2. Most people arent security experts so dont bother w/ stretching, just do one hash.

Those 2 assumptions right there get you what you want 90% of the time.

You have to test the password against the real login feature, otherwise you wouldn’t know if you guessed it. The hashing function can be widely known and attackers using brute force guesses would still be blocked by a security feature that requires a second factor (e.g. email) after a certain number of failed attempts.

As an attacker you're not trying to guess the hashed password and even if you had it you still would not be able to use it to log in. Hashing functions that are fit for real-world use are pure functions and their input cannot be determined by looking at their output, which renders rainbow tables (a list of plain text input and their corresponding hashed output) useless to attackers.

So knowing the hash function is useless and even if you also manage to access the database and get the hashed password you still need to run through a brute force technique to find which input gets that output. If the original password is itself a long random set of characters stored with Keychain or Onepass you’re looking at potentially trillions of attempts before you get it right. Hashing functions are written to be slow and computationally expensive so you’re going to incur a lot of energy costs by the time you get it. Also, you’ll be dead by then. When brute force works it’s because the password has no failure restrictions and is something short and simple like a mother’s maiden name with a zip code at the end.

One of the assumptions in designing cryptographic systems (Kerckhoff's Principle [1]) is that the attacker knows everything about the system and how it is implemented, except for the password itself. While you could hide the implementation details, that would mean that nobody could verify how strong your system is.

[1] https://en.wikipedia.org/wiki/Kerckhoffs%27s_principle

The "key" of a "key derivation function" typically stores all that information. For example, see the format for scrypt: https://github.com/Tarsnap/scrypt/blob/master/FORMAT

Since you know your own password on the system you can use that to figure out the hashing mechanism. Also, the hashing strategy and salt is often part of the stored hash.

This technique is referred to as a chosen plaintext attack.

IMO they would have ideally used "key derivation function" instead of "hash function". It could lead those who know enough to be dangerous to think that safely storing passwords is a simple `sha512($password)` away.

You’re kidding, right? It’s supposed to be a simple explanation.

Reply on news.ycombinator.com