ctutils: `CtLookup` index counter overflows. A 256-entry table with a `u8` index panics on every lookup with overflow checks on, and longer tables return the wrong element in release

未关闭
  • 哪里不对？
#1,589 0 条评论 0 个 reaction 已指派 0 人 在 GitHub 查看

维护者通常 1 天内回复

还没有人认领这个 Issue。

评估

难度
3/5
预计耗时
1-2 天
新手友好度
59/100
Issue 类型
缺陷
描述清晰度
描述清楚
活跃度
活跃
技术栈
rust
领域
backend

调研方向

Read src/traits/ct_lookup.rs:28-38 and inspect the CtLookup tests to understand the counter’s bounds and existing behavior. Reproduce both cases with a 256-entry and a 300-entry table using a u8 index. Done means full-size tables do not panic with overflow checks enabled and oversized tables cannot silently return a later element.

由索引模型根据 Issue 内容生成。

描述

Body

ctutils 0.4.8, src/traits/ct_lookup.rs:28-38:

let mut i = Idx::default();
for item in self {
    ret.insert_if(item, i.ct_eq(&index));
    // TODO(tarcieri): ideally we'd prevent overflow here but there's no core `CheckedAdd`
    i += Idx::from(1u8);
}

The TODO already notes that the counter can overflow. This issue is about two
concrete consequences, including one for the most natural use of the API:

  1. Panic on every lookup for an exactly-full table. A 256-entry table with
    a u8 index (an AES-style S-box) increments i past u8::MAX after
    the last element. With overflow checks enabled (debug builds, or release
    profiles with overflow-checks = true), every call to ct_lookup panics
    with attempt to add with overflow at ct_lookup.rs:36, even though every
    u8 index is valid for that table.
  2. Wrong element for longer tables in default release. For a table longer
    than the index type can address (e.g. 300 entries, u8 index), i wraps
    and later entries overwrite the correct match. ct_lookup(0u8) returns
    element 256, and ct_lookup(5u8) returns element 261.
Reproduction

Cargo.toml:

[package]
name = "ct-lookup-overflow"
version = "0.1.0"
edition = "2021"

[dependencies]
ctutils = "=0.4.8"

src/main.rs:

#![forbid(unsafe_code)]
use ctutils::CtLookup;

fn main() {
    // (1) 256-entry table, u8 index
    let sbox: [u8; 256] = core::array::from_fn(|i| (i as u8).wrapping_mul(7) ^ 0x63);
    println!("sbox[0x42] = {:?}", sbox.ct_lookup(0x42u8).into_option());

    // (2) 300-entry table, u8 index
    let table: Vec<u32> = (0..300u32).map(|i| 1000 + i).collect();
    for idx in [0u8, 5, 43, 44, 255] {
        println!("ct_lookup({idx}) = {:?}, expected {:?}",
                 table.as_slice().ct_lookup(idx).into_option(), table.get(idx as usize));
    }
}

Output with rustc 1.99.1:

$ cargo run            # debug (overflow checks on)
thread 'main' panicked at .../ctutils-0.4.8/src/traits/ct_lookup.rs:36:13:
attempt to add with overflow

$ cargo run --release  # overflow checks off
sbox[0x42] = Some(173)
ct_lookup(0) = Some(1256), expected Some(1000)
ct_lookup(5) = Some(1261), expected Some(1005)
ct_lookup(43) = Some(1299), expected Some(1043)
ct_lookup(44) = Some(1044), expected Some(1044)
ct_lookup(255) = Some(1255), expected Some(1255)

Affects every release containing CtLookup (checked: 0.3.2 and 0.4.0 through
0.4.8). Master is unchanged.

Possible fixes

Any of the following:

  • Skip the increment after the last element (e.g. increment at the top of
    each iteration except the first). That makes exactly-full tables such as a
    256-entry u8-indexed S-box work under overflow checks.
  • Reject tables longer than the index type can address, with a length check
    (public information, so not a constant-time concern) or a documented
    debug_assert!, so that wrapping can't silently select the wrong element.
  • Track the position as usize and convert the index once, if the Idx
    bounds allow it.
主要语言
Rust
星标
688
派生
177
平均合并
2 小时 31 分钟
30 天内合并 PR
31

环境准备

这个项目没有提供开发容器、Dockerfile 或贡献指南，环境需要你自己搭建：先看它的 README，通用步骤见我们的新手贡献指南。

从这里开始

  1. 先读完整个 Issue，再读项目的贡献指南。
  2. 在 Issue 下留言说明你要接手 —— 这能避免两个人做同样的事。
  3. Fork 仓库，在一个分支上完成修改。
  4. 提交 Pull Request，并在描述里引用这个 Issue 编号。

RustCrypto/utils 的其他 Issue

查看 RustCrypto/utils 的全部 Issue

相似的 Issue

更多 Rust Issue

把新 issue 发到你的邮箱

精选适合新手参与的 GitHub issue 摘要。