Streaming Interface for authenticated encryption?

[LoupVaillant]

Now that Monocypher is just under 1900 lines of code, we have room for more functionality. One that is very tempting to add is streaming AEAD, similar to Libsodium's.

One reason for the temptation is the ability to share code with crypto_lock() and crypto_unlock(). If the streaming API is provided separately, then a bunch of code, most notably authentication, must be duplicated. Inside Monocypher however, we can define the current AEAD interface in terms of the streaming API. I have written a prototype that currently costs 49 lines of code (and 6 new functions, and one additional struct).

On the other hand, we don't want to include something of limited value. We may want other functionality in the future, and it would be a pity if we had to break the 2KLoC psychological barrier to get it. To be included, this streaming interface should satisfy the following criteria:

• No major footguns.
• Close enough to ideal for file encryption.
• Close enough to ideal for interactive sessions over TCP (or other reliable ordered channel).

If possible, it should also satisfy those bonus criteria:

• RFC 8439 friendly: Implementing with IETF's ChaCha20 (96-bit nonce, 32-bit counter) should be straightforward.
• DJB friendly: Implementing it with the original ChaCha20 (64-bit nonce, 64-bit counter) should be straightforward.
• Fast: we should limit unneeded overhead.
• Compatible with crypto_lock() (mostly for the sake of elegance).
• Able to handle unreasonably large chunks without triggering nonce reuse. (Though, who uses large chunks with a streaming API?)

One major question remains about the "no major footguns" criterion: key commitment. As they stand, polynomial hash based ciphers are vulnerable to attacks where the same message could be successfully decrypted under several possible keys. And most importantly, an attacker could find those keys and exploit that for nefarious purposes. There's also a related question about message commitment, where it's possible to find several messages that produce the same authentication tag (that requires knowledge of the key).

We could solve those problems by using a random key robust AEAD, such as Chacha20/Blake2b, or by adding a bunch of encrypted zeroes to the message (well, to each chunk, actually). This is either slower or unwieldy, not to mention the increased size overhead.

I believe there is another way: make sure the protocol leaves no room for tricking the recipient into using the wrong decryption key. Commit the key once, then use ordinary AEAD. Also, we need to determine how much of an issue the lack of message commitment may be.

If this works, then a ChaPoly based streaming interface is probably worth adding. If it does not work, then even crypto_lock() was probably not worth adding, and we'd better not compound the problem with yet another broken construction.

Food for thought, to be considered when we can make the time.

[LoupVaillant]

Okay, I found why people worry about commitment in the context of encrypted messages. Following this paper about partitioning oracles, Age decided to mitigate the attack by limiting the size of its chunks.

Partitioning oracles are about exploiting the fact that some AEAD constructions, including ChaPoly, allow attackers to craft ciphertext that successfully decrypt under more than one key. Instinctively, you would think that a a ciphertext can only decrypt under the key that generated it. Not quite:

• By the pigeonhole principle, a 16-byte tag only has 2^128 possible values, while we have 2^256 possible keys. On average, a given ciphertext has the right tag for 2^128 possible keys. Though it doesn't matter if one can't find those keys efficiently.
• In some cases, an attacker can efficiently craft a message that decrypts under several keys. The worst possible case would be if they could craft messages that decrypt under half of all possible keys.

The partitioning oracle attack works thus: first, the attacker crafts a ciphertext that decrypts under half of all possible keys, such that the attacker knows that half. Then they send that message to the victim, that candidly leaks whether decryption was successful or not (through an error message or timing leak). Now the attacker has gained one bit of information about the key. Repeat the operation 255 more times, and voilà, the attacker has the whole key, and the victim is pwned.

While practical attacks aren't that powerful (against AES-GCM, the paper talks about covering up to 2^16 keys in a single message, and only up to 10 in the case of ChaPoly), they can still be quite scary in two scenarios:

• Password based encryption. Passwords have relatively little entropy. By ruling out several possible password in a single query, we could considerably speed up password recovery.
• De-anonymization. If we want to test which public key a recipient is using, and we have a list of possible public keys, we could speed up the search by ruling out several keys in a single query.

Age mitigate those attacks by limiting the size of its chunks: with this limitation, it's only possible to cover two keys per query instead of a gazillion.

---

