In
cryptographyCryptography is the practice and study of hiding information. Modern cryptography intersects the disciplines of mathematics, computer science, and engineering...
,
padding refers to a number of distinct practices.
Official messages often start and end in predictable ways:
My dear ambassador, Weather report, Sincerely yours, etc. The primary use of padding with
classical cipherA cipher is a means of concealing a message, where letters of the message are substituted or transposed for other letters, letter pairs, and sometimes for many letters. In cryptography, a classical cipher is a type of cipher that was used historically but now has fallen, for the most part, into...
s is to prevent the cryptanalyst from using that predictability to find
cribCrib, in cryptanalysis, is a known or suspected plaintext. The term originated at Bletchley Park, the British World War II decryption operation...
s that aid in breaking the encryption. Random length padding also prevents an attacker 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.
In
cryptographyCryptography is the practice and study of hiding information. Modern cryptography intersects the disciplines of mathematics, computer science, and engineering...
,
padding refers to a number of distinct practices.
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 cipherA cipher is a means of concealing a message, where letters of the message are substituted or transposed for other letters, letter pairs, and sometimes for many letters. In cryptography, a classical cipher is a type of cipher that was used historically but now has fallen, for the most part, into...
s is to prevent the cryptanalyst from using that predictability to find
cribCrib, in cryptanalysis, is a known or suspected plaintext. The term originated at Bletchley Park, the British World War II decryption operation...
s that aid in breaking the encryption. Random length padding also prevents an attacker 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.
A famous example of classical padding which caused a great misunderstanding is "
the world wonders"The world wonders" was security padding added by a radioman to a US Navy message from Admiral Chester Nimitz to Admiral William Halsey, Jr. on October 25, 1944 during the Battle of Leyte Gulf...
".
Hash functions
All modern
cryptographic hash functionA cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
s process messages in fixed-length blocks. Padding is appended to the final block in a predictable way that includes the total length of the message; this padding ensures that the final block is the right length, and is a key part of the security proof for this way of building hash functions, which is known as the Merkle-Damgård construction.
CBC mode
Cipher-block chaining (CBC) mode is a popular block cipher mode of operation. It requires messages whose length is a multiple of the block size (typically 8 or 16 bytes), so messages have to be padded to bring them to this length. 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. Another method is to append n bytes with value (n−1) to the end of the plaintext to fill out a complete block. If the message already exactly fills a block, then for the same reasons as before, a full block of padding block is added. This means the padding is either one byte of 0, or two bytes of 1 etc.
More intricate ways of ending a message such as
ciphertext stealingIn cryptography, ciphertext stealing is a general method of using a block cipher mode of operation that allows for processing of messages that are not evenly divisible into blocks without resulting in any expansion of the ciphertext, at the cost of slightly increased complexity.-General...
or
residual block terminationIn cryptography, residual block termination is a variation of cipher block chaining mode that does not require any padding. It does this by effectively changing to cipher feedback mode for one block...
avoid the need for such padding. However, today, CTR mode is largely replacing CBC mode, and CTR mode doesn't need padding at all.
There are
timing attackIn cryptography, a timing attack is a side channel attack in which the attacker attempts to compromise a cryptosystem by analyzing the time taken to execute cryptographic algorithms...
s based on structured CBC padding.
Bit padding
This is described in
RFC1321.
A single set ('1') bit is added to the message and then as many reset ('0') bits as required 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", in hex byte terms this is "80 00 ... 00 00"
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 011
1 0000 0000 |
Byte padding
ANSI X.923
In ANSI X.923 bytes filled with zeros (0)'s are padded and the last byte defines the padding boundaries or the number of padded bytes.
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 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 |
PKCS7
This is described in
RFC 3852.
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:
01
02 02
03 03 03
04 04 04 04
05 05 05 05 05
etc.
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 |
Zero Padding
All the bytes that are required to be padded are padded with zero.
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.
Public key cryptography
In public key cryptography, padding is the process of preparing a message for encryption or signing with a primitive such as
RSAIn cryptography, RSA is an algorithm for public-key cryptography. It is the first algorithm known to be suitable for signing as well as encryption, and one of the first great advances in public key cryptography...
. A popular example is
OAEPIn cryptography, Optimal Asymmetric Encryption Padding is a padding scheme often used together with RSA encryption. OAEP was introduced by Bellare and Rogaway....
. This is called "padding" because originally, random material was simply appended to the message to make it long enough for the primitive, but this is not a secure form of padding and is no longer used. 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
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 A and B 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.
Padding messages is a way to make it harder to do
traffic analysisTraffic analysis is the process of intercepting and examining messages in order to deduce information from patterns in communication. It can be performed even when the messages are encrypted and cannot be decrypted. In general, the greater the number of messages observed, or even intercepted and...
. 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 attackIn cryptography, a timing attack is a side channel attack in which the attacker attempts to compromise a cryptosystem by analyzing the time taken to execute cryptographic algorithms...
.
See also
- Russian copulation
In cryptography, Russian copulation is a method of rearranging plaintext before encryption so as to conceal stereotyped headers, salutations, introductions, endings, signatures, etc. This obscures clues for a cryptanalyst, and will nearly always increase cryptanalytic difficulty. This is of course...
, another technique to prevent cribs
- Initialisation vector, salt (cryptography)
In cryptography, a salt comprises random bits that are used as one of the inputs to a key derivation function. The other input is usually a password or passphrase. The output of the key derivation function is stored as the encrypted version of the password. A salt can also be used as a part of a...
, which are sometimes confused with padding