AES-SIV support

[jeremyherbert]

Suggested enhancement

Add support for AES-SIV mode outlined in https://datatracker.ietf.org/doc/html/rfc5297

Justification

Mbed TLS needs this because AES-GCM fails catastrophically when nonce reuse occurs. For long term keys, securely storing a monotonic nonce is very challenging if the device cannot maintain RAM data and must write the nonce to non-volatile memory with a limited number of write cycles and/or limited security.

AES-SIV solves this problem by allowing (and even recommending) the use of a random nonce.

I would like to work on this myself; is this something in principle which would be accepted into mbedtls?

[gilles-peskine-arm]

Yes, we would welcome AES-SIV. Thanks for offering!

Though I'm curious: can you talk publicly about where you've seen it used? SIV modes are somewhat widely implemented and often recommended by cryptographers, but they seem to have a hard time getting adopted anywhere...

In general, we do welcome cryptographic mechanisms that are generally considered secure at the time of integration and that are used in practice. Formal standardization is a plus but not strictly required. We tend to focus more on devices with limited resources, but this isn't a strict focus either.

The limiting factor for us is review bandwidth, especially when it comes to cryptographic expertise. There are other cryptographic mechanisms that we're likely to consider higher priority than AES-SIV, in particular SHA3 and EdDSA. However, a new mode is considerably easier to review than those two, so it'll be easier for us to find time.

Before AES-SIV can happen, we need to discuss a few architectural matters.

• If any changes are required in aes.c, such as new functions, this can break alternative implementations of AES (MBEDTLS_AES_ALT) which don't implement the new functions. This is only acceptable if the new feature is controlled by a compile-time option which is not included in the default build. Preferably the new mode should only be implemented via high-level modules (cipher.c, psa_crypto_aead.c).
• We're moving from mbedtls_cipher_xxx to psa_aead_xxx as the preferred API for AEAD algorithms. At some point, we may stop adding new features to cipher.c. The forward-looking way would be to add the algorithm to PSA and make it available to cipher only with MBEDTLS_USE_PSA_CRYPTO, however we are not be ready for this yet because the MBEDTLS_USE_PSA_CRYPTO API is not stable yet.
• Now that we've implemented multipart GCM and CCM, our test infrastructure may have trouble with AEAD mechanisms that have no multipart implementation (there may be some systematic testing that insists that if an algorithm is supported, it must run multipart tests on it). This is not a counterindication: if such trouble arise, we'll just have to fix it.
• We'll have to allocate a new PSA algorithm identifier for SIV. That's not a problem, Mbed TLS doesn't have to wait until a new version of the PSA specification comes out.
• With respect to PSA, the API doesn't support double-length keys well. It defines an algorithm for XTS, but that's never been implemented, and I suspect implementing it will require a tweak to the API such as defining a new key type. That's only a small hurdle, but it's a hurdle that SIV may have to be the first to solve. I (@gilles-peskine-arm) am the main point of contact for PSA crypto API design.

[jeremyherbert]

Thanks for your reply. What you have said makes sense to me.

I think probably the first step for me would be to hack something together to get things working and see exactly what parts of the codebase I need to touch. The exact API design is of course something that core folks (like yourself) would need to be advising on, as I don’t have any knowledge of future plans, etc.

I can’t point to anything public I am afraid, but ultimately the problem is that NIST SP 800-38D recommends an integer counter for the GCM IV. It is very challenging to store a counter in a low endurance memory (ie flash inside an MCU gives roughly 10k writes per 4k page) and where bandwidth is so restrictive that regularly regenerating/exchanging session keys is not viable. For example, in LoRaWAN networks, devices can’t keep exchanging new session keys regularly as gateways have highly asymmetric RX and TX bandwidth (gateway => device is much more expensive than device => gateway). Devices are also expected to be deployed with a single AES key for use in all communication over many years.

I think this a fundamental flaw with most recent security-infused MCUs on the market; most implement some form of hardware acceleration of algorithms and sometimes key storage, but secure, high-endurance, on-die nonvolatile counters seem to be very rare outside of the smartcard space. Storing data externally is a problem; nonce reuse is fairly easy to force using a rollback attack. At least if one was using SIV with a random nonce, the only risk would be replays (which can be mitigated in other ways).

I just wish I could get a secure FRAM!