1. A New Distribution-Sensitive Secure Sketch and Popularity-Proportional Hashing 2017 Crypto Hashing
    Joanne Woodage and Rahul Chatterjee and Yevgeniy Dodis and Ari Juels and Thomas Ristenpart
    [View PDF on eprint.iacr.org]
    [Show BibTex Citation]

    @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, Report 2017/542},
    year = {2017},
    note = {\url{https://eprint.iacr.org/2017/542}},
    }

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.

  1.