Padding (cryptography)

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In cryptography, padding refers to a number of distinct practices which all include adding data to the beginning, middle, or end of a message prior to encryption. In classical cryptography, padding may include adding nonsense phrases to a message to obscure the fact that many messages end in predictable ways, e.g. sincerely yours.

Classical cryptography[edit]

Official messages often start and end in predictable ways: My dear ambassador, Weather report, Sincerely yours, etc. The primary use of padding with classical ciphers is to prevent the cryptanalyst from using that predictability to find known plaintext[1] that aids in breaking the encryption. Random length padding also prevents an attacker from knowing the exact length of the plaintext message.

A famous example of classical padding which caused a great misunderstanding is "the world wonders" incident, which nearly caused an Allied loss at the WWII Battle off Samar, part of the larger Battle of Leyte Gulf. In that example, Admiral Chester Nimitz, the Commander in Chief, U.S. Pacific Fleet in World War II, sent the following message to Admiral Bull Halsey, commander of Task Force Thirty Four (the main Allied fleet) at the Battle of Leyte Gulf, on October 25, 1944:[2]

Where is, repeat, where is Task Force Thirty Four?[3]

With padding (bolded) and metadata added, the message became:


Halsey's radio operator mistook some of the padding for the message, so Admiral Halsey ended up reading the following message:

Where is, repeat, where is Task Force Thirty Four? The world wonders[3]

Admiral Halsey interpreted the padding phrase "the world wonders" as a sarcastic reprimand, causing him to have an emotional outburst and then lock himself in his bridge and sulk for an hour before moving his forces to assist at the Battle off Samar.[2] Halsey's radio operator should have been tipped off by the letters RR that "the world wonders" was padding; all other radio operators who received Admiral Nimitz's message correctly removed both padding phrases.[2]

Many classical ciphers arrange the plaintext into particular patterns (e.g., squares, rectangles, etc.) and if the plaintext doesn't exactly fit, it is often necessary to supply additional letters to fill out the pattern. Using nonsense letters for this purpose has a side benefit of making some kinds of cryptanalysis more difficult.

Symmetric cryptography[edit]

Hash functions[edit]

Most modern cryptographic hash functions process messages in fixed-length blocks; all but the earliest hash functions include some sort of padding scheme. It is critical for cryptographic hash functions to employ termination schemes that prevent a hash from being vulnerable to length extension attacks.

Many padding schemes are based on appending predictable data to the final block. For example, the pad could be derived from the total length of the message. This kind of padding scheme is commonly applied to hash algorithms that use the Merkle–Damgård construction.

Block cipher mode of operation[edit]

Electronic codebook and cipher-block chaining (CBC) mode are examples of block cipher mode of operation. Block cipher modes for symmetric-key encryption algorithms require plain text input that is a multiple of the block size, so messages may have to be padded to bring them to this length.

There is currently[when?] a shift to use streaming mode of operation instead of block mode of operation.[citation needed] An example of streaming mode encryption is the counter mode of operation.[4] Streaming modes of operation can encrypt and decrypt messages of any size and therefore do not require padding. More intricate ways of ending a message such as ciphertext stealing or residual block termination avoid the need for padding.

A disadvantage of padding is that it makes the plain text of the message susceptible to padding oracle attacks. Padding oracle attacks allow the attacker to gain knowledge of the plain text without attacking the block cipher primitive itself. Padding oracle attacks can be avoided by making sure that an attacker cannot gain knowledge about the removal of the padding bytes. This can be accomplished by verifying a message authentication code (MAC) or digital signature before removal of the padding bytes, or by switching to a streaming mode of operation.

Bit padding[edit]

Bit padding can be applied to messages of any size.

A single set ('1') bit is added to the message and then as many reset ('0') bits as required (possibly none) are added. The number of reset ('0') bits added will depend on the block boundary to which the message needs to be extended. In bit terms this is "1000 ... 0000".

