Halting Password Puzzles
Hard-to-break Encryption from Human-memorable Keys

By Xavier Boyen.

In 16th USENIX Security Symposium (SECURITY 2007), pages 119-134. The USENIX Association, 2007.

Abstract

We revisit the venerable question of ``pure password''-based key derivation and encryption, and expose security weaknesses in current implementations that stem from structural flaws in Key Derivation Functions (KDF). We advocate a fresh redesign, named Halting KDF (HKDF), which we thoroughly motivate on these grounds:

1. By letting password owners choose the hash iteration count, we gain operational flexibility and eliminate the rapid obsolescence faced by many existing schemes.
2. By throwing a Halting-Problem wrench in the works of guessing that iteration count, we widen the security gap with any attacker to its theoretical optimum.
3. By parallelizing the key derivation, we let legitimate users exploit all the computational power they can muster, which in turn further raises the bar for attackers.

HKDFs are practical and universal: they work with any password, any hardware, and a minor change to the user interface. As a demonstration, we offer real-world implementations for the TrueCrypt and GnuPG packages, and discuss their security benefits in concrete terms.

Material

- published in print (PDF) (hosted by the publisher)
- published online (HTML) (hosted by the publisher)
- author's version (PS) (PDF)
- presentation slides (HTML)

Reference

@InProceedings{Boyen:SECURITY-2007:hkdf,
  author = {Xavier Boyen},
  title = {Halting Password Puzzles -- Hard-to-break Encryption from Human-memorable Keys},
  booktitle = {16th USENIX Security Symposium---SECURITY 2007},
  pages = {119--134},
  publisher = {Berkeley: The USENIX Association},
  year = {2007},
  note = {Available at \url{http://www.cs.stanford.edu/~xb/security07/}}
}