zenith_foundation/

ct_compare.rs

//! 恒定时间比较工具
//!
//! 防止时序侧信道攻击（Timing Side-Channel Attack），
//! 确保安全关键路径的比较操作不受数据内容影响执行时间。
//!
//! # 攻击原理
//! 普通比较操作在遇到首个不匹配字节时会提前返回，
//! 攻击者通过测量比较耗时可逐字节推断密钥内容。
//!
//! # 防御策略
//! 恒定时间比较遍历所有字节，使用位操作累积差异，
//! 不进行提前返回，使执行时间仅取决于输入长度。

/// 恒定时间字节切片比较
///
/// 遍历所有字节，使用 XOR + OR 累积差异位，
/// 不进行提前返回。
///
/// # Arguments
/// * `a` - 第一个字节切片
/// * `b` - 第二个字节切片
///
/// # Returns
/// * `bool` - 是否相等
#[inline(never)]
pub fn constant_time_eq(a: &[u8], b: &[u8]) -> bool {
    let mut diff: u8 = 0;
    // 长度差异并入 diff，不提前返回；长度不等时结果恒为 false
    diff |= u8::from(a.len() != b.len());
    // 遍历较长一方的长度，越界字节按 0 参与比较，
    // 使耗时仅取决于较长的长度，与内容、长度差无关。
    let max_len = a.len().max(b.len());
    for i in 0..max_len {
        let av = a.get(i).copied().unwrap_or(0);
        let bv = b.get(i).copied().unwrap_or(0);
        diff |= av ^ bv;
        // 阻止编译器优化破坏恒定时间性质（防止 diff 被消除）
        core::hint::black_box(&mut diff);
    }
    diff == 0
}

/// 恒定时间 u32 比较
///
/// # Arguments
/// * `a` - 第一个值
/// * `b` - 第二个值
///
/// # Returns
/// * `bool` - 是否相等
#[inline(never)]
pub fn constant_time_eq_u32(a: u32, b: u32) -> bool {
    // 使用 XOR 累积差异，避免提前返回
    let mut diff = a ^ b;
    core::hint::black_box(&mut diff);
    diff == 0
}

/// 恒定时间 u64 比较
///
/// # Arguments
/// * `a` - 第一个值
/// * `b` - 第二个值
///
/// # Returns
/// * `bool` - 是否相等
#[inline(never)]
pub fn constant_time_eq_u64(a: u64, b: u64) -> bool {
    let mut diff = a ^ b;
    core::hint::black_box(&mut diff);
    diff == 0
}

/// 恒定时间 u128 比较
///
/// # Arguments
/// * `a` - 第一个值
/// * `b` - 第二个值
///
/// # Returns
/// * `bool` - 是否相等
#[inline(never)]
pub fn constant_time_eq_u128(a: u128, b: u128) -> bool {
    let mut diff = a ^ b;
    core::hint::black_box(&mut diff);
    diff == 0
}

/// 恒定时间布尔累积 OR（用于多项验证）
///
/// 即使某项失败也继续检查后续项，使所有验证
/// 总耗时保持一致。
///
/// # Arguments
/// * `checks` - 布尔检查结果数组
///
/// # Returns
/// * `bool` - 是否全部通过
#[inline(never)]
pub fn constant_time_all_pass(checks: &[bool]) -> bool {
    let mut result: u8 = 0;
    for &c in checks {
        // u8::from(!c) 由布尔直接转整数，无数据相关分支，语义同 if c {0} else {1}
        result |= u8::from(!c);
        core::hint::black_box(&mut result);
    }
    result == 0
}

