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 摘要。