Issues from high-level review of yescrypt core code

[zackw]

I looked over the yescrypt core code, mostly for integration problems with the libxcrypt environment. I didn’t do a thorough review; this code is already mature, and I’m not qualified to review cryptographic primitives anyway. I have some immediate concerns regarding the code in yescrypt-platform.c, but nothing else urgent. There are also a number of long-term changes that we might want to make, mostly in the direction of reducing code duplication between this hashing method and others.

I would like to ask @solardiz a number of questions in his role as upstream yescrypt maintainer; all direct questions below are aimed at him. I’m filing this as a bug on libxcrypt so I don’t lose it, but I’m happy to take the conversation to some upstream forum if you tell me where to go.

General commentary

I see _OPENMP ifdefs in yescrypt-opt.c. Does that actually work to the point where it would be worth the trouble for us to add a --with-openmp switch to the configure script and wiring it all up? Does this provide a useful performance gain for authentication uses, or is it just good for cracking?

I appreciate the detailed documentation comments on all the API functions in yescrypt.h. It would be nice to have complete documentation of all the flag bits as well (it says “refer to the description of yescrypt_kdf,” but that only covers YESCRYPT_WORM vs YESCRYPT_RW).

Down the road, I think it would make sense for libxcrypt to expose more of the tunability that is available via the yescrypt_* functions, by adding a new version of the crypt_gensalt interface that can take more parameters. It might even be desirable to bring back ROMs and other persistent state beyond what struct crypt_data can handle. I haven’t thought much at all about what that would entail API-wise, but because of that, I am fine with keeping around code that is currently unreachable.

Immediate concerns

These all relate to yescrypt-platform.c.

Nothing is arranging for HAVE_POSIX_MEMALIGN to be defined or not defined as appropriate. This is fixable on our end, since it’s the standard macro that autoconf would define if asked to check for posix_memalign, but I would like to ask where it came from in the first place—I don’t see any machinery in Openwall’s yescrypt repo to set it.

sys/mman.h is not guaranteed to exist just because __unix__ is defined. Normally I wouldn’t worry about that, but this library may be wanted in embedded no-MMU contexts. I would like to replace that with another autoconf test (using AC_CHECK_HEADERS to define HAVE_SYS_MMAN_H; AC_FUNC_MMAP does both more and less than we would actually need, having been written for the way GNU grep wants to use mmap), but how should we go about that such that it is not a problem to merge back?

I think it would be a good idea to restructure the logic in alloc_region so that it attempts to use posix_memalign and malloc if mmap fails. Would that be a change you would accept?

It’s weird that this file is included into yescrypt-opt.c. I see how it is desirable for init_region to be inline, but what would you think of creating a yescrypt-internal.h that defined that function and declared the other two (with yescrypt_ name prefixes) and then compiling this file separately?

It’s possible to determine the supported huge page size(s) at runtime by parsing /proc/meminfo and/or /sys/kernel/mm/hugepages. Down the road you may want to consider that instead of a pile of CPU-specific ifdefs.

Longer-term refactoring

The yescrypt code includes implementations of base64 encoding and decoding, fixed-endian-to-CPU conversions, SHA-2-256, Salsa20, HMAC, and PBKDF. With the exception of Salsa20, all of these have at least one other implementation in libxcrypt. I would like to move in the direction of giving each of these their own canonical implementation. This will both reduce code size and facilitate performance tuning—for instance, I can see people wanting ARM-specific optimizations down the road.

I have no problem with the canonical implementation being the one from yescrypt, but we would need them to be in their own files and have public headers. If we took the lead on factoring out these duplicated implementations, would you be open to the possibility of merging them upstream?

The most complicated thing to deduplicate will actually be the base64 coding, because bcrypt uses a slightly different alphabet from all the other hashes. And if we ever add Argon2, that has yet another one, because they decided to match MIME. The most bikesheddy thing to deduplicate will, alas, be the endian-to-CPU conversions. yescrypt is currently using names that collide with BSD <sys/endian.h> and working around that with macros, and I think that’s an argument for switching away from those names.

[solardiz]

Thank you for your review. A proper "upstream forum" could be the yescrypt mailing list, but then you also bring up questions specific to libxcrypt and I don't mind addressing them in here.

Re: General commentary