This method can be used to pad messages which are any number of bits long, not necessarily a whole number of bytes long. For example, a message of 23 bits that is padded with 9 bits in order to fill a 32-bit block:

... | 1011 1001 1101 0100 0010 0111 0000 0000 |

This padding is the first step of a two-step padding scheme used in many hash functions including MD5 and SHA. In this context, it is specified by RFC1321 step 3.1.

This padding scheme is defined by ISO/IEC 9797-1 as Padding Method 2.

Byte padding[edit]

Byte padding can be applied to messages that can be encoded as an integral number of bytes.

ANSI X9.23[edit]

In ANSI X9.23, between 1 and 8 bytes are always added as padding. The block is padded with random bytes (although many implementations use 00) and the last byte of the block is set to the number of bytes added.[5]

Example: In the following example the block size is 8 bytes, and padding is required for 4 bytes (in hexadecimal format)

... | DD DD DD DD DD DD DD DD | DD DD DD DD 00 00 00 04 |
ISO 10126[edit]

ISO 10126 (withdrawn, 2007[6][7]) specifies that the padding should be done at the end of that last block with random bytes, and the padding boundary should be specified by the last byte.

Example: In the following example the block size is 8 bytes and padding is required for 4 bytes

... | DD DD DD DD DD DD DD DD | DD DD DD DD 81 A6 23 04 |
PKCS#5 and PKCS#7[edit]

PKCS#7 is described in RFC 5652.

Padding is in whole bytes. The value of each added byte is the number of bytes that are added, i.e. N bytes, each of value N are added. The number of bytes added will depend on the block boundary to which the message needs to be extended.

The padding will be one of:

02 02
03 03 03
04 04 04 04
05 05 05 05 05
06 06 06 06 06 06

This padding method (as well as the previous two) is well-defined if and only if N is less than 256.

Example: In the following example the block size is 8 bytes and padding is required for 4 bytes

... | DD DD DD DD DD DD DD DD | DD DD DD DD 04 04 04 04 |

If the length of the original data is an integer multiple of the block size B, then an extra block of bytes with value B is added. This is necessary so the deciphering algorithm can determine with certainty whether the last byte of the last block is a pad byte indicating the number of padding bytes added or part of the plaintext message. Consider a plaintext message that is an integer multiple of B bytes with the last byte of plaintext being 01. With no additional information, the deciphering algorithm will not be able to determine whether the last byte is a plaintext byte or a pad byte. However, by adding B bytes each of value B after the 01 plaintext byte, the deciphering algorithm can always treat the last byte as a pad byte and strip the appropriate number of pad bytes off the end of the ciphertext; said number of bytes to be stripped based on the value of the last byte.

PKCS#5 padding is identical to PKCS#7 padding, except that it has only been defined for block ciphers that use a 64-bit (8-byte) block size. In practice the two can be used interchangeably.

ISO/IEC 7816-4[edit]

ISO/IEC 7816-4:2005[8] is identical to the bit padding scheme, applied to a plain text of N bytes. This means in practice that the first byte is a mandatory byte valued '80' (Hexadecimal) followed, if needed, by 0 to N-1 bytes set to '00', until the end of the block is reached. ISO/IEC 7816-4 itself is a communication standard for smart cards containing a file system, and in itself does not contain any cryptographic specifications.

Example: In the following example the block size is 8 bytes and padding is required for 4 bytes

... | DD DD DD DD DD DD DD DD | DD DD DD DD 80 00 00 00 |

The next example shows a padding of just one byte


Zero padding[edit]

All the bytes that are required to be padded are padded with zero. The zero padding scheme has not been standardized for encryption,[citation needed] although it is specified for hashes and MACs as Padding Method 1 in ISO/IEC 10118-1[9] and ISO/IEC 9797-1.[10]

Example: In the following example the block size is 8 bytes and padding is required for 4 bytes

... | DD DD DD DD DD DD DD DD | DD DD DD DD 00 00 00 00 |

