AES storing the length within the encrypted data versus storing it outside

Question

I need to strip off padding after decrypting AES(CBC)-encrypted data (I have control over encryption and data transmission), so have looked at adding the length of the original data to the payload being transmitted.

Option 1: [ IV | Length | Encrypt(original data) ]

Option 2: [ IV | Encrypt([ Length | original data ]) ]

Where: "Length" is the 4-byte length of the original data

Would either of these approaches compromise the security of the message?

My concern with Option 1 is that you're giving away information for free: is there a way in which a potential attacker might be able to utilize the length of the data in attempting to compromise the message?

My concern with Option 2 is that a potential attacker (after determining by decompiling source code that the first 4 bytes indicate length) might try a brute-force approach, only needing to go through a much smaller part of the data for each potential key to determine if the message for that particular key is valid; i.e. that he only has to try one block or only the first 4 bytes of the message until he ends up with a block for which the first 4 bytes are relatively close to the size of the payload (hence effectively reducing the amount of time it would take to determine the message's key)

Are any of the aforementioned concerns valid?

What are the best-practices to store the message length / strip away padding?

Answer 1

First, the advice:

What are the best-practices to store the message length / strip away padding?

1. Use standard padding, like PKCS#7 padding. It handles finding the length uniquely for you.

2. Use encrypt-then-MAC to prevent padding oracle attacks.

(Or better yet, don't use CBC. Use an authenticated encryption mode like GCM, or use CTR+MAC which doesn't require padding.)

---

My concern with Option 1 is that you're giving away information for free: is there a way in which a potential attacker might be able to utilize the length of the data in attempting to compromise the message?

Maybe not, since the length in number of blocks is known anyway. However, in some cases it would be a problem, like if the attacker was expecting either 'no' or 'yes' as the message. It depends on your messages. You likely shouldn't rely on it remaining secret, though.

My concern with Option 2 is that a potential attacker (after determining by decompiling source code that the first 4 bytes indicate length) might try a brute-force approach, only needing to go through a much smaller part of the data for each potential key to determine if the message for that particular key is valid; i.e. that he only has to try one block or only the first 4 bytes of the message until he ends up with a block for which the first 4 bytes are relatively close to the size of the payload (hence effectively reducing the amount of time it would take to determine the message's key)

This one is not a valid concern. AES has 128+ bit keys so a brute force attack is impossible. Whether they have to test one or several blocks for each key does not matter. Even if AES was broken somehow, such a small factor shouldn't matter, and the attacker could likely guess some other details about the message instead to gain a similar advantage (like all-ASCII for a certain part of it).