Padding (cryptography)

Padding (cryptography)

In cryptography, 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 ciphers is to prevent the cryptanalyst from using that predictability to find cribs 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".

ymmetric cryptography

Hash functions

All modern cryptographic hash functions 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 stealing or residual block termination 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 attacks based on structured CBC padding.

Padding methods

Two simple ways of padding a message are:

Bit padding

This is described in [http://www.faqs.org/rfcs/rfc1321.html 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.

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 [http://tools.ietf.org/html/rfc3852#section-6.3 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.

Public key cryptography

In public key cryptography, padding is the process of preparing a message for encryption or signing with a primitive such as RSA. A popular example is OAEP. 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 analysis. 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.

ee also

* Russian copulation, another technique to prevent cribs
* Initialisation vector, salt (cryptography), which are sometimes confused with padding


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Padding — (von engl. to pad für auffüllen) ist ein Fachbegriff der Informatik für Fülldaten, mit denen ein vorhandener Datenbestand vergrößert wird. Die Füllbytes werden auch Pad Bytes genannt. Die für Prüfsummen verwendeten Daten zählen hierbei nicht zum… …   Deutsch Wikipedia

  • Salt (cryptography) — In cryptography, a salt consists of random bits, creating one of the inputs to a one way function. The other input is usually a password or passphrase. The output of the one way function can be stored rather than the password, and still be used… …   Wikipedia

  • Optimal asymmetric encryption padding — This article is about the padding scheme used in public key cryptography. For the division of the Thailand Ministry of Science Technology and Environment entitled Office of Atomic Energy for Peace, see [1]. In cryptography, Optimal Asymmetric… …   Wikipedia

  • Optimal Asymmetric Encryption Padding — This article is about the padding scheme used in public key cryptography. For the division of the Thailand Ministry of Science Technology and Environment entitled Office of Atomic Energy for Peace, see [http://www.oaep.go.th/english/index.html] …   Wikipedia

  • MARS (cryptography) — MARS General Designers IBM First published 1998 Certification AES finalist Cipher detail Key sizes 128, 192, or 256 bits Block sizes …   Wikipedia

  • Grille (cryptography) — In the history of cryptography, a grille cipher was a technique for encrypting a plaintext by writing it onto a sheet of paper through a pierced sheet (of paper or cardboard or similar). The earliest known description is due to the polymath… …   Wikipedia

  • Malleability (cryptography) — Malleability is a property of some cryptographic algorithms.[1] An encryption algorithm is malleable if it is possible for an adversary to transform a ciphertext into another ciphertext which decrypts to a related plaintext. That is, given an… …   Wikipedia

  • MD2 (cryptography) — Infobox cryptographic hash function name = MD2 caption = designers = Ronald Rivest publish date = April 1992 series = MD, MD2, MD3, MD4, MD5 derived from = derived to = related to = certification = digest size = 128 bits structure = rounds = 18… …   Wikipedia

  • Optimal Asymmetric Encryption Padding — En cryptologie, l OAEP (Optimal Asymmetric Encryption Padding) est un schéma de remplissage, utilisé généralement avec le chiffrement RSA. Cet algorithme fut introduit en 1994 par Mihir Bellare et Phil Rogaway[1]. L OAEP est une forme de réseau… …   Wikipédia en Français

  • Block cipher modes of operation — This article is about cryptography. For method of operating , see modus operandi. In cryptography, modes of operation is the procedure of enabling the repeated and secure use of a block cipher under a single key.[1][2] A block cipher by itself… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”