Zero padding may not be reversible if the original file ends with one or more zero bytes, making it impossible to distinguish between plaintext data bytes and padding bytes. It may be used when the length of the message can be derived out-of-band. It is often applied to binary encoded strings as the null character can usually be stripped off as whitespace.

Zero padding is sometimes also referred to as "null padding" or "zero byte padding". Some implementations may add an additional block of zero bytes if the plaintext is already divisible by the block size.[citation needed]

Public key cryptography[edit]

In public key cryptography, padding is the process of preparing a message for encryption or signing using a specification or scheme such as PKCS#1 v1.5, OAEP, PSS, PSSR, IEEE P1363 EMSA2 and EMSA5. A modern form of padding for asymmetric primitives is OAEP applied to the RSA algorithm, when it is used to encrypt a limited number of bytes.

The operation is referred to as "padding" because originally, random material was simply appended to the message to make it long enough for the primitive. This form of padding is not secure and is therefore no longer applied. A modern padding scheme aims to ensure that the attacker cannot manipulate the plaintext to exploit the mathematical structure of the primitive and will usually be accompanied by a proof, often in the random oracle model, that breaking the padding scheme is as hard as solving the hard problem underlying the primitive.

Traffic analysis[edit]

Even if perfect cryptographic routines are used, the attacker can gain knowledge of the amount of traffic that was generated. The attacker might not know what Alice and Bob were talking about, but can know that they were talking and how much they talked. In certain circumstances this can be very bad. Consider for example when a military is organising a secret attack against another nation: it may suffice to alert the other nation for them to know merely that there is a lot of secret activity going on.

As another example, when encrypting Voice Over IP streams that use variable bit rate encoding, the number of bits per unit of time is not obscured, and this can be exploited to guess spoken phrases.[11]

Padding messages makes traffic analysis much harder. Normally, a number of random bits are appended to the end of the message with an indication at the end how much this random data is. The randomness should have a minimum value of 0, a maximum number of N and an even distribution between the two extremes. Note that increasing 0 does not help, only increasing N helps, though that also means that a lower percentage of the channel will be used to transmit real data. Also note that, since the cryptographic routine is assumed to be uncrackable (otherwise the padding length itself is crackable), it does not help to put the padding anywhere else, e.g. at the beginning, in the middle, or in a sporadic manner. For the same reason, padding can be structured (e.g. it can simply be a set of zeros) – though structured padding can be hazard, as explained in timing attack.

See also[edit]


  1. ^ Gordon Welchman, The Hut Six Story: Breaking the Enigma Codes, p. 78.
  2. ^ a b c Willmott, H. P. (19 August 2005). "The Great Day of Wrath: 25 October 1944". The Battle of Leyte Gulf: The Last Fleet Action. Indiana University Press. ISBN 9780253003515.
  3. ^ a b c Tuohy, William (2007). America's Fighting Admirals: Winning the War at Sea in World War II. MBI Publishing Company. ISBN 9780760329856.
  4. ^, pg 17
  5. ^ "ANSI X9.23 cipher block chaining". IBM Knowledge Center. IBM. Retrieved 31 December 2018.
  6. ^ ISO catalog, ISO 10126-1:1991
  7. ^ ISO catalog, ISO 10126-2:1991
  8. ^ ISO catalog, ISO/IEC 7816-4:2005
  9. ^ ISO/IEC 10118-1:2000 Information technology – Security techniques – Hash-functions – Part 1: General
  10. ^ ISO/IEC 9797-1:1999 Information technology – Security techniques – Message Authentication Codes (MACs) – Part 1: Mechanisms using a block cipher
  11. ^ Wright, Charles V.; Ballard, Lucas; Coull, Scott E.; Monrose, Fabian; Masson, Gerald M. (1 December 2010). "Uncovering Spoken Phrases in Encrypted Voice over IP Conversations". ACM Transactions on Information and System Security (TISSEC). 13 (4): 35. CiteSeerX doi:10.1145/1880022.1880029 – via

Further reading[edit]