5 ms·

SHA256-based Hashcash seems like a poor choice of PoW for a captcha that's supposed to incur a nontrivial cost for spammers. They can simply employ a SHA256 ASI

by tromp 3y ago

SHA256-based Hashcash seems like a poor choice of PoW for a captcha that's supposed to incur a nontrivial cost for spammers. They can simply employ a SHA256 ASIC to crack the captcha at practically no cost.

lucb1e 3y ago
I agree, but you literally have no other option: https://developer.mozilla.org/en-US/docs/Web/API/SubtleCrypto/deriveKey https://developer.mozilla.org/en-US/docs/Web/API/SubtleCrypt... Web cryptography is stuck in the 1990s. PBKDF2 is the only available algorithm, which gives an attacker's GPUs a big advantage over honest users, let alone ASICs. Maybe a webassembly-based solution, implementing something like Bcrypt or Scrypt/Argon2, is comparable to a browser-native implementation, but that would have to be verified before taking my word for it. These algorithms provide varying amounts of memory-hardness (Bcrypt only 4KB but even that proved surprisingly effective), which causes contention on the GPU memory bus (they're only a bit faster than the CPU's memory bus, making the GPU have only a small advantage, on the order of 5x instead of 100x) and causes larger ASIC die sizes (which the Argon2 paper argues is what causes cost for the attacker). Source for the latter: https://github.com/P-H-C/phc-winner-argon2/blob/16d3df698db2486dde480b09a732bf9bf48599f9/argon2-specs.pdf https://github.com/P-H-C/phc-winner-argon2/blob/16d3df698db2... section 2.1 > We aim to maximize the cost of password cracking on ASICs. There can be different approaches to measure this cost, but we turn to one of the most popular – the time-area product [4, 16]. [...] > - The 50-nm DRAM implementation [10] takes 550 mm² per GByte; > - The Blake2b implementation in the 65-nm process should take about 0.1 mm² (using Blake-512 implementation in [11]); I understand from this that adding more memory on the ASIC/chip is more expensive than adding more computing power.
- notpushkin 3y ago
  Ohhh, actualy mCaptcha seems to be using WASM already: https://mcaptcha.org/docs/api/browser https://mcaptcha.org/docs/api/browser So I think it should be possible to add another algo?
- tromp 3y ago
  A better choice would be a memory hard PoW (that's still instantly verifiable), where the performance gap between consumer and custom hardware can be limited to one or two orders of magnitude.
  - xigoi 3y ago
    What if the consumer has almost no free space?
    - lucb1e 3y ago
      Then you can trade-off processing power within reason. Modern websites are so heavy, it's not unusual to need a gigabyte of memory to use some of the heavier webpages. Using some megabytes (150MB I'd consider an upper bound of where the advantage will have leveled off for the coming years) is not typically impossible, and even 4KB is a lot better than no memory hardness at all.
  - lucb1e 3y ago
    > that's still instantly verifiable Good point, current verification of password hashes takes as long as generating the hash. I seem to remember that there was a technique to avoid this, but it wasn't usable for passwords or something. Do you happen to have a pointer for what algorithm has this property?
    - tromp 3y ago
      Asymmetric PoW algorithms, such as Cuckoo Cycle [1] or the poorly named Equihash [2] (which is not a hash function) do not lend themselves to password hashing, since a given problem instance can have 0 or 1 or many solutions. [1] https://github.com/tromp/cuckoo https://github.com/tromp/cuckoo [2] https://en.wikipedia.org/wiki/Equihash https://en.wikipedia.org/wiki/Equihash
- fabiospampinato 3y ago
  You do have other options, you can build your PoW on repeated squarings instead.
  - lucb1e 3y ago
    Not sure I understand. Numbers in JavaScript can't hold infinitely large numbers, so after a few squarings using x*x or Math.pow(x, 2) you're at float max (or at least lost some precision, breaking the proof) and would need to resort to custom code again rather than a hardware-accelerated browser-native operation.
    - tromp 3y ago
      He's talking about repeated squarings in a modular field, like integers mod N where N is the product of two large primes.

