Checksum for bailing early on first corrupt byte in stream?

Question

Suppose you want to transmit bytes of a file from computer a to b, but you want to bail early if any of the bytes are wrong.

It’s easy to prescribe a hash/checksum implementation for the entire file. For example, sha-256 is probably sufficient and only requires 256 extra bits to be transmitted, and for any file of significant size, 256 extra bits are negligible.

But if you want checks at multiple points during the transfer, so you can bail early, I assume the cost of transmitting hashes grows as the interval of checking approaches checking every single byte... unless I am missing something clever, I think that it becomes hard to justify.

Do you know how others have dealt with this issue or have any advice? Maybe there is no clever way around it and you must just choose a reasonable compromise, like one hash per every megabyte?

(My application is that I want to build a small/safe virtual machine + language that implements arbitrary compression/decompression algorithms to produce files. For decompression, I would like the machine to halt early if any unexpected bytes are emitted. )

Answer 1

..how others have dealt with (bailing early if any of the deciphered bytes are wrong)

A relatively common practice with this side effect is to restrict bytes in the plaintext to a certain discrete subset (e.g. Base64 characters, or those with an odd number of bits set) and stop at the first decoded byte that does not belong to this subset. Don't do this, for two reasons:

• If the adversary can detect when the receiver aborts (which is common and should be the default assumption), it often opens to padding oracle attacks which compromise message secrecy.
• It is not secure against adversarial modifications, to a degree varying with the cipher. The worst case is stream ciphers, including CTR and OFB, where the ciphertext can be trivially altered to escape this detection method, often even if the original plaintext is not known. It does not work well either in most other modes, especially when some plaintext is known.

Any advice?

There is a compromise between immediately detecting individual byte corruption and lost bandwidth. By a counting argument, for residual probability $\epsilon$ of not immediately detecting corruption over $n$ bits, we need to sacrifice $\log_2(1/\epsilon)$ bits for each $n$ bits. The only way to keep the relative overhead $1/(n/\log_2(1/\epsilon)+1)$ low with low residual odds of not immediately detecting an alteration is to increase the block size $n$ to more than a byte.

TLS has the functionality of authenticating individual enciphered blocks, and I'm confident that whatever it does in its modern ciphersuites is fine, and could be reused with some care. But I do not know what method(s) it uses.

A recommendable method is to use multiple independent blocks of information each individually enciphered and authenticated with an authenticated encryption mode, with some measure to prevent substitution of blocks. The simplest is numbering them using an explicit incremental block number. But we want to minimize lost bandwidth:

• The block numbers can come for free: we include them in the authenticated payload, but neither encipher nor transmit them. AES-GCM supports that.
• The IVs/Nonce of the authenticated mode can come for free: they can be derived from a CSPRNG seeded with an extra key (with perhaps that key and the encryption key derived from the main key).

We might additionally want to use a short authentication tag for intermediary blocks in order to conserve bandwidth, but maximize odds that a previous alteration that went undetected because of that is detected later. I know no standard method, but it is possible to improvise one if computational efficiency is not an issue: we can include a MAC (made with an independent key, e.g. derived) of the previous block (including its authenticated data) in the next block's authenticated and implicit data. Further, we can use a hash rather than a MAC if the authenticated encryption is such that passing it's integrity test does not compromise the confidentiality of authenticated data when that's implicit (which is the case at least if that integrity is checked using a MAC).

If we use a large authentication tag for the last block only, there must be some safe way to recognize that block, and that's not to be taken lightly. A safe method is to make it of a recognizable length and use a different derived key for that block.