/// 恒定时间 ASCII 大小写不敏感比较
///
/// 对两个字节切片做恒定时间、不提前退出的大小写不敏感比较。
/// 用于检测公开命名的敏感模式（如 `Password=` / `Authorization: Bearer `）时，
/// 避免因提前退出导致的模式存在性侧信道泄露。
///
/// # Arguments
/// * `a` - 待比较的第一个字节切片（任意大小写）
/// * `lower_b` - 待比较的第二个字节切片（必须为 ASCII 小写）
///
/// # Safety
/// 调用者需保证 `lower_b` 是已经转换为小写的 ASCII；若 `lower_b` 含大写，
/// 结果恒为 false，但执行时间依然恒定。
#[inline(never)]
pub fn constant_time_eq_ascii_lower(a: &[u8], lower_b: &[u8]) -> bool {
    let mut diff: u8 = 0;
    // 长度差异并入 diff，不提前返回；长度不等时结果恒为 false
    diff |= u8::from(a.len() != lower_b.len());
    let max_len = a.len().max(lower_b.len());
    for i in 0..max_len {
        diff |= a
            .get(i)
            .copied()
            .unwrap_or(0)
            .to_ascii_lowercase()
            ^ lower_b.get(i).copied().unwrap_or(0);
        core::hint::black_box(&mut diff);
    }
    diff == 0
}

/// 恒定时间 ASCII 大小写不敏感比较（双侧任意大小写）
///
/// 与 [`constant_time_eq_ascii_lower`] 语义相同，但两侧输入均允许任意大小写，
/// 比较前在寄存器内逐字节归一化为小写，无堆分配、不提前退出。
///
/// # Arguments
/// * `a` - 第一个字节切片（任意大小写）
/// * `b` - 第二个字节切片（任意大小写）
///
/// # Returns
/// * `bool` - 忽略 ASCII 大小写后是否相等
#[inline(never)]
pub fn constant_time_eq_case_insensitive(a: &[u8], b: &[u8]) -> bool {
    let mut diff: u8 = 0;
    // 长度差异并入 diff，不提前返回；长度不等时结果恒为 false
    diff |= u8::from(a.len() != b.len());
    let max_len = a.len().max(b.len());
    for i in 0..max_len {
        diff |= a
            .get(i)
            .copied()
            .unwrap_or(0)
            .to_ascii_lowercase()
            ^ b.get(i).copied().unwrap_or(0).to_ascii_lowercase();
        core::hint::black_box(&mut diff);
    }
    diff == 0
}

/// 恒定时间子串匹配（AGENT.md §4.9 时序安全）
///
/// 遍历所有可能的对齐位置，逐字节 XOR 累积差异并用位运算聚合结果，
/// 执行时间仅取决于输入长度，与是否命中、命中位置无关：
/// - 不因首个不匹配字节提前退出内层循环
/// - 不因已命中提前退出外层循环
/// - 无数据相关分支（匹配结果经位运算聚合，而非条件跳转）
///
/// 长度检查仅依赖输入长度（长度非秘密），不泄露内容信息。
///
/// # Arguments
/// * `haystack` - 被搜索的字节串
/// * `needle` - 待匹配的模式串（空模式恒为命中）
///
/// # Returns
/// * `bool` - `haystack` 中是否包含 `needle`
#[inline(never)]
pub fn constant_time_contains(haystack: &[u8], needle: &[u8]) -> bool {
    // 空 needle 恒命中，但走完整外层循环（内层 0 次），不提前返回；
    // 空 needle 长度恒为 0（非秘密），完整循环耗时与内容无关。
    // haystack 短于 needle 时必然不包含：将 last 置 0 仍做一次对齐比较，
    // 并累加长度差异，保证耗时与内容无关、结果恒为 false。
    let last = haystack.len().checked_sub(needle.len()).unwrap_or(0);
    let too_short = haystack.len() < needle.len();
    let mut found: u8 = 0;
    for i in 0..=last {
        // 逐字节比较，不因首个不匹配字节而退出
        let mut diff: u8 = 0;
        for j in 0..needle.len() {
            // 越界字节按 0 参与比较（结果已被 too_short 否决，不影响正确性）
            diff |= haystack.get(i + j).copied().unwrap_or(0)
                ^ needle.get(j).copied().unwrap_or(0);
            core::hint::black_box(&mut diff);
        }
        found |= u8::from(diff == 0);
        core::hint::black_box(&mut found);
    }
    // 长度不足时强制为 false；用位运算聚合，避免短路求值泄露时序信息
    let result = u8::from(!too_short) & found;
    result != 0
}

