Conference proceeding
The password allocation problem: strategies for reusing passwords effectively
Proceedings of the 12th ACM workshop on workshop on privacy in the electronic society, pp.255-260
WPES '13
11/04/2013
DOI: 10.1145/2517840.2517870
Abstract
Each Internet user has, on average, 25 password-protected accounts, but only 6.5 distinct passwords[webhabits]. Despite the advice of security experts, users are obviously re-using passwords across multiple sites. So this paper asks the question: given that users are going to re-use passwords across multiple sites, how should they best allocate those passwords to sites so as to minimize their losses from accidental password disclosures?
We provide both theoretical and practical results. First, we provide a mathematical formulation of the Password Allocation (PA) problem and show that it is NP-complete with a reduction via the 3-Partition problem. We then study several special cases and show that the optimal solution is often a contiguous allocation -- i.e., similar accounts share passwords. Next, we evaluate several human- and machine-computable heuristics that have very good performance and produce solutions that are reasonably close to optimal. We find that the human-computable heuristics do not perform nearly as well as the machine-computable heuristics, however, they provide a useful and easy to follow set of guidelines for re-using passwords.
Details
- Title: Subtitle
- The password allocation problem: strategies for reusing passwords effectively
- Creators
- Rishab NithyanandRob Johnson
- Resource Type
- Conference proceeding
- Publication Details
- Proceedings of the 12th ACM workshop on workshop on privacy in the electronic society, pp.255-260
- Publisher
- ACM
- Series
- WPES '13
- DOI
- 10.1145/2517840.2517870
- ISSN
- 1543-7221
- Language
- English
- Date published
- 11/04/2013
- Academic Unit
- Computer Science; Public Policy Center (Archive); Center for Social Science Innovation
- Record Identifier
- 9984002593802771
Metrics
27 Record Views