|
|
Yescrypt
Yescrypt is a password-based key derivation function. It applies slow cryptographic operations to a password and salt, creating a key suitable for performing encryption or storage to validate the password in the future. Yescrypt algorithm is based on scrypt by Colin Percival of Tarsnap.
Contents
Yescrypt parameters
The yescrypt algorithm accepts the following parameters:
- Password – The password from which to derive the key.
- Salt – A random string that is unique to this password.
- N – Increasing N increases running time and memory use.
- R – Increasing R increases the size of the blocks operated on by the algorithm (and thus increases memory use).
- P – Parallelism factor.
- T – Increasing T increases running time without increasing memory use.
- G – The number of times the hash has been "upgraded." This is used for strengthening stored password hashes without requiring knowledge of the original password.
- Flags – Flags enabling/disabling yescrypt features.
- [ROM] – Read-only memory that the resulting key will be made to depend on.
- DKLen – The length of key to derive (output).
Upon completion, yescrypt returns an array of DKLen bytes, which is a key derived from the Password and Salt according to the other parameters.
The parameters must be of the following types and must conform to the following restrictions.
- Password – A byte array of arbitrary length.
- Salt – A byte array of arbitrary length.
- N – An integer power of two, strictly greater than 1.
- R – An integer strictly greater than zero.
- P – An integer strictly greater than zero.
- T – An integer greater than or equal to zero.
- G – An integer greater than or equal to zero.
- Flags – Valid flags are: YESCRYPT_RW, YESCRYPT_WORM, and YESCRYPT_PREHASH. Each flag can either be set or not set.
- [ROM] – An array of NROM blocks (a block is defined below), where NROM is a power of two strictly greater than 1. Read-only memory supporting fast random access. Optional. Maybe NULL.
The YESCRYPT_RW and YESCRYPT_WORM flags may not be set at the same time. T may only be non-zero when either the YESCRYPT_RW flag or the YESCRYPT_WORM flag is set. When the YESCRYPT_RW flag is set, floor(N/p) must be strictly greater than 1.
When no flags are set, T = 0, G = 0, and no ROM is given, Yescrypt is equivalent to classic scrypt.
In actual implementations of yescrypt, there will be further restrictions to these parameters. Values computed from them may overflow the integer type used to store the result. It is up to the programmer to determine these limitations and check for them, as they are platform-dependant. The integerify() function is specified to return a 64-bit value. This value is then "wrapped" according to a value computed from these parameters. If the wrap limit is more than 264, then yescrypt is no longer secure. It is left to the programmer to check for this case.
Constants in Yescrypt
The Yescrypt algorithm depends on several constants. These constants are not parameters to the algorithm. They are fixed at compile-time, and it is recommended to use the default values as specified here. The configurable constants may be changed independently. The derived constants are computed from the configurable constants.
Configurable Constants
PWXSIMPLE = 2 PWXGATHER = 4 PWXROUNDS = 6 SWIDTH = 8
Derived Constants
The derived constants are derived from the configurable constants.
PWXBYTES = PWXGATHER * PWXSIMPLE * 8 PWXWORDS = PWXBYTES / 4 SBYTES = 3 * (2^SWIDTH) * PWXSIMPLE * 8 SWORDS = SBYTES / 4 SMASK = ((2^SWIDTH) - 1) * PWXSIMPLE * 8 RMIN = (PWXBYTES + 127) / 128
Data Types of Yescrypt algorithm
Yescrypt operates on arrays of 32-bit unsigned integers. Yescrypt operates on groups of words at a time, so it is useful to define terminology for the sizes of these groups. A "cell" will refer to an array of 16 words. A "block" will refer to an array of 2*R cells, where R is a yescrypt parameter as defined above.
For example, if B is a block, then B[0] will refer to the first cell in the block, and B[1] will refer to the second cell in the block. B[0][0] will refer to the first word in the first cell of B, and B[0][1] will refer to he second word in the first cell of B. Yescrypt uses a data structure called an Sbox. An sbox is an array S of SWORDS words with three pointers (equivalently, indices) into it, called S0, S1, and S2, and an integer w. When initialized, S2 points to the beginning of S, S1 points a third of the way into S (index SWORDS / 3), and S0 points two-thirds of the way into S (index 2 * SWORDS / 3). Whenever a block or cell needs to be interpreted as a byte array, the words should be encoded in little-endian byte order.
Whenever necessary, we assume integer parameters and loop counters are contained in 64-bit unsigned integers. Overflow checks have been omitted from the psuedocode in this document, but are necessary in real implementations.
Functions
For each function, developers specify the input parameters and precondition constraints they must satisfy. They also specify the output and the properties it should satisfy given that the preconditions were satisfied. Note that some of the functions return values by modifying one of their input parameters. The functions' actions are specified in pseudocode.
yescrypt_kdf
Input (See Section 2 for explanations and constraints):
Password
Salt
N
R
P
T
G
Flags
[ROM]
DKLen
Output:
DK - A key derived from the password and salt according to the other parameters.
Preconditions:
- See Section 2.
Steps:
if
YESCRYPT_RW flag is set AND
P >= 1 AND
N/P >= 0x100 AND
(N/P) * R >= 0x20000
then
Password = yescrypt(
Password,
Salt,
N / 2^6,
R,
P,
0,
0,
Flags | YESCRYPT_PREHASH,
32
)
end if
for i = 0 to g - 1 do
Password = yescrypt_kdf_body(Password, Salt, N, R, P, T, Flags, 32)
N = N * 4
T = floor(T / 2)
end
Password = yescrypt_kdf_body(Password, Salt, N, R, P, T, Flags, DKLen)
return Password
yescrypt_kdf_body
Input (See Section 2 for explanations and constraints):
Password
Salt
N
R
P
T
Flags
[ROM]
DKLen
Output:
DK - A key derived from the password and salt according to the
other parameters.
Preconditions:
- See Section 2.
Steps:
if YESCRYPT_PREHASH flag is set then
Password = HMAC-SHA256(Password, "yescrypt-prehash")
else if YESCRYPT_RW flag is set OR YESCRYPT_WORM flag is set
Password = HMAC-SHA256(Password, "yescrypt")
end if
B[0], B[1], ..., B[P-1] = PBKDF2-SHA256(Password, Salt, 1, P * 128 * R)
if any of the YESCRYPT_RW, YESCRYPT_WORM, or YESCRYPT_PREHASH flags are set
Password = The first 32 bytes of B[0]
end if
if YESCRYPT_RW flag is set then
sMix(N, R, T, P, B, Flags, ROM, Password)
else
for i = 0 to P - 1 do
sMix(N, R, T, 1, B[i], Flags, ROM, Password)
end
end if
Result = PBKDF2-SHA256(Password, B, 1, max(DKLen, 32))
if
(YESCRYPT_RW flag is set OR YESCRYPT_WORM flag is set) AND
YESCRYPT_PREHASH flag is *not* set
then
ClientValue = First 32 bytes of Result
ClientKey = HMAC-SHA256("Client Key", ClientValue)
StoredKey = SHA256(ClientKey)
Set the first 32 bytes of Result to the StoredKey
end if
return the first dkLen bytes of Result
sMix
Input:
N - An integer power of two strictly greater than one.
R - An integer strictly greater than zero.
T - An integer greater than or equal to zero.
P - An integer strictly greater than zero.
Blocks - An array of P blocks.
Flags - Valid flags are: YESCRYPT_RW, YESCRYPT_WORM, and YESCRYPT_PREHASH. Each flag can either be set or not set.
[ROM] - An array of NROM blocks, where NROM is a power of two. May be NULL.
sha256 - An array of 32 bytes.
Output:
The Blocks and sha256 parameters are modified in-place.
Preconditions:
Steps:
Allocate P Sboxes SBox[0], SBox[1], ..., SBox[P - 1].
n = N / P
Nloop_all = fNloop(n, T, Flags)
if YESCRYPT_RW flag is set
NLoop_rw = Nloop_all / P
else
NLoop_rw = 0
end
n = n - (n % 2)
Nloop_all = Nloop_all + (Nloop_all % 2)
Nloop_rw = Nloop_rw + (Nloop_rw % 2)
Allocate N blocks V[0], V[1], ..., V[N-1]
for i = 0 to p - 1 do
v = i * n
if i == p - 1 do
n = N - v
end if
w = v + n - 1
if YESCRYPT_RW flag is set
# Note: This call modifies the first two cells of Blocks[i], and
# that modification must be saved.
sMix1(1, First two cells of Blocks[i], SBYTES/128, SBox[i].S, Flags without YESCRYPT_RW, NULL, ROM)
if i == 0 do
sha255 = HMAC-SHA256(Blocks[i][2*r - 1], SHA256)
end
else
SBox[i] = NULL
end if
sMix1(R, Blocks[i], n, V[v..w], Flags, SBox[i], ROM)
sMix2(R, Blocks[i], p2floor(n), Nloop_rw, V[v..w], Flags, SBox[i], ROM)
end for
for i = 0 to p - 1 do
sMix2(R, Blocks[i], N, Nloop_all - Nloop_rw, V, flags without YESCRYPT_RW, SBox[i], ROM)
end
sMix1
Input:
R - An integer strictly greater than zero.
Block - A block.
N - An integer strictly greater than zero.
OutputBlocks - An array of N blocks.
Flags - Valid flags are: YESCRYPT_RW, YESCRYPT_WORM, and YESCRYPT_PREHASH. Each flag can either be set or not set.
[SBox] - Either NULL or an sbox.
[ROM] - An array of NROM blocks, where NROM is a power of two. May be NULL.
Output:
The Block and OutputBlocks parameters are modified in-place.
Preconditions:
Steps:
SIMDShuffle(Block)
for i = 0 to N - 1 do
OutputBlocks[i] = Block
if (ROM is not NULL) AND (i % 2 != 0)
j = integerify(R, Block) % NROM
Block = Block XOR ROM[j]
else if YESCRYPT_RW flag is set AND i > 1
j = wrap(integerify(R, Block), i)
Block = Block XOR OutputBlocks[j]
end if
if SBox is NULL
blockmix_salsa8(R, Block)
else
blockmix_pwxform(R, Block, SBox)
end if
end for
SIMDUnshuffle(Block)
sMix2
Input:
R - An integer strictly greater than zero.
Block - A block.
N - An integer power of two strictly greater than 1.
Nloop - An integer greater than or equal to zero.
OutputBlocks - An array of N blocks.
Flags - Valid flags are: YESCRYPT_RW, YESCRYPT_WORM, and YESCRYPT_PREHASH. Each flag can either be set or not set.
[Sbox] - Either NULL or an sbox.
[ROM] - An array of NROM blocks, where NROM is a power of two.
May be NULL.
Output:
The Block and OutputBlocks parameters are modified in-place.
Preconditions:
Steps:
SIMDShuffle(Block)
for i = 0 to NLoop - 1 do
if (ROM is not NULL) AND (i % 2 != 0)
j = integerify(R, Block) % NROM
Block = Block XOR ROM[j]
else
j = integerify(R, Block) % N
Block = Block XOR OutputBlocks[j]
if YESCRYPT_RW flag is set
OutputBlocks[j] = Block
end if
end if
if SBox is NULL
blockmix_salsa8(R, Block)
else
blockmix_pwxform(R, Block, SBox)
end if
end for
SIMDUnshufle(Block)
blockmix_pwxform
Input:
R - An integer strictly greater than zero.
Block - A block.
Sbox - An sbox (may not be NULL)
Output:
The Block parameter is modified in-place.
Preconditions:
Steps:
pwx_blocks = floor(2 * R * 16 / PWXWORDS)
# Pretend "cells" are now made up of PWXWORDs words, instead of 16.
PWXB = View Block as PWXB[0], PWXB[1], ..., PWXB[pwx_blocks - 1] chunks
of size PWXWORDS.
X = PWXB[pwx_blocks - 1]
for i = 0 to pwx_blocks - 1 do
if pwx_blocks > 1
X = X XOR PWXB[i]
end
pwxform(X)
PWXB[i] = X
end for
# Go back to thinking of cells as 16 words.
i = (pwx_blocks - 1) * PWXWORDS / 16
salsa20_r(Block[i], 2)
for i = i + 1 to 2 * r - 1 do
# Check this... I think this is right, and actually simpler.
# (If it is, we don't need that extra array in the Ruby impl.)
Block[i] = Block[i - 1] XOR Block[i]
salsa20_r(Block[i], 2)
end for
pwxform
Input:
PWXBlock - An array of PWXWORDS words.
Sbox - An sbox (may not be NULL).
Output:
The PWXBlock parameter is modified in-place.
Preconditions:
Steps:
S0 = Sbox.S0
S1 = Sbox.S1
S2 = Sbox.S2
for i = 0 to PWXROUNDS - 1 do
for j = 0 to PWXGATHER - 1 do
x_lo = PWXBlock[2 * j * PWXSIMPLE]
x_hi = PWXBlock[2 * j * PWXSIMPLE + 1]
p0 = (x_lo & SMASK) / (PWXSIMPLE * 8)
p1 = (x_hi & SMASK) / (PWXSIMPLE * 8)
for k = 0 to PWXSIMPLE - 1 do
lo = PWXBlock[2 * (j * PWXSIMPLE + k)]
hi = PWXBlock[2 * (j * PWXSIMPLE + k) + 1]
s0 = Sbox.S[S0 + 2 * (p0 * PWXSIMPLE + k)] + (Sbox.S[S0 + 2 * (p0 + PWXSIMPLE + k) + 1] * 2^32)
s1 = Sbox.S[S1 + 2 * (p1 * PWXSIMPLE + k)] + (Sbox.S[S1 + 2 * (p1 * PWXSIMPLE + k) + 1] * 2^32)
result = (((hi * lo) + s0) XOR s1) % 2^64
PWXBlock[2 * (j * PWXSIMPLE + k)] = result % 2^32
PWXBlock[2 * (j * PWXSIMPLE + k)] = floor(result / 2^32)
if i != 0 && i != PWXROUNDS - 1 do
Sbox.S[S2 + 2 * Sbox.w] = result % 2^32
Sbox.S[S2 + 2 * Sbox.w + 1] = floor(result / 2^32)
Sbox.w = Sbox.w + 1
end
end
end for
end for
Sbox.S0 = S2
Sbox.S1 = S0
Sbox.S2 = S1
sbox.w = sbox.w & (SMASK / 8)
blockmix_salsa8
Input:
R - An integer strictly greater than zero.
Block - A block.
Output:
The Block parameter is modified in-place.
Preconditions:
Steps:
X = Block[2 * r - 1]
Allocate a block Y.
for i = 0 to 2 * r - 1 do
X = X XOR Block[i]
salsa20_r(X, 8)
if i % 2 == 0
Y[i/2] = X
else
Y[r + (i-1)/2] = X
end
end for
Block = Y
salsa20_r
Input:
Cell - A cell.
r - Number of rounds.
Output:
The Words parameter is modified in-place.
Preconditions:
Steps:
This is the Salsa20 core reduced to r rounds with a SIMD unshuffle (like
SIMDUnshuffle) pre-applied and a SIMD shuffle (like SIMDShuffle)
post-applied. See [7] for more information.
specify the shuffling completely here
fNloop
Input:
N - An integer strictly greater than zero.
T - An integer greater than or equal to zero.
Flags - Valid flags are: YESCRYPT_RW, YESCRYPT_WORM, and
YESCRYPT_PREHASH. Each flag can either be set or not set.
Output:
Returns a positive integer.
Preconditions:
Steps:
The result is defined according to this table:
+------+-----------------+-----------------+-----------+
| | Nloop | | |
| t | YESCRYPT_RW | YESCRYPT_WORM | Otherwise |
+------+-----------------+-----------------+-----------+
| 0 | (N+2)/3 | N | N |
| 1 | (2N + 2) / 3 | N + (N + 1) / 2 | N |
| > 1 | (t - 1)*N | t*N | N |
+------+-----------------+-----------------+-----------+
p2floor
Input:
X - An integer strictly greater than 0.
Output:
Returns the greatest power of two less than or equal to X.
Preconditions:
Steps:
y = X & (X - 1)
while y != 0
X = y
y = X & (X - 1)
end while
return X
Yescrypt – wrap
Input:
X - An integer greater than or equal to zero.
L - An integer strictly greater than zero.
Output:
Returns an integer in the range 0 to L-1 (inclusive).
Preconditions:
Steps:
n = p2floor(X)
return (X % n) + (L - n)
integerify
Input:
R - An integer strictly greater than zero.
Block - A block.
Output:
Returns an integer. A 64-bit value derived from Block.
Preconditions:
Steps:
return B[2*R - 1][0] + (B[2*R - 1][13] * 2^32)
SIMDShuffle
Input:
R - An integer strictly greater than zero.
Block - A block.
Output:
Block is shuffled in place.
Preconditions:
Steps:
for i = 0 to 2*R - 1 do
Saved = Block[i]
for k = 0 to 15 do
Block[i][k] = Saved[(k * 5) % 16]
end
end for
SIMDUnshufle
Input:
R - An integer strictly greater than zero.
Block - A block.
Output:
Block is unshuffled in place.
Preconditions:
Steps:
for i = 0 to 2*R - 1 do
Saved = Block[i]
for k = 0 to 15 do
Block[i][(k * 5) % 16] = Saved[k]
end
end for
HMAC-SHA256
Input:
Key - An arbitrary-length array of bytes.
Message - An arbitrary-length array of bytes.
There are actual limitations coming from SHA256's input size limit.... should we be more precise?
Output:
An array of 32 bytes.
Preconditions:
Steps:
HMAC is defined in RFC2104.
PBKDF2-SHA256
Input:
Password - An arbitrary-length array of bytes.
Salt - An arbitrary-length array of bytes.
Iterations - An integer strictly greater than zero.
DKLen - An integer strictly greater than zero.
Output:
An array of DKLen bytes.
Preconditions:
Steps:
PBKDF2 is defined in RFC2898.
SHA256
Input:
Message - An arbitrary-length array of bytes.
Output:
An array of 32 bytes.
Preconditions:
Steps:
SHA-256 is defined in Secure Hash Standard (SHS) – FIPS180-4.
Security
Note that non-optimized implementations are essentially insecure, sothe implementer needs to know their platform and might need to changetheir implementation from what we implicitly assume (e.g. 32-bit integers)ю
Yescrypt Miner
There are GPU miners for mining of Yescrypt via AMD and NVIDIA. However, at the moment these miners show less performance compared to mining Yescrypt using CPU.
Two cryptocurrencies – Global Boot-u (BASTY) Unitas and TBC - are currently based on the Scrypt algorithm, and the ITI is an alternative cryptocurrency with multi-support algorithms.
Results for Yescrypt performance:
- i7 5820K processor: 5.22 XC
- AMD Radeon R9 280X GPU: 0.793 kHz
- NVIDIA GeForce GTX 980 GPU: 1.124 kHz
See also
External links
- The Yescrypt Password-Based Key Derivation Function DRAFT
- https://password-hashing.net/submissions/specs/yescrypt-v1.pdf
