Schneier on Security

q • June 26, 2014 9:22 AM

The paper leaves out of scope one important consideration: plaintext malleability. The security model proposed by the authors does not consider the possibility of achieving the ciphertext bias attack by modifying the plaintexts before encryption in a way that’s not obviously detectable by the receiver.

For example, if encrypting simple ASCII text in a natural language, the substituted algorithm can tweak the text a bit by adding some spaces before EOLs, changing single space to two spaces, introducing a plausible typo here and there etc. If encrypting Unicode, it can use aliases, insert a zero-width space somewhere, etc. These are just examples; for any kind of plaintext there is a way to introduce hard-to-spot modifications. E.g. if encrypting an array of floating-point numbers, the substituted algorithm can toggle the lowest-significant bit of a number with small exponent and nobody would notice.

Of course it requires the substituted algorithm to know the nature of the plaintext, but it’s not an impossible requirement. In some cases, where encryption and plaintext handling are done by the same program, it’s trivial. Examples: encrypted notes app such as Tombo, password manager such as PasswordSafe.

Example attack on an encrypted text application:
0. Suppose the application uses deterministic encryption with N-bit key, where N=2^{n}. E.g. for 128-bit encryption n=7.
1. The attacker’s key, K~, is used to select n+1 bits of ciphertext: c[1]…c[n+1] (the specific selection algorithm is unimportant).
2. First n bits of the selected bit array, c[1]…c[n], are used to form a number i, which is used as a bit index into the user’s key K.
3. The last bit of the selected bit array is compared against i-th bit of the user’s key. If c[n+1] == K[i], the ciphertext is accepted (and transmitted, or stored, or whatever). If not, the algorithm adds an empty line at the end of the plaintext and tries again (goto 1).

This way, each ciphertext leaks one (randomly chosen) bit of user’s key.

On average, half of the plaintexts will have to be tweaked and re-encrypted.
The user probably won’t notice extra blank lines (heck, some of the editors I used tend to add blank lines at the end of text sometimes without any reason).
The eavesdropper, on the other hand, will be able to reconstruct the user’s key K after capturing approx \Theta{N*log(N)} ciphertexts (it’s a coupon collector’s problem; for N=128 it gives 695 ciphertexts).

But even in a more generic setting it can be achieved. E.g. the big brother B can attack network encryption using a two-part exploit: the “bottom” part will compromise OpenSSL, and the “top” part will inject into the web browser. The “top” part will record (or hash) all text entered into input fields and communicate it to the “bottom” part, which will scan the data being encrypted and tweak only parts it knows how to deal with.

I write this not to diminish the importance of the paper, but only to say that even if deterministic encryption as proposed by the authors is proven secure under their model, I’m not sure it’s possible to implement their model in the real world. It’s impossible to shield against plaintext malleability without placing plaintext creation AND authentication into trusted environment. And if you have a trusted environment, why not put the encryption there as well?