Designing New Cryptography for Non-Standard Threat Models

Since the IETF’s CFRG decided to recommend OPAQUE as a next-generation Password Authenticated Key Exchange, there has been a lot of buzz in the cryptography community about committing authenticated encryption (known to the more academically inclined as Random Key Robustness), because OPAQUE requires an RKR-secure AE scheme.

Random Key Robustness is a property that some symmetric encryption modes have, where it’s not feasible to decrypt a valid (ciphertext, tag) pair into two different plaintexts if both recipients are using different keys.

To illustrate this visually:

An example of random key robustness: encrypting two different images, with two different keys, can produce an identical stream of bits (ciphertext + tag).
RKR-secure ciphers don’t let people produce the same ciphertext+tag from two different plaintexts, with two different keys. You might be able to create an identical ciphertext, but the authentication tag will differ. (Art by Swizz.)

In the wake of the CFRG discussion, it became immediately clear that AES-GCM doesn’t meet this requirement.

What wasn’t immediately clear is that AES-GCM-SIV also falls short. But don’t take my word for it, Sophie Schmieg worked out the math in the linked post, which I highly recommend reading.

This isn’t to say that AES-GCM or AES-GCM-SIV are doomed, or should be deprecated. You probably don’t even care about Random Key Robustness in most of the places you’d use either algorithm! But if you are doing something where RKR actually matters, you probably care a lot. And it certainly violates the principle of least astonishment.

ChaCha20-Poly1305 won’t save you here either, since this is a property that message authentication codes based on cryptographic hash functions (e.g. HMAC) provide, but polynomial MACs (GMAC, Poly1305, etc.) do not.

So, if every standardized and widely-supported AEAD construction fails to provide RKR security, what’s a software engineer to do? Roll their own crypto?!

Don’t actually do that. (Art by Swizz.)

If you’re always on a well-tread path with a well-defined, standard threat model (i.e. client-server application accessible via TLS 1.3, possibly storing hashed passwords server-side), then rolling your own crypto isn’t just dangerous; it’s wholly unnecessary.

Coping with Non-Standard Threat Models

Systems that require Random Key Robustness do not fall within the standard threat model of AEAD cipher constructions.

However, RKR is far from the only scenario in which application developers might find themselves without a clear solution. Another example that comes up a lot:

“I need to encrypt data in a relational database, but still somehow use it in SELECT queries.”

— Far too many damn developers who haven’t heard of CipherSweet.

The first thing that you should do is clearly document your requirements and what attacks your system must protect against. Any undefined attack vector in your model should be assumed to be a vulnerability in your design. (This gets into Unknown Unknowns territory quickly.)

And then you should have a cryptographer review your design, and then have a cryptography engineer build it for you.

But where’s the fun in that?

This would be a very boring blog post if I left it at that! (Art by Khia.)

Instead of copping out with sane and reasonable advice, let’s actually walk through the process. At the end of this post, I’ll share a toy example I cooked up for this blog post.

Designing New Cryptography

First, Understand the Problem

Why don’t AES-GCM, etc. provide Random Key Robustness? Because they’re built with universal hash functions rather than cryptographic hash functions.

Cryptographic hash functions have different properties (i.e. preimage resistance and collision resistance) that make it significantly difficult to calculate two different authentication tags under two different keys. Attacking HMAC-SHA-256 in this way is about as expensive as brute forcing a 128-bit AES key. (Good luck with that!)

However, cryptographic hash functions are much slower than polynomial MACs, and using them in a construction like HMAC approximately doubles the slowness.

You might be tempted to just hash they key and the message together to save on CPU cycles, but that’s actually not safe for the hash functions nearly everybody uses (due to length extension attacks).

It logically follows that, if we had an AEAD cipher construction based on a hash function, we could have RKR security.

OwO *notices your cryptogrpahic robustness*
Now we’re getting somewhere! (Art by Khia.)

Look At Prior Art

Before the days of AES-GCM and ChaCha20-Poly1305, there were a lot of ad hoc constructions used everywhere based on AES-CBC and HMAC. (In that era, everyone used HMAC-SHA1, but don’t do that.)

