proposal: x/crypto: yescrypt support

[gustavosbarreto]

With yescrypt being the default password hashing scheme on recent ALT Linux, Debian 11, Fedora 35+, and Kali Linux 2021.1+. It is also supported in Fedora 29+ and Ubuntu 20.04+, and is recommended for new passwords in Fedora CoreOS. it might be desirable to support yescript in golang.

Yescrypt is a notable algorithm:

• Publicly known, modern algorithm, by Solar Designer (@solardiz)
• PHC finalist: https://www.password-hashing.net/
• Interest appears to be increasing in this algorithm - starting to appear in the wild and reported in StackExchange questions, etc.

Where used:

• Supported by libxcrypt, a drop-in replacement for libcrypt.so.1: https://github.com/besser82/libxcrypt/
• Default hashing method on Fedora: https://fedoraproject.org/wiki/Changes/yescrypt_as_default_hashing_method_for_shadow
• Default hashing method on Debian: https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=978553

Tech details:

• Initial golang implementation: https://github.com/dmitescu/yescrypt_gsoc/blob/master/y_golang/main.go
• Pseudocode: https://openwall.info/wiki/yescrypt
• PHC full documentation: https://www.password-hashing.net/submissions/specs/yescrypt-v2.pdf
• Source code: https://github.com/openwall/yescrypt
• Official doc (yescrypt): https://www.openwall.com/yescrypt/
• Official doc (john-jumbo): https://github.com/openwall/john/tree/bleeding-jumbo/src/yescrypt
• More details from Debian manpage (https://manpages.debian.org/experimental/libcrypt1-dev/crypt.5.en.html):

* Hashed passphrase format: \$y\$[./A-Za-z0-9]+\$[./A-Za-z0-9]{,86}\$[./A-Za-z0-9]{43}
* Maximum passphrase length: unlimited
* Hash size: 256 bits
* Salt size: up to 512 bits
* CPU time cost parameter: 1 to 11 (logarithmic)

[seankhliao]

cc @FiloSottile

[mdlayher]

Although this is for x/crypto, I believe the stdlib FAQ applies here: https://go.dev/doc/faq#x_in_std

[gustavosbarreto]

Although this is for x/crypto, I believe the stdlib FAQ applies here: https://go.dev/doc/faq#x_in_std

I have no idea of the golang internals, so I don't know where this should be implemented. It would be nice if someone could help.

[solardiz]

Thanks for tagging me on this, @gustavosbarreto. I'm also not familiar with Go and where this would need to be. Would this require yescrypt implementation written in Go or would it use the existing C+SIMD code under the hood? I'd prefer the latter, for performance and future maintenance reasons. Also, this should possibly use shared code with scrypt from go.crypto, as yescrypt can also compute classic scrypt from the same codebase, and not only the password hashing but also the KDF functionality (both classic scrypt and yescrypt) should be exposed (unlike in libxcrypt, which only exposes a subset of the password hashing functionality). Maybe @dchest wants to comment?

[dchest]

@solardiz Go libraries don't use C, so it would need to be reimplemented in Go, but can use assembly for performance sensitive parts. Indeed, it makes sense to share code with existing x/crypto/scrypt implementation, especially if there's SIMD implementation (current scrypt is not SIMD).

Personally, I would like to see yescrypt in x/crypto, and can help review it. I think the best first step would be to have a nice third-party package outside of x/crypto first, that people can use, and then propose it for inclusion once it reaches some level of acceptance. From what I see, the linked initial implementation has some room for improvement with regards to code style.

[solardiz]

As an option, https://github.com/golang/crypto/blob/master/scrypt/scrypt.go can be enhanced to also compute yescrypt when that is requested by the caller. This file can then be renamed to yescrypt.go. Alternatively, if optimizing for speed rather than simplicity, a yescrypt.go can be created from scratch based on yescrypt-opt.c (which would avoid the block copy overhead and could have SIMD). Either way, wrapper functions for password hash encoding and optionally password hash encryption should then be added (based on yescrypt-common.c, so maybe also in a separate .go file). All of this can happen in a (derived) separate package first, like @dchest suggests.

[rsc]

What would the API be if we extended package scrypt?

[rsc]

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.
— rsc for the proposal review group

[dchest]

Some initial thoughts on API:

For yescrypt, there are new arguments in addition to N, r, p: t, g, and NROM:

Set t (time) to 0 to use the optimal running time for a given memory
usage.  This will allow you to maximize the memory usage (the value of
N*r) while staying within your running time constraints.  (Non-zero t
makes sense in specialized cases where you can't afford higher memory
usage but can afford more time.)

Set g (upgrades) to 0 because there have been no hash upgrades yet.

Set NROM (block count of ROM) to 0 unless you use a ROM (see below).
NROM must be a power of two.

The current signature of scrypt is:

func Key(password, salt []byte, N, r, p, keyLen int) ([]byte, error) 

For yescrypt it would be a lot of arguments for a single function. It also needs an optional ROM buffer to be passed. Perhaps, it should use a struct for parameters, which would also be useful for serialization.

Additionally, yescrypt defines a password hash format, just like bcrypt, so we can define GenerateFromPassword and CompareHashAndPassword (to be fair, I'm not a fan of the bcrypt package API).

Yescrypt also defines a way to encrypt/decrypt/re-encrypt hashes with a secret key. Those would be separate functions.

[rsc]

@dchest so it sounds like yescrypt really wouldn't reuse any of the bcrypt API?
In that case it probably make sense as its own package.
(It also sounds like the API should use a Config struct instead of an ever-growing list of ints.)

Given that it's not just a tweak to x/crypto/bcrypt, should it really be in x?
@mdlayher pointed out https://go.dev/doc/faq#x_in_std, which mostly applies to the x repos as well.

Is there a reason it shouldn't be a package maintained by someone else?
I see that Debian and Fedora are using it for /etc/shadow hashes.
Maybe that makes it important enough?

Thoughts, @FiloSottile?

[dchest]

@rsc it wouldn't use the API (of x/crypto/scrypt), but the internals of implementations can be shared. In fact, it might make sense to implement yescrypt, and then switch x/crypto/scrypt to call it.

Is there a reason it shouldn't be a package maintained by someone else?

I think this should be at least the first step. It would be nice to have a fast Go/assembly implementation of yescrypt as a package. Once there is such implementation, contributing it into x/crypto would benefit the performance of x/crypto/scrypt by switching it to call yescrypt with some configuration flags set to zero. (BTW, x/crypto/scrypt also began its life as a third-party package.)

[rsc]

/cc @golang/security

[FiloSottile]

The average Go application is probably fine with x/crypto/argon2 for generic password hashing, and providing multiple choices for the same job is not a goal of the standard library (or of x/crypto). Compatibility with Debian and Fedora is something that can be addressed through a third-party module. The strongest argument for inclusion would be centralizing improvements in the shared backend with scrypt. On balance, that does not feel worth the extra maintenance burden of a new package.

FYI, there is an approved proposal for adding a high-level API to x/crypto/scrypt, which might be of interest to anyone implementing the yescrypt package. #16971

[rsc]

Based on the discussion above, this proposal seems like a likely decline.
— rsc for the proposal review group

[rsc]

No change in consensus, so declined.
— rsc for the proposal review group

[xlango]

Can you provide the source code of golang to implement yescrypt?

[mdlayher]

I've been asked to share this link in case others search for yescrypt support on the Go issue tracker:

https://pkg.go.dev/github.com/openwall/yescrypt-go