kmac: Towards an implementation

[ok-ryoko]

I've given the implementation of KMAC within the RustCrypto ecosystem some thought. My ideas, reproduced below, are informed by the NIST SP 800-185 recommendation and the hmac and sha3 crates.

I'm willing to do any/all of the work described below. However, I'm not a cryptographer or security researcher, so all my work would have to be scrutinized tirelessly by the more qualified.

User experience

In keeping with the principle of least astonishment, I want to be able to use KMAC objects like other existing RustCrypto MAC objects:

use kmac::{Kmac128, Mac};
use hex_literal::hex;

let key = hex!("404142434445464748494a4b4c4d4e4f505152535455565758595a5b5c5d5e5f");
let customization = b"My Tagged Application";
let mut mac = Kmac128::new_with(&key, &customization);
mac.update(hex!("00010203"));
let buf = [0u8;32];
let result = mac.finalize_into(&buf);
let result_bytes = result.into_bytes();
let expected = hex!("3b1fba963cd8b0b59e8c1a6d71888b7143651af8ba0a7070c0979e2811324aa5");
assert_eq!(result_bytes[..], expected[..]);

We should first consider the digest::Mac trait imported in this example. The automatic implementation of Mac is helpful for augmenting a type T (here, Kmac128) with such methods as new, update, finalize and verify, to name a few. This mechanism provides a consistent user experience with little extra development effort across different types of MAC.

This mechanism doesn't support KMAC because it requires inappropriate traits. For example, digest::KeyInit supports initialization from only a key, whereas KMAC must also permit a customization string. Moreover, KMAC is defined in terms of CSHAKE (an extendable-output function) and thus shouldn't implement digest::FixedOutput, a trait required for the automatic implementation of Mac. These limitations shape the implementation strategies I identify below.

Implementing KMAC

Using keccak

