11 ms·
Scrypt is Maximally Memory-Hard
- murbard2 10y agoIt's worth noting that an issue with scrypt for proof-of-work cryptocurrencies is that is is expensive to check. The ideal problem is memory hard to solve but can be checked cheaply. This is what equihash (used by zcash, (https://www.internetsociety.org/sites/default/files/blogs-media/equihash-asymmetric-proof-of-work-based-generalized-birthday-problem.pdf https://www.internetsociety.org/sites/default/files/blogs-me...) attempts to do, though proving the memory hardness seems more harduous than in the case of scrypt.
- zaroth 10y agoIs this really a major pain point? You have to run billions of units of the work to find the proof. You run exactly one unit of the work to validate the proof. The units can be set somewhat arbitrarily. Although it is important for the unit to be memory-hard-enough to not accelerate well on a GPU. I would think that's a rather wide "target" which can be hit by scrypt at a certain difficulty. Needless to say, it's still possible to get it wrong, e.g. Litecoin.
- drostie 10y agoThere's something to be said for both. It's true that there is a scaling intrinsic to the Bitcoin protocol (which it had to have, as it was based on fast functions) to allow arbitrary slowdown at the brute-force level. However ideally it would be nice to have an asymmetry there. Just think of it purely in the manner of "why run exactly one unit of the work? why not run a hundredth of that unit to validate the proof?" An asymmetry allows you to more quickly verify the ledger, which is both a startup cost and a lesser ongoing cost for everyone. I'm wondering however if there is a connection with asymmetric encryption, though. Imagine a one-way function h and two functions f(x), g(x) such that f(g(x)) = x. Suppose the task is "find M such that g(h(M)) lies within some narrow subset," then if g is much slower than f, you can verify a pair (M, g_h_M) not by verifying that g(h(M)) = M (slow) but rather by verifying that f(g_h_M) = h(M) (much faster). The importance of h is just that for the most obvious application (f(x) = x^E modulo N, g(x) = x^D modulo N), you also have that g(f(x)) = x, and this is a relatively common property of inverse functions.
- murbard2 10y agoYou get the same properties with a basic proof of work scheme. The difficulty would be to make g memory hard and f not memory hard.
- CyberDildonics 10y ago> "why run exactly one unit of the work? why not run a hundredth of that unit to validate the proof?" Because it is a solution in search of a problem in many cases?
- murbard2 10y agoValidation needs to be as light as possible in absolute terms (not just relative to the computation) for DDOS protection. An attacker could spam you with fake blocks and force you to compute expensive hashes to realize they are fake. Also consider the case of building a lightweight hardware device to act as an SPV client.
- murbard2 10y agoValidation needs to be as light as possible in absolute terms (not just relative to the computation) for DDOS protection. An attacker could spam you with fake blocks and force you to compute expensive hashes to realize they are fake.
- tromp 10y ago> proving the memory hardness seems more harduous In fact, several submissions to the Zcash Open Miner Contest, at https://zcashminers.org/submissions https://zcashminers.org/submissions exhibit time-memory tradeoffs that were not considered in that paper, invalidating some of its claims. My own, memory latency bound, proof-of-work called Cuckoo Cycle https://github.com/tromp/cuckoo https://github.com/tromp/cuckoo offers $5000 in bounties for invalidating its claims of near-optimal implementations and trade-off resistence.
- murbard2 10y agoHopefully, in the near future, we can just slap a recursive SNARK on scrypt (or any memory hard hash function for that matter) and call it a day.
- tromp 10y agoWhile building snark proofs is very memory intensive in itself, it is far from optimization free, which is one of the primary requirements for a PoW...
- murbard2 10y agoNot my point. The idea is that you can obtain a cheaply checkable proof that you computed a memory bound function, such as a scrypt hash.
- tromp 10y agoI did get your point. But if the onus to produce such a proof is on the miner before they can broadcast the next block, then the PoW is no longer optimization free.
- murbard2 10y agoAh I see. It's true, but there's a good chance these optimizations would be discovered independently, progressively and percolate into the ecosystem. Turning to ASIC was an "optimization" that was replicated and copied. It's true that there is a lot more secret sauce to optimizing a SNARK, but if mining drives improvement in SNARK efficiency, I would call that a win.
- loup-vaillant 10y agoWait a minute, there's a time memory tradeoff attack for scrypt. Argon2 was developed precisely to remedy that problem. And now there's a proof Scrypt is the best anyone can do? This would mean a similar attack is possible on Argon2 as well, even if we haven't found it yet. This sounds like a significant result, so I'm a bit skeptical right now. Perhaps the paper doesn't mean what I think it means?
- cperciva 10y agoTime-memory tradeoffs don't reduce the cost, which is determined by the time-area product (or technically the integral of area over time).
- loup-vaillant 10y agoAfter you perform the tradeoff, you can still use ASIC to reduce your costs. We regular users only have an x86_64 box. Ideally we want ASIC to be just as expensive. And by the way I'm not sure time memory tradeoffs doesn't reduce the time area product some don't, but I bet some do (which is why they're called "attacks"). That said, my knowledge is quite sketchy here. Any recommended reading?
- loup-vaillant 10y agoPerhaps I was not clear. While memory cost about the same in all settings, processing power does not. Whatever part of an attack can be ASICified will be cheaper than it would have been if executed on stock hardware. Time memory tradeoffs, even if they don't reduce the time-area product, do increase the amount of silicon that can be ASICified. The additional computations might very well cost less than the equivalent memory lookups. I'd like to close the gap between stock hardware and ASIC. This paper's abstract suggest that we cannot. That's a bummer.
- loup-vaillant 10y agoAh, found it. I just had to read the damn paper. Turns out I was confusing memory hard functions, which allow for time/memory tradeoffs, and memory bound functions, which do not. Scrypt is hard, but not bound. I believe Argon2d attempts to be bound as well. Argon2i however might just be hard, at least in theory, because its memory accesses do not depend on the secrets, making them predictable.
- infruset 10y agoI was under the impression that there were scrypt ASICS. Can someone explain how, if true, this is compatible with this claim?
- cperciva 10y agoYou can put anything into an ASIC. The only question is how much it costs. But all the "scrypt" ASICs I'm familiar with are limited to computing the nerfed litecoin version anyway.
- TD-Linux 10y agoTake a normal CPU, delete the instructions that aren't used by scrypt, and bam, you have a cheaper and more power efficient chip. In general, you can't prevent ASICs unless you maximally utilize commodity hardware.
- jorangreef 10y agoThat's fine, scrypt was designed to defend against the eventuality of scrypt ASICS.
- masklinn 10y agoThe point of scrypt is to make ASICs expensive by requiring lots of fast memory. You can always build an ASIC, that doesn't mean the ASIC is cost-efficient.
- amelius 10y ago> The point of scrypt is to make ASICs expensive by requiring lots of fast memory But what is the point of that?
- masklinn 10y agoSignificantly lower the ROI password-cracking ASICs, more money and die area going to memory means less of it going to compute, and a much lower difference (in hash/s) between regular user and cracker. It all works towards the ultimate end of making cracking passwords too inefficient and expensive for "bad guys" to bother.
- todd-davies 10y agoWhen we talk about the term 'computationally hard', we usually mean an NP-hard problem. I assume that here, 'memory-hard' means that no other hashing algorithm can have a greater lower bound on its memory complexity than Scrypt. Is that correct? Edit: After a re-read, I realised that the answer is in the text: "Memory-hard functions (MHFs) are hash algorithms whose evaluation cost is dominated by memory cost."
- zaroth 10y agoThe point of scrypt is to utilize the commodity hardware to the max. Commodity hardware gives you a lot of memory IO for the buck. You can't spend the same dollars and get 100x more IO on an ASIC. But you can spend the same dollars and get 100x (actually even more) faster at typical hashes like SHA256. The point is to cut down on an attacker's possible advantage by using specialized hardware. Scrypt uses memory IO so that you can "get your money's worth" by running it for 100ms on an Intel CPU. This is old-school thinking and a defensive play at trying to prevent offline attacks. The idea is impose a run-time cost on each attempt to verify a password. Defender spends it every time they try to log someone in. Attacker spends it for every guess at trying to crack a password. The new approach (well I'm quite biased since I founded a company that does this) is to add a one-time cost which is unbounded and does not impose run-time latency. We do this with a large amount of random data. Many TBs or perhaps as much as a PB. The salted hashes are entangled with the data pool with a simple API, in such a way that an attacker would need to steal the entire data pool to run an offline attack. Stealing only part of the data pool does not let you crack any passwords, even if they are trivially simple. The bigger the data pool, the easier it is to defend, and the faster the system runs and more hashes/second it supports. So, is essence it's high performance scalable security that actually stops offline attacks even after the site is breached. You use this new approach as an additive layer on top of the existing scrypt hashing that you are already doing.
- eigenvalue 10y agoIt occurs to me that another benefit of this approach is that it gives you ample time and warning that an attack is occurring, because unless the attacker has physical access to the machines and can just plug in a drive, you will know that a ton of data is crossing the wire.
- zaroth 10y agoPrecisely! We monitor the network traffic very closely. The only data over the wire is API requests/responses which are counted. Every 5 minutes we compare that against the actual number of requests performed according to the application counters. If the traffic doesn't line up, it pages the whole ops team. Every day we are looking at total network egress. It would take an attacker over 200 days to move the data pool at full line rate. It gives us time to detect and remediate the inevitable breaches without ever exposing any passwords to an attack. The best part is we don't see the login, we don't see the password, we just see the hash. And without the salt it's just a random number. We don't even know if the login is valid or invalid, and there's nothing we could do to make an invalid login appear valid. So our customers effectively retain full control over their authentication process. The hash determines where we read from the data pool. 64 bytes read from each of 64 uniformly distributed locations. The 4K result is hashed and the digest is sent back in the response. On the customer side, they use the response to run one HMAC and save the result (we call it Hash2). The original hash (Hash1) can be discarded, or if you want a way to leave the service sometime in the future, encrypted using a public key with a semantically secure (non-deterministic) algorithm. Large enterprises where we are doing pilots also tell us they like this because it defends against insider threats as well.
- hippich 10y agoat https://hashcash.io/ https://hashcash.io/ I am using litecoin hashing algo, which in turn uses scrypt.