Balloon Hashing: A Function Providing Protection Against Sequential Attacks [pdf] | Hacker News Reader

Balloon Hashing: A Function Providing Protection Against Sequential Attacks [pdf]

eprint.iacr.org

62 pointsbqe21 comments

> The staggering number of password files breaches in recent months demonstrates the importance of cryptographic protection for stored passwords.

Rather, they demonstrate the importance of not re-using a password for multiple sites.

The value of a password is under the user's control. A password which controls access to a user's account on a site which has been compromised (only to that account and nothing else) has very low value, even compared to other pieces of personal information (which are usually stored plain text, and likely included in the breach).

In an ideal world that would be the case, but we are not in an ideal world. If your cryptography can prevent attackers from figuring out shared passwords, then it is a godsend.

Balloon is neat, and has a good pedigree. But: all the password hashes are fine, including the ones that aren't space-hard. If you're undecided, throw a dart, or pick the one with the simplest library for your platform.

Where you get into trouble is when you try to roll your own password hash with a crypto hash and a "salt".

>But: all the password hashes are fine, including the ones that aren't space-hard.

Not quite sure this is true: the Alwen-Blocki attack at CRYPTO this year (and some other nice recent work) demonstrated that there are some subtleties in this area that we don't fully understand yet.

Reducing the memory requirements of a space-hard password hash is important in theoretical terms, and perhaps for systems built around the hardness of a space-hard KDF as, for instance, a proof of work. But it's of virtually no bearing whatsoever to business applications that store passwords. Your space-hard password hash is less space-hard than you hoped it would be. Oh well. The low-hanging fruit is using salted SHA hashes.

This would also be useful for making better bitcoin systems, ones which are resilient to current asics.

Based on a quick skim of the paper it's not clear whether Balloon would be an improvement on existing memory-hard proof-of-work functions like EquiHash or Cuckoo Cycle.

It doesn't make much sense to use a memory hard hash function as part of the Hashcash proof of work system, since

1) Proof of Work systems should make verification as cheap as possible.

2) Hashcash makes verification as expensive as proof attempt.

Project pages for the above asymmetric Proof of Work systems, which do not suffer from this conflict, can be found at

https://github.com/khovratovich/equihash

https://github.com/tromp/cuckoo

Better bitcoin system should have some sane non-libertarian economics behind it.

It should be engineered to have steady inflation that is slightly higher than most common currencies. 4-5% for example.

This would discourage hoarding and increase velocity of money. Good money should not be investment asset or speculation asset. It should be something used for transactions between assets.

The thing is... why would any reasonable individual use a currency with inflation when they can use an equivalent currency with deflation? Governments can force inflation on people - cryptocurrencies have no ability to force anyone to use them.

Governments can only force inflation of the currency, not of all assets. That helps to keep value in investments that pay a return and increase real value to society over holding currency which doesn't.

Or you could say why would any reasonable individual use a currency with built-in boom-bust cycles when they can use an equivalent currency with reasonably stable value?

Given the choice between bitcoin and what you have suggested (a money that is engineered to lose value over time), any sane person would choose bitcoin. Regardless of whether or not you believe that everyone using an inflationary currency is Pareto optimal (I do not), it is not a stable equilibrium. On the other hand, people using an appreciating asset like Bitcoin forms a Nash equilibrium.

The only reason people use inflationary fiat money is that A) it was by far the most convenient thing before Bitcoin (and still is, depending on your use case), B) it has a decent track record for stability, and C) most governments aggressively attack private monies with good monetary properties, often in the name of anti money laundering. More Machiavellian motivations include that governments don't want to lose seigniorage power or control over monetary policy.

Bitcoin isn't money it's a Fiat Commodity Currency. If you want money I hear the US Dollar is fairly popular.

Some alternative cryptocurrencies were created using memory-hard hash functions. Litecoin uses scrypt, for example.

No it doesn't. Litecoin uses a variant of scrypt which has been deliberately nerfed by limiting its memory usage.

I agree, but it's actually hard not to nerf scrypt, since it's time-cost and memory-cost are tied together. I'm not sure if they could have increased the memory cost sufficiently for their purposes, without making the time cost prohibitively high.

That's one of the things argon2 (https://github.com/P-H-C/phc-winner-argon2) is trying to fix, though I don't think any cryptocurrencies are using it yet (which is reasonable, it's just too young)

This paper also describes an attack on Argon2, which lowers the amount of memory required by an attacker.

Instead of "deliberately", you might as well say "necessarily".

As I argue in [1], "in order to keep verification cheap, hash functions in Hashcash must restrict their resource usage as well. That’s why scrypt is configured to use only 128KB of memory."

To achieve ASIC-resistance, one should avoid Hashcash in favor of asymmetric proof of work systems, where proof attempts can take huge amounts of memory even while verification is instant and memory less.

[1] http://cryptorials.io/beyond-hashcash-proof-work-theres-mini...

Right. Cryptocoins' need for cheap verification of proofs-of-work is precisely opposed to KDFs' need for expensive checking of candidate passwords.

I think they overcorrected. They want it to run on a phone, fine, but a phone app can easily dedicate 100MB of ram to verifying blocks.

Reply on news.ycombinator.com