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

Aberta
  • Algo errado?
#1,589 0 comentários 0 reações 0 responsáveis Ver no GitHub

Mantenedores costumam responder em até 1 dia

Ninguém assumiu esta issue ainda.

Avaliação

Dificuldade
3/5
Tempo estimado
1-2 dias
Facilidade para iniciantes
59/100
Tipo de issue
Bug
Clareza
Claramente especificada
Status de atividade
Ativa
Stack de tecnologia
rust
Domínio
backend

Direção de pesquisa

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.

Escrita pelo modelo de indexação a partir do texto da issue.

Descrição

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.
Linguagem predominante
Rust
Estrelas
688
Forks
177
Merge médio
2h 31min
PRs com merge (30d)
31

Preparar o ambiente

Este projeto não oferece contêiner de desenvolvimento, Dockerfile nem guia de contribuição, então a configuração fica por sua conta: comece pelo README e veja nosso guia da primeira contribuição para os passos gerais.

Primeiros passos

  1. Leia a issue inteira e depois o guia de contribuição do projeto.
  2. Comente na issue dizendo que vai assumir — evita que duas pessoas façam o mesmo trabalho.
  3. Faça um fork do repositório e trabalhe em uma branch.
  4. Abra um pull request que referencie o número da issue.

Mais de RustCrypto/utils

Todas as issues de RustCrypto/utils

Issues semelhantes

Mais issues de Rust

Receba novas issues na sua caixa de entrada

Um resumo curto de issues do GitHub para quem está começando.