Stronger Password-Based Encryption Using All-or-Nothing Transforms
Greg Zaverucha · 2015
When encrypting data with a low-entropy key, the primary threat to consider is a brute-force key search. Let C = C0, . . . , Cs−1 be a ciphertext encrypting a plaintext P = P0, . . . , Ps−1, produced by a block cipher (a concrete example is AES in CBC mode). In a brute-force attack where P0 is known, the attacker could focus on C0, i.e., for each candidate key K, check whether DK(C0) = P0. One idea to increase the cost of a brute force attack is due to Rivest [8]. Apply a randomized encoding to the plaintext, P ′ = Encode(P ), such that in order to decode P ′ and obtain P , one needs all of P ′. In this way DK(C0) = P ′ 0 does not give enough information about P to let the adversary decide if K is correct. In order to check that K is the correct key, the attacker must decrypt all s blocks of C to recover P ′, then compute P = Decode(P ′). The Encode operation is called an all-or-nothing transform (ANT), because it cannot be even partly reversed without all of the encoded output. The ANT is randomized, but not keyed (no secret values are required in Encode and Decode). This adds a factor of s to each guess, which can be considerable. For example, when P is 1 GByte, and a 128-bit block cipher is used s ≈ 2. So the cost of brute forcing a 40-bit key goes from 2 to 2 block cipher operations. There may also be a significant I/O cost, as the attack must work with 2 ciphertext blocks instead of just one. We are unaware of any papers, systems or software that uses Rivest’s ANT idea for password-based encryption (PBE), based on the observation that export strength keys (Rivest’s original motivation) are similar to passwords (in that they are both