I figure that filling up all the padded bytes with random nonsense and the last byte with the number of padded bytes would be far more secure. Why isn't that the case in such a widely distributed padding standard? Isn't the example below more secure?
53 65 63 72 65 74 20 74 65 78 74 2e --> 53 65 63 72 65 74 20 74 65 78 74 2e 5a 2c 12 04
This is basically known as ISO 10126 padding, compatible with ANSI X9.23 padding.
First of all, it should be noted that padding oracle attacks are only part of a wider set of plaintext oracle attacks. So if the decrypted plaintext can generate any error, the same issues can be present when the system is trying to apply the plaintext. For instance, it's very easy to create a plaintext oracle attack using errors of an XML decoder. Even easier: if the plaintext blocks consists of padding from the left hand side, then obviously it would also fail to a padding oracle attack.
Secondly a ciphertext will now be accepted (i.e. not generate a padding error) 1 time out of 256 / 8 = 32 times (final byte is valued 01 to 08) instead of about once in 256 times (final byte is valued 01 or the final bytes are valued 02 02 etc.). This precludes using the padding for message integrity / authenticity.
Thirdly you've mitigated the padding oracle attack, but you haven't entirely eliminated it. The final byte will still needs to be evaluated after all. We consider a cipher broken if anything can be learned from the original plaintext.
Finally you haven't eliminated the padding overhead.
If you assume overhead anyway then you might as well add an authentication tag, created by using a MAC or authenticated cipher. This is the reason why we're not very interested in the padding properties. We can use a mode that doesn't require padding, add the authentication tag and have a cipher mode with better security properties, while keeping message expansion limited.
