yescrypt 0.1.0

//! Algorithm parameters.

use crate::{
    Error, Result,
    mode::Mode,
    pwxform::{PwxformCtx, RMIN},
};
use core::{
    fmt::{self, Display},
    str::{self, FromStr},
};

/// `yescrypt` algorithm parameters.
///
/// [`Params::default`] provides the recommended parameters.
///
/// These are various algorithm settings which can control e.g. the amount of resource utilization.
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub struct Params {
    /// yescrypt mode of operation: classic scrypt, write-once/read-many, or read-write.
    pub(crate) mode: Mode,

    /// `N`: CPU/memory cost (like `scrypt`).
    ///
    /// yescrypt, including in scrypt compatibility mode, is defined only for values of N that are
    /// powers of 2 (and larger than 1, which matches scrypt’s requirements).
    pub(crate) n: u64,

    /// `r`: block size (like `scrypt`).
    pub(crate) r: u32,

    /// `p`: parallelism (like `scrypt`).
    pub(crate) p: u32,

    /// Controls yescrypt’s computation time while keeping its peak memory usage the same.
    ///
    /// `t = 0` is optimal for achieving the highest normalized area-time cost for ASIC attackers.
    pub(crate) t: u32,

    /// The number of cost upgrades performed to the hash so far.
    ///
    /// `0` means no upgrades yet, and is currently the only allowed value.
    pub(crate) g: u32,

    /// Number of NROM blocks (128r bytes each).
    pub(crate) nrom: u64,
}

impl Params {
    /// Maximum length of params when encoded as Base64: up to 8 params of up to 6 chars each.
    pub(crate) const MAX_ENCODED_LEN: usize = 8 * 6;

    /// Initialize params.
    ///
    /// Accepts the following arguments:
    /// - `mode`: most users will want [`Mode::default`]. See the [`Mode`] type for more info.
    /// - `n`: CPU/memory cost. See [`Params::n`] for more info.
    /// - `r`: resource usage. See [`Params::r`] for more info.
    /// - `p`: parallelization. See [`Params::p`] for more info.
    ///
    /// # Errors
    /// Returns [`Error::Params`] if the params are not valid.
    pub fn new(mode: Mode, n: u64, r: u32, p: u32) -> Result<Params> {
        Self::new_with_all_params(mode, n, r, p, 0, 0)
    }

    /// Initialize params including additional `yescrypt`-specific settings.
    ///
    /// Accepts all the same arguments as [`Params::new`] with the following additional arguments:
    /// - `t`: increase computation time while keeping peak memory usage the same. `0` is optimal.
    /// - `g`: number of cost upgrades performed on the hash so far. `0` is the only allowed value.
    ///
    /// # Errors
    /// Returns [`Error::Params`] if the params are not valid.
    pub fn new_with_all_params(
        mode: Mode,
        n: u64,
        r: u32,
        p: u32,
        t: u32,
        g: u32,
    ) -> Result<Params> {
        // TODO(tarcieri): support non-zero `g`?
        if g != 0 {
            return Err(Error::Params);
        }

        if mode.is_rw()
            && (n / u64::from(p) <= 1
                || r < RMIN
                || u64::from(p) > u64::MAX / (3 * (1 << 8) * 2 * 8)
                || u64::from(p) > u64::MAX / (size_of::<PwxformCtx<'_>>() as u64))
        {
            return Err(Error::Params);
        }

        Ok(Params {
            mode,
            n,
            r,
            p,
            t,
            g,
            nrom: 0,
        })
    }

    /// `N`: CPU/memory cost (like `scrypt`).
    ///
    /// Memory and CPU usage scale linearly with `N`.
    #[must_use]
    pub const fn n(&self) -> u64 {
        self.n
    }

    /// `r` parameter: resource usage (like `scrypt`).
    ///
    /// Memory and CPU usage scales linearly with this parameter.
    #[must_use]
    pub const fn r(&self) -> u32 {
        self.r
    }

    /// `p` parameter: parallelization (like `scrypt`).
    ///
    /// Allows use of multithreaded parallelism (not currently implemented, `1` is the recommended
    /// setting for now).
    #[must_use]
    pub const fn p(&self) -> u32 {
        self.p
    }

    /// Encode params as (s)crypt-flavored Base64.
    #[allow(non_snake_case)]
    pub(crate) fn encode<'o>(&self, out: &'o mut [u8]) -> Result<&'o str> {
        let flavor = u32::from(self.mode);

        let N_log2 = N2log2(self.n);
        if N_log2 == 0 {
            return Err(Error::Params);
        }

        let NROM_log2 = N2log2(self.nrom);
        if self.nrom != 0 && NROM_log2 == 0 {
            return Err(Error::Params);
        }

        if u64::from(self.r) * u64::from(self.p) >= (1 << 30) {
            return Err(Error::Params);
        }

        let mut pos = 0;

        // encode flavor
        let written = encode64_uint32(&mut out[pos..], flavor, 0)?;
        pos += written;

        // encode N_log2
        let written = encode64_uint32(&mut out[pos..], N_log2, 1)?;
        pos += written;

        // encode r
        let written = encode64_uint32(&mut out[pos..], self.r, 1)?;
        pos += written;

        // "have" bits signal which additional optional fields are present
        let mut have = 0;
        if self.p != 1 {
            have |= 1;
        }
        if self.t != 0 {
            have |= 2;
        }
        if self.g != 0 {
            have |= 4;
        }
        if NROM_log2 != 0 {
            have |= 8;
        }

        if have != 0 {
            let written = encode64_uint32(&mut out[pos..], have, 1)?;
            pos += written;
        }

        if self.p != 1 {
            let written = encode64_uint32(&mut out[pos..], self.p, 2)?;
            pos += written;
        }

        if self.t != 0 {
            let written = encode64_uint32(&mut out[pos..], self.t, 1)?;
            pos += written;
        }

        if self.g != 0 {
            let written = encode64_uint32(&mut out[pos..], self.g, 1)?;
            pos += written;
        }

        if NROM_log2 != 0 {
            let written = encode64_uint32(&mut out[pos..], NROM_log2, 1)?;
            pos += written;
        }

        str::from_utf8(&out[..pos]).map_err(|_| Error::Encoding)
    }
}

