Error-tolerant password recovery

ABSTRACT

Many encryption systems require the user to memorize high entropy passwords or passphrases and reproduce them exactly. This is often a difficult task. We propose a more fault-tolerant scheme, where a high entropy key (or password) is derived from a sequence of low entropy passwords. The user is able to recover the correct key if she remembers a certain percentage of the passwords correctly. In contrast to other systems that have been proposed for fault-tolerant passwords, our basic design is provably secure against a computationally unbounded attacker.

REFERENCES

• 1: Biometrics consortium,2001.Website at http://www.biometrics.org.
• 2: G.Blakely.Safeguarding cryptographic keys.In AFIPS Conference Proceedings 1979:National Computer Conference ,volume 48,pages 313 -317, June 1979.
• 3: D.Bleichenbacher and P.Q.Nguyen.Noisy polynomial interpolation and noisy Chinese remaindering.In B.Preneel,editor,Advances in Cryptology -EUROCRYPT '00 ,pages 53 -69. Springer-Verlag,2000.LNCS no.1807.
• 4: Carl Ellison , Chris Hall , Randy Milbert , Bruce Schneier, Protecting secret keys with personal entropy, Future Generation Computer Systems, v.16 n.4, p.311-318, Feb. 2000 [doi>10.1016/S0167-739X(99)00055-2]
• 5: Warwick Ford , Burton S. Kaliski, Jr., Server-Assisted Generation of a Strong Secret from a Password, Proceedings of the 9th IEEE International Workshops on Enabling Technologies: Infrastructure for Collaborative Enterprises, p.176-180, June 04-16, 2000
• 6: N.Frykholm.Passwords:Beyond the terminal interaction odel.Master 's thesis,Ume~ University, Department of Computing Science,2000.UMNAD 298/2000.
• 7: V.Guruswami and M.Sudan.Improved decoding of Reed-Solomon and algebraic-geometry codes.IEEE TOIT:IEEE Transactions on Information Theory , 45:1757 -1767,Oct.1999.
• 8: I.Jermyn,A.Mayer,F.Monrose,M.K.Reiter,and A.D.Rubin.The design and analysis of graphical passwords.In 8th USENIX Security Symposium ,pages 1 -14,Washington,D.C.,USA,Aug.1999.USENIX.
• 9: Ari Juels , Martin Wattenberg, A fuzzy commitment scheme, Proceedings of the 6th ACM conference on Computer and communications security, p.28-36, November 01-04, 1999, Kent Ridge Digital Labs, Singapore [doi>10.1145/319709.319714]
• 10: RSA.PKCS #5:Password-based cryptography standard 2.0,Mar.1999. http://www.rsasecurity.com/rsalabs/pkcs/pkcs- 5/index.html.
• 11: Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]
• 12: Statistics Sweden,2001.Website at http://www.scb.se/eng/index.asp.
• 13: D.Stinson.Universal hash families and the leftover hash lemma,and applications to cryptography and computing,jan 2001. http://citeseer.nj.nec.com/stinson01universal.html.
• 14: Hacker takes credit-card nu bers.Washington Post , (Tuesday,January 11):E02,2000.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Error control codes

  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.2 User/Machine Systems
          Subjects: Human factors

General Terms:
Human Factors, Security

Keywords:
Reed-Solomon codes, error-correcting codes, fault-tolerance, fuzzy commitment, password ensembles, password recovery