tkaitchuck / aHash

aHash is a non-cryptographic hashing algorithm that uses the AES hardware instruction
https://crates.io/crates/ahash
Apache License 2.0
1.03k stars 101 forks source link

Critical issue: aHash's specialized hash is constant value 7161677110969590627 on ARM #166

Closed orlp closed 11 months ago

orlp commented 11 months ago

The AES intrinsics are not correctly implemented on ARM. These are the implementations (stripped of compiler directives for posterity):

pub(crate) fn aesenc_x86(value: u128, xor: u128) -> u128 {
    use core::arch::x86_64::*;
    unsafe {
        let value = transmute(value);
        transmute(_mm_aesenc_si128(value, transmute(xor)))
    }
}

pub(crate) fn aesenc_arm(value: u128, xor: u128) -> u128 {
    use core::arch::aarch64::*;
    unsafe {
        let value = transmute(value);
        transmute(vaesmcq_u8(vaeseq_u8(value, transmute(xor))))
    }
}

In detail, we see the following intrinsic for x86:

_mm_aesenc_si128(value, transmute(xor))

This is xor ^ MixColumns(SubBytes(ShiftRows(value))). For ARM on the other hand we have:

vaesmcq_u8(vaeseq_u8(value, transmute(xor)))

This is MixColumns(SubBytes(ShiftRows(xor ^ value))).

This difference goes wrong in a nuclear fashion in the final step of the specialized hash:

#[cfg(feature = "specialize")]
fn short_finish(&self) -> u64 {
    let combined = aesdec(self.sum, self.enc);
    let result: [u64; 2] = aesenc(combined, combined).convert();
    result[0]
}

The first step of aesenc(combined, combined) on ARM is combined ^ combined, which simplifies to... the constant 0. That is, aHash's specialized hash implementation used by hash_one on ARM is always a constant value.