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 #1589

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.