Now as much as we could discourage scenarios under which there is a decryption oracle, we're gonna have to assume users may fall into this trap. So as a crypto library, it would be best to only provide committing AEAD. Unfortunately, (i) Monocypher already provides a non-committing ChaPoly construction, and (ii) polynomial hashes are fast. So there's seem to be a tension between usability and performance.

That said, there is a way to defeat partitioning Oracles: commit the key before actually using it:

• In the context of interactive key exchange, this means using a key exchange mechanism that unambiguously selects the shared secret. That is, make it so there is only one possible shared secret, and if any party uses another one, the key exchange fails. I think, but don't know for sure, that modern key exchange protocols such as Noise already have this guarantee.

• In the context of non-interactive encryption, this means checking the validity of the key before trying to decrypt anything. We could for instance, start the file with a hash of the key or similar, so that we can abort decryption if we don't see the right hash. This is useful to not waste time for files on which we're trying the wrong key, or checking multiple possible slots in the case of PURBs. The disadvantage is the possibility of leaking the fact that we failed to open the file header, as opposed to a decryption failure elsewhere. It's not clear to me what interesting attack could be mounted with this information, though.

So, if we manage to commit the key before starting the secure session or decrypting the actual message, we should be good. No need to limit the size of chunks like Age does. And since this naturally happens in a number of situation, a non-committing AEAD could be viewed as legitimate.

Still, we must recognise that partitioning oracle attacks are a foot gun, and we must consider carefully whether that should stop us. In any case, we probably want to add a security considerations section about them in the current manual.

[snej]

Encrypted streams would be very good to have.

Sodium's crypto_stream isn't really a stream, however, it's a sequence of messages, and the encrypting and decrypting parties have to agree on what the sizes of the messages are, because the decryption API requires the caller to pass in the entire encrypted message.

This is a pain in the butt for use in network connections, because

• You can't just divide the stream into fixed-size messages, because in an interactive protocol the sender will send some data and await a response, and if that data ends up in an unfilled buffer in the encryption layer, the connection will deadlock.
• So messages have to be variable length. But that means framing, i.e. prefixing the encrypted message with its length in bytes. This tends to reveal the message boundaries to eavesdroppers.
• The workaround that I've seen (e.g. Scuttlebutt's box-stream) is to encrypt the byte-count, then encrypt the message. That's extra work and adds a second MAC to every message.

[LoupVaillant]

Hmm, I'm not sure we can meaningfully hide message sizes from traffic analysis in an interactive protocol, so I'm not sure Scuttlebutt's workaround really works: when you're sending a message and there's no other message right behind it, you have to send your first message anyway, and encrypting its length won't do you much good if the eavesdropper can just notice a pause in the data stream. If you really want to hide message sizes & boundaries, I have two strategies in mind:

• Group messages in a single, bigger message. That may mean accumulating messages until you have enough to send.
• Pad your messages. The overhead will be… significant, though it could be reduced by message grouping.

How effective those strategies are really is application dependent. And more to the point, I don't think I can come up with a nice, simple, low-overhead streaming scheme that supports any of the above out of the box.

Then there are the use cases where you do know chunk sizes in advance: file encryption and streaming lots of data. In both cases, chunk length can be a hard coded convention, written at the beginning of the file, or agreed upon during the handshake. For these use cases, libsodium's approach minimises overhead.

Personally, I don't think I can find a lightweight approach that satisfies your use case out of the box. I'm afraid users will have to endure butt pain, at least until I get around to write an actual network library.

[LoupVaillant]

Seems like I finally have a design worth considering (latest version). Here's the API:

typedef struct {
    uint32_t counter; // MSB of the ChaCha20 counter
    uint8_t  key[32];
    uint8_t  nonce[8];
} crypto_stream_ctx;

void crypto_stream_init(crypto_stream_ctx *ctx,
                        const uint8_t key[32], const uint8_t nonce[24]);
void crypto_stream_write(crypto_stream_ctx *ctx,
                         uint8_t            mac[16],
                         uint8_t           *cipher_text,
                         const uint8_t     *plain_text, size_t text_size);
int crypto_stream_read(crypto_stream_ctx *ctx,
                       uint8_t           *plain_text,
                       const uint8_t      mac[16],
                       const uint8_t     *cipher_text, size_t text_size);

void crypto_stream_rekey(crypto_stream_ctx *ctx);
void crypto_stream_init_raw(crypto_stream_ctx *ctx,
                            const uint8_t key[32],
                            const uint8_t nonce[8],
                            uint32_t counter);

