Hazmat scryptscrypt is a password-based key derivation function which produces a hash with a salt and iterations. The iteration count slows down the cracking and the salt makes pre-computation difficult. The main parameters are: passphrase (P); salt (S); Blocksize (r) and CPU/Memory cost parameter (N - a power of 2). |
Outline
The focus of password-based key derivation functions (KDFs) is to derive a secret from a secret. This has included the usage of crypt, PBKDF2 and bcrypt, and which use a number of cryptography rounds to slow down the operation and general add cost. Unfortunately, as the processor gets faster, the barrier caused by the number of iterations will reduce. This is especially the case if we use GPUs. Overall, PBKDF2 does not use up much memory, and so does not make things difficult for the GPU.
Scrypt is based on an original paper from Colin Percival [2]:
The paper made the following estimates for costings:
with this we see that scrypt has a significantly higher cost for cracking than bcrypt and PBKDF2. In this case, for the approximately the same time to generate a key for each method, the cost for scrypt is always much higher. For 10 characters, we see that PBKDF2 (5.0 s) has a cost of £10m, while the same equivalent with scrypt is $210 billion. Even with six characters, scrypt has a cost of $900 to crack.
It uses a passphrase and a salt value, and computes a memory-hard compution. For this it different approach to most KDFs with a number of parameters: Blocksize (r) and CPU/Memory cost parameter (N — a power of 2) and the amount of parallelisation (p). At the core of the computation is not a hash function but Salsa20/8 Core — and which is a round-reduced variant of the Salsa20 Core [1].
Overall, it is possible to run the system with N, r, and p, and that relates to the amout of memory and computing power available, and the amount of parallelization required. It is seen that r = 8 and p = 1 gives good results.
An evaluation in 2016 [here], outlined the effect that the values of 2^N, r and p have on the time to compute the key:
In this we see that increasing the parameters increases the size of the required memory. If a GPU has a certain size of memory, we can make sure that we overflow it. Recommended parameters are:
N: 16384 (2^14) r: 8 p: 1
The memory used is:
Memory (Bytes) = (128.N.r) + (128.r.p)
If we use the parameters above, we get:
Memory = (128 * 214 * 8 ) + (128 * 8 * 1) = 16,778,240 bytes (16 MB)
Coding
The code is:
import os import sys import base64 from cryptography.hazmat.primitives import hashes from cryptography.hazmat.primitives.kdf.scrypt import Scrypt length=32 message="Hello" N=14 r=8 p=1 if (len(sys.argv)>1): message=str(sys.argv[1]) if (len(sys.argv)>2): N=int(sys.argv[2]) if (len(sys.argv)>3): r=int(sys.argv[3]) if (len(sys.argv)>4): length=int(sys.argv[4]) if (len(sys.argv)>5): p=int(sys.argv[5]) salt = os.urandom(16) kdf = Scrypt(salt=salt,length=length,n=2**N,r=r,p=p) key = kdf.derive(message.encode()) # verify kdf = Scrypt(salt=salt,length=length,n=2**N,r=r,p=p) rtn=kdf.verify(message.encode(), key) print("== scrypt === ") print(f"Message:\t{message}") print(f"Salt:\t\t{salt.hex()}") print(f"Salt:\t\t{base64.b64encode(salt).decode()}") print(f"scrypt param:\tn=2**{N}, r={r}, p={p}") print(f"\nKey:\t\t{key.hex()}") print(f"Key:\t\t{base64.b64encode(key).decode()}") if (rtn==None): print("KDF Verified")
and a sample run :
Message: Hello Salt: 286c7de58de074fc9131ba0ba3d88ac2 Salt: KGx95Y3gdPyRMboLo9iKwg== scrypt param: n=2**14, r=8, p=1 Key: 9368d90b8067d7999fd062bd748dc351799c83d2a76192252db23efb505bfd0e Key: k2jZC4Bn15mf0GK9dI3DUXmcg9KnYZIlLbI++1Bb/Q4= KDF Verified
Conclusions
PBKDF2 and bcrypt are excellent methods for KDP, and use a number of rounds to slow down the process. Unfortunately, fast computers — such as GPUs — will tend to speed-up the cracking processing and make it less costly. scrypt, though, uses a memory-hard problem, and which can easily overwealm a GPU, as these tend to have smaller amounts of memory that core processors.
References
[1] Bernstein, D., “The Salsa20 Core”, March 2005, https://cr.yp.to/salsa20.html
[2] Percival, C. (2009). Stronger key derivation via sequential memory-hard functions.