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

Aperta
  • Qualcosa non va?
#1,589 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub

I maintainer di solito rispondono entro 1 giorno

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
3/5
Tempo stimato
1-2 giorni
Idoneità per principianti
59/100
Tipo di issue
Bug
Chiarezza
Specificata chiaramente
Stato di attività
Attiva
Stack tecnologico
rust
Ambito
backend

Direzione di ricerca

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.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

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.
Lingua principale
Rust
Stelle
688
Fork
177
Merge medio
2h 31m
PR unite (30g)
31

Preparare l'ambiente

Questo progetto non fornisce container di sviluppo, Dockerfile né guida per i contributori, quindi l'ambiente è a tuo carico: parti dal suo README e consulta la nostra guida al primo contributo per i passaggi generali.

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di RustCrypto/utils

Tutte le issue di RustCrypto/utils

Issue simili

Altre issue su Rust

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.