universal-hash: `Key` type should be fallible

[ericlagergren]

It’s currently possible to create weak keys. See https://github.com/RustCrypto/universal-hashes/issues/182

[tarcieri]

The meta questions here are: should we have a fallible equivalent of KeyInit, and how much misuse resistance should we provide for UHF crates?

The question of fallibility impacts a large stack of crates which all use KeyInit: AEAD modes like aes-gcm and aes-gcm-siv use KeyInit to infallibly initialize the AEAD construction, and really this is the main use case of UHFs as well. If ghash/polyval have fallible constructors, we need to handle them failing inside of the AEAD constructors (for aes-gcm, at least, which is by far our most used AEAD crate)

In the case of either of those crates, the GHASH/POLYVAL keys are derived as part of the AEAD construction, and there is a vanishingly small probability (1 : 2^128) that the derived key will be 0. Is it worth making the whole constructor fallible to handle an edge case whose probability of occurring is the same as successfully guessing a 128-bit cryptographic key at random? I'm not sure it's worth complicating the API to handle an edge case which is statistically never going to happen.

Since UHFs are low-level building blocks of MACs/AEAD modes, perhaps we should just mark them as "hazmat" like we do block/stream ciphers.

[ericlagergren]

If ghash/polyval have fallible constructors, we need to handle them failing inside of the AEAD constructors (for aes-gcm, at least, which is by far our most used AEAD crate)

The probability of getting an all-zero hash key for AES-GCM et al. is cryptographically negligible, you'd be justified in panicking in that case.

Is it worth making the whole constructor fallible to handle an edge case whose probability of occurring is the same as successfully guessing a 128-bit cryptographic key at random? I'm not sure it's worth complicating the API to handle an edge case which is statistically never going to happen.

As we've both mentioned, the risk isn't AES-GCM, AES-GCM-SIV, etc. getting all zeros. It's other cryptographic algorithms that want to use POLYVAL or GHASH. This was an issue with the original AES-GCM-SIV drafts, so it's not inconceivable.

Since UHFs are low-level building blocks of MACs/AEAD modes, perhaps we should just mark them as "hazmat" like we do block/stream ciphers.

I think this is probably the best choice for the current version of RustCrypto. Hopefully once (if?) const_generic_exprs stabilizes a new version of RustCrypto could have simplified APIs like:

// in crate crypto_common
trait Key {
    const KEY_SIZE: usize;
    fn new(rng: impl CryptoRng + RngCore) -> Self;
    fn from_bytes(data: &[u8]) -> Result<Self, ...>;
}

// in crate aead
trait Aead {
    type Key: Key;
}

// in crate aesgcm
struct Aes256Gcm { ... }
impl Aead for Aes256Gcm {
    type Key = Aes256GcmKey;
}

struct Aes256GcmKey([u8; 32]);
impl From<[u8; 32]> for Aes256GcmKey { ... }
impl Key for Aes256GcmKey { ... }

// in crate universal_hash
trait UniversalHash {
    type Key: Key;
}

// in crate polyval
struct Polyval { ... }
impl UniversalHash for Polyval {
    type Key = PolyvalKey;
}

struct PolyvalKey([u8; 16]);
impl Key for PolyvalKey {
    const KEY_SIZE: usize = 16;

    fn from_bytes(key: &[u8]) -> Result<Self, ...> {
        if is_all_zero(key) {
           Err(...)
        } else {
           Ok(...)
        }
    }
}

[newpavlov]

I don't think that fallibility or panicking is the right solution. The algorithms based on UHF are defined in the ways which accept zero keys, but since they use permuted versions of user key, probability of passing zero key to UHF is astronomically low. By introducing fallibility or panic, our implementation would be incompatible with the specifications. Can you provide examples of widely used implementations which guard against zero keys?

If we are going with the non-compatible route, then it could be better to replace zero key with a non-zero constant key. In some cases it's important to prove that implementation does not contain any panics and we strife to keep our crates panic-free if possible.

Currently, I prefer the "hazmat" approach to this problem.

[tarcieri]

The one place we do have checks like this right now is the elliptic-curve crate, where SecretKey is a wrapper for a NonZeroScalar, and PublicKey a wrapper for a non-identity point.

However, these types already assert complex invariants and must be fallible to do so (scalar must be mod order, affine points must be a valid solution to the curve equation), so adding these additional checks isn't that difficult.

As it were, Curve25519 went out of its way to remove such fallibility: scalars are "clamped" to ensure they're in range rather than failing if they aren't, and will happily accept a key of 0.

[ericlagergren]

but since they use permuted versions of user key, probability of passing zero key to UHF is astronomically low. [...] Can you provide examples of widely used implementations which guard against zero keys?

To be clear, I am not concerned about well-established schemes (like AES-GCM, AES-GCM-SIV, HCTR2, ...) where the probability of generating H=0 is negligible.

What I am concerned about is people using POYLVAL outside of well-established schemes and not taking H=0 into consideration.

It's not a crazy concern—early versions of AES-GCM-SIV did not use a PRP to generate H and assumed the user would know better than to select a 'weak' authentication key. It's easy to imagine an armchair cryptographer forgetting about that case.

I think either option (panicking or making universal-hash hazmat) is fine. In either case, the polyval crate should have a warning about H=0 and perhaps even have a way to check for H=0 in constant time.