by tromp 3y ago

lucb1e 3y ago

I agree, but you literally have no other option: https://developer.mozilla.org/en-US/docs/Web/API/SubtleCrypto/deriveKey https://developer.mozilla.org/en-US/docs/Web/API/SubtleCrypt... Web cryptography is stuck in the 1990s. PBKDF2 is the only available algorithm, which gives an attacker's GPUs a big advantage over honest users, let alone ASICs. Maybe a webassembly-based solution, implementing something like Bcrypt or Scrypt/Argon2, is comparable to a browser-native implementation, but that would have to be verified before taking my word for it. These algorithms provide varying amounts of memory-hardness (Bcrypt only 4KB but even that proved surprisingly effective), which causes contention on the GPU memory bus (they're only a bit faster than the CPU's memory bus, making the GPU have only a small advantage, on the order of 5x instead of 100x) and causes larger ASIC die sizes (which the Argon2 paper argues is what causes cost for the attacker). Source for the latter: https://github.com/P-H-C/phc-winner-argon2/blob/16d3df698db2486dde480b09a732bf9bf48599f9/argon2-specs.pdf https://github.com/P-H-C/phc-winner-argon2/blob/16d3df698db2... section 2.1 > We aim to maximize the cost of password cracking on ASICs. There can be different approaches to measure this cost, but we turn to one of the most popular – the time-area product [4, 16]. [...] > - The 50-nm DRAM implementation [10] takes 550 mm² per GByte; > - The Blake2b implementation in the 65-nm process should take about 0.1 mm² (using Blake-512 implementation in [11]); I understand from this that adding more memory on the ASIC/chip is more expensive than adding more computing power.

notpushkin 3y ago
Ohhh, actualy mCaptcha seems to be using WASM already: https://mcaptcha.org/docs/api/browser https://mcaptcha.org/docs/api/browser So I think it should be possible to add another algo?
tromp 3y ago
A better choice would be a memory hard PoW (that's still instantly verifiable), where the performance gap between consumer and custom hardware can be limited to one or two orders of magnitude.
- xigoi 3y ago
  What if the consumer has almost no free space?
  - lucb1e 3y ago
    Then you can trade-off processing power within reason. Modern websites are so heavy, it's not unusual to need a gigabyte of memory to use some of the heavier webpages. Using some megabytes (150MB I'd consider an upper bound of where the advantage will have leveled off for the coming years) is not typically impossible, and even 4KB is a lot better than no memory hardness at all.
- lucb1e 3y ago
  > that's still instantly verifiable Good point, current verification of password hashes takes as long as generating the hash. I seem to remember that there was a technique to avoid this, but it wasn't usable for passwords or something. Do you happen to have a pointer for what algorithm has this property?
  - tromp 3y ago
    Asymmetric PoW algorithms, such as Cuckoo Cycle [1] or the poorly named Equihash [2] (which is not a hash function) do not lend themselves to password hashing, since a given problem instance can have 0 or 1 or many solutions. [1] https://github.com/tromp/cuckoo https://github.com/tromp/cuckoo [2] https://en.wikipedia.org/wiki/Equihash https://en.wikipedia.org/wiki/Equihash
fabiospampinato 3y ago
You do have other options, you can build your PoW on repeated squarings instead.
- lucb1e 3y ago
  Not sure I understand. Numbers in JavaScript can't hold infinitely large numbers, so after a few squarings using x*x or Math.pow(x, 2) you're at float max (or at least lost some precision, breaking the proof) and would need to resort to custom code again rather than a hardware-accelerated browser-native operation.
  - tromp 3y ago
    He's talking about repeated squarings in a modular field, like integers mod N where N is the product of two large primes.