Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

A central challenge in password security is to characterize the attacker's guessing curve i.e., what is the probability that the attacker will crack a random user's password within the first G guesses. A key challenge is that the guessing curve depends on the attacker's guessing strategy and the distribution of user passwords both of which are unknown to us. In this work we aim to follow Kerckhoffs's principal and analyze the performance of an optimal attacker who knows the password distribution. Let \lambda_G denote the probability that such an attacker can crack a random user's password within G guesses. We develop several statistically rigorous techniques to upper and lower bound \lambda_G given N independent samples from the unknown password distribution P. We show that our upper/lower bounds on \lambda_G hold with high confidence and we apply our techniques to analyze eight large password datasets. Our empirical analysis shows that even stateoftheart password cracking models are often significantly less guess efficient than an attacker who can optimize its attack based on its (partial) knowledge of the password distribution. We also apply our statistical tools to reexamine different models of the password distribution i.e., the empirical password distribution and Zipf's Law. We find that the empirical distribution closely matches our upper/lower bounds on \lambda_G when the guessing number G is not too large i.e., G << N. However, for larger values of G our empirical analysis rigorously demonstrates that the empirical distribution (resp. Zipf's Law) overestimates the attacker's success rate. We apply our statistical techniques to upper/lower bound the effectiveness of password throttling mechanisms (keystretching) which are used to reduce the number of attacker guesses G. Finally, if we are willing to make an additional assumption about the way users respond to password restrictions, we can use our statistical techniques to evaluate the effectiveness of various password composition policies which restrict the passwords that users may select.more » « less

Largescale online password guessing attacks are widespread and pose a persistant privacy and security threat to users. The common method for mitigating the risk of online cracking is to lock out the user after a fixed number ($K$) of consecutive incorrect login attempts. Selecting the value of $K$ induces a classic securityusability tradeoff. When $K$ is too large, a hacker can (quickly) break into a significant fraction of user accounts, but when $K$ is too low, we will start to annoy honest users by locking them out after a few mistakes. Motivated by the observation that honest user mistakes typically look quite different from an online attacker's password guesses, we introduce $\DALock$, a {\em distributionaware} password lockout mechanism to reduce user annoyance while minimizing user risk. As the name suggests, $\DALock$ is designed to be aware of the frequency and popularity of the password used for login attacks. At the same time, standard throttling mechanisms (e.g., $K$strikes) are oblivious to the password distribution. In particular, $\DALock$ maintains an extra ``hit count" in addition to ``strike count" for each user, which is based on (estimates of) the cumulative probability of {\em all} login attempts for that particular account. We empirically evaluate $\DALock$ with an extensive battery of simulations using realworld password datasets. In comparison with the traditional $K$strikes mechanism, {our simulations indicate that} $\DALock$ offers a superior {simulated} security/usability tradeoff. For example, in one of our simulations, we are able to reduce the success rate of an attacker to $0.05\%$ (compared to $1\%$ for the $3$strikes mechanism) whilst simultaneously reducing the unwanted lockout rate for accounts that are not under attack to just $0.08\%$ (compared to $4\%$ for the $3$strikes mechanism).more » « less

We formally introduce, define, and construct {\em memoryhard puzzles}. Intuitively, for a difficulty parameter $t$, a cryptographic puzzle is memoryhard if any parallel random access machine (PRAM) algorithm with ``small'' cumulative memory complexity ($\ll t^2$) cannot solve the puzzle; moreover, such puzzles should be both ``easy'' to generate and be solvable by a sequential RAM algorithm running in time $t$. Our definitions and constructions of memoryhard puzzles are in the standard model, assuming the existence of indistinguishability obfuscation (\iO) and oneway functions (OWFs), and additionally assuming the existence of a {\em memoryhard language}. Intuitively, a language is memoryhard if it is undecidable by any PRAM algorithm with ``small'' cumulative memory complexity, while a sequential RAM algorithm running in time $t$ can decide the language. Our definitions and constructions of memoryhard objects are the first such definitions and constructions in the standard model without relying on idealized assumptions (such as random oracles). We give two applications which highlight the utility of memoryhard puzzles. For our first application, we give a construction of a (onetime) {\em memoryhard function} (MHF) in the standard model, using memoryhard puzzles and additionally assuming \iO and OWFs. For our second application, we show any cryptographic puzzle (\eg, memoryhard, timelock) can be used to construct {\em resourcebounded locally decodable codes} (LDCs) in the standard model, answering an open question of Blocki, Kulkarni, and Zhou (ITC 2020). Resourcebounded LDCs achieve better rate and locality than their classical counterparts under the assumption that the adversarial channel is resource bounded (e.g., a lowdepth circuit). Prior constructions of MHFs and resourcebounded LDCs required idealized primitives like random oracles.more » « less

The Schnorr signature scheme is an efficient digital signature scheme with short signature lengths, i.e., $4k$bit signatures for $k$ bits of security. A Schnorr signature $\sigma$ over a group of size $p\approx 2^{2k}$ consists of a tuple $(s,e)$, where $e \in \{0,1\}^{2k}$ is a hash output and $s\in \mathbb{Z}_p$ must be computed using the secret key. While the hash output $e$ requires $2k$ bits to encode, Schnorr proposed that it might be possible to truncate the hash value without adversely impacting security. In this paper, we prove that \emph{short} Schnorr signatures of length $3k$ bits provide $k$ bits of multiuser security in the (Shoup's) generic group model and the programmable random oracle model. We further analyze the multiuser security of keyprefixed short Schnorr signatures against preprocessing attacks, showing that it is possible to obtain secure signatures of length $3k + \log S + \log N$ bits. Here, $N$ denotes the number of users and $S$ denotes the size of the hint generated by our preprocessing attacker, e.g., if $S=2^{k/2}$, then we would obtain secure $3.75k$bit signatures for groups of up to $N \leq 2^{k/4}$ users. Our techniques easily generalize to several other FiatShamirbased signature schemes, allowing us to establish analogous results for ChaumPedersen signatures and KatzWang signatures. As a building block, we also analyze the $1$outof$N$ discretelog problem in the generic group model, with and without preprocessing.more » « less

We introduce password strength signaling as a potential defense against password cracking. Recent breaches have exposed billions of user passwords to the dangerous threat of offline password cracking attacks. An offline attacker can quickly check millions (or sometimes billions/trillions) of password guesses by comparing a candidate password’s hash value with a stolen hash from a breached authentication server. The attacker is limited only by the resources he is willing to invest. We explore the feasibility of applying ideas from Bayesian Persuasion to password authentication. Our key idea is to have the authentication server store a (noisy) signal about the strength of each user password for an offline attacker to find. Surprisingly, we show that the noise distribution for the signal can often be tuned so that a rational (profitmaximizing) attacker will crack fewer passwords. The signaling scheme exploits the fact that password cracking is not a zerosum game i.e., it is possible for an attacker to increase their profit in a way that also reduces the number of cracked passwords. Thus, a welldefined signaling strategy will encourage the attacker to reduce his guessing costs by cracking fewer passwords. We use an evolutionary algorithm to compute the optimal signaling scheme for the defender. We evaluate our mechanism on several password datasets and show that it can reduce the total number of cracked passwords by up to 12% (resp. 5%) of all users in defending against offline (resp. online) attacks. While the results of our empirical analysis are positive we stress that we view the current solution as a proofofconcept as there are important societal concerns that would need to be considered before adopting our password strength signaling solution.more » « less

Tessaro, Stefano (Ed.)A Proof of Sequential Work (PoSW) allows a prover to convince a resourcebounded verifier that the prover invested a substantial amount of sequential time to perform some underlying computation. PoSWs have many applications including timestamping, blockchain design, and universally verifiable CPU benchmarks. Mahmoody, Moran, and Vadhan (ITCS 2013) gave the first construction of a PoSW in the random oracle model though the construction relied on expensive depthrobust graphs. In a recent breakthrough, Cohen and Pietrzak (EUROCRYPT 2018) gave an efficient PoSW construction that does not require expensive depthrobust graphs. In the classical parallel random oracle model, it is straightforward to argue that any successful PoSW attacker must produce a long ℋsequence and that any malicious party running in sequential time T1 will fail to produce an ℋsequence of length T except with negligible probability. In this paper, we prove that any quantum attacker running in sequential time T1 will fail to produce an ℋsequence except with negligible probability  even if the attacker submits a large batch of quantum queries in each round. The proof is substantially more challenging and highlights the power of Zhandry’s recent compressed oracle technique (CRYPTO 2019). We further extend this result to establish postquantum security of a noninteractive PoSW obtained by applying the FiatShamir transform to Cohen and Pietrzak’s efficient construction (EUROCRYPT 2018).more » « less

Given a directed acyclic graph (DAG) G=(V,E), we say that G is (e,d)depthrobust (resp. (e,d)edgedepthrobust) if for any set S⊆V (resp. S⊆E) of at most S≤e nodes (resp. edges) the graph G−S contains a directed path of length d. While edgedepthrobust graphs are potentially easier to construct, many applications in cryptography require node depthrobust graphs with small indegree. We create a graph reduction that transforms an (e,d)edgedepthrobust graph with m edges into a (e/2,d)depthrobust graph with O(m) nodes and constant indegree. One immediate consequence of this result is the first construction of a provably (nloglognlogn,nlogn(logn)loglogn)depthrobust graph with constant indegree. Our reduction crucially relies on STrobust graphs, a new graph property we introduce which may be of independent interest. We say that a directed, acyclic graph with n inputs and n outputs is (k1,k2)STrobust if we can remove any k1 nodes and there exists a subgraph containing at least k2 inputs and k2 outputs such that each of the k2 inputs is connected to all of the k2 outputs. If the graph if (k1,n−k1)STrobust for all k1≤n we say that the graph is maximally STrobust. We show how to construct maximally STrobust graphs with constant indegree and O(n) nodes. Given a family M of STrobust graphs and an arbitrary (e,d)edgedepthrobust graph G we construct a new constantindegree graph Reduce(G,M) by replacing each node in G with an STrobust graph from M. We also show that STrobust graphs can be used to construct (tight) proofsofspace and (asymptotically) improved wideblock labeling functions.more » « less

Borisov, N. (Ed.)An attacker who breaks into an authentication server and steals all of the cryptographic password hashes is able to mount an offlinebrute force attack against each user’s password. Offline bruteforce attacks against passwords are increasingly commonplace and the danger is amplified by the well documented human tendency to select lowentropy password and/or reuse these passwords across multiple accounts. Moderately hard password hashing functions are often deployed to help protect passwords against offline attacks by increasing the attacker’s guessing cost. However, there is a limit to how “hard” one can make the password hash function as authentication servers are resource constrained and must avoid introducing substantial authentication delay. Observing that there is a wide gap in the strength of passwords selected by different users we introduce DAHash (Distribution Aware Password Hashing) a novel mechanism which reduces the number of passwords that an attacker will crack. Our key insight is that a resourceconstrained authentication server can dynamically tune the hardness parameters of a password hash function based on the (estimated) strength of the user’s password. We introduce a Stackelberg game to model the interaction between a defender (authentication server) and an offline attacker. Our model allows the defender to optimize the parameters of DAHash e.g., specify how much effort is spent in hashing weak/moderate/high strength passwords. We use several large scale password frequency datasets to empirically evaluate the effectiveness of our differentiated cost password hashing mechanism. We find that the defender who uses our mechanism can reduce the fraction of passwords that would be cracked by a rational offline attacker by up to 15%.more » « less

null (Ed.)Memory hard functions (MHFs) are an important cryptographic primitive that are used to design egalitarian proofs of work and in the construction of moderately expensive keyderivation functions resistant to bruteforce attacks. Broadly speaking, MHFs can be divided into two categories: datadependent memory hard functions (dMHFs) and dataindependent memory hard functions (iMHFs). iMHFs are resistant to certain sidechannel attacks as the memory access pattern induced by the honest evaluation algorithm is independent of the potentially sensitive input e.g., password. While dMHFs are potentially vulnerable to sidechannel attacks (the induced memory access pattern might leak useful information to a bruteforce attacker), they can achieve higher cumulative memory complexity (CMC) in comparison than an iMHF. In particular, any iMHF that can be evaluated in N steps on a sequential machine has CMC at most 𝒪((N^2 log log N)/log N). By contrast, the dMHF scrypt achieves maximal CMC Ω(N^2)  though the CMC of scrypt would be reduced to just 𝒪(N) after a sidechannel attack. In this paper, we introduce the notion of computationally dataindependent memory hard functions (ciMHFs). Intuitively, we require that memory access pattern induced by the (randomized) ciMHF evaluation algorithm appears to be independent from the standpoint of a computationally bounded eavesdropping attacker  even if the attacker selects the initial input. We then ask whether it is possible to circumvent known upper bound for iMHFs and build a ciMHF with CMC Ω(N^2). Surprisingly, we answer the question in the affirmative when the ciMHF evaluation algorithm is executed on a twotiered memory architecture (RAM/Cache). We introduce the notion of a krestricted dynamic graph to quantify the continuum between unrestricted dMHFs (k=n) and iMHFs (k=1). For any ε > 0 we show how to construct a krestricted dynamic graph with k=Ω(N^(1ε)) that provably achieves maximum cumulative pebbling cost Ω(N^2). We can use krestricted dynamic graphs to build a ciMHF provided that cache is large enough to hold k hash outputs and the dynamic graph satisfies a certain property that we call "amenable to shuffling". In particular, we prove that the induced memory access pattern is indistinguishable to a polynomial time attacker who can monitor the locations of read/write requests to RAM, but not cache. We also show that when k=o(N^(1/log log N)) , then any krestricted graph with constant indegree has cumulative pebbling cost o(N^2). Our results almost completely characterize the spectrum of krestricted dynamic graphs.more » « less

Recent efforts in coding theory have focused on building codes for insertions and deletions, called insdel codes, with optimal tradeoffs between their redundancy and their errorcorrection capabilities, as well as {\em efficient} encoding and decoding algorithms. In many applications, polynomial running time may still be prohibitively expensive, which has motivated the study of codes with {\em superefficient} decoding algorithms. These have led to the wellstudied notions of Locally Decodable Codes (LDCs) and Locally Correctable Codes (LCCs). Inspired by these notions, Ostrovsky and PaskinCherniavsky (Information Theoretic Security, 2015) generalized Hamming LDCs to insertions and deletions. To the best of our knowledge, these are the only known results that study the analogues of Hamming LDCs in channels performing insertions and deletions. Here we continue the study of insdel codes that admit local algorithms. Specifically, we reprove the results of Ostrovsky and PaskinCherniavsky for insdel LDCs using a different set of techniques. We also observe that the techniques extend to constructions of LCCs. Specifically, we obtain insdel LDCs and LCCs from their Hamming LDCs and LCCs analogues, respectively. The rate and errorcorrection capability blow up only by a constant factor, while the query complexity blows up by a poly log factor in the block length. Since insdel locally decodable/correctble codes are scarcely studied in the literature, we believe our results and techniques may lead to further research. In particular, we conjecture that constantquery insdel LDCs/LCCs do not exist.more » « less