impl Default for Params {
    // From the upstream C reference implementation's `PARAMETERS` file:
    //
    // > Large and slow (memory usage 16 MiB, performance like bcrypt cost 2^8 -
    // > latency 10-30 ms and throughput 1000+ per second on a 16-core server)
    fn default() -> Self {
        // flags = YESCRYPT_DEFAULTS, N = 4096, r = 32, p = 1, t = 0, g = 0, NROM = 0
        Params {
            mode: Mode::default(),
            n: 4096,
            r: 32,
            p: 1,
            t: 0,
            g: 0,
            nrom: 0,
        }
    }
}

impl FromStr for Params {
    type Err = Error;

    #[allow(non_snake_case)]
    fn from_str(s: &str) -> Result<Params> {
        let bytes = s.as_bytes();
        let mut pos = 0usize;

        // flags
        let (flavor, new_pos) = decode64_uint32(bytes, pos, 0)?;
        pos = new_pos;
        let mode = Mode::try_from(flavor)?;

        // Nlog2
        let (nlog2, new_pos) = decode64_uint32(bytes, pos, 1)?;
        pos = new_pos;
        if nlog2 > 63 {
            return Err(Error::Encoding);
        }
        let n = 1 << nlog2;

        // r
        let (r, new_pos) = decode64_uint32(bytes, pos, 1)?;
        pos = new_pos;

        let mut p = 1;
        let mut t = 0;
        let mut g = 0;

        if pos < bytes.len() {
            // "have" bits signaling which optional fields are present
            let (have, new_pos) = decode64_uint32(bytes, pos, 1)?;
            pos = new_pos;

            // p
            if (have & 0x01) != 0 {
                let (_p, new_pos) = decode64_uint32(bytes, pos, 2)?;
                pos = new_pos;
                p = _p;
            }

            // t
            if (have & 0x02) != 0 {
                let (_t, new_pos) = decode64_uint32(bytes, pos, 1)?;
                pos = new_pos;
                t = _t;
            }

            // g
            if (have & 0x04) != 0 {
                let (_g, new_pos) = decode64_uint32(bytes, pos, 1)?;
                pos = new_pos;
                g = _g;
            }

            // NROM
            if (have & 0x08) != 0 {
                let (nrom, _) = decode64_uint32(bytes, pos, 1)?;
                if nrom != 0 {
                    return Err(Error::Params);
                }
            }
        }

        Self::new_with_all_params(mode, n, r, p, t, g)
    }
}

impl Display for Params {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let mut buf = [0u8; Self::MAX_ENCODED_LEN];
        f.write_str(self.encode(&mut buf).expect("params encode failed"))
    }
}

#[allow(non_snake_case)]
fn N2log2(N: u64) -> u32 {
    if N < 2 {
        return 0;
    }

    let mut N_log2 = 2u32;
    while (N >> N_log2) != 0 {
        N_log2 += 1;
    }
    N_log2 -= 1;

    if (N >> N_log2) != 1 {
        return 0;
    }

    N_log2
}

/// (ye)scrypt-flavored Base64 alphabet.
static ITOA64: &[u8] = b"./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

/// Reverse lookup table for (ye)scrypt-flavored Base64 alphabet.
static ATOI64: [u8; 128] = {
    let mut tbl = [0xFFu8; 128]; // use 0xFF as a placeholder for invalid chars
    let mut i = 0u8;
    while i < 64 {
        tbl[ITOA64[i as usize] as usize] = i;
        i += 1;
    }
    tbl
};

