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 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+IV pair). Classically, an attacker can just XOR together the two ciphertexts, effectively removing the keystream and obtaining the two plaintexts XORed 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 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 statistical and known plaintext attacks: even a cipher with 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 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 ciphers (Cipher1 and Cipher2), using two distinct keys:
Cipher1( Cipher2( plaintext ) ) = (plaintext ⊕ Keystream2) ⊕ Keystream1 = (plaintext ⊕ Keystream1) ⊕ Keystream2 = plaintext ⊕ (Keystream1 ⊕ Keystream2)
As you can see, the problem is that, since XOR is 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 ⊕ Keystream2 as its keystream. On the other hand, if you apply an all-or-nothing transform between the two encryptions, they are no longer 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 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 academic point-of-view, a type of transform like this is not very efficient, as it requires an additional encryption and 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: