Editing Padding (cryptography) (section)

===Deterministic padding===

A deterministic padding scheme always pads a message payload of a given length to form an encrypted message of a particular corresponding output length.  When many payload lengths map to the same padded output length, an eavesdropper cannot distinguish or learn any information about the payload's true length within one of these length ''buckets'', even after many observations of the identical-length messages being transmitted.  In this respect, deterministic padding schemes have the advantage of not leaking any additional information with each successive message of the same payload size.

On the other hand, suppose an eavesdropper can benefit from learning about ''small'' variations in payload size, such as plus or minus just one byte in a password-guessing attack for example.  If the message sender is unlucky enough to send many messages whose payload lengths vary by only one byte, and that length is exactly on the border between two of the deterministic padding classes, then these plus-or-minus one payload lengths will consistently yield different padded lengths as well (plus-or-minus one block for example), leaking exactly the fine-grained information the attacker desires.  Against such risks, randomized padding can offer more protection by independently obscuring the least-significant bits of message lengths.

Common deterministic padding methods include padding to a constant block size and padding to the next-larger power of two.  Like randomized padding with a small maximum amount&nbsp;''M'', however, padding deterministically to a block size much smaller than the message payload obscures only the least-significant bits of the messages true length, leaving the messages's true approximate length largely unprotected.  Padding messages to a power of two (or any other fixed base) reduces the maximum amount of [[Entropy (information theory)|information]] that the message can leak via its length from {{math|''O''(log ''M'')}} to {{math|''O''(log log ''M'')}}.  Padding to a power of two increases message size overhead by up to 100%, however, and padding to powers of larger integer bases increase maximum overhead further.

The PADMÉ scheme, proposed for [[PURB (cryptography)|padded uniform random blobs or PURBs]], deterministically pads messages to lengths representable as a [[IEEE 754|floating point number]] whose mantissa is no longer (i.e., contains no more significant bits) than its exponent.<ref name="pets19" />  This length constraint ensures that a message leaks at most {{math|''O''(log log ''M'')}} bits of information via its length, like padding to a power of two, but incurs much less overhead of at most 12% for tiny messages and decreasing gradually with message size.