Once in a while I come across a research paper that’s so off the beaten path and so obviously applicable to a real problem, that I know it’s going to sink like a stone and never be heard from again.
Today I’d like to talk about an idea that was introduced back in CRYPTO 2006, but doesn’t seem to have gotten any real traction out in the real world since. (If I’m wrong and someone is using it, feel free to email me. I’d be happy to eat my words and hear more.)
This particular idea comes from a 2006 paper by Ran Canetti, Shai Halevi and Michael Steiner,* and it addresses a very real problem that we have with deployed encryption schemes: namely, they tend to rely on passwords. This means that even if you use strong cryptography, all of your data is vulnerable to someone with a password dictionary and a lot of computing power.
Password-Based Encryption (and why we hate it)
To explain how Canetti, Halevi and Steiner propose to deal with this, I need to give a little bit of background on password-based encryption.
First of all of all, no matter what Dan Brown says, we’ve gotten pretty good at building encryption schemes that stand up against very motivated adversaries. If you’re using a modern scheme and are properly generating/storing your secret keys, then it’s awfully unlikely that a third party is going to decrypt your data — even if that party is a government agency.** (I’m leaving aside the wrench factor).
Unfortunately, the previous paragraph embeds one major assumption that makes it inapplicable to the way that many people secure their data. You see, in a cryptographer’s imagination, everyone encrypts with a strong, random 128+ bit secret key, which they memorize and never write down.
But in real life, people mostly prefer to use their cat’s name.
The use of passwords to derive encryption keys is a lot more common than it should be. It’s depressingly common in many applications where people really need security. Passwords are the default authorization method for many fancy encrypting hard-drives and WDE packages. Windows just loves to encrypt things under your login credentials. (Many of these tools also support hardware tokens and TPM, but these are such a drag that most people don’t bother.)
To your attacker, this is a feature not a bug. If a key is derived from dictionary words, or some predictable mutation of dictionary words, then it can be guessed. All it takes is time and computing power. Moreover, since password guessing is embarrassingly parallel, it’s just the kind of enterprise that you can throw a data center or five at. (Ever wondered why the state of Maryland uses so much electricity?)
So far I haven’t said anything you didn’t already know. But just for fun, let’s quickly talk about what we currently do to prevent dictionary attacks. There are basically three approaches:
- Use some trusted, on-line server (or tamper-resistant hardware) to assist with the key derivation process. If done correctly, the server/hardware can shut off an attacker after a few invalid guesses, assuming that it isn’t also compromised. Unfortunately, this solution assumes that the server or hardware will be available when you need your data. That isn’t always possible.
- Use key stretching, which increases the time required to convert a password into a cryptographic key. This can slow down a dictionary attack, but it just slows it down. Moreover, it’s pretty ineffective against an attacker with specialized hardware.
- Use salt, which is hardly worth mentioning since if you aren’t salting your passwords then you’re crazy. Unfortunately all this does is prevent pre-computation. It does nothing against normal dictionary attacks.
The human touch
In a perfect world, the online solution (1) above would probably be the best way to go. Unfortunately, we don’t live in a perfect world, and this may not be compatible with people’s requirements.
While it’s not possible to prevent dictionary attacks in an offline system, we may be able to slow them down. To do this, we have to make the decryption process much more resource-intensive. Unfortunately, it’s hard to win this game through computation alone, at least not in a world full of FPGAs and elastic compute clouds.
 |
