Honey Encryption

As a mostly asymmetric cryptographer, my non-hummus highlight of this year's Bar-Ilan Winter School on Cryptography came when Tom Ristenpart gave us "A Contemporary View of Symmetric Encryption". Avoiding both S-boxes and bit flipping, this talk included a sneak peak at his upcoming Eurocrypt paper with Ari Juels on "Honey Encryption".

Honey encryption addresses the issue of being able to detect the key a ciphertext was encrypted under through trial decryptions, by recognising valid data. For example, an encryption of ASCII text decrypted under the wrong key is unlikely to look like ASCII text, so if your decrypted ciphertext is readable then odds-on you've found the right key. While this is intractable for a large key space, the scenario here is password-based encryption where users choose their own (typically awful) passwords, so trial decryption becomes a feasible attack. In a honey encryption scheme decryption under the wrong password returns plausible looking data, frustrating this attack since all recovered plaintexts appear equally likely.

The approach taken to realise honey encryption is through a pair of algorithms called a distribution-transforming encoder (DTE). A DTE consists of a (usually) randomised encoding algorithm that maps a message to a point in a set, and a deterministic decoding algorithm that reverses the encoding. In constructing a honey encryption scheme messages are first encoded through the DTE, then encrypted under a standard symmetric encryption (SE) scheme using a key derived from the supplied password. Decryption involves applying the SE scheme's decryption algorithm, followed by the DTE decoding algorithm. This straightforward construction means any semantic security guarantees offered by the SE scheme are retained by the honey encryption scheme, should users pick their passwords wisely.

So with all the responsibility now pushed into the DTE, what are the requirements on it? To provide security it should have the property (roughly) that encoding a message sampled from the message distribution (e.g. equally likely strings of ASCII text) results in a uniformly distributed value in the SE scheme's message space, and applying the decoding algorithm to a uniformly chosen value from the SE scheme's message space should result in a message distributed according to the honey encryption scheme's message distribution.

This turns out to be really difficult, and in fact dealing with encryptions of ASCII text is beyond the scope of current constructions. The DTEs given are for encrypting credit card numbers, and prime numbers, with the motivation for the latter being storing RSA secret keys away from the public modulus.

If you can't wait until Eurocrypt to find out more, want to try your hand at constructing a DTE for a new message distribution, or just enjoy wacky combinatorial proofs, you can check out the preprint on Ristenpart's webpage [http://pages.cs.wisc.edu/~rist/papers/HoneyEncryptionpre.pdf].