[Cryptography] Low grade randomness for padding.

[Jerry Leichter]

> I generally agree that zeroes are a good padding, but there is one situation where they might not be the best choice. That is, if the secret needs to be kept for a long time, long enough that an exhaustive search attack on AES become feasible, then searching for a key which gives zero (or any other known plaintext) padding makes the attack easier.
Realistically ... if you're really at the level of exhaustive search against a 128-bit key, probable-plaintext attacks are a small level of extra effort.  And what's being encrypted can't all be random.  (Well, if could be a random key used elsewhere - but then you simply try the value elsewhere.)  A classic example is that if you're attacking ASCII text, the chance of a randomly-decrypted block having the top bits of all 8 bytes set to 0 is 1/256, so you can very quickly reject 255/256 trial keys.

I made a back-of-the-envelope computation on this list a number of years back that showed a physical limit on exhaustive search, based on a bound one can get on the number of bit flips that physics allows in a given volume of space-time.  As it turned out, in principle, you could just barely do 128 bit exhaustive search in 100 years (hence in a sphere 100-light years in radius - which is actually a big overestimate as your answer could appear somewhere out on the surface of the 200-ly-across sphere, and getting it back to where you started the computation would take another 100 years).  However, 256 bits cannot be reached even in principle.  The argument is actually based on quantum mechanics, so a quantum computer doesn't help.

So I'm not sure we really need to be concerned about exhaustive search any more....

                                                        -- Jerry