However, there are a number of problems with ad hoc CBC+HMAC that we don’t want to reintroduce in modern systems:

  1. If you forget to include the initialization vector in the HMAC tag, you give attackers free reign over the first 16 bytes of the decrypted plaintext without having to break the MAC.
  2. The order of operations (Encrypt-then-MAC, MAC-then-Encrypt, Encrypt and MAC) matters tremendously.
  3. CBC+HMAC is usually implemented in application-layer code, but the security of such a construction depends heavily on the availability and utilization of constant-time functions.
  4. There is no standard format for CBC+HMAC, nor the order of operations for what gets fed into the MAC.
    • IV + ciphertext? Ciphertext + IV?
    • Append the MAC, or prepend it?
  5. CBC+HMAC is only an AE mode, there is no room for additional authenticated data. If you try to naively shove extra data into the HMAC, now you have to worry about canonicalization attacks!
  6. CBC mode requires padding (usually PKCS #7 padding), whereas cipher modes based on CTR do not.

This is among the long list of reasons why cryptographers have spent the past decade (or longer) pushing developers towards AEAD modes.

Boring cryptography is good cryptography!

This isn't IND-CCA2 Secure!
You never want to hear this about your design. (Art by Khia.)

Make sure you clearly understand the risks of the components other constructions have used.

Sketch Out A First Draft

By now, it should be clear that if we have an Encrypt-then-MAC construction, where the MAC is based on a cryptographic hash function (e.g. SHA-256), we may be able to attain RKR security.

With that in mind, our sketch will probably look something like this:

  • Encrypt(K1, M, N) -> C
    • Where Encrypt() is AES-CTR or equivalent
  • Auth(K2, C, A) -> T
    • Where Auth() wraps HMAC-SHA2 or equivalent
    • How we feed C and A into the underlying MAC is important
  • ???? -> K1, K2

We still have to define some way of splitting a key (K) into two distinct keys (K1, K2). You never want to use a cryptographic key for more than one purpose, after all.

Key-Splitting and Robustness

Your encryption key and authentication key should be different, but they should also derived from the same input key! This is mainly to protect implementors from having independent keys and accidentally creating a forgery vulnerability.

There are several different ways you can split keys:

  1. Just use SHA-512(k), then cut it in half. Use one half for encryption, the other for authentication.
  2. Use HMAC-SHA256(k, c1) and HMAC-SHA256(k, c2), where c1 and c2 are distinct (yet arbitrary) constants.
  3. Use HKDF. This works with any secure cryptographic hash function, and was specifically designed for situations like this. HKDF also supports salting, which can be used to randomize our derived keys.

We can really pick any of these three and be safe, but I’d advise against the first option. HKDF uses HMAC under-the-hood, so either of the latter options is fine.

Can We Make it Faster?

What if, instead of HMAC-SHA256, we used BLAKE3?

BLAKE3’s performance compared with other hash functions.

BLAKE3’s advertised 6.8 GiB/s can be even faster than Poly1305 or GHASH (and BLAKE3’s speed really shines through with long messages, due to its extreme parallelism through Merkle trees).

In Favor of ChaCha over AES

It’s no secret that I’m not a fan of AES. It’s not the mathematical properties of AES that bother me, it’s the 128-bit block size and the fact that software implementations have to decide between being fast or being secure.

Me, whenever I find an insecure software AES implementation. (Art by Khia.)

ChaCha’s 256-bit security level is easier to justify: The underlying PRF state is 512 bits (which implies an approximately 256-bit security level) and the keys are always 256 bits.

Furthermore, if you’re building ChaCha and BLAKE3 in the same codebase, you could reuse some components (i.e. the compression function, G). This is very desirable if you’re trying to ship a small amount of code (e.g. embedded systems). EDIT: One of the BLAKE3 authors informed me that I’m mistaken about this: “[N]ope, not exactly the same logic (rotations in different direction)”.

Other Desirable Security Properties

Nonce Nonsense

One of the biggest problems with standard AEAD modes is that they explode gloriously when you reuse a nonce. There are two ways out of this peril:

  1. Use a nonce misuse resistant AEAD construction (AES-GCM-SIV, etc.).
    • For prior art on nonce-misuse resistant cipher modes based on ChaCha, check out DAENCE.
  2. Use large nonces (e.g. XChaCha20 uses 192-bit nonces) and generate them randomly, so the probability of nonce reuse becomes negligible.

Since we’re already planning on using a hash function to derive subkeys (one for encryption, one for authentication), it makes sense to also accept a longer nonce than our stream cipher demands. The excess bytes can be passed to our KDF without significant risk or additional overhead.

Since the IETF’s ChaCha20 variant expects a 96-bit nonce, designing our construction to support 256-bit nonces means we can pass the first 160 bits of the nonce to the KDF and the latter 96 bits to the stream cipher. You can expect a single KDF collision after 2^80 encryptions, but it will almost certainly occur with a different nonce.

Safe MAC Canonicalization

We want to ensure it’s infeasible for an attacker to feed two different (ciphertext, AAD) pairs into our construction that produce the same tag.

Simply concatenating the two values will run the risk of someone shaving off a chunk of the ciphertext and storing it in the AAD instead.

Soatok angrily grasping computer monitor
There’s always a complication! (Art by Swizz.)

The simplest solution is to either prepend or append the lengths of the components (as the little-endian octet string representation of 64-bit unsigned integers).

The choice between prepending and appending doesn’t affect security much, but appending the lengths is friendlier for streaming interfaces.

After all, in a streaming encryption/decryption interface, you might not know the lengths of the either component until you’ve finished encrypting and authenticating all of the data.

(Art by Khia.)

Putting It All Together

Now that we’ve meandered through a rough list of desirable design properties, let’s recap:

  • We want to Encrypt then MAC.
  • We want to use ChaCha20 (the IETF’s variant) as our stream cipher.
  • We want to use keyed BLAKE3 for the KDF and MAC algorithm.
  • We want to accept 256-bit nonces (160 bits for the KDF, 96 for the stream cipher).
  • We want to ensure our ChaCha20 and BLAKE3-MAC keys are derived from the same input key, using some domain separation constants.
  • We want to feed the data into the MAC this order:
    1. AAD
    2. Ciphertext
    3. Length of AAD
    4. Length of Ciphertext
  • We want to ensure our authentication tags are always verified in constant-time.

That sounds like a lot. But what does it yield in terms of code size? Surprisingly very little!

You can find the JS implementation of my design on Github.

Should I Use This?

No. Don’t do it.

I mean, would your users really feel safe if you got your cryptography recommendations and implementations from a furry blogger?

This is just a toy example I put together for the sake of illustrating how a new cryptographic design might be proposed. That’s only the first step.

Ultimately, you shouldn’t use this for one simple reason: Neither my design nor my implementation have been peer reviewed.

Maybe I’ll refine it a bit and kick it over to the CFRG for consideration for inclusion with OPAQUE someday. It might turn out to be a good design. It might be vulnerable to some subtle attack I can’t even imagine right now.

Until experts tell you otherwise, it’s hazardous material and you should only play with it for educational purposes.

Soatok has a eureka moment
(Art by Swizz.)

Further Reading

I’ve written a lot about cryptography, and there are always more topics to write about than I have the time or energy to cover, so here’s a few cool blogs/etc. to check out while I slog through Rough Draft Hell.

  • Cryptography Dispatches — Newsletter ran by Filippo Valsorda, cryptographer and Go security team lead.
  • Bulletproof TLS Newsletter — Newsletter ran by Hanno Böck, freelance journalist, IT security expert, and AES-GCM exploiter.
  • Key Material — A new blog by Sophie Schmieg (cryptographer at Google) and Sarai Rosenberg (security engineer at Pager Duty).
  • Little Man In My Head — A blog by Scott Contini, a security expert who frequently posts helpful comments on /r/crypto.

Header art by Khia. The figure in the background is from this paper on Message Franking via Committing Authentication Encryption.

By Soatok

Security engineer with a fursona. Ask me about dholes or Diffie-Hellman!

5 replies on “Designing New Cryptography for Non-Standard Threat Models”

Spotted a mistake – ‘it’s not feasible to do decrypt a valid’. I think I saw another one when I first read the article, but I didn’t see it skimming through on my reread. Keep up the good work!


BLAKE3 is great for large messages but if these are for really tiny messages (<= 16-bytes w\ 256-bit security), it might suffice to just use hchacha20. If the messages are a little larger, say 16-32 bytes, then you could investigate using a 16-byte key and use the rest of the key to extend the nonce with 128-bit security.

But this customization obviously diverges from the standard and may increase attacker controlled or known data depending on how it is used in OPAQUE.

Either way, you'll want to check the size range before comparing hash function performance.


What do you think of the ARX-KW keywraps?

I’m working on an OPAQUE registration/verification client & server library in Rust and came across ARX-KW (specifically the GX variant) as a possible means of implementing AuthEnc for the OPAQUE EnvU.
The paper is here:
If I’m not mistaken, it is random-key robust as it used SipHash (cryptographically secure) to generate the authentication tags, but if anyone can confirm that would be great.

I have written a Rust library for it here and there’s a link to the reference implementation in C in the paper, should anyone want to experiment with it.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s