The OpenMP support is primarily for the KDF use case and for ROM initialization. It is currently mostly irrelevant for authentication (except for a possible ROM initialization step) and for password cracking. It does provide "a useful performance gain" when p > 1, but for authentication we currently recommend p = 1, so there's nothing to parallelize at thread level within one hash computation. (Password crackers typically have their parallelism at a higher level, across multiple hash computations.) Thus, whether "it would be worth the trouble for us to add a --with-openmp switch" depends on the use cases for libxcrypt: if it's authentication only then no, if it's also KDF and/or ROM initialization then probably yes (but if so we may also need to discuss libgomp reliability issues).

A direct answer to your "Does this provide a useful performance gain for authentication uses, or is it just good for cracking?" is thus "Typically neither."

YESCRYPT_WORM and YESCRYPT_RW are currently the only flag bits a user may configure, but YESCRYPT_RW also requires the setting of the rest of the bits in YESCRYPT_DEFAULTS. Those many extra bits provide for future extension: we specify and encode the pwxform parameters via YESCRYPT_DEFAULTS right now, so that these defaults may change later yet the old hashes would still work.

As to passing of more parameters via libxcrypt, I think a way to do that might be to allow for specification of prefix strings that already include the parameters. They would then need to be encoded into those strings separately, e.g. by expert users having invoked programs bundled with yescrypt and Argon2 distributions separate from libxcrypt.

Regarding bringing back the ROMs, they're useful on large authentication servers, and not for logging in to local Unix accounts. Is that a use case for libxcrypt? Perhaps a non-local authentication service could link against libxcrypt instead of building/linking in yescrypt files directly into itself?

Re: Immediate concerns (yescrypt-platform.c)

Yes, nothing defines HAVE_POSIX_MEMALIGN. I was already unhappy about that, and now that you also point it out I think I should simply drop that version of the code, and only support mmap and malloc. We have structs and code to keep track of the allocation start vs. aligned addresses anyway. OK to drop it?

I'm unaware of an improvement I can make on checking for __unix__ for sys/mman.h without resorting to autoconf, so I'm unlikely to make any related change in my tree. I think whoever is building for no-MMU will easily edit this, and you may add autoconf checks in your tree. I'd also take a look at what libsodium does there.

I dislike the idea of falling back to malloc if mmap fails, because mmap is not supposed to fail and if it does that's something I'd like to be notified of. Also, mmap / munmap removes the sensitive data from the process' address space, which can matter in case the process is compromised through some untrusted input post-authentication. It is not good to have this property conditional upon a fallback not occurring.

Yes, it's weird that yescrypt-platform.c is included into yescrypt-opt.c. I didn't want to export those internal symbols, and this file used to be shared between -simd and -opt. Now that those files have been merged together, maybe I should merge -platform contents in there too. OTOH, the regions API is also useful without yescrypt, e.g. libsodium reuses it along with Argon2. So this isn't a trivial decision.

I'd rather not "determine the supported huge page size(s) at runtime" - this is extra complexity and potential for failure, and besides transparent hugepages just work in recent kernels.

Re: Longer-term refactoring

The Salsa20 included in yescrypt isn't the full thing - it's just the Salsa20 core.

The rest of primitives you list are in fact complete. However, the HMAC and PBKDF2 are tied to their use with SHA-256. To make more generic ones that would also work e.g. with SHA-512 would require object-oriented-like APIs with function pointers (extra risk in case of memory corruption vulnerabilities, and slower) or uses of the x-macro programming technique (IIRC, I saw NetBSD do that for the HMACs).

Yes, their reuse by the rest of libxcrypt makes sense to me, except that I'd like these HMAC and PBKDF2 to stay SHA-256 only. Also, I'd rather keep the sha256.c file as-is, not split it further. Splitting it would unnecessarily expose internal symbols, and would be inconsistent with the way Colin Percival has it in scrypt and FreeBSD.

Yes, this base 64 encoding is not usable for bcrypt, nor for Argon2, but should be reusable for the rest of crypts.

The sysendian functions and workaround macros come from the scrypt tree, and I'd rather keep them as-is. Colin is a FreeBSD developer (and was once FreeBSD Security Officer), so if code reuse and resolving the clash in this way is OK with him, it certainly also is OK with me.