[next>] [day] [month] [year] [list]
Message-ID: <20180309225309.GA12626@openwall.com>
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.
