About parallelism (of Argon2) in the password hashing API

[stevenwdv]

I know this is not the first request for parallelism support in the pwhash API (#488/#986/#993), but it seems weird to me that this is not implemented. Let me elaborate:

On #986 @jedisct1 commented:

threads don’t provide a significant slowdown of the hash computation

Isn't the idea of having parallelism support that the computation is not much slower for desktop computers while it is slower for crackers using specialized hardware, because of the large amount of shared memory between multiple CPUs? This is also mentioned by someone on Crypto SE (although that in itself of course doesn't make it true).

The Argon2 draft RFC currently recommends p=4 lanes (it used to recommend choosing your own value (as the first parameter you choose, by the way, so before memory and then time), but probably this was changed because of portability).

Or does the comment mean that the slowdown on dedicated hardware is not that significant?

Of course not all password hashing functions support parallelism like Argon2 does, but I don't think that that should mean that we can't take advantage of it in functions that do support it.

[stevenwdv]

By the way, correct me if I'm wrong anywhere, I'm not really an expert on this.

I also found some other related SE question, which suggest that when the memory cost is too low, a GPU may unfortunately have an advantage over a CPU with too many lanes.

[al-caveman]

What makes your password harder to bruteforce, is total number of times Blake2b was called by your argon2 configuration. Now, the reason parallelism is great, is because, if you have, say, 4 CPU cores, you can get same amount of security by waiting 1/4 of the time.

E.g. argon2 somesaltofyourchoice -d -t 20 -k 1048576 -p 4 will run Blake2b 20*1048576 = 20971520 many times, distributed over 4 CPU cores, each working in parallel on 20971520 / 4 = 5242880 Blake2b calls. So you will get 20,971,520 worth of security for waiting for 5,242,880 (thanks to parallelism). On my PC, that's the difference between 18.8 wall clock seconds (without parallelism) vs. 4.7 wall clock seconds (with parallelism). This time reduction is critical, since users will give up security in order to not lag/wait for extra seconds.

I'm actually very surprised that pwhash does not implement parallelism, as it is a key feature in memory-hard key derivation functions, such scrypt and argon2. Specially when knowing that libsodium is designed with thread safety in mind. So why doesn't its argon2 implementation do it?

[justusranvier]

I read through all the existing issues about argon2 parallelism and I have a different reason for needing it - it's required for compatibility with an externally-specified file format that my application needs to support.

If libsodium doesn't provide access to that parmeter through the API (which I know is possible because the third party Argon2 implementation libsodium embeds supports it:

libsodium/src/libsodium/crypto_pwhash/argon2/argon2.h

Line 273 in fe1d6d1

int argon2id_hash_raw(const uint32_t t_cost, const uint32_t m_cost,

) then really stuck between a rock and a hard place.

I don't read Makefile very well so I can't tell if the argon2id_hash_raw symbol is exported by libsodium or not. If so then I can copy the header into my sources and rely on the implementation being available if I've linked to libsodium at least until some future update switches things around and breaks my application, if not I can copy the entire Daniel Dinu and Dmitry Khovratovich implementation into my applications source tree and pray that I don't run into any symbol collision bugs, especially in static builds.

[z3bra]

I'm bumping this thread because I ran into this issue recently.

Because libsodium doesn't let the caller specify the number of threads, it's not possible to generate the correct key created by other implementation.

I've compared 3 argon2id implementations:

• libsodium's crypto_pwhash_argon2id()
• PHC's argon2 reference implementation
• Go's Argon2 package

The code used to test all three implementations in in this gist: https://gist.github.com/z3bra/acee29fb2815e170c5674177beb041bc

% ./benchmark.sh
m=65536,t=3,p=1
phc    :bac8c2da3ea370cd916560750fa83b3b50b2d5b42fe0ba1017c6e517066ee715
go     :bac8c2da3ea370cd916560750fa83b3b50b2d5b42fe0ba1017c6e517066ee715
sodium :bac8c2da3ea370cd916560750fa83b3b50b2d5b42fe0ba1017c6e517066ee715

m=65536,t=3,p=4
phc    :57bf8befb740f474ef6c7cff20b3c84b7e7e8075a4c15499f90f50893bb5dd02
go     :57bf8befb740f474ef6c7cff20b3c84b7e7e8075a4c15499f90f50893bb5dd02
sodium :bac8c2da3ea370cd916560750fa83b3b50b2d5b42fe0ba1017c6e517066ee715

As you can see, when p=1 (default hardcoded value for libsodium), all 3 computed hash are the same. However, when you change this value to 4 (as recommended per RFC 9106), the computed hash values from go and phc implementations change. As libsodium's value is hardcoded, the hash remain the same.

Because of this, it is impossible to use libsodium when dealing with Argon2 keys that are generated elsewhere.

I realize that adding this parameter to the API will break compatibility. But it would be nice to add this parameter to the crypto_pwhash_argon2i() and crypto_pwhash_argon2id() functions, while perhaps keeping the default value of 1U in the generic crypto_pwhash() function, when they call them.

Currently working on a patch (#1221)