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:

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.

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!

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.

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.

(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.

https://soatok.blog/2020/09/09/designing-new-cryptography-for-non-standard-threat-models/

#BLAKE3 #ChaCha20 #cryptography #randomKeyRobustness #SecurityGuidance #symmetricCryptography

Dhole Moments

2020-04-21 12:25:46

Authenticated Key Exchanges are an interesting and important building block in any protocol that aims to allow people to communicate privately over an untrusted medium (i.e. the Internet).

What’s an AKE?

At their core, Authenticated Key Exchanges (AKEs for short) combine two different classes of protocol.

1. An authentication mechanism, such as a MAC or a digital signature.
2. Key encapsulation, usually through some sort of Diffie-Hellman.

A simple example of an AKE is the modern TLS handshake, which uses digital signatures (X.509 certificates signed by certificate authorities) to sign ephemeral Elliptic Curve Diffie-Hellman (ECDH) public keys, which is then used to derive a shared secret to encrypt and authenticate network traffic.

I guess I should say “simple” with scare quotes. Cryptography is very much a “devil’s in the details” field, because my above explanation didn’t even encapsulate mutual-auth TLS or the underlying machinery of protocol negotiation. (Or the fact that non-forward-secret ciphersuites can be selected.)

AKEs get much more complicated, the more sophisticated your threat model becomes.

For example: Signal’s X3DH and Double Ratchet protocols are components of a very sophisticated AKE. Learn more about them here.

The IETF is working to standardize their own approach, called Messaging Layer Security (MLS), which uses a binary tree of ECDH handshakes to manage state and optimize group operations (called TreeKEM). You can learn more about IETF MLS here.

Password AKEs

Recently, a collection of cryptographers at the IETF’s Crypto Research Forum Group (CFRG) decided to hammer on a series of proposed Password-Authenticated Key Exchange (PAKE) protocols.

PAKEs come in two flavors: Balanced (mutually authenticated) and augmented (one side is a prover, the other is a verifier). Balanced PAKEs are good for encrypted tunnels where you control both endpoints (e.g. WiFi networks), whereas Augmented PAKEs are great for eliminating the risk of password theft in client-server applications, if the server gets hacked.

Ultimately, the CFRG settled on one balanced PAKE (CPace) and one augmented PAKE (OPAQUE).

Consequently, cryptographer Filippo Valsorda managed to implement CPace in 125 lines of Go, using Ristretto255.

I implemented the CPace PAKE yesterday with Go and ristretto255, and it felt like cheating.

📦 https://t.co/Q0kI19JOPY 📦

125 lines of code! Really happy with it and it was a lot of fun.

— Filippo Valsorda (@FiloSottile) March 29, 2020

Why So Complicated?

At the end of the day, an AKE is just a construction that combines key encapsulation with an authentication mechanism.

But how you combine these components together can vary wildly!

Some AKE designs (i.e. Dragonfly, in WPA3) are weaker than others; even if only in the sense of being difficult to implement in constant-time.

The reason there’s so many is that cryptographers tend to collectively decide which algorithms to recommend for standardization.

(n.b. There are a lot more block ciphers than DES, Blowfish, and AES to choose from! But ask a non-cryptographer to name five block ciphers and they’ll probably struggle.)

https://soatok.blog/2020/04/21/authenticated-key-exchanges/

#ake #authenticatedKeyExchange #cryptography #ECDH