Description
The AES version of aHash only performs a single round of AES between inputs. This is not sufficient, a single-bit difference only gets amplified once in the SubBytes step, leading to one of 256 possibilities, but nothing further. An attacker can guess this to recover the key byte-by-byte, leading to a complete key recovery in ~4000 tests. Note that the only thing an attacker has to see is whether two inputs collide, nothing else. The attack can thus be done entirely through side-channels.
That is, the following program (instantly) succeeds when compiled with -C target-feature=+aes. Again note that recover_ahash_seed is completely blind to the hash outputs, and only gets to test if h(s1) == h(s2). This can be done in e.g. hash tables through timing attacks.
use ahash::random_state::RandomState;
use rand::prelude::*;
const PI2: [u64; 4] = [
0x4528_21e6_38d0_1377,
0xbe54_66cf_34e9_0c6c,
0xc0ac_29b7_c97c_50dd,
0x3f84_d5b5_b547_0917,
];
fn main() {
// Instantiate a random aHash instance.
let mut rng = rand::thread_rng();
let seed: [u64; 4] = rng.gen();
let rs = RandomState::with_seeds(seed[0], seed[1], seed[2], seed[3]);
// Simulate aHash key init for the AES-based hash.
let k0 = seed[0] ^ PI2[0];
let k1 = seed[1] ^ PI2[1];
let k2 = seed[2] ^ PI2[2];
let k3 = seed[3] ^ PI2[3];
let ahash_reference_key = bytemuck::cast::<_, u128>([k0 ^ k2, k1 ^ k3]);
// Crack secret key using ONLY collision checks.
let mut total_collision_checks = 0;
let decoded = recover_ahash_seed(&mut |s1, s2| {
total_collision_checks += 1;
rs.hash_one(s1) == rs.hash_one(s2)
});
assert!(decoded == ahash_reference_key);
println!("aHash key recovery attack complete using {total_collision_checks} collision checks.");
}While it may be possible to thwart this particular instantiation of this attack using a different input schedule, I find the usage of only a single round of AES between input absorption to be deeply disturbing as it is simply insufficiently mixing. I strongly implore you to use at least two rounds between accepting input into the hash state, like Go's AES-based hash does.
For the purpose of responsible disclosure I have not included recover_ahash_seed here. It's not particularly sophisticated however - it's about 70 lines of code, 20 of which is AES intrinsic boilerplate. If you wish I can send the source code of it to a maintainer through private communication, please specify how/where you would wish to receive it. To give you time to fix this vulnerability, while it remains active I will not publicize the details of the attack or the source code before 1st of January 2024.