// with additional data
void crypto_stream_write_aead(crypto_stream_ctx *ctx,
                              uint8_t            mac[16],
                              uint8_t           *cipher_text,
                              const uint8_t     *ad        , size_t ad_size,
                              const uint8_t     *plain_text, size_t text_size);
int crypto_stream_read_aead(crypto_stream_ctx *ctx,
                            uint8_t           *plain_text,
                            const uint8_t      mac[16],
                            const uint8_t     *ad        , size_t ad_size,
                            const uint8_t     *cipher_text, size_t text_size);

A few things to consider:

• The true kernel of this whole interface is crypto_stream_init_raw(), crypto_stream_write_aead() crypto_stream_read_aead(), and crypto_stream_rekey(). Everything else can be implemented just by calling those functions. This includes the existing non-streaming API, and even RFC 8439.

• Right now we have crypto_stream_init() and crypto_stream_init_raw(), but realistically the only purpose of the latter is to implement crypto_stream_rfc8439_init() and crypto_stream_djb_init(). Having raw access reduces the surface of the core API, but then users would have to write the following themselves:

void crypto_stream_rfc8439_init(crypto_stream_ctx *ctx,
                                const uint8_t key[32], const uint8_t nonce[12])
{
    crypto_stream_init_raw(ctx, key, nonce + 4, load32_le(nonce));
}

void crypto_stream_djb_init(crypto_stream_ctx *ctx,
                            const uint8_t key[32], const uint8_t nonce[8])
{
    crypto_stream_init_raw(ctx, key, nonce, 0);
}

• For consistency with the rest of the library, the read() and write() functions come in two flavours: one with additional data, and one without. Consistency is important, but it does cost us 12 lines of code and 2 exported symbols. Probably not a big deal, though still worth noting.

• Despite being called automatically to avoid counter-nonce overflow (which with the current design happens once every 4 billion messages), The rekey() function still needs to be exposed for easy forward secrecy (symmetric ratchet) in long lived symmetric sessions.

• When used to implement the current crypto_lock() or a "DJB original" ChaCha20 version of it, the streaming API has no practical limit on message length. However, as soon as we have more than one message in the stream, message length (except for the last message before rekeying) is limited to 512GiB (minus 64 bytes). This is in my opinion an acceptable limit, considering that people use streaming interfaces precisely to avoid such unreasonably gigantic chunks.

• Since IETF ChaCha20 and DJB ChaCha20 can both be implemented in terms of each other, we can write the same streaming interface with an IETF version of ChaCha20 instead. Doing so would likely limit all message lengths to 256GiB, but apart from that we can achieve perfect interoperability with existing IETF ChaCha20 implementations.

• Just writing this comment caused me to correct a critical nonce&counter reuse in the rekey step. There may be more errors. Thus, the exact design of the streaming interface absolutely must be formalised and peer reviewed before we even dream of merging it to the master branch.

[fscoto]

I haven't actually used the API yet, so take the following with a grain of salt, but I'd like to know these ahead of time going in:

1. Is the libsodium crypto_secretstream_xchacha20poly1305_* family compatible with the crypto_stream_* family? Considering a large amount of questions we get is about libsodium compatibility, I would assume this to be a consideration.
2. Considering this is a high-level offering, are you sure you want a detachable authentication tag? The rest of Monocypher consistently has it detached, but they're also lower-level building blocks. My understanding of the purpose of this new interface is e.g. in network communications, agree on a secret key and then just have both sides talk to each other with the streaming interface, or e.g. in age-style file encryption, just dump the stream output and treat it as opaque. I'm not sure if a higher-level construction should detach the MAC, especially considering RFC 8439 § 2.8 formally defines that the AEAD is ciphertext followed by MAC.
3. Why rfc8439 instead of ietf in the function name? This seems inconsistent with the other ChaCha20 functions.

[snej]

This looks reasonable to me (and similar to the libSodium API that I recently built a byte-oriented stream around.) I assume the behavior of crypto_stream_rekey is such that both the sender and receiver have to call it at the same "time" in the message stream?

[LoupVaillant]

@fscoto:

1. No it's not. I considered it, but I disagree pretty strongly with Libsodium's design choices on the matter: its streaming interface is incompatible with its monolithic interfaces, and requires too much code to be implemented without significant runtime overhead.

