# How does Scrypt use Salsa?

Bcrypt uses Blowfish to encrypt a derived key from the passphrase, and Blowfish is a cryptographic algorithm, but here it is said that:

Note that Salsa20/8 Core is not a cryptographic hash function since it is not collision-resistant.

so how this is useful in Scrypt?

-

Salsa20/8 is used not to enhance cryptographic strength, but to make random-ordered requests to the RAM (and to slower FPGA/ASIC implementation of scrypt). The scrypt uses PBKDF2-HMAC-SHA-256 (PBKDF2 of HMAC-SHA256) to provide such strength.

There is simple variant of scrypt, with parameters p=1 (Parallelization parameter), N=16384, r=8, taken from linked draft and simplified for p=1:

Algorithm scrypt

Input:
P       Passphrase, an octet string.
S       Salt, an octet string.
N       CPU/Memory cost parameter, must be larger than 1,
a power of 2 and less than 2^(128 * r / 8).
r       Block size parameter.
p       Parallelization parameter, a positive integer
less than or equal to ((2^32-1) * hLen) / MFLen
where hLen is 32 and MFlen is 128 * r.
dkLen   Intended output length in octets of the derived
key; a positive integer less than or equal to
(2^32 - 1) * hLen where hLen is 32.

Output:
DK      Derived key, of length dkLen octets.

Steps:

1. B[0] = PBKDF2-HMAC-SHA256 (P, S, 1, 128 * r)

2. B[0] = scryptROMix (r, B[0], N)

3. DK = PBKDF2-HMAC-SHA256 (P, B[0], 1, dkLen)


We can see that there are two PBKDF2 with HMAC SHA256, one before ROMix and one after. They will provide collision resistance for the scrypt.

And here is the scryptROMix, which uses N-sized array, every element of which is equal to scryptBlockMix of previous element (step 2). Salsa is used inside scryptBlockMix and in scryptROMix it defines both transformations of X and the order of read accesses to V array:

Algorithm scryptROMix

Input:
r       Block size parameter.
B       Input octet vector of length 128 * r octets.
N       CPU/Memory cost parameter, must be larger than 1,
a power of 2 and less than 2^(128 * r / 8).

Output:
B'      Output octet vector of length 128 * r octets.

Steps:

1. X = B

2. for i = 0 to N - 1 do
V[i] = X
X = scryptBlockMix (X)
end for

3. for i = 0 to N - 1 do
j = Integerify (X) mod N
where Integerify (B[0] ... B[2 * r - 1]) is defined
as the result of interpreting B[2 * r - 1] as a
little-endian integer.
T = X xor V[j]
X = scryptBlockMix (T)
end for

4. B' = X

-
PBKDF2 is the (KDF) function definition (pbkdf2 algorithm), it can be used with many hashed; and HMAC-SHA256 is actual parameter to the PBKDF2 function. So, when author writes only PBKDF2, we can't implement it; but when the PBKDF2-HMAC-SHA-256 name is used, we can implement PBKDF2 with HMAC-SHA-256 as hash function. –  osgx Jul 24 '13 at 19:02
The scrypt draft even says "The PBKDF2-HMAC-SHA-256 function used below denote the PBKDF2 algorithm used with HMAC-SHA-256 as the PRF." –  osgx Jul 24 '13 at 19:03
Abdelouahab Pp, wrong. There is scrypt algorithm for crypting passowrds. Scrypt uses PBKDF2, then some function (which uses Salsa20 for some operations), then another iteration of PBKDF2. –  osgx Jul 24 '13 at 21:12
Abdelouahab Pp, There are lot of algorithms: SHA1, SHA256, HMAC, PBKDF2, Bcrypt, Scrypt (and other listed in wikipedia). And some of them are built based on another, sometimes via usage of original algo, and sometimes by usage of some parts of original algo. E.g. PBKDF2-HMAC-SHA-256 is variant of PBKDF2, which uses HMAC-SHA256 as PRF parameter. HMAC-SHA256 itself uses SHA256 (but there are also HMAC with MD5 and other hashes). Bcrypt uses parts of modified Bluefish cipher. And for scrypt - is uses PBKDF2 (PBKDF2-HMAC-SHA-256 variant) and some parts of Salsa20. –  osgx Jul 24 '13 at 22:30
Abdelouahab Pp, but bcrypt, scrypt and PBKDF2 are sometimes used as concurrents (for secure storage of hashed passwords in client-server applications)! And PBKDF2 even had some NIST recommendations. But scrypt still uses PBKDF2, and the scrypt's author claims that scrypt is very good for password storage while both bcrypt, PBKDF2, HMAC, FreeBSD MD5 are bad choice for storage because either they are easily attacked using GPU/FPGA/ASIC, or they should be tuned to very long checks of single passwords - minutes per client. Will you wait 2 minutes between entering gmail password and entering site? –  osgx Jul 25 '13 at 0:18

