# Vulnerabilities of encrypting data with known regularities

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.

-
No, known in plaintext is a standard assumption and does not lead to a vulnerability for a modern, properly keyed algorithm. –  fgrieu Jul 2 '12 at 18:49
I found an interesting paper I thought you might like to see, cs.au.dk/~stm/local-cache/fusion.pdf –  mikeazo Jul 8 '12 at 15:46

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$.
Just to be pedantic, decrypting the last block with OFB mode doesn't require decrypting the entire ciphertext, just generating the entire keystream. All you need to do that are $k_1$ and the IV. –  Ilmari Karonen Jul 3 '12 at 11:46
@IlmariKaronen, true. Granted, generating the key stream is the majority of the work load anyhow. Still a good point. But to get $P$ you would have to do the entire OFB decryption. Then do 1 block of the CBC decryption. –  mikeazo Jul 3 '12 at 12:40