Prepare two core types of fixed security strength, Kmac128Core and Kmac256Core, that manage their own state and are implemented in terms of KECCAK[c] as described in Appendix B of NIST SP 800-185. The public API, similar to what we would expect if we were to import Mac, is implemented by hand. This is the cheaper approach but it violates the principle of least astonishment both internally (divergence of implementation strategy) and externally (users don't import a convenience trait). Moreover, it involves the duplication of private code in sha3.

Using sha3

Prepare a core generic type, KmacCore<D>, that wraps a hash function satisfying certain traits, e.g., ExtendableOutputCore. Implement the remaining traits as needed. Optionally, construct the Kmac128 and Kmac256 types, each a CoreWrapper<KmacCore<D>> where D is a sha3::CShake128 and sha3::CShake256, respectively.

Implement a convenience trait in digest that feels like Mac but requires a distinct set of methods. For example, this new trait should rely on digest::ExtendableOutput rather than FixedOutput. Thus, I'll call it MacXof in this post, but I note that this name doesn't capture all the key differences with Mac. In particular, MacXof must also support initialization with both a key and, optionally, a customization string. (The closest trait I can find that enables this behavior is crypto_common::KeyIvInit. However, the iv parameter is indicated for nonces and I'm unsure whether this is appropriate in this context.)

I've identified one concrete obstacle in relation to implementing traits on KmacCore. Consider the following code in hmac (edited for brevity):

impl<D> KeyInit for HmacCore<D>
where
    D: CoreProxy,
    D::Core: HashMarker + UpdateCore + FixedOutputCore + BufferKindUser<BufferKind = Eager> + Default + Clone,
    <D::Core as BlockSizeUser>::BlockSize: IsLess<U256>,
    Le<<D::Core as BlockSizeUser>::BlockSize, U256>: NonZero,
{
    // ...
    #[inline(always)]
    fn new_from_slice(key: &[u8]) -> Result<Self, InvalidLength> {
        let mut buf = get_der_key::<CoreWrapper<D::Core>>(key);
        // ...
        let mut digest = D::Core::default();
        digest.update_blocks(slice::from_ref(&buf));
        // ...
    }
    // ...
}

Here, the state can be initialized because the expectation is that D::Core implements Default. CSHAKE types in sha3 don't implement Default and we would need to fill this gap. However, instead of Default, it would be more appropriate to implement an initialization trait—an IvInit of sorts—so that the customization string passed to a Kmac128/Kmac256 constructor can be forwarded to the underlying CShake128/CShake256 constructor call.

In addition, the CSHAKE implementations in sha3 don't store their security strength. I don't see an easy way to prepare the expected algorithm names for KMAC (Kmac128 and Kmac256) without manipulating the CSHAKE type names directly, which I find undesirable.

Overall, this approach requires more development effort. It involves extending the digest API with one or more new traits, and implementing at least one trait on CSHAKE types in sha3. However, I'm in favor of this approach because it preserves both the user experience as well as the existing implementation style for MACs.

Testing

To test MAC implementations, RustCrypto serializes Project Wycheproof test vectors into binary blobs using the blobby crate. In turn, these are consumed by such macros as digest::new_mac_test. But there are no Wycheproof KMAC test vectors, nor does today's Wycheproof MAC schema support specification of the output length. So, we have no straightforward manner of leveraging the MAC test suite for KMAC.

I haven't found any official and public-facing KMAC test vectors. The NIST Cryptographic Algorithm Validation Program page currently provides only HMAC test vectors. There's a collection of KMAC test vectors that appears to be at a legitimate NIST domain (csrc.nist.gov); I'm inclined to use these as the basis for a handwritten test. The Legion of the Bouncy Castle uses these samples in their KMAC tests.

---

All this aside, my sincere thanks go to the RustCrypto contributors for your work over the years!

[tarcieri]

This is a great synopsis of the issue and a lot of great feedback on trait design.

My high-level suggestion is to implement the existing traits and then we can separately work towards ones that are a better fit for KMAC.

[newpavlov]

I agree that we probably should start with the fixed output size traits and work on improving our traits after that.

As for API design, XofMac as a convenience wrapper around ExtendableOutput + MacMarker and something like KeyCustomInit look good to me. KeyIvInit would be a bad fit here, not only because of the name, but also because customization strings are usually byte slices, not fixed size arrays. We probably should also introduce something similar to CtVariableCoreWrapper, but for ExtendableOutput.

@tarcieri
Maybe it's worth to move this issue to the traits repo?

[ok-ryoko]

Thank you both for your valuable feedback. You can now find a proof-of-concept implementation for Kmac128 at ok-ryoko/RustCrypto-MACs. I'm open to any and all changes.

Implementations for the following traits are fully generic and deemed complete:

• MacMarker
• BufferKindUser
• BlockSize
• UpdateCore
• Reset

On the other hand, the following traits are implemented by hand for only KmacCore<CShake128>:

• KeySizeUser
• OutputSizeUser
• KeyInit
• AlgorithmName
• Debug

By fixing KeySizeUser and OutputSizeUser to U32, I was able to satisfy the conditions of the first test vector and write a passing unit test that leverages Mac.

Aside: I duplicated left_encode from sha3 and mentioned the original author (@jvdsn) in the license files.

[ok-ryoko]

Because impl_cshake! in sha3 builds exclusively over extendable-output traits, I found the XOF aspect of the problem more accessible for my next iteration.

Using crypto-common v0.2.0-pre as a base, I first defined a KeyCustomInit trait.

Using digest v0.11.0-pre as a base, I implemented KeyCustomInit for CoreWrapper<T> and added MacXof.

I then updated sha3 for v0.11.0-pre of digest (link) uneventfully.

With all the ingredients in place, I arrived at a compiling KMACXOF implementation.

Now, for what’s missing…

The six test vectors include explicitly requested output lengths. Because I coded only KMACXOF (and thus the right-encoded output length is not incorporated when finalizing the reader) none of the tests pass. But by hard-coding an output length of 256 and 512 bits, I can get the KMAC128 and KMAC256 tests passing, respectively. This makes me more confident that the remainder of the implementation is working as expected.

The tests could be made to pass if I had FixedOutputCore and were able to leverage a finalize_into() method. I need OutputSizeUser, of course. My understanding is that the output size, being arbitrary in the context of SHAKE, is a run-time parameter that can’t be represented by compile-time type information (hence the absence of any OutputSizeUser-based constructs for the CSHAKE types). I can’t implement such a finalize_into() for KmacCore either because CoreWrapper obfuscates type methods in client code. This is my top blocker.

I didn’t introduce any verification methods to MacXof because I’m unsure whether it’s possible to guarantee constant-time equality checks for arbitrarily long byte sequences. In the post-quantum literature, there’s discussion of constant-time implementations of lattice cryptography schemes that build over SHAKE. Whether the same strategies are applicable here is beyond my current understanding.

Finally, I have to import KeyCustomInit explicitly in the tests. I speculate that this is because there’s (currently) no possible blanket implementation of this trait for KmacCore.

Thank you for your patience, @tarcieri and @newpavlov.