Name
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 framework 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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/978-3-319-63697-9_23 | ADVANCES IN CRYPTOLOGY - CRYPTO 2017, PT III |
Field | DocType | Volume |
Cryptography,Computer science,A priori and a posteriori,Popularity,Universal hashing,Theoretical computer science,Hash function,Password authentication protocol,Sketch | Conference | 10403 |
ISSN | Citations | PageRank |
0302-9743 | 1 | 0.34 |
References | Authors | |
17 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Joanne Woodage | 1 | 8 | 2.15 |
| Rahul Chatterjee | 2 | 45 | 8.47 |
| Yevgeniy Dodis | 3 | 5843 | 277.49 |
| Ari Juels | 4 | 7263 | 590.42 |
| Thomas Ristenpart | 5 | 3390 | 149.67 |