Shai Halevi
IBM Research

Mitigating Dictionary Attacks on Password-Protected Local Storage"


We address the issue of encrypting data in local storage using a key
that is derived from the user's password. The typical solution in use
today is to derive the key from the password using a cryptographic
hash function. This solution provides relatively weak protection,
since an attacker that gets hold of the encrypted data can mount an
off-line dictionary attack on the user's password, thereby recovering
the key and decrypting the stored data.

We propose an approach for limiting off-line dictionary attacks in
this setting without relying on secret storage or secure hardware. In
our proposal, the process of deriving a key from the password requires
the user to solve a puzzle that is presumed to be solvable only by
humans (e.g, a CAPTCHA). We describe a simple protocol using this
approach: many different puzzles are stored on the disk, the user's
password is used to specify which of them need to be solved, and the
encryption key is derived from the password and the solutions of the
specified puzzles. Completely specifying and analyzing this simple
protocol, however, raises a host of modeling and technical issues,
such as new properties of human-solvable puzzles and some seemingly
hard combinatorial problems. Here we analyze this protocol in some
interesting special cases.

Joint work with Ran Canetti and Michael Steiner