Date: Fri, 9 Mar 2018 23:53:09 +0100 From: Solar Designer <solar@...nwall.com> To: announce@...ts.openwall.com, yescrypt@...ts.openwall.com Subject: yescrypt 1.0.0 - modern KDF and password hashing scheme Hi, This is to announce the release of yescrypt 1.0.0. yescrypt is a password-based key derivation function (KDF) and password hashing scheme. It builds upon Colin Percival's scrypt and includes classic scrypt, a minor extension of scrypt known as YESCRYPT_WORM (named that for "write once, read [potentially] many [times]", which is how scrypt works), and the full native yescrypt also known as YESCRYPT_RW (for "read-write"). You can download yescrypt 1.0.0 from its new homepage: http://www.openwall.com/yescrypt/ We've also setup a mailing list (CC'ed here) for discussions around yescrypt. Please direct any questions or comments on yescrypt to the mailing list. We'll setup a web-based archive of the list once messages start to appear. yescrypt has been in development, albeit initially not under this name, since my introduction of the concept of ROM-port-hardness at ZeroNights in 2012: http://www.openwall.com/presentations/ZeroNights2012-New-In-Password-Hashing/ some revisions of yescrypt were made public under the Password Hashing Competition (PHC), where yescrypt ended up being one of the "special recognition" entries "for its rich feature set and easy upgrade path from scrypt", but not the winner: https://password-hashing.net and yescrypt 0.9.x is in production use protecting millions of passwords (we assisted with those deployments). Yet it was really difficult to commit to a certain design and feature set, knowing that we'll have to support this for many years to come. Luckily, we have finally reached this point. Moreover, the core design of yescrypt is unchanged since its last revision submitted to PHC in 2015. Even the test vectors used in PHC have remained the same. It's the various extras (beyond the PHC-mandated functionality) that took extra time to finalize and that have changed. This release is timed for tomorrow's BSidesLjubljana event, considering that I gave an extensive talk on yescrypt at last year's: http://www.openwall.com/presentations/BSidesLjubljana2017-Yescrypt-Large-scale-Password-Hashing/ Some of the detail on the last few slides in that deck pertains to yescrypt 0.9.x and is no longer valid for yescrypt 1.0+ (e.g., the ROM initialization algorithm has changed and is now faster), but overall this slide deck still applies. Why yescrypt? Like it or not, password authentication remains relevant (including as one of several authentication factors), password hash database leaks happen, the leaks are not always detected and fully dealt with right away, and even once they are many users' same or similar passwords reused elsewhere remain exposed. To mitigate these risks (as well as those present in other scenarios where password-based key derivation or password hashing is relevant), computationally expensive (bcrypt, PBKDF2, etc.) and more recently also memory-hard (scrypt, Argon2, etc.) password hashing schemes have been introduced. Unfortunately, at high target throughput and/or low target latency their memory usage is unreasonably low, up to the point where they're not obviously better than the much older bcrypt (considering attackers with pre-existing hardware). This is a primary drawback that yescrypt addresses. Most notable for large-scale deployments is yescrypt's optional initialization and reuse of a large lookup table, typically occupying at least tens of gigabytes of RAM and essentially forming a site-specific ROM. This limits attackers' use of pre-existing hardware such as botnet nodes. yescrypt's other changes from scrypt further slow down GPUs, FPGAs, and ASICs even when its memory usage is low (and even when there's no ROM), and provide extra knobs and built-in features. Technically, yescrypt is the most scalable password hashing scheme so far, providing near-optimal security from offline password cracking across the whole range from kilobytes to terabytes and beyond. However, the price for this is complexity, and we recognize that complexity is a major drawback of any software. Thus, at this time we focus on large-scale deployments. For smaller deployments, bcrypt with its simplicity and existing library support is a reasonable short-term choice (although we're making progress towards more efficient FPGA attacks on bcrypt under a separate project). We might introduce a cut-down yescrypt-lite later or/and yescrypt might become part of standard or popular libraries, making it more suitable for smaller deployments as well. A note on cryptocoins. Although multiple cryptocoins already use yescrypt 0.5'ish as their proof-of-work (PoW) scheme, we currently do not recommend yescrypt 1.0+ for use by cryptocoins. If you feel like starting a new coin or forking one, for now please use the exact same older revision of yescrypt that other coins already use (this is also easier for you to do, through forking another coin's existing codebase). We might introduce a special mode optimized for the PoW use case later. Performance. Please see the PERFORMANCE file inside the yescrypt distribution for example setup and benchmarks relevant to the mass user authentication use case. The test system is a server (kindly provided by Packet.net) with dual Xeon Gold 5120 CPUs (2.2 GHz, turbo to up to 3.2 GHz) and 384 GiB RAM (12x DDR4-2400 ECC Reg). These CPUs have 14 cores and 6 memory channels each, for a total of 28 physical cores, 56 logical CPUs (HT is enabled), and 12 memory channels. Some highlights: initialization of a 368 GiB ROM takes 22 seconds (to be done on server bootup), and while using the ROM we're able to compute over 20k, over 10k, or around 1200 password hashes per second with per-thread RAM usage of 1.4375 MiB, 2.875 MiB, or 23 MiB, respectively. When not using a ROM, we're able to compute over 20k, over 10k, over 2k, or over 1k hashes per second with per-thread RAM usage of 2 MiB, 4 MiB, 16 MiB, or 32 MiB, respectively. Changes since the last revision submitted to PHC. Hash string encoding has been finalized under the "$y$" prefix for both native yescrypt and classic scrypt hashes, using a new variable-length and extremely compact encoding of (ye)scrypt's many parameters. (Also still recognized under the "$7$" prefix is the previously used encoding for classic scrypt hashes, which is fixed-length and not so compact.) Optional format-preserving salt and hash (re-)encryption has been added, using the Luby-Rackoff construction with SHA-256 as the PRF. Support for hash upgrades has been temporarily excluded to allow for its finalization at a later time and based on actual needs (e.g., will 3x ROM size upgrades be in demand now that Intel went from 4 to 6 memory channels in their server CPUs, bringing a factor of 3 into RAM sizes?) ROM initialization has been sped up through a new simplified algorithm. ROM tags (magic constant values) and digests (values that depend on the entire computation of the ROM contents) have been added to the last block of ROM. (The placement of these tags/digests is such that nested ROMs are possible, to allow for ROM size upgrades later.) The last block of ROM is now checked for the tag and is always used for hash computation before a secret-dependent memory access is first made. This ensures that hashes won't be computed with a partially initialized ROM or with one initialized using different machine word endianness, and that they will be consistently miscomputed if the ROM digest is other than what the caller expected. This in turn helps early detection of problems with ROM initialization even if the calling application fails to check for them. This also helps mitigate cache-timing attacks when the attacker doesn't know the contents of the last block of ROM. Many implementation changes have been made, such as for performance, portability, security (intentional reuse and thus rewrite of memory where practical and optional zeroization elsewhere), and coding style. This includes addition of optional SSE2 inline assembly code (a macro with 8 instructions) to yescrypt-simd.c, which tends to slightly outperform compiler-generated code, including AVX(2)-enabled code, for yescrypt's currently recommended settings. This is no surprise since yescrypt was designed to fit the 64-bit mode extended SSE2 instruction set perfectly (including SSE2's lack of 3-register instructions), so for its optimal implementation AVX would merely result in extra instruction prefixes and not provide any benefit (except for the uses of Salsa20 inherited from scrypt, but those are infrequent). The auxiliary files inherited from scrypt have been sync'ed with scrypt 1.2.1, and the implementation of PBKDF2 has been further optimized, especially for its use in (ye)scrypt where the "iteration count" is 1 but the output size is relatively large. (The speedup is measurable at realistically low settings for yescrypt, such as at 2 MiB of memory.) The included tests have been revised and test vectors regenerated to account for the ROM initialization/use updates and hash (re-)encryption. The PHC test vectors have been compacted into a single SHA-256 hash of the expected output of phc.c, but have otherwise remained unchanged as none of the incompatible changes have affected the subset of yescrypt exposed via the PHS() interface for the Password Hashing Competition. The specification document and extra programs that were included with the PHC submission and its updates are now excluded from this release. The rest of documentation files have been updated for the 1.0.0 release. Alexander
Powered by blists - more mailing lists
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.