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.