| Not this sort of brains. (XKCD). |
What Canetti, Halevi and Steiner realized is that there’s one resource that the adversary might not have in abundance: human brains.
What if we could mandate some sort of human interaction each time a user tries to decrypt a file? This shouldn’t be too burdensome for the legitimate decryptor, since presumably he’s human, and moreover he only needs to try once.
But a password cracker needs to try millions of passwords. Requiring a human interaction for each attempt should throw a serious wrench into the process.
Using Human Puzzles to stop dictionary attacks
Fortunately we already have a whole class of technologies that differentiate human beings from computers. Generally, these are known as Reverse Turing Tests (RTTs). Canetti, Halevi and Steiner propose to use RTTs to construct “human puzzles”. At a high level, the idea is pretty simple.
In every PBE scheme, a password must first be converted into a key. Normally you do this by hashing the password and some salt via a standard key derivation function (e.g., PBKDF2). Usually this is where you’d stop. The output of this function, which we’ll call K, would be the key used to encrypt and decrypt.
However, now we’re going to take things one step further. The first key will be further processed by converting it into a puzzle that only a human can solve. When a human solves this puzzle, they create a new key that, ideally, a computer all by itself should not be able to recover. The process should be reliable — it needs to produce the same result every time it’s run, possibly across many different users.
Once you get past the theoretical stuff, the concrete example that Canetti, Halevi and Steiner propose is to use CAPTCHAs to implement human puzzles.
|
|
CAPTCHAs: don’t you love them? |
In their example, the process of deriving an encryption key from a password now looks like this:
- First hash the password with some random salt r to derive a first key K. Now break this into a bunch of small chunks, each (for example) about 20 bits long.
- Use each of these 20-bit chunks to index into a huge table containing 2^20 (about 1 million) distinct CAPTCHA images. Each CAPTCHA contains a hard-to-read string with at least 20 bits of entropy in it. This string could be a bunch of numbers, or some randomly-selected dictionary words.
- Give each CAPTCHA to the human user to solve. Collect the results.
- Hash all of the user’s responses together with another salt s to derive a final decryption key.
If we instantiate the hash function with, say, PBKDF2 and a 160-bit output, then this requires the legitimate user to solve 8 puzzles the first time they encrypt, and every subsequent time they decrypt.
The dictionary attacker, however, has to solve eight puzzles for every password they try. If we assume that they have to guess a large number of passwords, this means that over time they’ll have to solve a substantial fraction (if not all) of the 1 million CAPTCHAs. Even if they can outsource this work at a rate of 5 cents per CAPTCHA, solving the whole collection will still cost $50,000 and a whole lot of hassle.
(This is a hugely simplified analysis. Obviously the attacker doesn’t have to solve all of the CAPTCHAs. Rather, their probability of guessing the key is a function of the number of CAPTCHAs, the fraction of the CAPTCHAs that they’ve been able to solve, the complexity of the password, etc. See the full paper for a much better analysis.)
The sticky wicket
Now, this really might work, in the sense that it will slow down attacks. But if you’re a practical-minded sort, you probably have one small question about this proposal. Namely: where do the CAPTCHAs come from?
Well, a simple answer is that you generate them all randomly the first time you encrypt, and you ship them along with the encrypted file. If we assume that each CAPTCHA is a 4KB image file, then storing the entire collection will require about 4GB.
That’s seems like a lot of space, but really it isn’t. After all, it’s not like we’re working with floppy drives. We live in a world where a 16GB USB Flash Drive can be had for about $10. So it’s perfectly reasonable to assume that we’ll have lots storage for things we really care about.
In summary
Now maybe CAPTCHAs aren’t your thing. Maybe you don’t like the idea of storing 4GB worth of files just to ship someone an encrypted ZIP file. That’s fine. One of the neatest open problems in the paper is to find new sorts of human puzzles. In general, a human puzzle is any function that converts some input (say a 20-bit string) into an output, such that only a human being can do the transformation.
These don’t need to rely on bulky, stored CAPTCHAs. Hypothetically you could come up with a human puzzle that dynamically generates instances without a big stored database. For example, your puzzle might be based on recognizing human expressions, or inkblots. It just has to be reliable.
And that’s why I think this is such a neat paper. Whether or not this particular idea changes the world, it’s a new idea, it tries to solve a hard practical problem that most people have given up on, and it inspires some new ideas.
The crypto publishing game rarely produces papers with that particular combination. Just for that, I’d love to see it go somewhere.
Notes:
* Ran Canetti, Shai Halevi and Michael Steiner. 2006. Mitigating Dictionary Attacks on Password-Protected Local Storage. In CRYPTO ’06.
** Leaving aside what we all know the NSA’s got in its basement.
A Few Thoughts on Cryptographic Engineering 
The basic idea is still very much a topic of research. For example here is a paper that was just published a couple of months ago: http://arxiv.org/abs/1103.6219
I'm not aware of any implementations of this being used by production systems though. From what I can tell, there are a number of very good reasons why it hasn't caught on, almost all of them falling into the usability/economic category.
I'm going to generalize here, (which is always dangerous), since there have been several proposed ways to integrate captchas into password hashing algorithms. The main idea though is that these algorithms offload the computational “key stretching” part of the hash onto the end user. Aka rather than having the server hash the user's guess 1 million times, it has the user compute a captcha instead. This is nice in the fact that most servers are limited in how computationally expensive they can make a password hash. Aka if it takes 1 minute to hash a user's password, and you have 100 users trying to log into your website at the same time, that's a problem.
From a usability standpoint though there are a lot of problems. For example, it makes accessing your site harder for the users. Admittedly, if a user logs into the site a lot it because easier since they memorize the captchas but that still is annoying. That's a big deal as research like the following has shown:
weis2010.econinfosec.org/papers/session3/weis2010_bonneau.pdf
You also have to provide several types of captchas, (such as visual and audio), to deal with various people's disabilities. That's certainly do-able but it increases the complexity. Can you imagine having to listen to 8 audio captchas before you log in? That would really be a pain! Also alternate methods of encoding the captcha in a hash such as the one I referenced above would have to support audio as well.
Then there's the limited benefit of having a very strong hashing algorithm. Attacks like keystroke loggers and pass-the-hash greatly reduce the need for an attacker to actually crack passwords. Therefore, most hashing algorithms now are designed to make cracking them painful enough that the attacker switches to those other methods. Disk encryption is the big exception, and in that case computationally expensive password hashing algorithms is very important.
(continued in next post)
(continued from previous post)
Now I referenced captcha enhanced hashing methods as a key stretching method, and I'd like to expand on that a bit since it's really a key stretching method of unpredictable cost to the attacker. With traditional key stretching methods like cycling, the cost to an attacker is fairly predicable. Yes every once in a while a new technique like using GPUs comes out and reduces the time required to make a guess by a factor of 10 or so, but for the most part the cost/time to make a guess roughly follows Moore's law. With Captcha's though, it depends on the algorithm the attacker uses to solve them. If someone suddenly comes up with a very efficient way to solve the captcha you are using, the security provided by your hashing algorithm can be drastically reduced. What's more, the captcha solving algorithms that an attacker uses can have a high false positive rate without hurting them that much. If they can't tell the difference between an 'i', '1',or 'j' who cares? Just try all three of them. This is different from most captcha use cases, (where a new captcha is given each guess, or the Post Office sends a letter to the wrong address). The problem with this is it's hard for a defender to estimate how hard a hashing algorithm will be to attack several years in the future.
This is compounded by the fact that the ability to upgrade to a new captcha based hashing algorithm may be harder than with your traditional hashing algorithms. Admittedly most people don't upgrade their hashing algorithms correctly now, but it's still an issue. Aka with a traditional scheme, you just store new_hash(old_hash(password, old_salt), new_salt). When a user logs in, you compute their old hash based on their password, and then hash it using the new algorithm. This is completely transparent to the user. With Captchas through you would have to leave the old user interface for entering captchas in place as well. Once again, this isn't an insurmountable problem, but it is an issue you need to keep in mind.
To sum this up, I'm not saying that using captchas in password hashing algorithms is a bad idea. In certain cases like disk encryption I think there's certainly potential for it. But there's also a lot of reasons why it hasn't achieved much recognition outside academic circles.
Oh I'd also like to echo your view on how neat it is to see original ideas like what was proposed in the Canetti, Halevi and Steine paper! I realize my comments sounded a bit harsh, but the reason I spent so much time thinking about how to implement and/or attack that method was because I was really impressed by the novel approach the authors took.
@Matt Weir: All great comments. Perhaps I should have added more disclaimers about how this idea isn't a magic bullet. I don't know that it should be a primary method for protecting stored files. What I like about it is that it goes along with all of the other protections (key stretching, etc.) that you mention, and offers a different type of security. I'd like to see someone try it out, just to see if it does stand up to the kind of concerns you mention in your comments.
I actually started to write a paper on the subject talking about the implementation details along with the strengths and weaknesses, but I put that on hold in favor of working on some other projects.
I think the most promising area to use captcha enhanced hashing is with hard-drive encryption of low power mobile devices, (smart phones, tablets, and whatnot). The main protections for them right now are hardware registers that are difficult to extract along with the issues involved with pulling the hashes off a locked device. Yes, a defender could further up the protection with TPMs but that's not exactly easy to do, (just ask all the people involved with DRM).
I'm fairly confident though those difficulties will be overcome by attackers in time, (if they are not already). Since mobile devices will never be able to match the computing power that an attacker can bring to the table, traditional key stretching techniques will only be able to do so much. In that case, captcha enhanced hashing can help add additional key stretching beyond what the mobile device could normally accomplish.
There's a lot of implementation decisions though that need to be made in how you combine it with traditional stretching. Aka, if it takes a user 30 seconds to enter in the captcha, is the captcha solution hard enough for an attacker to implement in software so that it's stronger than if the defender's device just spent 30 seconds cycling a password hash instead? Also during the time the user is entering in their captcha, can you pair the results with another hash the device is cycling for 20 seconds as a salt so the time spent entering the captcha isn't wasted by the defender's device? You also need to make the time spent turning the captcha into the second hash somewhat expensive since otherwise the cost for an attacker to make a false-positive guess on the captcha becomes trivial.
So yah, it's something that would be neat to see, but I'd also hope that it's deployed in a way where it actually does serve a purpose beyond annoying the end user and wasting their time 😉
This is a nice summary!
Another “neat” research idea for combatting brute-force attacks that “went nowhere” that I like is Boyen's Halting Password Puzzles from Usenix Security 2007. It is essentially key stretching with a user-chosen cut-off time (at registration), forcing the adversary trying an exhaustive search to be unsure how long to stretch each candidate password.