Use a better proof-of-work mechanism

[Xe]

SHA-256 works for now to buy time but it's not GPU-safe. Use a better mechanism to be sure it's GPU-safe.

[runxiyu]

Another problem is that the WebCrypto/SubtleCrypto/IForgotWhatTheProperNamesAre is extremely slow; a simple C implementation outperforms those by 200 times. I found a hash difficulty of 21 bits to be appropriate, but that would take ages in JS.

So people don't even need GPUs and whatnot...

[runxiyu]

I think variable delay functions might be worth investigating here.

Edit: I've been reading some introductory material on lattice problems recently (trying to get a basic understanding of e.g. ML-KEM) and I suspect there's a way out here too

[fossifousacid]

Would switching to a more complicated hash like argon2 help? There are existing implementations in Rust that can be compiled to a webassembly module.

https://www.rfc-editor.org/rfc/rfc9106.html

[runxiyu]

Argon2 is too computationally expensive to verify on the server side.

[mimi89999]

SHA2 has a WASM SIMD implementation: https://github.com/RustCrypto/hashes/blob/sha2-v0.11.0-pre.5/sha2%2Fsrc%2Fsha256.rs#L30

Any algorithm that doesn't have it will be much worse in the browser than run directly on hardware.

[runxiyu]

I just grabbed a generic public domain C implementation of SHA-256. It's significantly slower than running the same program directly (150% vs 200% speedup compared to SubtleCrypto — strange as I'd expect the latter to be optimized too), but still good enough for the purposes of Anubis/etc, in my opinion. Interesting WASM SIMD implementations.

[runxiyu]

See also: https://people.csail.mit.edu/rivest/pubs/RSW96.pdf

[nicoonoclaste]

Would switching to a more complicated hash like argon2 help?

Potentially yes. In general, a memory-hard proof-of-work mechanism would reduce the advantage in utilizing more-specialized hardware, like GPU- or ASIC-based solvers. That's all-the-more important given that it seems (to me, based on a cursory analysis) attackers could repurpose Bitcoin-mining ASICs (which may be gathering dust somewhere) to attack the current PoW system.

The harder part is making such a PoW system not require too much work on the verifier's side, as it otherwise becomes an easy DoS vector in addition to being a server-side performance issue.

Something like Argon2d might work, but will require as much memory on the verifier side, as one solver thread; intuitively, a PoW protocol which is memory-hard only for the solver might not exist:
an attacker which directly enumerates possible solutions and verifies them, wouldn't use much more memory than the verifier itself (but plausibly a lot more time than the intended solver)

Argon2 is too computationally expensive to verify on the server side.

Not necessarily, depending on the parameter set: Argon2d set to use 32 KiB of memory, uses less than 1ms... on a 7 years-old laptop CPU, while contending with other applications for CPU time:

❯ echo -n test > input
❯ hyperfine -S none --input input -- 'argon2 saltsalt -d -m 5 -t 1 -r'
Benchmark 1: argon2 saltsalt -d -m 5 -t 1 -r
  Time (mean ± σ):     746.3 µs ± 307.7 µs    [User: 311.6 µs, System: 274.4 µs]
  Range (min … max):   448.5 µs … 1615.4 µs    2217 runs

❯ lscpu
[...]
Vendor ID:                GenuineIntel
  Model name:             Intel(R) Core(TM) i5-8265U CPU @ 1.60GHz

I expect most of that to be the overhead of starting a process, as I got similar (if higher) numbers when getting the help message, but it still tells us that even on not-so-new hardware, the runtime of Argon2d (with those parameters) is significantly lower than 1ms.

I could put a better benchmark together, but I don't have the availability right now.

[Xe]

The wasm PR has argon2id set as the default mechanism for testing. It uses a fair bit of ram (default settings), but I was gonna hammer the server and set a singleton or worker group for that checker in particular. I'm setting it use about 20MB of wasm memory per validate run on the server and about 24MB * the number of threads on the client.

[ejrydhfs]

If it is running on GPU judging by throughput and other fingerprinting reveals it's a bot by aka checking that it's running in docker or a virtual machine judging by latency? why not use it to Mine crypto to cover costs and make some money as a donation for the site owner?

[mwoelke]

Hi, I developed an anti-bot PoW mechanisms for my bachelor thesis last year and used Argon2id for this (PoC is available at https://github.com/mwoelke/antispam-poc).

I wanted to share my experience with using Argon2 on the web for PoW:

• The identical RAM usage on the server and the client can be a real problem. The devs of Argon2 actually developed an algorithm with asymmetric RAM usage ("MTP-Argon2", see https://www.usenix.org/system/files/conference/usenixsecurity16/sec16_paper_biryukov.pdf) but it was later broken. I ended up using low memory requirements (4096 KiB) because of this. This is definitely not ideal.

• I compared the speed of different web implementations of Argon2. As of early 2024, argon2-browser (https://github.com/antelle/argon2-browser) with SIMD enabled was the fastest option. When not using SIMD, libsodium.js was faster. Because of this, I asked the libsodium.js devs why they don't support SIMD, see Question: State of SIMD? (Regarding Argon2) jedisct1/libsodium.js#340. tl;dr: WASM SIMD (at least as of early 2024) is just a draft (even though supported by all major browsers). The C reference implementation was between 2 - 5 times faster than argon2-browser with SIMD.
  -> Testing for SIMD support at runtime ended up easier than expected; I just borrowed 1 LoC from https://github.com/GoogleChromeLabs/wasm-feature-detect

function checkSimd() {
    return WebAssembly.validate(new Uint8Array([0,97,115,109,1,0,0,0,1,5,1,96,0,1,123,3,2,1,0,10,10,1,8,0,65,0,253,15,253,98,11]));
}

• During testing, most bots were already blocked by the JavaScript/WASM requirement. The actual choice of hash function might not be that important. I want to stress, however, that my testing was rather short. You guys probably have way more data.

Ultimately, I'm not sure if it makes that much of a difference. Argon2 does not seem 100% ideal for the job.

[runxiyu]

why not use it to Mine crypto to cover costs and make some money as a donation for the site owner?

Your lawyer would love this.

Disclaimer: This is not legal advice.

[surfaceflinger]

why not use it to Mine crypto to cover costs and make some money as a donation for the site owner?

RandomX is ASIC resistant but requires 2080MB ram which isn't realistic in this case. Theoretically there is light mode which needs just 256 MiB (No idea if that's a lot in browsers world) but it's probably impossible to prove that someone didn't resolve the PoW with full 2GB to have the result faster.

If it's possible to prove that light mode was used then the only JS implementation (https://github.com/l1mey112/randomx.js) is probably slower than having light mode running outside of browser.

Mining XMR in light mode isn't realistic though and would also introduce latency by waiting for stratum jobs etc. (Unless the job was sent to the browser with everything else)

[PhotonQuantum]

fyi I attempted to implement a PoW challenge based on Argon2i, using a WASM compilation of the RustCrypto implementation. However, I gave up after realising that the hash rate was only around 100H/S (with memory 10k, iterations 1, threads 1). At this rate, it becomes impractical to create a meaningful challenge, as you can only test about 1000 different inputs in 2-3 seconds. This results in a poor probability distribution. A user might spend tens of seconds searching for a solution without success or, conversely, discover the answer within their first 20 attempts.