/// 恒定时间前缀比较（AGENT.md §4.9 时序安全）
///
/// 逐字节 XOR 累积差异，不因首个不匹配字节提前退出；
/// `haystack` 长度不足时仍完成全长比较后返回 `false`
/// （长度检查仅依赖输入长度，长度本身非秘密）。
///
/// # Arguments
/// * `haystack` - 被检查的字节串
/// * `prefix` - 待匹配的前缀（空前缀恒为命中，与 `str::starts_with` 语义一致）
///
/// # Returns
/// * `bool` - `haystack` 是否以 `prefix` 开头
#[inline(never)]
pub fn constant_time_starts_with(haystack: &[u8], prefix: &[u8]) -> bool {
    // 长度不足必然不匹配（仅依赖长度，长度非秘密），但仍完成全长比较
    let len_ok = haystack.len() >= prefix.len();
    let mut diff: u8 = 0;
    for (i, &p) in prefix.iter().enumerate() {
        // 越界字节以 0 参与比较（结果已被 len_ok 否决，不影响正确性）
        let b = haystack.get(i).copied().unwrap_or(0);
        diff |= b ^ p;
        core::hint::black_box(&mut diff);
    }
    // 使用位运算聚合结果，避免短路求值泄露时序信息
    let result = u8::from(len_ok) & u8::from(diff == 0);
    result == 1
}

