scrypt Algorithm
The scrypt algorithm is a key derivation function and password-based encryption scheme designed to provide improved security compared to traditional cryptographic hash functions. It was created in 2009 by Colin Percival, primarily to address the vulnerabilities associated with dictionary and brute-force attacks. Scrypt is utilized in various security applications, such as password authentication systems, cryptocurrencies, and encrypted data storage. Its primary advantage lies in its adaptive memory-hardness property, which makes it more resistant to custom hardware attacks and large-scale parallelism, thus making it more difficult and time-consuming for attackers to crack passwords.
Scrypt works by requiring a significant amount of memory in addition to processing power, making it more challenging and costly for attackers to perform parallel operations using specialized hardware, such as Application-Specific Integrated Circuits (ASICs) or Field-Programmable Gate Arrays (FPGAs). The algorithm achieves this by incorporating a tunable parameter that adjusts the memory usage, thus enabling the user to define the level of security depending on the desired memory and time constraints. Scrypt's memory-hard property ensures that the computational cost of deriving a key increases linearly with the memory size, effectively deterring attackers from exploiting parallelism and substantially raising their attack costs. As a result, scrypt has become a popular choice for applications requiring a robust and adaptive security infrastructure.
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.
/*!
* This module implements the Scrypt key derivation function as specified in [1].
*
* # References
* [1] - C. Percival. Stronger Key Derivation Via Sequential Memory-Hard Functions.
* http://www.tarsnap.com/scrypt/scrypt.pdf
*/
use std;
use std::iter::repeat;
use std::io;
use std::mem::size_of;
use cryptoutil::copy_memory;
use rand::{OsRng, Rng};
use serialize::base64;
use serialize::base64::{FromBase64, ToBase64};
use cryptoutil::{read_u32_le, read_u32v_le, write_u32_le};
use hmac::Hmac;
use pbkdf2::pbkdf2;
use sha2::Sha256;
use util::fixed_time_eq;
// The salsa20/8 core function.
fn salsa20_8(input: &[u8], output: &mut [u8]) {
let mut x = [0u32; 16];
read_u32v_le(&mut x, input);
let rounds = 8;
macro_rules! run_round (
($($set_idx:expr, $idx_a:expr, $idx_b:expr, $rot:expr);*) => { {
$( x[$set_idx] ^= x[$idx_a].wrapping_add(x[$idx_b]).rotate_left($rot); )*
} }
);
for _ in 0..rounds / 2 {
run_round!(
0x4, 0x0, 0xc, 7;
0x8, 0x4, 0x0, 9;
0xc, 0x8, 0x4, 13;
0x0, 0xc, 0x8, 18;
0x9, 0x5, 0x1, 7;
0xd, 0x9, 0x5, 9;
0x1, 0xd, 0x9, 13;
0x5, 0x1, 0xd, 18;
0xe, 0xa, 0x6, 7;
0x2, 0xe, 0xa, 9;
0x6, 0x2, 0xe, 13;
0xa, 0x6, 0x2, 18;
0x3, 0xf, 0xb, 7;
0x7, 0x3, 0xf, 9;
0xb, 0x7, 0x3, 13;
0xf, 0xb, 0x7, 18;
0x1, 0x0, 0x3, 7;
0x2, 0x1, 0x0, 9;
0x3, 0x2, 0x1, 13;
0x0, 0x3, 0x2, 18;
0x6, 0x5, 0x4, 7;
0x7, 0x6, 0x5, 9;
0x4, 0x7, 0x6, 13;
0x5, 0x4, 0x7, 18;
0xb, 0xa, 0x9, 7;
0x8, 0xb, 0xa, 9;
0x9, 0x8, 0xb, 13;
0xa, 0x9, 0x8, 18;
0xc, 0xf, 0xe, 7;
0xd, 0xc, 0xf, 9;
0xe, 0xd, 0xc, 13;
0xf, 0xe, 0xd, 18
)
}
for i in 0..16 {
write_u32_le(
&mut output[i * 4..(i + 1) * 4],
x[i].wrapping_add(read_u32_le(&input[i * 4..(i + 1) * 4])));
}
}
fn xor(x: &[u8], y: &[u8], output: &mut [u8]) {
for ((out, &x_i), &y_i) in output.iter_mut().zip(x.iter()).zip(y.iter()) {
*out = x_i ^ y_i;
}
}
// Execute the BlockMix operation
// input - the input vector. The length must be a multiple of 128.
// output - the output vector. Must be the same length as input.
fn scrypt_block_mix(input: &[u8], output: &mut [u8]) {
let mut x = [0u8; 64];
copy_memory(&input[input.len() - 64..], &mut x);
let mut t = [0u8; 64];
for (i, chunk) in input.chunks(64).enumerate() {
xor(&x, chunk, &mut t);
salsa20_8(&t, &mut x);
let pos = if i % 2 == 0 { (i / 2) * 64 } else { (i / 2) * 64 + input.len() / 2 };
copy_memory(&x, &mut output[pos..pos + 64]);
}
}
// Execute the ROMix operation in-place.
// b - the data to operate on
// v - a temporary variable to store the vector V
// t - a temporary variable to store the result of the xor
// n - the scrypt parameter N
fn scrypt_ro_mix(b: &mut [u8], v: &mut [u8], t: &mut [u8], n: usize) {
fn integerify(x: &[u8], n: usize) -> usize {
// n is a power of 2, so n - 1 gives us a bitmask that we can use to perform a calculation
// mod n using a simple bitwise and.
let mask = n - 1;
// This cast is safe since we're going to get the value mod n (which is a power of 2), so we
// don't have to care about truncating any of the high bits off
let result = (read_u32_le(&x[x.len() - 64..x.len() - 60]) as usize) & mask;
result
}
let len = b.len();
for chunk in v.chunks_mut(len) {
copy_memory(b, chunk);
scrypt_block_mix(chunk, b);
}
for _ in 0..n {
let j = integerify(b, n);
xor(b, &v[j * len..(j + 1) * len], t);
scrypt_block_mix(t, b);
}
}
/**
* The Scrypt parameter values.
*/
#[derive(Clone, Copy)]
pub struct ScryptParams {
log_n: u8,
r: u32,
p: u32
}
impl ScryptParams {
/**
* Create a new instance of ScryptParams.
*
* # Arguments
*
* * log_n - The log2 of the Scrypt parameter N
* * r - The Scrypt parameter r
* * p - The Scrypt parameter p
*
*/
pub fn new(log_n: u8, r: u32, p: u32) -> ScryptParams {
assert!(r > 0);
assert!(p > 0);
assert!(log_n > 0);
assert!((log_n as usize) < size_of::<usize>() * 8);
assert!(size_of::<usize>() >= size_of::<u32>() || (r <= std::usize::MAX as u32 && p < std::usize::MAX as u32));
let r = r as usize;
let p = p as usize;
let n: usize = 1 << log_n;
// check that r * 128 doesn't overflow
let r128 = match r.checked_mul(128) {
Some(x) => x,
None => panic!("Invalid Scrypt parameters.")
};
// check that n * r * 128 doesn't overflow
match r128.checked_mul(n) {
Some(_) => { },
None => panic!("Invalid Scrypt parameters.")
};
// check that p * r * 128 doesn't overflow
match r128.checked_mul(p) {
Some(_) => { },
None => panic!("Invalid Scrypt parameters.")
};
// This check required by Scrypt:
// check: n < 2^(128 * r / 8)
// r * 16 won't overflow since r128 didn't
assert!((log_n as usize) < r * 16);
// This check required by Scrypt:
// check: p <= ((2^32-1) * 32) / (128 * r)
// It takes a bit of re-arranging to get the check above into this form, but, it is indeed
// the same.
assert!(r * p < 0x40000000);
ScryptParams {
log_n: log_n,
r: r as u32,
p: p as u32
}
}
}
/**
* The scrypt key derivation function.
*
* # Arguments
*
* * password - The password to process as a byte vector
* * salt - The salt value to use as a byte vector
* * params - The ScryptParams to use
* * output - The resulting derived key is returned in this byte vector.
*
*/
pub fn scrypt(password: &[u8], salt: &[u8], params: &ScryptParams, output: &mut [u8]) {
// This check required by Scrypt:
// check output.len() > 0 && output.len() <= (2^32 - 1) * 32
assert!(output.len() > 0);
assert!(output.len() / 32 <= 0xffffffff);
// The checks in the ScryptParams constructor guarantee that the following is safe:
let n = 1 << params.log_n;
let r128 = (params.r as usize) * 128;
let pr128 = (params.p as usize) * r128;
let nr128 = n * r128;
let mut mac = Hmac::new(Sha256::new(), password);
let mut b: Vec<u8> = repeat(0).take(pr128).collect();
pbkdf2(&mut mac, salt, 1, &mut b);
let mut v: Vec<u8> = repeat(0).take(nr128).collect();
let mut t: Vec<u8> = repeat(0).take(r128).collect();
for chunk in &mut b.chunks_mut(r128) {
scrypt_ro_mix(chunk, &mut v, &mut t, n);
}
pbkdf2(&mut mac, &*b, 1, output);
}
/**
* scrypt_simple is a helper function that should be sufficient for the majority of cases where
* an application needs to use Scrypt to hash a password for storage. The result is a String that
* contains the parameters used as part of its encoding. The scrypt_check function may be used on
* a password to check if it is equal to a hashed value.
*
* # Format
*
* The format of the output is a modified version of the Modular Crypt Format that encodes algorithm
* used and the parameter values. If all parameter values can each fit within a single byte, a
* compact format is used (format 0). However, if any value cannot, an expanded format where the r
* and p parameters are encoded using 4 bytes (format 1) is used. Both formats use a 128-bit salt
* and a 256-bit hash. The format is indicated as "rscrypt" which is short for "Rust Scrypt format."
*
* $rscrypt$<format>$<base64(log_n,r,p)>$<base64(salt)>$<based64(hash)>$
*
* # Arguments
*
* * password - The password to process as a str
* * params - The ScryptParams to use
*
*/
pub fn scrypt_simple(password: &str, params: &ScryptParams) -> io::Result<String> {
let mut rng = try!(OsRng::new());
// 128-bit salt
let salt: Vec<u8> = rng.gen_iter::<u8>().take(16).collect();
// 256-bit derived key
let mut dk = [0u8; 32];
scrypt(password.as_bytes(), &*salt, params, &mut dk);
let mut result = "$rscrypt$".to_string();
if params.r < 256 && params.p < 256 {
result.push_str("0$");
let mut tmp = [0u8; 3];
tmp[0] = params.log_n;
tmp[1] = params.r as u8;
tmp[2] = params.p as u8;
result.push_str(&*tmp.to_base64(base64::STANDARD));
} else {
result.push_str("1$");
let mut tmp = [0u8; 9];
tmp[0] = params.log_n;
write_u32_le(&mut tmp[1..5], params.r);
write_u32_le(&mut tmp[5..9], params.p);
result.push_str(&*tmp.to_base64(base64::STANDARD));
}
result.push('$');
result.push_str(&*salt.to_base64(base64::STANDARD));
result.push('$');
result.push_str(&*dk.to_base64(base64::STANDARD));
result.push('$');
Ok(result)
}
/**
* scrypt_check compares a password against the result of a previous call to scrypt_simple and
* returns true if the passed in password hashes to the same value.
*
* # Arguments
*
* * password - The password to process as a str
* * hashed_value - A string representing a hashed password returned by scrypt_simple()
*
*/
pub fn scrypt_check(password: &str, hashed_value: &str) -> Result<bool, &'static str> {
static ERR_STR: &'static str = "Hash is not in Rust Scrypt format.";
let mut iter = hashed_value.split('$');
// Check that there are no characters before the first "$"
match iter.next() {
Some(x) => if x != "" { return Err(ERR_STR); },
None => return Err(ERR_STR)
}
// Check the name
match iter.next() {
Some(t) => if t != "rscrypt" { return Err(ERR_STR); },
None => return Err(ERR_STR)
}
// Parse format - currenlty only version 0 (compact) and 1 (expanded) are supported
let params: ScryptParams;
match iter.next() {
Some(fstr) => {
// Parse the parameters - the size of them depends on the if we are using the compact or
// expanded format
let pvec = match iter.next() {
Some(pstr) => match pstr.from_base64() {
Ok(x) => x,
Err(_) => return Err(ERR_STR)
},
None => return Err(ERR_STR)
};
match fstr {
"0" => {
if pvec.len() != 3 { return Err(ERR_STR); }
let log_n = pvec[0];
let r = pvec[1] as u32;
let p = pvec[2] as u32;
params = ScryptParams::new(log_n, r, p);
}
"1" => {
if pvec.len() != 9 { return Err(ERR_STR); }
let log_n = pvec[0];
let mut pval = [0u32; 2];
read_u32v_le(&mut pval, &pvec[1..9]);
params = ScryptParams::new(log_n, pval[0], pval[1]);
}
_ => return Err(ERR_STR)
}
}
None => return Err(ERR_STR)
}
// Salt
let salt = match iter.next() {
Some(sstr) => match sstr.from_base64() {
Ok(salt) => salt,
Err(_) => return Err(ERR_STR)
},
None => return Err(ERR_STR)
};
// Hashed value
let hash = match iter.next() {
Some(hstr) => match hstr.from_base64() {
Ok(hash) => hash,
Err(_) => return Err(ERR_STR)
},
None => return Err(ERR_STR)
};
// Make sure that the input ends with a "$"
match iter.next() {
Some(x) => if x != "" { return Err(ERR_STR); },
None => return Err(ERR_STR)
}
// Make sure there is no trailing data after the final "$"
match iter.next() {
Some(_) => return Err(ERR_STR),
None => { }
}
let mut output: Vec<u8> = repeat(0).take(hash.len()).collect();
scrypt(password.as_bytes(), &*salt, ¶ms, &mut output);
// Be careful here - its important that the comparison be done using a fixed time equality
// check. Otherwise an adversary that can measure how long this step takes can learn about the
// hashed value which would allow them to mount an offline brute force attack against the
// hashed password.
Ok(fixed_time_eq(&*output, &*hash))
}
#[cfg(test)]
mod test {
use std::iter::repeat;
use scrypt::{scrypt, scrypt_simple, scrypt_check, ScryptParams};
struct Test {
password: &'static str,
salt: &'static str,
log_n: u8,
r: u32,
p: u32,
expected: Vec<u8>
}
// Test vectors from [1]. The last test vector is omitted because it takes too long to run.
fn tests() -> Vec<Test> {
vec![
Test {
password: "",
salt: "",
log_n: 4,
r: 1,
p: 1,
expected: vec![
0x77, 0xd6, 0x57, 0x62, 0x38, 0x65, 0x7b, 0x20,
0x3b, 0x19, 0xca, 0x42, 0xc1, 0x8a, 0x04, 0x97,
0xf1, 0x6b, 0x48, 0x44, 0xe3, 0x07, 0x4a, 0xe8,
0xdf, 0xdf, 0xfa, 0x3f, 0xed, 0xe2, 0x14, 0x42,
0xfc, 0xd0, 0x06, 0x9d, 0xed, 0x09, 0x48, 0xf8,
0x32, 0x6a, 0x75, 0x3a, 0x0f, 0xc8, 0x1f, 0x17,
0xe8, 0xd3, 0xe0, 0xfb, 0x2e, 0x0d, 0x36, 0x28,
0xcf, 0x35, 0xe2, 0x0c, 0x38, 0xd1, 0x89, 0x06 ]
},
Test {
password: "password",
salt: "NaCl",
log_n: 10,
r: 8,
p: 16,
expected: vec![
0xfd, 0xba, 0xbe, 0x1c, 0x9d, 0x34, 0x72, 0x00,
0x78, 0x56, 0xe7, 0x19, 0x0d, 0x01, 0xe9, 0xfe,
0x7c, 0x6a, 0xd7, 0xcb, 0xc8, 0x23, 0x78, 0x30,
0xe7, 0x73, 0x76, 0x63, 0x4b, 0x37, 0x31, 0x62,
0x2e, 0xaf, 0x30, 0xd9, 0x2e, 0x22, 0xa3, 0x88,
0x6f, 0xf1, 0x09, 0x27, 0x9d, 0x98, 0x30, 0xda,
0xc7, 0x27, 0xaf, 0xb9, 0x4a, 0x83, 0xee, 0x6d,
0x83, 0x60, 0xcb, 0xdf, 0xa2, 0xcc, 0x06, 0x40 ]
},
Test {
password: "pleaseletmein",
salt: "SodiumChloride",
log_n: 14,
r: 8,
p: 1,
expected: vec![
0x70, 0x23, 0xbd, 0xcb, 0x3a, 0xfd, 0x73, 0x48,
0x46, 0x1c, 0x06, 0xcd, 0x81, 0xfd, 0x38, 0xeb,
0xfd, 0xa8, 0xfb, 0xba, 0x90, 0x4f, 0x8e, 0x3e,
0xa9, 0xb5, 0x43, 0xf6, 0x54, 0x5d, 0xa1, 0xf2,
0xd5, 0x43, 0x29, 0x55, 0x61, 0x3f, 0x0f, 0xcf,
0x62, 0xd4, 0x97, 0x05, 0x24, 0x2a, 0x9a, 0xf9,
0xe6, 0x1e, 0x85, 0xdc, 0x0d, 0x65, 0x1e, 0x40,
0xdf, 0xcf, 0x01, 0x7b, 0x45, 0x57, 0x58, 0x87 ]
},
]
}
#[test]
fn test_scrypt() {
let tests = tests();
for t in tests.iter() {
let mut result: Vec<u8> = repeat(0).take(t.expected.len()).collect();
let params = ScryptParams::new(t.log_n, t.r, t.p);
scrypt(t.password.as_bytes(), t.salt.as_bytes(), ¶ms, &mut result);
assert!(result == t.expected);
}
}
fn test_scrypt_simple(log_n: u8, r: u32, p: u32) {
let password = "password";
let params = ScryptParams::new(log_n, r, p);
let out1 = scrypt_simple(password, ¶ms).unwrap();
let out2 = scrypt_simple(password, ¶ms).unwrap();
// This just makes sure that a salt is being applied. It doesn't verify that that salt is
// cryptographically strong, however.
assert!(out1 != out2);
match scrypt_check(password, &out1[..]) {
Ok(r) => assert!(r),
Err(_) => panic!()
}
match scrypt_check(password, &out2[..]) {
Ok(r) => assert!(r),
Err(_) => panic!()
}
match scrypt_check("wrong", &out1[..]) {
Ok(r) => assert!(!r),
Err(_) => panic!()
}
match scrypt_check("wrong", &out2[..]) {
Ok(r) => assert!(!r),
Err(_) => panic!()
}
}
#[test]
fn test_scrypt_simple_compact() {
// These parameters are intentionally very weak - the goal is to make the test run quickly!
test_scrypt_simple(7, 8, 1);
}
#[test]
fn test_scrypt_simple_expanded() {
// These parameters are intentionally very weak - the goal is to make the test run quickly!
test_scrypt_simple(3, 1, 256);
}
}
