Streaming API to authenticated encryption

Question

In regards to NaCl, I asked DJB he had any intent to add a streaming API to an authenticated cipher. His response was obvious in retrospect, that one should never release a decrypted plaintext before verifying the authenticator.

However, this got me to thinking. Streaming is important — for instance, when working with extremely large datasets. Is it possible, or even advisable, to mimic a streaming interface?

One simple approach would be to chunk the data every certain number of blocks. Once you've received enough blocks, output the IV and a complete ciphertext into the cryptostream. When you've received the next set of blocks to complete a chunk, generate a new IV and repeat. To decrypt, take the first block of the cryptostream and consider this to be the first IV. Read a full chunk, and decrypt. Output the result as the first chunk of plaintext. Repeat.

This runs all the data through an authenticated cipher and verifies the authenticator before releasing the plaintext, but it does not verify the whole ciphertext before releasing some plaintext. Is this problematic, or is it generally considered safe? Is it safe in some circumstances, depending on your particular problem? Or does it invariably introduce serious flaws?

I realize that this is well into rolling-your-own-crypto territory, and do not plan to implement this myself. That said, what's the verdict on the approach? Are there alternative solutions to the problem? Is there a general approach that one can use to safely encrypt extremely large datasets with authenticated modes, or are any solutions still highly dependent on the exact problem being solved?

Update: Hoang, Reyhanitabar, Rogaway, and Vizár published a paper which defines the "STREAM" protocol that addresses this problem.

Answer 1

As pointed in the question, a conservative API to authenticated encryption should only ever release authenticated plaintext on the deciphering side. Anything else is too open to attacks (padding, timing, denial of service, unamit).

In a streaming API, this forces aggregation of data into blocks, each authenticated. The simplest method is fixed size ciphertext blocks (blocking related to characteristics of plaintext, e.g. at end-of-line for text, is too susceptible to information leak; on-demand blocking by the receiver requires feedback on the communication link, that could leak information, and is overly complex).

One obvious drawback of blocking is that it increases the overhead; however, even with 128-bit overhead per block (which is enough for an IV and authenticator), 8kiB blocking leads to less than 0.1% overhead, and this is acceptable in many use cases. That's basically what the OP is proposing.

One other very real problem with this blocking strategy is that we must resist suppression, duplication, and reordering of authenticated blocks by an adversary, with the intend of altering the plaintext correspondingly. The scheme proposed in the question does not, and is vulnerable to these attacks.

To correct that, one method is to include a block sequence number in the authenticated data, starting at 0 at start of data, and incremented by one at each block. That does not even necessarily increase the size overhead, as this block number needs neither to be encrypted, nor explicitly transmitted. Using GCM, we can have this block number implicitly included in the authenticated data, but not transmitted. With an Encrypt-then-MAC authenticated encryption, we can insert the block number after encryption and before MAC-ing. With a MAC-then-encrypt authenticated encryption, we can enter this block number in the MAC-ed data, and remove it before encryption.

Another method to correct that is to use a different key for each block, generating them with a fast KDF.

With such tweak, I do not see any systematic flaw in the use of authenticated encryption with blocking, packaged in a streaming API to authenticated encryption, beyond the obvious inherent (but practically acceptable) dangers, in particular

• the adversary can interrupt the flow of authenticated data and deduce something from how the receiver reacts to that, especially if there is a retry mechanism other than "redo from start".
• the receiver is likely to perform actions detectable by the adversary on the basis of what is in a block; that's enough to leak information that would not leak in non-blocked authenticated encryption (for example, assume the plaintext is known to contain either 98 or 99 ! characters, with spacing much higher than the block size, each ! causing a power consumption burst on the receiver side, and the adversary gets a power meter reading every second allowing to reliably discern if that burst occurred or not. Then when blocking is used, she can use that to determine whether there are 98 or 99 ! characters, by restricting the flow of information to one block between two meter readings; something that likely would not be possible without blocking assuming there is 5% uncertainty in the difference between two consecutive power readings).

Answer 2

I think (emphasis on think) that treating the data as a series of packets is okay, as long as you verify each packet. You are only releasing authenticated chunks of plain text (or rejecting tampered packets). However, you also need to use some kind of implicit or explicit counter in the nonce/IV, so that the stream can't have packets sent out of order which would allow tampering with the resultant plaintext via reordering, if the order is important (it probably is). You'd still have to cope with potentially dropped packets due to tampering, though.

Something similar happens in TLS when you stream a movie from youtube via TLS. You don't have to download the whole movie to see the start of it. TLS packets have an implicit counter which is used as part of the MAC code.