How is block cipher padding verified for consistancy?

Question

Under what circumstances is a decryption routine able to tell that the padding of a message is invalid? If a cipher text block where to be randomly modified, what is the probability that the padding would be correct? How does the type of padding influence the detectability of cipher text that has been tampered with?

Answer 1

Let's say we are using PKCS#7 padding, and we'll stick to a single block message for simplicity. Modifying the ciphertext should result in an completely random decryption. To get proper padding, the resulting decryption would have to look something like this (RANDOM DATA)01 or (RANDOM DATA)0202, and so on.

Since the result is random, the probability that you would get (RANDOM DATA)01 is $1/256\approx 0.004$, the probability that you would get (RANDOM DATA)0202 is $(1/256)^2$, and so on. The sum of these is the probability $\displaystyle\sum_{n=1}^{16} (1/256)^n\approx 0.004$ (notice that all cases except padding of 01 are of negligible probability).

Looking at this padding method, it is easy to see how one would detect a modified ciphertext by simply looking at the padding. If the resulting plaintext is something like (RANDOM DATA)(SOMETHING OTHER THAN 02)02, the padding is not correct. Using this as a message authentication attack and reporting the result to the user (either directly or indirectly) would result in a padding oracle attack, which would be very devastating.

Other padding methods, for example, will have different probabilities. For example, ISO 10126 uses random padding with the last byte used to tell how much padding was used. If the block size is 16 bytes, a last byte of 01 through 0f would be valid. Thus the probability would be $16/256=0.0625$.