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)
- 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
-
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} }