all-or-nothing transform (thing)
Return to all-or-nothing transform (thing)
|In [cryptography], an "[all-or-nothing] [transform]" (also called a "package transform") is a [randomized] unkeyed [reversible] [transformation] (P'i = f( Pi )) with the following properties:|
[Cryptanalysis] often exploits [known plaintext] or [redundancy|redundancies] in the [plaintext] (i.e. statistical structure) to deduce information about a cipher's [keystream] or key, in order to break this [cipher]. Applying an [all-or-nothing transform] before encryption effectively randomizes the data (at the cost of a small [expansion] in the message size and some computational [overhead]), spreading the information you need to recover the original message over all the message. This generally turns "[partial] information about the plaintext" into "no information about the plaintext".
An example would be: imagine someone encrypts two different plaintexts with a [stream cipher] using exactly the same key (or key+[Initialization vector|IV] pair). Classically, an attacker can just [XOR] together the two [ciphertext|ciphertexts], effectively removing the [keystream] and obtaining the two plaintexts [XOR]ed together; this enables the attacker to eventually obtain the two separate plaintexts, due to assumptions that can be made regarding the statistical structure of the plaintext (e.g. it mostly consists of [whitespace|spaces] and letters). On the other hand, if someone first applies an [all-or-nothing transform] to the two plaintexts before encryption with the stream cipher (using again, the same key), the attacker can no longer recover any of the plaintexts, as it's not possible to invert two all-or-nothing transforms if you only have the two transformed plaintexts XORed together (since they are effectively random). This means that an [all-or-nothing transform] increases the [resistance] of a cipher against [statistics|statistical] and [known plaintext attack|known plaintext attacks]: even a cipher with [certificational weakness|certificational weaknesses] can be considered pretty safe, if you only use it to encrypt data that has been processed with an all-or-nothing transform.
It should be noted, for example, that some [public key cryptography] protocols are only secure under the assumption that you only encrypt random data (e.g. a randomly-generated [AES] [session key]) with it, as direct encryption of a (redundant/non-random) plaintext might leak information about the [private key]. In these types of contexts, it is also useful to apply an all-or-nothing transform prior to the encryption (like [optimal asymmetric encryption padding|OAEP], which is usually used with [RSA]), to prevent leaking information about the private key.
A final example of where an all-or-nothing transform would be useful is a situation where you want to encrypt a plaintext with two different [stream cipher|stream ciphers] (Cipher1 and Cipher2), using two distinct keys:
Cipher1( Cipher2( plaintext ) ) = (plaintext [XOR|⊕] Keystream2) [XOR|⊕] Keystream1 = (plaintext [XOR|⊕] Keystream1) [XOR|⊕] Keystream2 = plaintext [XOR|⊕] (Keystream1 [XOR|⊕] Keystream2)
As you can see, the problem is that, since [XOR] is [Commutativity|commutative], the attacker doesn't have to decrypt the ciphertext by the same order you encrypted it. In fact, the attacker doesn't even have to attack the two ciphers: (s)he can attack an equivalent cipher that outputs Keystream1 [XOR|⊕] Keystream2 as its [keystream]. On the other hand, if you apply an all-or-nothing transform between the two encryptions, they are no longer [Commutativity|commutative], and the attacker now has to "peel off" Cipher1 before he can undo the all-or-nothing transform and "peel off" Cipher2.
An example of an all-or-nothing transform (using [AES]-256 as block cipher and [SHA-256] as hash function) would be something like:
Notice that each possible [plaintext] maps to [absurdly large number|2256] different (expanded) messages, depending on the key you choose. Also, note that the message is effectively randomized, as every element of P'i has been encrypted under a [random] key and element J results from the [XOR] of a randomly chosen number (K) with several hashes obtained from the (randomized) P'i blocks. By "randomized", I mean that, even if someone knows P0 (or any other block) with 100% [certainty], they still cannot [predict] P'0, J or any P'i. Also, even if they know P'0, they cannot recover P0 unless they know J and every other element of P'i.
To "unpackage" an [incoming] transformed message (Zi, with a length of M blocks), the recipient only has to perform the following steps:
As you can see, as long as someone knows all the bits of the "package", it's trivial to [reverse] this transform. On the other hand, to show how this transformation is "all-or-nothing", let's see what happens when only [partial] information is available:
Finally, it should be said that, from a purely [academia|academic] point-of-view, a type of transform like this is not very [efficiency|efficient], as it requires an additional encryption and [hash function|hashing] step per block and results in an expanded message. On the other hand, it's also true that the expansion rate is small for large ciphertexts (and tends to 0% as the ciphertext size grows to [infinity]), so it's [negligible] when you're encrypting [bulk] data and computational [overhead] is mostly negligible for small ciphertexts (particularly in a world where people use stuff like [scrypt] and [bcrypt]). Besides, if it's data you're not likely to decrypt every day, spending a handful of seconds more while decrypting is not the end of the world.
So... yeah... if you're thinking of encrypting data you're not going to touch for a while, the correct order of steps should be: