In cryptography, padding is any of a number of distinct practices, all of which 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 such as sincerely yours.
Classical cryptography 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 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 that caused a great misunderstanding is "the world wonders" incident, which nearly caused an Allied loss at the Battle off Samar, part of the larger Battle of Leyte Gulf, during World War II. In that example, Admiral Chester Nimitz, the Commander in Chief, U.S. Pacific Fleet during the war, sent the following message to Admiral William Halsey, the commander of Task Force Thirty Four (the main Allied fleet) at the Battle of Leyte Gulf, on October 25, 1944:
Where is, repeat, where is Task Force Thirty Four? With padding (bolded) and metadata added, the message became:
TURKEY TROTS TO WATER GG FROM CINCPAC ACTION COM THIRD FLEET INFO COMINCH CTF SEVENTY-SEVEN X WHERE IS RPT WHERE IS TASK FORCE THIRTY FOUR RR THE WORLD WONDERS Halsey's radio operator mistook some of the padding for the message and so Halsey ended up reading the following message:
Where is, repeat, where is Task Force Thirty Four? The world wonders Halsey interpreted the padding phrase "the world wonders" as a sarcastic reprimand, which caused him to have an emotional outburst and then to lock himself in his bridge and sulk for an hour before he moved his forces to assist at the Battle off Samar. His radio operator should have been tipped off by the letters RR that "the world wonders" was padding; all of the other radio operators who received Nimitz's message had correctly removed both padding phrases. Many classical ciphers arrange the plaintext into particular patterns (squares, rectangles, etc.), and if the plaintext does not exactly fit, supplying additional letters is often necessary to fill out the pattern. Using nonsense letters for that purpose has the side benefit of making some kinds of cryptanalysis more difficult. Such padding is not used in modern cryptography because modern ciphers are designed to be secure even when the cryptanalyst chooses the message to encrypt.
Symmetric cryptography
Hash functions 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 such as MD-5, SHA-1, and SHA-2 family such as SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224, and SHA-512/256
Block cipher mode of operation Cipher-block chaining (CBC) mode is an example of block cipher mode of operation. Some block cipher modes (CBC and PCBC essentially) for symmetric-key encryption algorithms require plain text input that is a multiple of the block size and so messages may have to be padded to bring them to that length.
There is currently a shift to use streaming mode of operation instead of block mode of operation. An example of streaming mode encryption is the counter mode of operation. 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, which 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. That 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 Bit padding can be applied to messages of any size. A single '1' bit is added to the message, and as many '0' bits as required (possibly none) are then added. The number of '0' bits added will depend on the block boundary to which the message needs to be extended. That is in bit terms "1000 ... 0000." The method can be used to pad messages that are long by any number of bits long, not necessarily a whole number of bytes. For example, this message of 23 bits is padded with 9 bits in order to fill a 32-bit block:
... | 1011 1001 1101 0100 0010 0111 0000 0000 |
The 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 Byte padding can be applied to messages that can be encoded as an integral number of bytes.
ANSI X9.23 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. 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 ISO 10126 (withdrawn in 2007) 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 |
… excerpt ends here. Continue reading the full article.
