New lint suggestion: disallow division/remainder operations

[tarcieri]

What it does

In cryptographic contexts, division can result in timing sidechannel vulnerabilities (additional example), and needs to be replaced with constant-time code instead (e.g. Barrett reduction).

An off-by-default opt-in lint for uses of / or % on core integers, similar to the analysis performed in the arithmetic-side-effects lint, would make it possible to automatically detect usages of division

Advantage

This can potentially help auto-detect security vulnerabilities in cryptographic code and highlight where they need to be replaced with constant-time code.

Drawbacks

The main potential drawback I can think of is false positives, such as #11220 which exists for arithmetic_side_effects. This lint should ideally trigger only on core integers, and not Div/Rem impls on user-defined types (or at least provide a way to "bless" impls as safe), as user-defined types may implement division/remainder in constant-time

Example

// Real-world example from Kyber polynomial compression
fn map_to_standard_representative(u: u16) -> u8 {
    ((((u << 4) + KYBER_Q as u16 / 2) / KYBER_Q as u16) & 15) as u8
}

Could be written as:

#![deny(arithmetic_division)]

fn map_to_standard_representative(u: u16) -> u8 {
    let mut tmp = (u << 4) as u32;
    tmp = tmp.wrapping_add(1665);
    tmp = tmp.wrapping_mul(80635);
    (tmp >> 28 & 0xf) as u8
}

[Jacherr]

@rustbot claim

[tarcieri]

Thank you very much! Can't wait to try this out