Paper 2017/542

A New Distribution-Sensitive Secure Sketch and Popularity-Proportional Hashing

Joanne Woodage, Rahul Chatterjee, Yevgeniy Dodis, Ari Juels, and Thomas Ristenpart

Abstract

Motivated by typo correction in password authentication, we investigate cryptographic error-correction of secrets in settings where the distribution of secrets is a priori (approximately) known. We refer to this as the distribution-sensitive setting. We design a new secure sketch called the layer-hiding hash (LHH) that offers the best security to date. Roughly speaking, we show that LHH saves an additional log H_0(W) bits of entropy compared to the recent layered sketch construction due to Fuller, Reyzin, and Smith (FRS). Here H_0(W) is the size of the support of the distribution W. When supports are large, as with passwords, our new construction offers a substantial security improvement. We provide two new constructions of typo-tolerant password-based authentication schemes. The first combines a LHH or FRS sketch with a standard slow-to-compute hash function, and the second avoids secure sketches entirely, correcting typos instead by checking all nearby passwords. Unlike the previous such brute-force-checking construction, due to Chatterjee et al., our new construction uses a hash function whose run-time is proportional to the popularity of the password (forcing a longer hashing time on more popular, lower entropy passwords). We refer to this as popularity-proportional hashing (PPH). We then introduce a frame-work for comparing different typo-tolerant authentication approaches. We show that PPH always offers a better time / security trade-off than the LHH and FRS constructions, and for certain distributions outperforms the Chatterjee et al. construction. Elsewhere, this latter construction offers the best trade-off. In aggregate our results suggest that the best known secure sketches are still inferior to simpler brute-force based approaches.

Note: Added full version, and fixed error in title.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in CRYPTO 2017
Keywords
Secure sketchestypo-tolerant password authentication
Contact author(s)
joanne woodage 2014 @ rhul ac uk
History
2017-07-05: revised
2017-06-08: received
See all versions
Short URL
https://ia.cr/2017/542
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/542,
      author = {Joanne Woodage and Rahul Chatterjee and Yevgeniy Dodis and Ari Juels and Thomas Ristenpart},
      title = {A New Distribution-Sensitive Secure Sketch and Popularity-Proportional Hashing},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/542},
      year = {2017},
      url = {https://eprint.iacr.org/2017/542}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.