scrypt: The Memory-Hard GPU Cruncher

The focus of password-based key derivation functions (KDFs) is to derive a secret from a secret. This has included the usage of crypt…
Reference

scrypt: The Memory-Hard GPU Cruncher

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, which use a number of cryptography rounds to slow down the operation and generally 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:

Reference [2]

with this, we see that scrypt has a significantly higher cost for cracking than bcrypt and PBKDF2. In this case, for 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 computation. 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 parallelization (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 amount of memory and computing power available, and the amount of parallelization required. It is seen that r = 8 and p = 1 give 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 [here]:

import os
import sys
import base64
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.kdf.scrypt import Scrypt
round=1000
hashtype=0
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(f"== ")
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 [here]:

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 KDF, and use a number of rounds to slow down the process. Unfortunately, fast processors — such as GPUs — will tend to speed up the cracking processing and make it less costly. scrypt, though, uses a memory-hard problem, which can easily overwhelm a GPU, as these tend to have smaller amounts of memory than core processors. We can design our KDF so that it targets a range of devices, and make it memory-hard to crack.

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.

Appendix

scrypt is defined in RFC 7914: