Many parlor tricks involve a show of seemingly superhuman strength by a person of ordinary physique. Given how weak ordinary passwords are, it would be nice to find a parlor trick or two that allows them to resist the brute force cracking attempts of a powerful and determined adversary. Here I’ll show you how they can, using a technique I devised with my Cornell Tech colleague Tom Ristenpart (another Skyhigh Networks Cryptography Advisory Board member) a couple of years ago [2,3]. The idea, called honey encryption, is useful for protecting consumer data in the cloud, as I’ll explain.

The idea behind honey encryption is a bit like that of the one-time pad. You have probably heard the one-time pad described as the only cipher that is truly “unbreakable.” It’s unbreakable in the sense that even with an unbounded amount of computing power, an attacker with knowledge of the ciphertext alone cannot learn any information whatsoever about the plaintext. Consider an example using a variant that maps letters to their ordinal values and performs letter-by-letter mod 26 addition. Given a randomly selected 14-letter key such as ABJDYQNEAOWXEY, we can encrypt any 14-letter message of our choice.

For example, we can conceal our invasion plans:

blog image - encryption1 600

You see here, for example, that the first letter of the message, `W’, maps to 23, while that of the key, `A’, maps to 1. 23 + 1 = 24, which corresponds to `X’, the first letter of the ciphertext.

How is it that the ciphertext reveals no information about the plaintext? One way to see this is to observe that for any desired plaintext M there exists a key that decrypts the ciphertext XGSRURRJTXAGQX to M. For example, an alternative invasion plan is equally plausible under an invalid key:

blog image - encryption2 600

Thus, even if an adversary had an extremely powerful computer that could try all possible keys, it couldn’t tell when it had decrypted correctly.

The one-time pad has been used by secret agents and to secure the nuclear hotline between the U.S. and Soviet Union. Unfortunately, though, the one-time pad requires a key as long as the message it encrypts. And even the 14-letter key used for this rather short ciphertext would be hard for a human being to commit to memory in a short space of time. So the one-time pad cannot easily be used with weak keys such as passwords.

Enter honey encryption.

The idea behind honey encryption is to relax the one-time pad to obtain a similar but somewhat weaker guarantee. The goal is to enable a sender to encrypt a message M under a potentially weak password P such that even an attacker with unbounded computing power cannot recover M with high probability.

While there isn’t space here to describe the mechanics behind honey encryption, I’ll give a rough sketch of its construction.

To build a honey encryption scheme, we need a good statistical model of how messages are selected by a sender. As a simple example, suppose the plaintext M is four-digit PIN. Thanks to various password breaches, we have a pretty good idea of how people select PINs [1]. The most popular PIN, for example, is 1234. It is selected about 10.7% of the time.

What we need, more precisely, is an algorithm A that allows us to sample messages according to this model. This algorithm A may be thought of (loosely) as taking passwords as input and outputting messages according to the model. For example, given a random password, an algorithm A for four-digit PINs will output the PIN 1234 with probability 10.7%.

In honey encryption, a ciphertext is a way of “cooking” the algorithm A so that the correct password P yields the correct message M. Other passwords, though, still output effectively random sample messages according to the statistical model. Importantly, any password input to the algorithm yields a valid message. The statistical model in fact provides a stronger property: the messages output upon decryption with an incorrect password don’t just look correct, they also look plausible as choices by the sender.

 

The Cloud Encryption Handbook

Get an overview of encryption schemes and their tradeoffs between security and functionality.

Download Now

Given a ciphertext produced by honey encryption, the best an adversary can do to crack it is take her best guess P’ at the password P, decrypt, and treat the output M’ as a guess for M. Sometimes the adversary will be right, and M = M’, but the adversary will not know whether her guess is correct. And most of the time, even if P is an ordinary password, M’ will be incorrect.

Honey encryption has a number of applications. Next month at the IEEE Security and Privacy conference, my colleagues and I will be presenting papers that show how honey encryption can provide strong protection for genetic data [4] in a system called GenoGuard and, in a system called NoCrack, for password vaults [5].

Honey encryption is especially valuable for protecting password-protected consumer data in the cloud against breaches. For example, password vaults tend to be backed up in the cloud in a way that relies for security on encryption under user-selected passwords. In at least one case, vaults may have been exposed in a cloud-side breach. If vaults are protected using ordinary encryption, they can be cracked offline via brute-force attack, leading to exposure of all of an affected user’s passwords—very bad news. You can find source code for NoCrack here.

[1] N. Berry. PIN analysis. 3 Sept. 2012. Referenced April 2015 at www.datagenetics.com/blog/september32012.
[2] A. Juels and T. Ristenpart. Honey Encryption: Security Beyond the Brute-Force Bound. EUROCRYPT, pp. 293-310, 2014.
[3] A. Juels and T. Ristenpart. Honey Encryption: Encryption Beyond the Brute-Force Barrier. IEEE Security & Privacy Magazine, 12(4): 59-62, 2014.
[4] Z. Huang, E. Ayday, J.-P. Hubaux, J. Fellay, and A. Juels. GenoGuard: Protecting Genomic Data Against Brute-Force Attacks. IEEE Symposium on Security and Privacy (SP), 2015. To appear.
[5] R. Chatterjee, J. Bonneau, A. Juels, and T. Ristenpart. Cracking-Resistant Password Vaults using Natural Language Encoders. IEEE Symposium on Security and Privacy (SP), 2015. To appear.

Note: Dan Brown aficionados (of which I’m admittedly not one), may appreciate a seeming correspondence between the one-time pad and honey encryption and the “rotating cleartext” encryption in Digital Fortress:

The notion of a rotating cleartext function was first put forth in an obscure, 1987 paper by a Hungarian mathematician, Josef Harne. Because brute-force computers broke codes by examining cleartext for identifiable word patterns, Harne proposed an encryption algorithm that, in addition to encrypting, shifted decrypted cleartext over a time variant. In theory, the perpetual mutation would ensure that the attacking computer would never locate recognizable word patterns and thus never know when it had found the proper key. The concept was somewhat like the idea of colonizing Mars—fathomable on an intellectual level, but, at present, well beyond human ability.

—Dan Brown, Digital Fortress