/// yescrypt uses a special variable-width packing to make small parameter values shorter.
///
/// This function, which has been adapted from the yescrypt reference implementation, implements
/// both Base64 decoding and decoding of the variable-width format.
fn decode64_uint32(src: &[u8], mut pos: usize, min: u32) -> Result<(u32, usize)> {
    let mut start = 0u32;
    let mut end = 47u32;
    let mut chars = 1u32;
    let mut bits = 0u32;

    if pos >= src.len() {
        return Err(Error::Encoding);
    }

    let n = *ATOI64
        .get(usize::from(src[pos]))
        .filter(|&&n| n <= 63)
        .ok_or(Error::Encoding)?;

    pos += 1;

    let mut dst = min;
    while u32::from(n) > end {
        dst += (end + 1 - start) << bits;
        start = end + 1;
        end = start + (62 - end) / 2;
        chars += 1;
        bits += 6;
    }

    dst += (u32::from(n) - start) << bits;

    while chars > 1 {
        chars -= 1;

        if bits < 6 || pos >= src.len() {
            return Err(Error::Encoding);
        }

        let c = match ATOI64.get(src[pos] as usize) {
            Some(&c) if c <= 63 => c,
            _ => return Err(Error::Encoding),
        };
        pos += 1;

        bits -= 6;
        dst += u32::from(c) << bits;
    }

    Ok((dst, pos))
}

/// yescrypt uses a special variable-width packing to make small parameter values shorter.
///
/// This function, which has been adapted from the yescrypt reference implementation, implements
/// simultaneously encoding the variable-width format and encoding Base64.
fn encode64_uint32(dst: &mut [u8], mut src: u32, min: u32) -> Result<usize> {
    let mut start = 0u32;
    let mut end = 47u32;
    let mut chars = 1u32;
    let mut bits = 0u32;

    if src < min {
        return Err(Error::Params);
    }

    src -= min;

    loop {
        let count = (end + 1 - start) << bits;
        if src < count {
            break;
        }
        if start >= 63 {
            return Err(Error::Encoding);
        }
        start = end + 1;
        end = start + (62 - end) / 2;
        src -= count;
        chars += 1;
        bits += 6;
    }

    if dst.len() < (chars as usize) {
        return Err(Error::Encoding);
    }

    let mut pos: usize = 0;
    dst[pos] = ITOA64[(start + (src >> bits)) as usize];
    pos += 1;

    while chars > 1 {
        chars -= 1;
        bits = bits.wrapping_sub(6);
        dst[pos] = ITOA64[((src >> bits) & 0x3f) as usize];
        pos += 1;
    }

    Ok(pos)
}

#[cfg(test)]
mod tests {
    use crate::{Mode, Params};
    use alloc::string::ToString;

    #[test]
    fn encoder() {
        let p1 = Params {
            mode: Mode::default(),
            n: 4096,
            r: 32,
            p: 1,
            t: 0,
            g: 0,
            nrom: 0,
        };
        assert_eq!(p1.to_string(), "j9T");

        // p != 1
        let p2 = Params {
            mode: Mode::default(),
            n: 4096,
            r: 8,
            p: 4,
            t: 0,
            g: 0,
            nrom: 0,
        };
        assert_eq!(p2.to_string(), "j95.0");

        // t and g set
        let p3 = Params {
            mode: Mode::default(),
            n: 4096,
            r: 8,
            p: 1,
            t: 2,
            g: 5,
            nrom: 0,
        };
        assert_eq!(p3.to_string(), "j953/2");

        // NROM set (power of two)
        let p4 = Params {
            mode: Mode::default(),
            n: 32768,
            r: 8,
            p: 1,
            t: 0,
            g: 0,
            nrom: 4096,
        };
        assert_eq!(p4.to_string(), "jC559");
    }

    #[test]
    #[allow(clippy::unwrap_used)]
    fn decoder() {
        let p1: Params = "j9T".parse().unwrap();
        assert_eq!(
            p1,
            Params {
                mode: Mode::default(),
                n: 4096,
                r: 32,
                p: 1,
                t: 0,
                g: 0,
                nrom: 0,
            }
        );

        // p != 1
        let p2: Params = "j95.0".parse().unwrap();
        assert_eq!(
            p2,
            Params {
                mode: Mode::default(),
                n: 4096,
                r: 8,
                p: 4,
                t: 0,
                g: 0,
                nrom: 0,
            }
        );

        // g set
        // TODO(tarcieri): support non-zero g
        assert!("j953/2".parse::<Params>().is_err());

        // NROM set
        // TODO(tarcieri): support NROM
        assert!("jC559".parse::<Params>().is_err());
    }
}