Differentially Private Password Frequency Lists Or, How to release statistics from 70 million passwords (on purpose)

Jeremiah Blocki, Anupam Datta, Joseph Bonneau

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Given a dataset of user-chosen passwords, the frequency list reveals the frequency of each unique password. We present a novel mechanism for releasing perturbed password frequency lists with rigorous security, efficiency, and distortion guarantees. Specifically, our mechanism is based on a novel algorithm for sampling that enables an efficient implementation of the exponential mechanism for differential privacy (naive sampling is exponential time). It provides the security guarantee that an adversary will not be able to use this perturbed frequency list to learn anything of significance about any individual user’s password even if the adversary already possesses a wealth of background knowledge about the users in the dataset. We prove that our mechanism introduces minimal distortion, thus ensuring that the released frequency list is close to the actual list. Further, we empirically demonstrate, using the now-canonical password dataset leaked from RockYou, that the mechanism works well in practice: as the differential privacy parameter ɛ varies from 8 to 0.002 (smaller ɛ implies higher security), the normalized distortion coefficient (representing the distance between the released and actual password frequency list divided by the number of users N) varies from 8.8 × 10-7 to 1.9 × 10-3. Given this appealing combination of security and distortion guarantees, our mechanism enables organizations to publish perturbed password frequency lists. This can facilitate new research comparing password security between populations and evaluating password improvement approaches. To this end, we have collaborated with Yahoo! to use our differentially private mechanism to publicly release a corpus of 50 password frequency lists representing approximately 70 million Yahoo! users. This dataset is now the largest password frequency corpus available. Using our perturbed dataset we are able to closely replicate the original published analysis of this data.

Original languageEnglish (US)
Title of host publication23rd Annual Network and Distributed System Security Symposium, NDSS 2016
PublisherThe Internet Society
ISBN (Electronic)189156241X, 9781891562419
DOIs
StatePublished - 2016
Event23rd Annual Network and Distributed System Security Symposium, NDSS 2016 - San Diego, United States
Duration: Feb 21 2016Feb 24 2016

Publication series

Name23rd Annual Network and Distributed System Security Symposium, NDSS 2016

Conference

Conference23rd Annual Network and Distributed System Security Symposium, NDSS 2016
Country/TerritoryUnited States
CitySan Diego
Period2/21/162/24/16

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Control and Systems Engineering
  • Safety, Risk, Reliability and Quality

Fingerprint

Dive into the research topics of 'Differentially Private Password Frequency Lists Or, How to release statistics from 70 million passwords (on purpose)'. Together they form a unique fingerprint.

Cite this