Distinguishing the correct IV from incorrect IV in AES CBC when key is known

Currently, I'm using a static IV value for all encryption and decryption but I would like it to be dynamic for each encyption/decryption request so I started using new byte[16] and it works. The problem is how to detect and decrypt old data. Below is my code to decrypt and I'm passing static IV stored on a secret in keyvault.

private static byte[] DecryptFromBytes_Aes(byte[] dataBytes, byte[] key, byte[] iV)
    {
        if (dataBytes == null || dataBytes.Length <= 0)
            throw new ArgumentNullException("DataBytes");
        if (key == null || key.Length <= 0)
            throw new ArgumentNullException("key");
        if (iV == null || iV.Length <= 0)
            throw new ArgumentNullException("iV");

        byte[] result = null;
        using (AesCryptoServiceProvider aesAlg = new AesCryptoServiceProvider())
        {
            aesAlg.Key = key;
            aesAlg.IV = iV;
            aesAlg.Padding = PaddingMode.PKCS7;
            ICryptoTransform decryptor = aesAlg.CreateDecryptor(aesAlg.Key, aesAlg.IV);
            using (MemoryStream memoryStream = new MemoryStream(dataBytes))
            {
                using (CryptoStream cryptoStream = new CryptoStream(memoryStream, decryptor, CryptoStreamMode.Read))
                {
                    byte[] decryptedBytes = new byte[dataBytes.Length];
                    int read = cryptoStream.Read(decryptedBytes, 0, dataBytes.Length);
                    Array.Resize(ref decryptedBytes, read);
                    result = decryptedBytes;
                }
            }

        }

        return result;
    }

Problem is how to detect and decrypt old data. Below is my code to decrypt and I'm passing static IV stored on a secret in keyvault.

The answer relies on the padding and the correctness of the key.

• Case: If the key is correct and IV not;

  Remember that CBC decryption executed as \begin{align} P_1 =& Dec_k(C_1) \oplus IV\\ P_i =& Dec_k(C_i) \oplus C_{i-1},\;\; 1 < i \leq nb, \end{align}

  Therefore if the IV is not correct, then the first block $P_1$ is not correct. We can consider this similar to bit-flipping attack in the first block. Next blocks $P_i$ will decrypt correctly since they rely on the correctness of $C_i$ and $C_{i-1}$ and in this case, they are correct. Only your first block will be incorrect. Distinguishing this can be hard and you need to prepare some filter to distinguish it from the properties of the plaintext - language or format. Comparing the two cases is needed; is it static IV or random IV. Whichever passes your filter can be the correct case and this really depends on your data.

  If the first block of the plaintext is pure text and contains only characters from ASCII's first part ( i.e. the int value of char < 128 ) then this is a good distinguisher. Just check that each 16 byte < 128.

  Migrate all your files into a unique format as soon as possible.

• Case: If the key is not correct then you will get a PKCS#7 padding error with a high probability.

  The padding bytes will be one of the following at the end of the plaintext depending on the size of the plaintext. With padding, the size needs to be a minimum multiple of the size of the block of AES, which has a 16-byte block size.

    missing  1 byte - padding bytes : 01
    missing  2 byte - padding bytes : 02 02
    missing  3 byte - padding bytes : 03 03 03
    missing  4 byte - padding bytes : 04 04 04 04
    missing  5 byte - padding bytes : 05 05 05 05 05
    missing  6 byte - padding bytes : 06 06 06 06 06 06
    ...
    full block      - padding bytes : 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 
    Even if the plaintext is a multiple of 128, a full block is needed so that padding is not ambigious.
  

  Check that the padding is correct.

  If not correct, you can be sure that the IV is not correct. If correct, there is a $1/256$ probability that the IV generates a random valid 01 padding, with $1/(256)^2$ probability 0202 valid padding, and so on. To remove this possibility, you need to check the data. The language or any other format about the plaintext may help you to eliminate the false positives.

You cannot reliably check if the data has a random prefixed or not. For the same key, the data will even generally not fail unpadding. So what you need to do is to use a different protocol.

For instance, you can have a 16 byte fully random magic in front of the newly encrypted files (generated once, of course), then a version number and other data including a random IV, the ciphertext and a HMAC over the header and data including the IV. That way you can detect that the right encryption is used (as generating that magic by accident has got a probability of 1 in $2^{128}$) by simply doing a compare. You've also protected your file for integrity and authenticity using the HMAC (this is optional, and not strictly required for confidentiality - but it comes highly recommended).

So that would be:

 MAGIC (16 bytes) | VERSION | IV (16 bytes) | CIPHERTEXT | TAG

Where TAG is the authentication tag produced using HMAC over everything before.

Of course, there have been many people that have written protocols like these already as well, so you may want to look into container formats such as CMS (which usually depends on public key encryption / certificates) or even NaCL.