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

Open
  • Is something wrong?
#1,589 0 comments 0 reactions 0 assignees View on GitHub

Maintainers usually reply within 1 day

Nobody has claimed this yet.

Assessment

Difficulty
3/5
Estimated time
1-2 days
Newbie friendliness
59/100
Issue type
Bug
Clarity
Clearly specified
Activity status
Active
Tech stack
rust
Domain
backend

Research direction

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.

Written by the indexing model from the issue text.

Description

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.
Dominant language
Rust
Stars
688
Forks
177
Avg merge
2h 31m
Merged PRs (30d)
31

Getting set up

This project ships no dev container, Dockerfile or contributing guide, so setting up is up to you: start from its README, and see our first-contribution guide for the general steps.

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from RustCrypto/utils

All issues in RustCrypto/utils

Similar issues

More Rust issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.