/// 恒定时间 ASCII 大小写不敏感子串匹配（AGENT.md §4.9 时序安全）
///
/// 与 [`constant_time_contains`] 同一安全语义：
/// 遍历全部对齐位置、逐字节 XOR 累积差异、无数据相关分支、不提前退出，
/// 执行时间仅取决于输入长度，与是否命中、命中位置无关。
/// 比较前在寄存器内逐字节 ASCII 折叠为小写，零堆分配
/// （替代热路径 `to_lowercase()/to_uppercase()` 的每请求堆分配）。
///
/// # Arguments
/// * `haystack` - 被搜索的字节串（任意大小写）
/// * `needle` - 待匹配的模式串（任意大小写；空模式恒为命中）
///
/// # Returns
/// * `bool` - 忽略 ASCII 大小写后，`haystack` 中是否包含 `needle`
#[inline(never)]
pub fn constant_time_contains_case_insensitive(haystack: &[u8], needle: &[u8]) -> bool {
    // 空 needle 恒命中，但走完整外层循环（内层 0 次），不提前返回；
    // haystack 短于 needle 时必然不包含：将 last 置 0 仍做一次对齐比较，
    // 并累加长度差异，保证耗时与内容无关、结果恒为 false。
    let last = haystack.len().checked_sub(needle.len()).unwrap_or(0);
    let too_short = haystack.len() < needle.len();
    let mut found: u8 = 0;
    for i in 0..=last {
        // 逐字节 ASCII 折叠后比较，不因首个不匹配字节而退出
        let mut diff: u8 = 0;
        for j in 0..needle.len() {
            // 越界字节按 0 参与比较（结果已被 too_short 否决，不影响正确性）
            diff |= haystack
                .get(i + j)
                .copied()
                .unwrap_or(0)
                .to_ascii_lowercase()
                ^ needle.get(j).copied().unwrap_or(0).to_ascii_lowercase();
            core::hint::black_box(&mut diff);
        }
        found |= u8::from(diff == 0);
        core::hint::black_box(&mut found);
    }
    // 长度不足时强制为 false；用位运算聚合，避免短路求值泄露时序信息
    let result = u8::from(!too_short) & found;
    result != 0
}

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

    #[test]
    fn test_constant_time_starts_with_basic() {
        assert!(constant_time_starts_with(b"hello world", b"hello"));
        assert!(constant_time_starts_with(b"hello", b"hello"));
        assert!(constant_time_starts_with(b"hello", b""));
        assert!(!constant_time_starts_with(b"hello world", b"world"));
        assert!(!constant_time_starts_with(b"hi", b"hello"));
        assert!(!constant_time_starts_with(b"hellx", b"hello"));
    }

    #[test]
    fn test_constant_time_contains_case_insensitive_basic() {
        assert!(constant_time_contains_case_insensitive(b"Hello World", b"world"));
        assert!(constant_time_contains_case_insensitive(b"HELLO WORLD", b"hello"));
        assert!(constant_time_contains_case_insensitive(b"abcdef", b""));
        assert!(!constant_time_contains_case_insensitive(b"Hello", b"word"));
        assert!(!constant_time_contains_case_insensitive(b"ab", b"ABC"));
        // 非 ASCII 字节按原值折叠（to_ascii_lowercase 不影响非字母）
        assert!(constant_time_contains_case_insensitive(b"a\xFFb", b"A\xFF"));
    }

    #[test]
    fn test_constant_time_eq_equal() {
        let a = b"secret_key_123";
        let b = b"secret_key_123";
        assert!(constant_time_eq(a, b));
    }

    #[test]
    fn test_constant_time_eq_different() {
        let a = b"secret_key_123";
        let b = b"secret_key_124";
        assert!(!constant_time_eq(a, b));
    }

    #[test]
    fn test_constant_time_eq_different_length() {
        let a = b"short";
        let b = b"longer";
        assert!(!constant_time_eq(a, b));
    }

    #[test]
    fn test_constant_time_eq_empty() {
        let a: &[u8] = b"";
        let b: &[u8] = b"";
        assert!(constant_time_eq(a, b));
    }

    #[test]
    fn test_constant_time_eq_u32() {
        assert!(constant_time_eq_u32(42, 42));
        assert!(!constant_time_eq_u32(42, 43));
        assert!(constant_time_eq_u32(0, 0));
        assert!(constant_time_eq_u32(u32::MAX, u32::MAX));
    }

    #[test]
    fn test_constant_time_eq_u64() {
        assert!(constant_time_eq_u64(123456789, 123456789));
        assert!(!constant_time_eq_u64(123456789, 123456790));
        assert!(constant_time_eq_u64(0, 0));
        assert!(constant_time_eq_u64(u64::MAX, u64::MAX));
    }

    #[test]
    fn test_constant_time_eq_u128() {
        assert!(constant_time_eq_u128(1, 1));
        assert!(!constant_time_eq_u128(1, 2));
        assert!(constant_time_eq_u128(u128::MAX, u128::MAX));
    }

    #[test]
    fn test_constant_time_all_pass() {
        assert!(constant_time_all_pass(&[true, true, true]));
        assert!(!constant_time_all_pass(&[true, false, true]));
        assert!(!constant_time_all_pass(&[false, false, false]));
        assert!(constant_time_all_pass(&[]));
    }

    #[test]
    fn test_constant_time_eq_all_byte_values() {
        for byte in 0u16..=255 {
            let val = byte as u8;
            let a = [val; 32];
            let b = [val; 32];
            assert!(constant_time_eq(&a, &b));

            let mut c = [val; 32];
            if val < 255 {
                c[16] = val + 1;
                assert!(!constant_time_eq(&a, &c));
            }
        }
    }

    // ===== constant_time_eq_case_insensitive 测试 =====

    #[test]
    fn test_constant_time_eq_case_insensitive_equal() {
        assert!(constant_time_eq_case_insensitive(b"Content-Type", b"content-type"));
        assert!(constant_time_eq_case_insensitive(b"CONTENT-TYPE", b"content-type"));
        assert!(constant_time_eq_case_insensitive(b"content-type", b"content-type"));
        assert!(constant_time_eq_case_insensitive(b"AbCdEf", b"aBcDeF"));
    }

    #[test]
    fn test_constant_time_eq_case_insensitive_not_equal() {
        assert!(!constant_time_eq_case_insensitive(b"content-type", b"content-length"));
        assert!(!constant_time_eq_case_insensitive(b"abc", b"abd"));
        // 长度不同恒为 false
        assert!(!constant_time_eq_case_insensitive(b"abc", b"abcd"));
        assert!(!constant_time_eq_case_insensitive(b"", b"a"));
    }

    #[test]
    fn test_constant_time_eq_case_insensitive_non_ascii() {
        // 非 ASCII 字节按原值比较（to_ascii_lowercase 不影响非字母）
        assert!(constant_time_eq_case_insensitive(b"a\xFFb", b"A\xFFB"));
        assert!(!constant_time_eq_case_insensitive(b"a\xFFb", b"A\xFEb"));
        // 空切片相等
        assert!(constant_time_eq_case_insensitive(b"", b""));
    }

    // ===== constant_time_contains 测试 =====

    #[test]
    fn test_constant_time_contains_basic() {
        assert!(constant_time_contains(b"hello world", b"world"));
        assert!(constant_time_contains(b"hello world", b"hello"));
        assert!(constant_time_contains(b"hello world", b"o w"));
        assert!(!constant_time_contains(b"hello world", b"word"));
    }

    #[test]
    fn test_constant_time_contains_boundaries() {
        // 完全相等
        assert!(constant_time_contains(b"abc", b"abc"));
        assert!(!constant_time_contains(b"abc", b"abd"));
        // needle 长于 haystack
        assert!(!constant_time_contains(b"ab", b"abc"));
        // 空 needle 恒命中；空 haystack 仅容纳空 needle
        assert!(constant_time_contains(b"ab", b""));
        assert!(constant_time_contains(b"", b""));
        assert!(!constant_time_contains(b"", b"a"));
    }

    #[test]
    fn test_constant_time_contains_all_positions() {
        // 命中在末尾位置（最后一个对齐点）
        assert!(constant_time_contains(b"aaab", b"ab"));
        // 单字节 needle 遍历所有位置
        assert!(constant_time_contains(b"xyz", b"z"));
        assert!(!constant_time_contains(b"xyz", b"w"));
    }

    // ===== 长度不同但内容相关时结果正确（false） =====

    #[test]
    fn test_constant_time_eq_different_length_content_related() {
        // a 是 b 的前缀，仅长度不同，结果必须为 false
        assert!(!constant_time_eq(b"secret", b"secret_key"));
        assert!(!constant_time_eq(b"secret_key", b"secret"));
        // 较长者是较短者的重复/扩展，仍因长度不同而为 false
        assert!(!constant_time_eq(b"ab", b"abab"));
        assert!(!constant_time_eq(b"abab", b"ab"));
        // 空与空的特殊情况
        assert!(constant_time_eq(b"", b""));
        assert!(!constant_time_eq(b"", b"a"));
        assert!(!constant_time_eq(b"a", b""));
    }

    #[test]
    fn test_constant_time_eq_ascii_lower_different_length_content_related() {
        assert!(!constant_time_eq_ascii_lower(b"ABC", b"abcd"));
        assert!(!constant_time_eq_ascii_lower(b"abcd", b"ABC"));
        assert!(!constant_time_eq_ascii_lower(b"abc", b"abcD"));
        assert!(!constant_time_eq_ascii_lower(b"", b"a"));
        assert!(!constant_time_eq_ascii_lower(b"a", b""));
    }

    #[test]
    fn test_constant_time_eq_case_insensitive_different_length_content_related() {
        assert!(!constant_time_eq_case_insensitive(b"AbC", b"aBcD"));
        assert!(!constant_time_eq_case_insensitive(b"aBcD", b"AbC"));
        assert!(!constant_time_eq_case_insensitive(b"AbC", b"aBcCd"));
        assert!(!constant_time_eq_case_insensitive(b"", b"a"));
        assert!(!constant_time_eq_case_insensitive(b"a", b""));
    }

    #[test]
    fn test_constant_time_contains_needle_longer_than_haystack() {
        // needle 长于 haystack 时恒为 false，即使内容高度相关
        assert!(!constant_time_contains(b"abc", b"abcd"));
        assert!(!constant_time_contains(b"abc", b"abcabc"));
        assert!(!constant_time_contains(b"", b"a"));
        assert!(!constant_time_contains(b"a", b"ab"));
        // 空 needle 恒命中
        assert!(constant_time_contains(b"", b""));
        assert!(constant_time_contains(b"abc", b""));
    }

    #[test]
    fn test_constant_time_contains_case_insensitive_needle_longer() {
        assert!(!constant_time_contains_case_insensitive(b"ABC", b"AbCd"));
        assert!(!constant_time_contains_case_insensitive(b"abc", b"abcabc"));
        assert!(!constant_time_contains_case_insensitive(b"", b"A"));
        assert!(!constant_time_contains_case_insensitive(b"a", b"AB"));
        assert!(constant_time_contains_case_insensitive(b"", b""));
        assert!(constant_time_contains_case_insensitive(b"ABC", b""));
    }

    // ===== 形式化验证恒定性（说明性，避免 flaky） =====

    #[test]
    fn test_timing_constant_eq_different_length() {
        // 说明性测试：测量不同长度输入的比较耗时，断言耗时差异在容忍范围内。
        // constant_time_eq 现在遍历 max(a.len(), b.len()) 次，耗时与长度差无关。
        let a_short = vec![0x5Au8; 64];
        let b_short = vec![0x5Bu8; 64];
        let a_long_fixed = vec![0x5Au8; 4096];
        let b_long_fixed = vec![0x5Bu8; 4096];
        // 长度差很大但内容高度相关（长串是短串的前缀）
        let long_prefix = {
            let mut v = a_short.clone();
            v.resize(4096, 0x5Au8);
            v
        };

        let iters = 200_000u32;

        // 预热（触发分支预测/缓存）
        for _ in 0..10_000 {
            core::hint::black_box(constant_time_eq(&a_short, &b_short));
        }

        let t0 = std::time::Instant::now();
        for _ in 0..iters {
            core::hint::black_box(constant_time_eq(&a_short, &b_short));
        }
        let short_elapsed = t0.elapsed();

        let t1 = std::time::Instant::now();
        for _ in 0..iters {
            core::hint::black_box(constant_time_eq(&a_long_fixed, &b_long_fixed));
        }
        // 较长输入的耗时必然更大（字节数更多），此项仅作 sanity 检查
        let long_fixed_elapsed = t1.elapsed();
        assert!(
            long_fixed_elapsed >= short_elapsed,
            "较长输入应花费不少于较短输入的耗时"
        );

        // 关键断言：同为 4096 字节、仅内容不同（相关 vs 不相关）时耗时应接近
        let t2 = std::time::Instant::now();
        for _ in 0..iters {
            core::hint::black_box(constant_time_eq(&long_prefix, &a_long_fixed));
        }
        let related_elapsed = t2.elapsed();

        // 相同长度下，内容相关与否耗时应当几乎一致（恒定时间核心性质）。
        // 使用宽松阈值（30%）避免 flaky。
        let lower = long_fixed_elapsed.as_secs_f64() * 0.7;
        let upper = long_fixed_elapsed.as_secs_f64() * 1.3;
        let got = related_elapsed.as_secs_f64();
        assert!(
            got >= lower && got <= upper,
            "相同长度下比较耗时应基本恒定：related={got:.6}s, fixed={:.6}s",
            long_fixed_elapsed.as_secs_f64()
        );
        // 避免 unused 警告
        let _ = short_elapsed;
    }
}