Yescrypt

From BitcoinWiki
This is the approved revision of this page, as well as being the most recent.
Jump to: navigation, search
Yescrypt miner

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.

Yescrypt parameters[edit]

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.

Yescrypt miner

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[edit]

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[edit]

   PWXSIMPLE = 2
   PWXGATHER = 4
   PWXROUNDS = 6
   SWIDTH = 8

Derived Constants[edit]

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[edit]

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[edit]

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[edit]

   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[edit]

   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[edit]

   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[edit]

   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[edit]

   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[edit]

   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[edit]

   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[edit]

   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[edit]

   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[edit]

   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[edit]

   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[edit]

   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[edit]

   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[edit]

   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[edit]

   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[edit]

   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[edit]

   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[edit]

   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[edit]

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[edit]

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 on BitcoinWiki[edit]

External links[edit]