If you take a CBC-encrypted file and alter one bit (i.e. change a zero bit into a one, or vice versa), then, upon decryption, this will:
- jumble more or less randomly the corresponding block in the plaintext data;
- flip exactly one bit in the next block (i.e. 128 bits further);
- change nothing else whatsoever. In particular, decryption won't "fail".
See the schema on the Wikipedia page for CBC to understand why this works that way.
What you are seeing is that when you use encryption (for confidentiality), you usually also want to have checked integrity, with a MAC algorithm such as HMAC. It so happens that properly combining encryption and a MAC is tricky. Your best bet would be to use an encryption format which already does things properly. If you must, for some reason, do your own encryption, then try to use an encryption mode which inherently includes a MAC, e.g. GCM or EAX. If for technical reasons (e.g. lack of available implementation) you must still use CBC, then add some HMAC with the following rules:
- Hash your master key K (the one you "store securely") with SHA-256. Split the 256-bit result into two 128-bit halves, K1 and K2.
- Use AES-128 in CBC mode, with K1 as key, to encrypt the data. Be sure to use a random IV, generated anew for each file, with a cryptographically secure PRNG.
- Compute HMAC/SHA-256, with K2 as key, over the concatenation of the IV and the encrypted file.
- Store the file in some format which will include the IV, the HMAC output, and the encryption result. Simple concatenation would work, since the IV and HMAC output have known fixed lengths (16 bytes for the IV, 32 bytes for HMAC/SHA-256).
- When decrypting, verify the HMAC value first, and proceed with data decryption only if the HMAC value appears to be correct.
You may note that I advocate for AES-128, not AES-256. This is because a 256-bit encryption key is needless overkill and incurs a 40% speed penalty. If you still want a 256-bit encryption key, e.g. because you need to woo some clueless manager with how big your key is, then use SHA-512 to hash your master key K into a 512-bit output, which can be split into two 256-bit halves.
I also recommend HMAC/SHA-256, which should be "fast enough". A basic PC can do AES-128 and HMAC/SHA-256 combined at more than 60 megabytes per second. If you need more speed and you have a 64-bit platform, then HMAC/SHA-512 can give you an edge, but at the expense of making it harder for 32-bit systems. In any case, 100 Mbit/s network will top at about 11 megabytes per second, so encryption speed will probably not be an issue anyway.