padding (cryptography)

In cryptography, padding is the practice of adding material of varying length to the plaintext of messages. The padding is supposed to be discarded before the plaintext is delivered to the recipient. Historically, padding was used to make cryptanalysis more difficult. It has been practiced for many hundreds of years, but is now used for more technical reasons with block ciphers, cryptographic hashes and public key cryptography.

Past uses

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 it to prevent the cryptanalyst from using that predictability to find cribs that aid in breaking the encryption. Random length padding also prevents an atttacker from knowing the exact length of the plaintext message. 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 .

Modern usage

When using block ciphers, plaintext data is handled one block at a time; typical block sizes are 64 bits (as in DES) and 128 bits (AES). Plaintext data rarely exactly fills the last block, so padding is required. One method is to fill out the last block with a 1 bit followed by zero bits. If the input happens to fill up an entire block, another block is added to accommodate the padding; otherwise, the end of the input plaintext might be misinterpreted as padding. Ciphertext stealing is an alternative. Likewise, the inner workings of cryptographic hash functions process input in blocks and thus require padding. Public key cryptosystems like RSA usually treat plaintext as a single large number in a formula. Such numbers often have to have certain mathematical properties to avoid compromising the security of the cryptosystem, such as being even, lying within a certain range of numbers, or not being greater than 1. Standard padding schemes such as PKCS ensure that all possible plaintexts can be turned into appropriate numbers for encryption. A sort of padding more akin to its historical uses has been suggested by Ronald Rivest to entirely conceal the existence of a message within a larger data sequence. His term is 'chaffing and winnowing'. It is a form of steganography. Padding can also be used to prevent certain stream cipher attacks and deny an adversary knowledge of the plaintext length (by varying the amount of padding used).

A famous example

At the Battle of Leyte Gulf in WWII, the Japanese Navy planned to attack the landings, but wished to do so only after drawing away the US Navy's covering (aircraft carrier) Task Force 34. They managed to attract Admiral Halsey's attention (by dangling most of their remaining large ships, including carriers, as bait), and he went after them. The remaining Japanese forces carried out several attacks on the landing operation off Samar, and an encrypted message was radioed to Halsey from Admiral Nimitz (the Pacific Fleet Commander). The message itself included both initial and trailing padding. The radioman who did the encryption added the padding from an approved list, just as he had been trained to do. It was not excised by the receiving operator who was not completely certain it was't part of the message. The padding -- added to the end of the plaintext Where is repeat where is Task Force 34? before encryption -- was, 'the world wonders'. Halsey did not appreciate the (unintended) editorial comment on his decision to attempt to sink most of what was left of the Japanese Navy.