3 ms·

Wait 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

Wait 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 ago
Time-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 ago
  After 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 ago
    Perhaps 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 ago
      Ah, 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.
- Tomte 10y ago
  What's "area" here? Silicon size?
  - cperciva 10y ago
    Yes. Square mm of silicon, number of transistors, words of memory -- they're all equivalent asymptotically.
    - psyoptix 10y ago
      I dont think they are equivalent. routing area overhead scales in the square root (or at least cube root if your willing to optimize the hell out of things) in the total memory on chip.
psyoptix 10y ago
Argon2i has worse parallel time-memory tradeoff attacks than scrypt. E.g. https://eprint.iacr.org/2016/115 https://eprint.iacr.org/2016/115 Argon2d probably not though.
psyoptix 10y ago
I dont think there is a time-memory attack on scrypt. There is a time-area attack. AFAIK area is whats expensive for an ASIC, not just space. Thing is, memorytime is not a an ideal measure for "area used for memory on chip"time. routing wires to and from memory also require area on the chip. A lot if you want to have a lot of memory. storing 1KB in a chip with total 1KB of mem. takes a lot less area (and energy to read/write) than storing 1KB on a 1GB chip. scrypt (probably in contrast to Argon2d) can be computed either with lots of memory in little time or with little memory in lots of time (and any variant in the middle too as long as the product is n^2 as shown in that new paper). But the later approach doesnt have all that routing overhead. So AFAIK thats what the ASICs in Litecoin miners use. The algorithm still has space-time n^2 so it doesnt contradict the paper. The other (IMHO much bigger) reason why we have Litecoin ASICs is that the parameters used scrypt in that protocol are just way to small to give any serious memory-hardness properties.

cperciva 10y ago

Time-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 ago
After 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 ago
  Perhaps 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 ago
    Ah, 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.
Tomte 10y ago
What's "area" here? Silicon size?
- cperciva 10y ago
  Yes. Square mm of silicon, number of transistors, words of memory -- they're all equivalent asymptotically.
  - psyoptix 10y ago
    I dont think they are equivalent. routing area overhead scales in the square root (or at least cube root if your willing to optimize the hell out of things) in the total memory on chip.

psyoptix 10y ago

Argon2i has worse parallel time-memory tradeoff attacks than scrypt. E.g. https://eprint.iacr.org/2016/115 https://eprint.iacr.org/2016/115 Argon2d probably not though.

psyoptix 10y ago

I dont think there is a time-memory attack on scrypt. There is a time-area attack. AFAIK area is whats expensive for an ASIC, not just space. Thing is, memorytime is not a an ideal measure for "area used for memory on chip"time. routing wires to and from memory also require area on the chip. A lot if you want to have a lot of memory. storing 1KB in a chip with total 1KB of mem. takes a lot less area (and energy to read/write) than storing 1KB on a 1GB chip. scrypt (probably in contrast to Argon2d) can be computed either with lots of memory in little time or with little memory in lots of time (and any variant in the middle too as long as the product is n^2 as shown in that new paper). But the later approach doesnt have all that routing overhead. So AFAIK thats what the ASICs in Litecoin miners use. The algorithm still has space-time n^2 so it doesnt contradict the paper. The other (IMHO much bigger) reason why we have Litecoin ASICs is that the parameters used scrypt in that protocol are just way to small to give any serious memory-hardness properties.