2. Actually, this is quite a low-level offering, to the point where the monolithic AEAD is implemented in terms of it. I couldn't do that without a detached tag. Another reason is consistency with the existing API. Another reason yet is buffer lengths: I'd rather have the size of the plaintext and ciphertext be the same, makes it easier to know how long each buffer must be. (If I could go back in time, maybe I would reattach the tag everywhere, though to be honest I'm not sure.)

3. Ah, you're right, ietf is better. Blame the naming scheme I (mistakenly) chose for the test suite. Note however that this alternate init function will probably not be included: not only would it require more code, consistency would almost demand that we implement the corresponding monolithic versions as well, meaning 8 functions. Way too much code for too little benefit.

---

@snej:

Yes, both parties need to call rekey() at the same time. There's no tag for the recipient to detect & trigger rekey with, it must be decided manually by the application writer (either by convention, or by communicating the rekey order in-band).

[LoupVaillant]

Added some tests, and refined the design. I have managed to lift the size limits of chunks, at the cost of an increased rekey overhead (the automatic rekey occurs every 256 chunks instead of every 4 billions).

The API maintains an internal context with the following information:

• A 32-byte key.
• An 8-byte nonce.
• A 32-bit counter.

There are 3 ways to initialise this context that makes some sense:

• From a key and 24-byte nonce (the default):
  • ctx.key = HChacha20(key, nonce[0:16[)
  • ctx.nonce = nonce[16:24[
  • ctx.counter = 0
• From a key and 8-byte nonce ("DJB original"):
  • ctx.key = key
  • ctx.nonce = nonce
  • ctx.counter = 0
• From a key and 12-byte nonce (RFC 8439)
  • ctx.key = key
  • ctx.nonce = nonce[4:12[
  • ctx.counter = little_endian(nonce[0:4[)

(I have realised that the 12 byte nonce cannot be used for the incremental interface because of catastrophic nonce reuse problems with chunks beyond the first one, as well as rekeying. Because of this, the current design only provides the short and extended nonce versions, which do not have this problem. I removed the raw_init() function, which is impossible to document. That being said, full compliance with RFC 8439 is still possible for messages that use only one chunk. It requires poking at the internals of the context, but this beats copying & editing the entire AEAD code.)

Nonce sizes have their usual pros & cons: short nonces have no overhead, but they cannot be random. Long nonces can be random, but they incur an additional HChaCha20 call. Once the context is initialised, we can start sending message chunks. Each chunk is built thus:

• counter = ctx.counter << 32
• ciphertext, tag = AEAD(ctx.key, ctx.nonce, counter)
• ctx.counter = ctx.counter + 2^24
• If ctx.counter == 0, rekey()

The AEAD works the same as RFC 8439, except with a 64-bit counter and a 64-bit nonce, and the start value of the counter is not always zero. The counter is then incremented, and if it cycles back to zero we rekey.

With the chosen increment, we end up rekeying every 256 messages. This means one one additional HChaCha20 call per 256 messages. In the absolute worst case (empty messages), the overhead is less than 0.4%. In a reasonable worst case (short messages), the overheads halves down to 0.2%. In a typical streaming scenario with 32KiB chunks, even if we assume perfect vector instructions parallelism we get a 0.006% overhead, which I deem negligible. The reason for this big increment is because it ensures message chunk lengths are unlimited (the theoretical limit is 2^62 bytes, which is close enough to infinity).

Finally, the rekey operation derives the next key from the current one:

• ctx.key = HChaCha20(ctx.key, 0xffffffffffffffff || ctx.nonce)
• ctx.counter does not change.
• ctx.nonce does not change.

---

With this design, I believe we have a versatile, limitless, low-overhead streaming API, that as a bonus even allows RFC 8439 compliance if we can tolerate a tiny little hack (I currently use that hack in the tests to verify RFC compliance). Though I'll still seek peer review, I'm fairly confident the current design is sound. The only thing left to do now is discuss tradeoffs.

[LoupVaillant]

One small change to the rekeying algorithm: we should reset the counter to zero.

This changes nothing for automatic rekeying, because the counter is already zero. However, manual rekeying can happen at any time, and when it happens, we can safely delay automatic rekeying to reduce overhead.

[LoupVaillant]

I had an epiphany. 😎

Rekeying can be achieved by copying 32 previously unused bytes. See, RFC 8439 requires one ChaCha20 call to generate the authentication key. Strangely enough, it does not use HChacha20, but regular Chacha20. This incurs a small overhead, but Monocypher conforms to it because it provides cheap compatibility with Libsodium. Thing is, a ChaCha20 block is 64 bytes, and the authentication key is only uses the first 32. The last 32 can be used however we want.

This is ideal for rekeying. And since the overhead is so low (just copy 32 bytes), we can afford to do it for every single message, which by the way makes the rekey() function redundant. The result is very cheap, automatic forward secrecy with a symmetric ratchet.

Even better, since we change the key on a systematic basis, we no longer need to mess with the counter. As a consequence, we now can use 96-bit nonces with multi-chunk messages without fearing any collision, so I can justify core support for those (and along them RFC 8439 compatibility).

Icing on the cake, users now have a (somewhat low-performance) fast key erasure user-space CSPRNG at their disposal. When they need new random bytes, they can just write a new message from a stream context, and the current seed will automatically be erased. With this poor man's RNG, the temptation to add a dedicated one plummets.

This design is also very close to full blown key commitment support: for single chunk messages, we can use the key as an additional tag instead of a key for the next chunk, and have the recipient compare that tag along with the authentication tag. I'm not sure this is worth the trouble however, because of the increased message size overhead.

And on top of it the whole thing is simpler. I saved 8 lines of code.

---

The API didn't change much: I've removed the now redundant rekey() function, and added crypto_stream_init_ietf():

void crypto_stream_init(crypto_stream_ctx *ctx,
                        const uint8_t key[32], const uint8_t nonce[24]);
void crypto_stream_init_djb(crypto_stream_ctx *ctx,
                            const uint8_t key[32], const uint8_t nonce[8]);
void crypto_stream_init_ietf(crypto_stream_ctx *ctx,
                             const uint8_t key[32], const uint8_t nonce[12]);

void crypto_stream_write(crypto_stream_ctx *ctx,
                         uint8_t            mac[16],
                         uint8_t           *cipher_text,
                         const uint8_t     *plain_text, size_t text_size);
int crypto_stream_read(crypto_stream_ctx *ctx,
                       uint8_t           *plain_text,
                       const uint8_t      mac[16],
                       const uint8_t     *cipher_text, size_t text_size);

void crypto_stream_write_aead(crypto_stream_ctx *ctx,
                              uint8_t            mac[16],
                              uint8_t           *cipher_text,
                              const uint8_t     *ad        , size_t ad_size,
                              const uint8_t     *plain_text, size_t text_size);
int crypto_stream_read_aead(crypto_stream_ctx *ctx,
                            uint8_t           *plain_text,
                            const uint8_t      mac[16],
                            const uint8_t     *ad        , size_t ad_size,
                            const uint8_t     *cipher_text, size_t text_size);

Internally, initialisation is unchanged, but the way chunks are generated is simplified:

ciphertext, tag = AEAD(ctx.key, ctx.nonce, ctx.counter)
ctx.key         = free_bytes_from_AEAD

That simple. If I zoom in a little and detail the AEAD we get this:

auth_key, new_key = ChaCha20(ctx.key, ctx.nonce, ctx.counter, zeroes, 64)
ciphertext        = ChaCha20(ctx.key, ctx.nonce, ctx.counter + 1, plaintext, message_size)
tag               = AUTH(auth_key, ad, ad_size, ciphertext, text_size);
ctx.key           = new_key

The AUTH() step is directly taken from RFC 8439. The new_key is basically free, because a ChaCha block is 64 bytes anyway.

[fscoto]

So essentially, you're doing away with the rekey method because every stream chunk is an immediate re-key anyway at the cost of an extra 32-byte copy for each message. Do you have your RPi on hand? I wonder how bad the extra copy expenses end up being on a smaller platform.

Going back to try and rewrite fk to use the new API, I notice that I'm missing libsodium's crypto_secretstream tag handling. Namely, I'm missing a way to signal end-of-stream. The current API works well enough for a network-based API where the connection just gets dropped or there's a protocol-level "we are going to stop communicating" message. However, you cannot detect a premature end-of-stream with the current API, i.e. the size of the entire steam can only be effectively authenticated with user-level code rather than library code and involves non-trivial extra effort in the form of branches and relatively fragile additional code that is easy to forget to test.

Was this part of your threat model?