krypteia-tessera 0.2.0

// SPDX-License-Identifier: Apache-2.0
// Copyright 2026 Cédric Mesnil <cslashm@pm.me>

//! scrypt — memory-hard password-based key derivation (RFC 7914 / Percival 2009).
//!
//! `scrypt(P, S, N, r, p, dkLen)` derives `dkLen` octets from a password `P`
//! and salt `S`. Unlike [`pbkdf2`](mod@crate::pbkdf2) (iteration-hard only),
//! scrypt is **memory-hard**: it fills an `N · 128 · r`-byte table, so a
//! brute-force attacker pays large memory as well as time. Built entirely on
//! this crate: the two wrapping steps are `PBKDF2-HMAC-SHA-256`
//! ([`crate::pbkdf2`](mod@crate::pbkdf2)) and the mixing core is Salsa20/8
//! (implemented inline here — scrypt uses the reduced-round Salsa20 *hash*, a
//! 64-byte permutation, not the stream cipher).
//!
//! Parameters (RFC 7914 §2): `N` a power of two `> 1` (CPU/memory cost), `r`
//! block-size factor, `p` parallelisation. Memory ≈ `128 · N · r` bytes;
//! e.g. the RFC's `N=16384, r=8, p=1` interactive-login profile uses ~16 MiB.
//!
//! # Side-channel posture
//!
//! scrypt's `ROMix` reads the table at a **password-derived index** `j`
//! (`Integerify(X) mod N`) — a data-dependent memory access, so scrypt is
//! **not** constant-time and is a cache-timing target on shared hardware.
//! This is inherent to scrypt's design (it is *why* it is memory-hard) and
//! matches RFC 7914; do not run it in a context where a co-resident attacker
//! can observe the cache. The Salsa20/8 core and the HMAC/PBKDF2 wrapping are
//! themselves data-oblivious.

use crate::Sha256;
use crate::pbkdf2::pbkdf2;
use alloc::vec;
use alloc::vec::Vec;
use core::num::NonZeroU32;

/// scrypt parameter error (RFC 7914 §2).
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Error {
    /// `n` is not a power of two strictly greater than 1.
    InvalidN,
    /// `r == 0`, `p == 0`, or `p · 128 · r` overflows / exceeds the RFC limit.
    InvalidBlockParams,
}

/// The Salsa20/8 core (RFC 7914 §3): 8 rounds over a 64-octet block, in place.
fn salsa20_8(block: &mut [u8; 64]) {
    let mut x = [0u32; 16];
    for (i, w) in x.iter_mut().enumerate() {
        *w = u32::from_le_bytes([block[4 * i], block[4 * i + 1], block[4 * i + 2], block[4 * i + 3]]);
    }
    let orig = x;
    // R(a, b) = (a + b) rotate_left b. 4 × (column round + row round) = 8 rounds.
    for _ in 0..4 {
        x[4] ^= x[0].wrapping_add(x[12]).rotate_left(7);
        x[8] ^= x[4].wrapping_add(x[0]).rotate_left(9);
        x[12] ^= x[8].wrapping_add(x[4]).rotate_left(13);
        x[0] ^= x[12].wrapping_add(x[8]).rotate_left(18);
        x[9] ^= x[5].wrapping_add(x[1]).rotate_left(7);
        x[13] ^= x[9].wrapping_add(x[5]).rotate_left(9);
        x[1] ^= x[13].wrapping_add(x[9]).rotate_left(13);
        x[5] ^= x[1].wrapping_add(x[13]).rotate_left(18);
        x[14] ^= x[10].wrapping_add(x[6]).rotate_left(7);
        x[2] ^= x[14].wrapping_add(x[10]).rotate_left(9);
        x[6] ^= x[2].wrapping_add(x[14]).rotate_left(13);
        x[10] ^= x[6].wrapping_add(x[2]).rotate_left(18);
        x[3] ^= x[15].wrapping_add(x[11]).rotate_left(7);
        x[7] ^= x[3].wrapping_add(x[15]).rotate_left(9);
        x[11] ^= x[7].wrapping_add(x[3]).rotate_left(13);
        x[15] ^= x[11].wrapping_add(x[7]).rotate_left(18);
        x[1] ^= x[0].wrapping_add(x[3]).rotate_left(7);
        x[2] ^= x[1].wrapping_add(x[0]).rotate_left(9);
        x[3] ^= x[2].wrapping_add(x[1]).rotate_left(13);
        x[0] ^= x[3].wrapping_add(x[2]).rotate_left(18);
        x[6] ^= x[5].wrapping_add(x[4]).rotate_left(7);
        x[7] ^= x[6].wrapping_add(x[5]).rotate_left(9);
        x[4] ^= x[7].wrapping_add(x[6]).rotate_left(13);
        x[5] ^= x[4].wrapping_add(x[7]).rotate_left(18);
        x[11] ^= x[10].wrapping_add(x[9]).rotate_left(7);
        x[8] ^= x[11].wrapping_add(x[10]).rotate_left(9);
        x[9] ^= x[8].wrapping_add(x[11]).rotate_left(13);
        x[10] ^= x[9].wrapping_add(x[8]).rotate_left(18);
        x[12] ^= x[15].wrapping_add(x[14]).rotate_left(7);
        x[13] ^= x[12].wrapping_add(x[15]).rotate_left(9);
        x[14] ^= x[13].wrapping_add(x[12]).rotate_left(13);
        x[15] ^= x[14].wrapping_add(x[13]).rotate_left(18);
    }
    for i in 0..16 {
        let v = x[i].wrapping_add(orig[i]);
        block[4 * i..4 * i + 4].copy_from_slice(&v.to_le_bytes());
    }
}

