In this article I will describe a novel technique that allows an attacker to pass attacker-chosen string keys to a hash table implementation such that each lookup query takes O(n) instead of the expected O(1) work. The attack takes O(n × log⁡ n) interactive steps with the hash table to prepare, and does not require knowledge of the hash function used by the hash table. Instead, the technique directly targets the underlying structure of the hash table.

Luckily these attacks as described are quite niche (requiring lookup, insert and clear access on a table without interference from others), and mitigations are possible. However, the attack isn’t purely theoretical, I construct a working attack against Rust’s standard library hash table implementation below.

«Нас убили. 9 ноября мы погасим свет в нашем доме, где прожили 30 лет, выключим сервера и уйдем. Газеты больше нет. Российские власти и российские спецслужбы заставили редакцию прекратить работу», — говорится в заявлении редакции.

use owo_colors::OwoColorize;

fn main() {
    // Foreground colors
    println!("My number is {:#x}!", 10.green());
    // Background colors
    println!("My number is not {}!", 4.on_red());
}