Vulnerabilities of encrypting data with known regularities

Question

I need to encrypt data that has a pre-defined header and footer structure, and furthermore the data follows pre-defined patterns. The header and footer structure follow a defined structure but cannot be left out because they are never truly equal. An example of this kind of data is an html file: it will in most cases start with a doctype declaration (which has a pre-defined form) and html opening tag. The file ends with the html closing tag, and even though the data in between tags can be arbitrary, the tags are fixed structures as well. This is like a known-plaintext attack.

Suppose an attacker were to do a brute-force attack, then he could easily verify that a key is wrong after decrypting only a few bytes. My question is: is this a vulnerability? I presume that when the key size is large enough, it is not, but consider the case for a small enough key where the amount of work required could make a significant difference. Ideally, it should only be possible to check whether the decrypted data is correct after all data has been decrypted. (I assume that it requires much more work to process large amounts of data, similar to PBKDF using many iterations to make trying many words infeasable; is this correct?) Could the information that plaintext must follow a pattern be of any use to an attacker?

If it is a vulnerability, how would one resolve the issue? In other words, is it possible to encrypt data with many regularities in such a way that these regularities only become apparent after decrypting all the data?

My question applies to encryption algorithms in general, but I intend to use AES with a 256-bit key.

Answer 1

Typically the cost of brute force so greatly out weighs the cost of decrypting a single block, that the fact that an adversary can check for proper decryption after decrypting a single block is not a serious concern. Otherwise protocols like SSL would not be secure.

That said, as you point out, this relates to the key space. If the key space is too small, then decrypting the first block with every possible key would be feasible for an adversary. If you could make it necessary to decrypt every block in order to get the plaintext, that would slow down an adversary. But, with the speeds we see in encryption algorithms, you'd have to encrypt terrabytes for this to matter. For example, the throughput of AES running on a GPU was shown to be around 35,000 Mbps. That number will only continue to rise. The point is to use a cipher that supports a large enough key space and choose keys randomly from the entire space.

If you still feel this is a problem though, why not do the following $E^{ofb}_{k_1}(E^{cbc}_{k_2}(P)||k_2)$ where $||$ is concatenation and $P=p_1\cdots p_n$ (i.e., a number of blocks of plaintext). The use of OFB on the outside ensures that the entire ciphertext must be decrypted to get the last block ($k_2$), which is then used to get $P$.