All-or-nothing transform

Last updated

In cryptography, an all-or-nothing transform (AONT), also known as an all-or-nothing protocol, is an encryption mode which allows the data to be understood only if all of it is known. AONTs are not encryption, but frequently make use of symmetric ciphers and may be applied before encryption. In exact terms, "an AONT is an unkeyed, invertible, randomized transformation, with the property that it is hard to invert unless all of the output is known." [1]

Contents

Algorithms

The original AONT, the package transform, was described by Ronald L. Rivest in his 1997 paper "All-Or-Nothing Encryption and The Package Transform". [2] The transform that Rivest proposed involved preprocessing the plaintext by XORing each plaintext block with that block's index encrypted by a randomly chosen key, then appending one extra block computed by XORing that random key and the hashes of all the preprocessed blocks. The result of this preprocessing is called the pseudomessage, and it serves as the input to the encryption algorithm. Undoing the package transform requires hashing every block of the pseudomessage except the last, XORing all the hashes with the last block to recover the random key, and then using the random key to convert each preprocessed block back into its original plaintext block. In this way, it's impossible to recover the original plaintext without first having access to every single block of the pseudomessage.

Although Rivest's paper only gave a detailed description of the package transform as it applies to CBC mode, it can be implemented using a cipher in any mode. Therefore, there are multiple variants: the package ECB transform, package CBC transform, etc.

In 1999 Victor Boyko proposed another AONT, provably secure under the random oracle model. [1]

Apparently at about the same time, D. R. Stinson proposed a different implementation of AONT, without any cryptographic assumptions. [3] This implementation is a linear transform, perhaps highlighting some security weakness of the original definition.

Applications

AONTs can be used to increase the strength of encryption without increasing the key size. This may be useful to, for example, secure secrets while complying with government cryptography export regulations. AONTs help prevent several attacks.

One of the ways AONTs improve the strength of encryption is by preventing attacks which reveal only part of the information from revealing anything, as the partial information is not enough to recover any of the original message.

Another application, suggested in the original papers is to reduce the cost of security: for example, a file can be processed by AONT, and then only a small portion of it can be encrypted (e.g., on a smart-card). AONT will assure that as a result the whole file is protected. It is important to use the stronger version of the transform (such as the one by Boyko above).

AONT may be combined with forward error correction to yield a computationally secure secret sharing scheme. [4]

Other uses of AONT can be found in optimal asymmetric encryption padding (OAEP).

Related Research Articles

Blowfish is a symmetric-key block cipher, designed in 1993 by Bruce Schneier and included in many cipher suites and encryption products. Blowfish provides a good encryption rate in software, and no effective cryptanalysis of it has been found to date. However, the Advanced Encryption Standard (AES) now receives more attention, and Schneier recommends Twofish for modern applications.

In cryptography, a block cipher is a deterministic algorithm that operates on fixed-length groups of bits, called blocks. Block ciphers are the elementary building blocks of many cryptographic protocols. They are ubiquitous in the storage and exchange of data, where such data is secured and authenticated via encryption.

In cryptography, RC4 is a stream cipher. While it is remarkable for its simplicity and speed in software, multiple vulnerabilities have been discovered in RC4, rendering it insecure. It is especially vulnerable when the beginning of the output keystream is not discarded, or when nonrandom or related keys are used. Particularly problematic uses of RC4 have led to very insecure protocols such as WEP.

<span class="mw-page-title-main">Stream cipher</span> Type of symmetric key cipher

A stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream (keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystream, to give a digit of the ciphertext stream. Since encryption of each digit is dependent on the current state of the cipher, it is also known as state cipher. In practice, a digit is typically a bit and the combining operation is an exclusive-or (XOR).

<span class="mw-page-title-main">Symmetric-key algorithm</span> Algorithm

Symmetric-key algorithms are algorithms for cryptography that use the same cryptographic keys for both the encryption of plaintext and the decryption of ciphertext. The keys may be identical, or there may be a simple transformation to go between the two keys. The keys, in practice, represent a shared secret between two or more parties that can be used to maintain a private information link. The requirement that both parties have access to the secret key is one of the main drawbacks of symmetric-key encryption, in comparison to public-key encryption. However, symmetric-key encryption algorithms are usually better for bulk encryption. With exception of the one-time pad they have a smaller key size, which means less storage space and faster transmission. Due to this, asymmetric-key encryption is often used to exchange the secret key for symmetric-key encryption.

In cryptography, an initialization vector (IV) or starting variable is an input to a cryptographic primitive being used to provide the initial state. The IV is typically required to be random or pseudorandom, but sometimes an IV only needs to be unpredictable or unique. Randomization is crucial for some encryption schemes to achieve semantic security, a property whereby repeated usage of the scheme under the same key does not allow an attacker to infer relationships between segments of the encrypted message. For block ciphers, the use of an IV is described by the modes of operation.

In cryptography, a block cipher mode of operation is an algorithm that uses a block cipher to provide information security such as confidentiality or authenticity. A block cipher by itself is only suitable for the secure cryptographic transformation of one fixed-length group of bits called a block. A mode of operation describes how to repeatedly apply a cipher's single-block operation to securely transform amounts of data larger than a block.

In cryptography, a Feistel cipher is a symmetric structure used in the construction of block ciphers, named after the German-born physicist and cryptographer Horst Feistel, who did pioneering research while working for IBM; it is also commonly known as a Feistel network. A large proportion of block ciphers use the scheme, including the US Data Encryption Standard, the Soviet/Russian GOST and the more recent Blowfish and Twofish ciphers. In a Feistel cipher, encryption and decryption are very similar operations, and both consist of iteratively running a function called a "round function" a fixed number of times.

In cryptography, padding is any of 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.

CipherSaber is a simple symmetric encryption protocol based on the RC4 stream cipher. Its goals are both technical and political: it gives reasonably strong protection of message confidentiality, yet it's designed to be simple enough that even novice programmers can memorize the algorithm and implement it from scratch. According to the designer, a CipherSaber version in the QBASIC programming language takes just sixteen lines of code. Its political aspect is that because it's so simple, it can be reimplemented anywhere at any time, and so it provides a way for users to communicate privately even if government or other controls make distribution of normal cryptographic software completely impossible.

Probabilistic encryption is the use of randomness in an encryption algorithm, so that when encrypting the same message several times it will, in general, yield different ciphertexts. The term "probabilistic encryption" is typically used in reference to public key encryption algorithms; however various symmetric key encryption algorithms achieve a similar property, and stream ciphers such as Freestyle which are inherently random. To be semantically secure, that is, to hide even partial information about the plaintext, an encryption algorithm must be probabilistic.

In cryptography, ciphertext stealing (CTS) 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.

In cryptography, Optimal Asymmetric Encryption Padding (OAEP) is a padding scheme often used together with RSA encryption. OAEP was introduced by Bellare and Rogaway, and subsequently standardized in PKCS#1 v2 and RFC 2437.

Authenticated Encryption (AE) is an encryption scheme which simultaneously assures the data confidentiality and authenticity. Examples of encryption modes that provide AE are GCM, CCM.

Disk encryption is a special case of data at rest protection when the storage medium is a sector-addressable device. This article presents cryptographic aspects of the problem. For an overview, see disk encryption. For discussion of different software packages and hardware devices devoted to this problem, see disk encryption software and disk encryption hardware.

In cryptography, Galois/Counter Mode (GCM) is a mode of operation for symmetric-key cryptographic block ciphers which is widely adopted for its performance. GCM throughput rates for state-of-the-art, high-speed communication channels can be achieved with inexpensive hardware resources.

<span class="mw-page-title-main">Cryptography</span> Practice and study of secure communication techniques

Cryptography, or cryptology, is the practice and study of techniques for secure communication in the presence of adversarial behavior. More generally, cryptography is about constructing and analyzing protocols that prevent third parties or the public from reading private messages. Modern cryptography exists at the intersection of the disciplines of mathematics, computer science, information security, electrical engineering, digital signal processing, physics, and others. Core concepts related to information security are also central to cryptography. Practical applications of cryptography include electronic commerce, chip-based payment cards, digital currencies, computer passwords, and military communications.

The following outline is provided as an overview of and topical guide to cryptography:

There are various implementations of the Advanced Encryption Standard, also known as Rijndael.

<span class="mw-page-title-main">Xor–encrypt–xor</span>

The xor–encrypt–xor (XEX) is a (tweakable) mode of operation of a block cipher. In tweaked-codebook mode with ciphertext stealing, it is one of the more popular modes of operation for whole-disk encryption. XEX is also a common form of key whitening, and part of some smart card proposals.

References

  1. 1 2 Boyko, Victor (1999). "On the Security Properties of OAEP as an All-or-Nothing Transform". Advances in Cryptology — CRYPTO' 99. Lecture Notes in Computer Science. Vol. 1666. pp. 503–518. doi:10.1007/3-540-48405-1_32. ISBN   978-3-540-66347-8.
  2. ↑ Rivest, Ronald (1997). "All-or-nothing encryption and the package transform". Fast Software Encryption. Lecture Notes in Computer Science. Vol. 1267. pp. 210–218. doi:10.1007/BFb0052348. ISBN   978-3-540-63247-4.
  3. ↑ Stinson, D. R. (1 January 2001). "Something About All or Nothing (Transforms)". Designs, Codes and Cryptography. 22 (2): 133–138. doi:10.1023/A:1008304703074. S2CID   10118200.
  4. ↑ Resch, Jason; Plank, James (February 15, 2011). AONT-RS: Blending Security and Performance in Dispersed Storage Systems (PDF). Usenix FAST'11.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.