Hacker News Reader

Comment by jazzyjackson | Hacker News Reader

I feel like there's a way to put salts and hashes in here so that I can publish a list of conditions, "don't send traffic my way if myblocklist.includes(argon2($username + $salt)"

instead of publishing the list of people I don't want to hear from

i also think it's fine to let everyone know who i've blocked, but people have different threat models

View on HN

With this model someone just develops a website that passively collects usernames, performs the calculation, and maps usernames to hashed values.

That's why they added the salt.

It’s still feasible. The search space is limited to “The list of known user names” rather than “every possible combination of N characters”. That’s the difference between computable in under an hour vs computable in millions of years.

Password hashing algorithms don't work well if the entire search space is small. If you block me it's trivial for me to check my username against your hashes to prove you blocked me. Reversing every hash is mostly a question of how many known usernames there are.

this approach results in false positives

Extremely unlikely if you take enough bits from the hash.

"extremely unlikely" is still not the same as "impossible"

hash(x) != x

Are you afraid to go out because you might get struck by lightning?

if you and I have accounts at the same bank, it's incredibly unlikely that my account number will hash to the same value as your account number

are you OK with the bank using a hash of your account number to identify your account instead of the number itself?

of course not -- any risk of collision, no matter how low, is unacceptable

that's the baseline -- risk tolerance is zero

you have to justify any increase of that risk on a case-by-case basis

Yeah, because the consequences of accidentally blocking someone on social media are just as serious as the consequences of a bank confusing two accounts.

If the hash is cryptographically secure and 128 bits I would be perfectly comfortable with them assuming uniqueness of it.

To repeat that guy's question, do you avoid going outside in order to avoid freak lightning strikes?

hash functions map infinite-cardinality input sets to finite-cardinality output sets

definitionally, this means each output value maps to multiple input values -- which means uniqueness is, factually, not guaranteed

it doesn't matter if the likelihood of collisions is 1-in-10, or 1-in-100000, or 1-in-1000000000000, or etc. -- if a collision is possible at all, then uniqueness is not guaranteed, and cannot be assumed as true

You can and should assume sufficiently likely things. It's a waste of time to worry about probabilities with enough zeroes.

Especially because in the real world even a mathematically perfect system has a baseline failure rate. If the chance of hash collision is orders of magnitude lower than the baseline failure rate, then there is no downside to using that hash.

> It's a waste of time to worry about probabilities with enough zeroes.

what? no. absolutely not.

the "baseline failure rate" of a program with some input values X is zero.

> in the real world even a mathematically perfect system has a baseline failure rate.

what? no. absolutely not.

    x = 1
    print(x)

this is not a probabilistic program, there is no baseline failure rate above zero, the output must be "1", any other output means the program is incorrect

this line of reasoning is absolutely invalid -- hash(x) != x

If a cosmic ray flips that 1 to a 3, that will bring your failure rate above zero. No program is correct then.

i can't control solar rays

i can control what my application uses as IDs

> what? no. absolutely not.

Please explain how the benefit outweighs the cost to spend even 30 seconds to prevent a potential problem with 10^-40 probability. (And by that I mean 10^-40 total probability, not per-item.)

> this is not a probabilistic program, there is no baseline failure rate above zero, the output must be "1", any other output means the program is incorrect

You could have a power outage, or the OS could crash, or the CPU could have a bug on those opcodes when certain counters roll over at the exact wrong time, or a bit could flip in your memory.

The baseline failure rate for a program on a computer in the universe is never zero. This isn't abstract math. And the collision rate of many hashing systems is much smaller than that baseline failure rate.

There are even situations where assuming a hash never collides can increase reliability, because the code will be done sooner and that improves the baseline.

obviously computers are not totally infallible, solar rays can flip memory bits from 1 to 0 or vice versa -- but those failure modes are not expressed by the source code of the running program, they're triggered at a layer of abstraction well below the compiled and running software

say the probability of a solar ray bit flip is (say) 0.01%, then consider the following function

    fn x -> int {
      if (randf32() < 0.0001) { panic("boom") }
      return 123
    }

x will panic with the same probability that a solar ray will flip a memory bit

is this acceptable? can i assume that calling x will never panic, in practice?

> are you OK with the bank using a hash of your account number to identify your account instead of the number itself?

Why not? Cryptographically, entropically, there's no difference between a call to "give me a uuid to throw on this new account" and "now crunch it through a sponge function and use that instead"

Your uuid generator will probably check for uniqueness, or your database will enforce unique values, so there's a few places you would be alerted of the collision, but 2^256 is a very large number

you misunderstand the scenario

if we're talking about hash(x) == x then the hash function doesn't consult any central DB to compute a UUID or evaluate uniqueness or anything

there is no UUID generator or DB involved

An absolutely minimal probability of false positives. The probability that you can find a hash collision that's also a valid username is even smaller. I don't think it's something you'd need to worry about.

Reply on news.ycombinator.com