Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
Depends on the padding in question, and on how the validation routine works. But should be around 1/256 resulting in a message that has length (blocksize-1) mod blocksize. –  CodesInChaos Aug 26 '12 at 22:24
1  
Another annoying thing in this context are padding-oracles, where an attacker can figure out if a text decrypted correctly(i.e. the padding was valid) and use that to decrypt the whole message. Padding oracles are one of the reasons why MACs are strongly recommended. –  CodesInChaos Aug 26 '12 at 22:26
add comment

1 Answer 1

up vote 3 down vote accepted

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$.

share|improve this answer
    
+1 Great answer, but I still have some questions. There appears to be some sanity checks for null byte padding, does this also lead to a padding oracle attack? –  Rook Aug 31 '12 at 16:25
    
@Rook, based on what I have seen, yes. The padding oracle attack works any time one relies on some format of the decrypted message being present. If that format is not present, and that piece of information is leaked, a padding oracle is very likely. This is typically through padding, but is not limited to that. –  mikeazo Sep 5 '12 at 12:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.