/// BlockMix (RFC 7914 §4): mix a `128·r`-octet block into a new one.
fn block_mix(b: &[u8], r: usize) -> Vec<u8> {
    let two_r = 2 * r;
    let mut x = [0u8; 64];
    x.copy_from_slice(&b[(two_r - 1) * 64..two_r * 64]);
    let mut out = vec![0u8; 128 * r];
    for i in 0..two_r {
        for k in 0..64 {
            x[k] ^= b[i * 64 + k];
        }
        salsa20_8(&mut x);
        // Y even indices → first half, odd indices → second half.
        let dst = if i % 2 == 0 { i / 2 } else { r + i / 2 };
        out[dst * 64..dst * 64 + 64].copy_from_slice(&x);
    }
    out
}

/// `Integerify(X) mod n` (RFC 7914 §5): interpret the last 64-octet block of
/// `x` as a little-endian integer, reduced mod `n` (a power of two).
fn integerify_mod(x: &[u8], r: usize, n: usize) -> usize {
    let last = (2 * r - 1) * 64;
    let j = u32::from_le_bytes([x[last], x[last + 1], x[last + 2], x[last + 3]]) as usize;
    j & (n - 1) // n is a power of two
}

/// ROMix (RFC 7914 §5): the memory-hard step over a `128·r`-octet block.
fn romix(b: &mut [u8], n: usize, r: usize) {
    let blen = 128 * r;
    let mut v = vec![0u8; n * blen]; // the N-block table — the memory cost.
    let mut x = b.to_vec();
    for i in 0..n {
        v[i * blen..(i + 1) * blen].copy_from_slice(&x);
        x = block_mix(&x, r);
    }
    for _ in 0..n {
        let j = integerify_mod(&x, r, n);
        for k in 0..blen {
            x[k] ^= v[j * blen + k];
        }
        x = block_mix(&x, r);
    }
    b.copy_from_slice(&x);
}

/// scrypt (RFC 7914): derive `dk.len()` octets from `password` and `salt`.
///
/// `n` must be a power of two `> 1`; `r`, `p` ≥ 1. Errors on invalid
/// parameters (see [`Error`]).
pub fn scrypt(password: &[u8], salt: &[u8], n: usize, r: usize, p: usize, dk: &mut [u8]) -> Result<(), Error> {
    if !n.is_power_of_two() || n <= 1 {
        return Err(Error::InvalidN);
    }
    if r == 0 || p == 0 {
        return Err(Error::InvalidBlockParams);
    }
    let blen = (128usize).checked_mul(r).ok_or(Error::InvalidBlockParams)?;
    let total = p.checked_mul(blen).ok_or(Error::InvalidBlockParams)?;
    // RFC 7914 §2: p ≤ ((2^32 − 1) · 32) / (128 · r).
    if (p as u64) * (blen as u64) > ((u32::MAX as u64) * 32) {
        return Err(Error::InvalidBlockParams);
    }

    // B = PBKDF2-HMAC-SHA256(P, S, 1, p·128·r).
    let mut b = vec![0u8; total];
    pbkdf2::<Sha256>(password, salt, NonZeroU32::MIN, &mut b);
    // B[i] = ROMix(B[i], N) for each of the p blocks.
    for i in 0..p {
        romix(&mut b[i * blen..(i + 1) * blen], n, r);
    }
    // DK = PBKDF2-HMAC-SHA256(P, B, 1, dkLen).
    pbkdf2::<Sha256>(password, &b, NonZeroU32::MIN, dk);
    Ok(())
}

#[cfg(test)]
mod tests {
    use super::*;

    fn hx(h: &str) -> Vec<u8> {
        (0..h.len())
            .step_by(2)
            .map(|i| u8::from_str_radix(&h[i..i + 2], 16).unwrap())
            .collect()
    }

    // RFC 7914 §12 vector 1 (smallest, fast). Larger vectors + a Python
    // hashlib.scrypt cross-check live in the integration suite `tests/kdf.rs`.
    #[test]
    fn rfc7914_vector1() {
        let mut dk = [0u8; 64];
        scrypt(b"", b"", 16, 1, 1, &mut dk).unwrap();
        assert_eq!(
            dk[..],
            hx("77d6576238657b203b19ca42c18a0497f16b4844e3074ae8dfdffa3fede21442\
                fcd0069ded0948f8326a753a0fc81f17e8d3e0fb2e0d3628cf35e20c38d18906")[..]
        );
    }

    #[test]
    fn invalid_params() {
        let mut dk = [0u8; 16];
        assert_eq!(scrypt(b"p", b"s", 15, 1, 1, &mut dk), Err(Error::InvalidN)); // not pow2
        assert_eq!(scrypt(b"p", b"s", 1, 1, 1, &mut dk), Err(Error::InvalidN)); // n == 1
        assert_eq!(scrypt(b"p", b"s", 16, 0, 1, &mut dk), Err(Error::InvalidBlockParams));
        assert_eq!(scrypt(b"p", b"s", 16, 1, 0, &mut dk), Err(Error::InvalidBlockParams));
    }
}