Salsa20 core is not a collision resistant hash function, see DJB's own webpage:

http://cr.yp.to/salsa20.html

For example, Salsa20core(x) = Salsa20core(x + c) for c = "0000000800000008...", thus demonstrating trivial collisions.

To be concrete, try computing Salsa20core for the the following two inputs:

00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000

and

00000080000000800000008000000080 00000080000000800000008000000080 00000080000000800000008000000080 00000080000000800000008000000080

the output for both inputs should be all zeros.

In what way do you think this property weakens scrypt?

-
so that means SCrypt is not collision resistant too? so then BCrypt is better? –  Abdelouahab Pp Jun 13 '13 at 18:43
Ah, thanks so much for correcting me!! –  fgrieu Jun 13 '13 at 19:01

IMHO it's just a warning to the reader that this is not a standard hash-based design like BSD-crypt or PBKDF2, which are traditional choices. They use the Salsa20/8 Core mixing function because its speed improves upon the first mixing function that was used in the defining paper for scrypt (that is referenced in the RFC you linked to): there he uses the SHA-1 compress function (not SHA-1 as a hash) which is function that transforms 20 bytes to 20 bytes (it's really a blockcipher, using the message blocks as a key); In the same paper he then suggests SALSA20/8 as a mixing function.

-
so salsa is not a cryptographic function? because i dont find it like DES or AES or Blowfish or Twofish? –  Abdelouahab Pp Jun 8 '13 at 12:41
It is, but it is not a hash in the traditional sense. It's a cryptographic mixing function, normally used as a component in the stream cipher Salsa20. The use in scrypt is different from its use in the stream cipher, and the author in the scrypt paper shortly discusses that too. –  Henno Brandsma Jun 8 '13 at 12:59
ah, so it is a new concept, what they want to say is: it is different than BCrypt and PBKDF2 –  Abdelouahab Pp Jun 8 '13 at 14:19
Study the SHA-1 spec. The work is done mostly in a function that transforms the 20 byte state to another 20 byte state with the message as "key" (this component is the blockcipher SHACAL). So at the core of SHA-1 is a block transform as well, and this is the one used. The whole hash is the function with the fixed input state, and message padding added, plus the iterative application of this transform for successive blocks. –  Henno Brandsma Jun 9 '13 at 4:13
The compression is as seen from the point of view of the message, not of the state. The state stays the same size, and the message bytes are all used, as many as we have. We output the state at the end, which is often a lot shorter than the message, which has been mixed into the state iteratively. –  Henno Brandsma Jun 9 '13 at 7:37

Yes, Salsa20 core is not meant to be collision resistant. But that is not relevant to the intended use case of Scrypt: Password hashing.

Password hashing is an unfortunate name, as "hashing" has so many specific meanings depending on the context. Two scenarios where you use password hashing are:

• Password storage for online services. Imagine your users log in to your site using passwords and you have to store some information per user to check that the supplied password is correct. On the other hand, if that stored information is stolen (SQL injections etc.) you don't want the passwords to be recoverable.
• Key derivation for symmetric encryption. TrueCrypt and other full disc encryption software encrypt your data using a key that is derived from the password you type in at boot time. Usually that password is not as good as a 128 bit random key would be. For example if you use 5 alphanumeric characters you might only have 36^5=60,466,176 possible passwords. If the time it takes to check whether one password is correct or not is small, bruteforcing becomes quite feasible.

What both have in common is that you have low entropy input data and want to have a guaranteed and relatively high time to compute the hash of the password. This makes sure that bruteforcing the small number of likely passwords is difficult.

Out of the classical security criteria (collision resistance, pre-image resistance and second pre-image resistance) of a cryptographic hash function only pre-image resistance is thus of interest for password hashing, as you don't want an attacker to be able to compute valid login data out of the password hash in the password storage scenario.

-
and SCrypt will use salsa to make the ram full in small amount of time? –  Abdelouahab Pp Jun 13 '13 at 22:40
It's not about filling the ram, but about needing a lot of memory to be fast. This is meant to hinder extremely parallelized hardware implementations. See en.wikipedia.org/wiki/Scrypt#Overview for details. –  Perseids Jun 14 '13 at 8:56
it's kind of feeling, since that ram is not shared, then it cant be accessible for another resource? –  Abdelouahab Pp Jun 14 '13 at 13:44