Shuffling has been shown to amplify differential privacy guarantees, enabling a more favorable privacy-utility trade-off. To characterize and compute this amplification, two fundamental analytical frameworks have been proposed: the \emph{privacy blanket} by Balle et al. (CRYPTO 2019) and the \emph{clone}--including both the standard and stronger variant--by Feldman et al. (FOCS 2021, SODA 2023). These frameworks share a common foundation: decomposing local randomizers into structured components for analysis. In this work, we introduce a unified analytical framework--the general clone paradigm--which subsumes all possible decompositions, with the clone and blanket decompositions arising as special cases. Within this framework, we identify the optimal decomposition, which is precisely the one used by the privacy blanket. Moreover, we develop a simple and efficient algorithm based on the Fast Fourier Transform (FFT) to compute optimal privacy amplification bounds. Experimental results show that our computed upper bounds nearly match the lower bounds, demonstrating the tightness of our method. Building on this method, we also derive optimal amplification bounds for both \emph{joint} and \emph{parallel} compositions of LDP mechanisms in the shuffle model.

Passwords are widely used for website authentication, but they are vulnerable to guessing attacks. To measure password guessability, the commonly used approach involves modeling the distribution of passwords with a password probability model and then estimating the guessability using Monte Carlo methods based on the model. We found that users’ passwords are closely linked to their usernames. However, few password models proposed by previous research consider this connection, which significantly overestimates the security of passwords and can result in inadequate security measures, potentially leading to data breaches and financial losses. In this paper, we propose a new category of password model called username-password model, which models the conditional probability of passwords given usernames. We also provide an instance of the username-password model using Transformer (TUPM). The experimental results of guessing attacks show that TUPM outperforms other password models in terms of crack rate across any number of guesses (up to 1020). Notably, TUPM cracks 100%–175% more passwords compared to the state-of-the-art models, within the first 1,000 guesses. This indicates that TUPM can provide a more accurate estimation of password guessability.

With the increasing prevalence of personal information breaches, targeted password guessing based on user-specific data has emerged as a serious security threat. Existing targeted password guessing attacks primarily rely on traditional statistical language models, which have limited capability in addressing the complexities of password structures and user behavior. Recent advancements in neural language models, particularly Transformer-based architectures, have achieved significant success in natural language processing tasks by capturing complex patterns and dependencies. However, their potential for improving targeted password guessing remains largely unexplored.To address this gap, we conduct a systematic evaluation of several widely used neural language models from NLP and assess their effectiveness in targeted password guessing. Experimental results on multiple real-world password datasets show that neural language models outperform existing approaches. Our proposed models achieve an improvement of 1.4%–4.6% compared to RFGuess-PII model, and 18%–40% compared to TarPCFG model. This work provides new insights into the potential of neural language models to enhance the effectiveness of targeted password guessing attacks.

Password guessing attack is a significant threat to account security. Understanding this attack is crucial for identifying the vulnerabilities of current password systems and for developing more effective methods to protect user accounts. Adaptive password guessing techniques can dynamically adjust their strategies based on cracked passwords, resulting in improved performance under varying password distributions. However, existing adaptive password guessing models are typically trained on a single password dataset and attempt to crack a target website through dynamic adjustments. In recent years, the number of leaked password datasets has increased significantly. To fully leverage the diversity of various datasets and accurately assess the threat of password guessing, we propose an adaptive password guessing framework that employs a transformer architecture capable of learning multiple password distributions from various datasets and generate password guesses adaptively for the target. Through experiments involving 29 real-world leaked password datasets, we demonstrate that our framework achieves an average improvement of 44.63% over the state-of-the-art adaptive password guessing models.

Variational Autoencoder (VAE) has been used as password generative model for trawling attack in multiple works. Its sample distribution can be easily changed by controling the mean and variance of the prior distribution, which makes it natively suitable for dynamic attack scenario. Combining transformer blocks with VAE can achieve better performance since attention mechanisms can handle sequence data better. But such design is unstable for password generation tasks. The encoder-decoder model tends to degrade into decoder-only model due to the KL vanishing problem, making it hard to train. To handle this problem, we performed an in-depth analysis and proposed a new transformer-based VAE model specifically designed for password generation. It out-performs former encoder-decoder generative model by 4%–15% in cracking rate. Moreover, we make an improvement to dynamic attack by using a 3-period strategy, with which our method becomes competitive with probabilistic ordered attack models such as PCFG [11] and FLA [8].

Modeling password distributions is a fundamental problem in password security, benefiting the research and applications on password guessing, password strength meters, honey password vaults, etc. As one of the best segment-based password models, WordPCFG has been proposed to capture individual semantic segments (called words) in passwords. However, we find WordPCFG does not address well the ambiguity of password segmentation by maximum matching, leading to the unreasonable segmentation of many password and further the inaccuracy of modeling password distributions. To address the ambiguity, we improve WordPCFG by maximum probability segmentation with A*-like pruning algorithm. The experimental results show that the improved WordPCFG cracks 99.26%–99.95% passwords, with nearly 5.67%–18.01% improvement.

Passwords have been widely used in online authentication, and they form the front line that protects our data security and privacy. But the security of password may be easily harmed by insecure password generator. Massive reports state that users are always keen to generate new passwords by reusing or fine-tuning old secrets. Once an old password is leaked, the users may suffer from credential tweaking attacks. We propose a password reuse model PassTrans and simulate credential tweaking attacks. We evaluate the performance in leaked password datasets, and the results show that 67.51% of accounts is breakable under 1,000 guesses, indicating our model is accurate in capturing password reuse behavior.

To date there are few researches on the semantic information of passwords, which leaves a gap preventing us from fully understanding the passwords characteristic and security. We propose a new password probability model for semantic information based on Markov Chain with both generalization and accuracy, called WordMarkov, that can capture the semantic essence of password samples. Further, we evaluate our design via password guessing attacks, on six real-world datasets, and we show that WordMarkov obtains 24.29%–67.37% improvement over the state-of-the-art password probability models. Even more surprising is that WordMarkov achieves 75.35%–96.34% attack improvement on "long" passwords, indicating the importance of semantic parts in long passwords.

Probabilistic context-free grammars (PCFGs) have been pro-posed to capture password distributions, and further been used in password guessing attacks and password strength meters. However, current PCFGs suffer from the limitation of inaccurate segmentation of password, which leads to misestimation of password probability and thus seriously affects their performance. In this paper, we propose a word extraction approach for passwords, and further present an improved PCFG model, called WordPCFG. The WordPCFG using word extraction method can precisely extract semantic segments (called word) from passwords based on cohesion and freedom of words. We evaluate our WordPCFG on six large-scale datasets, showing that WordPCFG cracks 83.04%–95.47% passwords and obtains 12.96%–71.84% improvement over the state-of-the-art PCFGs.

Multi-factor authentication (MFA) has been widely used to safeguard high-value assets. Unlike single-factor authentication (e.g., password-only login), t-factor authentication ( tFA) requires a user always to carry and present t specified factors so as to strengthen the security of login. Nevertheless, this may restrict user experience in limiting the flexibility of factor usage, e.g., the user may prefer to choose any factors at hand for login authentication. To bring back usability and flexibility without loss of security, we introduce a new notion of authentication, called (t,n) threshold MFA, that allows a user to actively choose t factors out of n based on preference. We further define the “most-rigorous” multi-factor security model for the new notion, allowing attackers to control public channels, launch active/passive attacks, and compromise/corrupt any subset of parties as well as factors. We state that the model can capture the most practical security needs in the literature. We design a threshold MFA key exchange (T-MFAKE) protocol built on the top of a threshold oblivious pseudorandom function and an authenticated key exchange protocol. Our protocol achieves the “highest-attainable” security against all attacking attempts in the context of parties/factors being compromised/corrupted. As for efficiency, our design only requires 4+t exponentiations, 2 multi-exponentiations and2communication rounds. Compared with existing tFA schemes, even the degenerated (t,t) version of our protocol achieves the strongest security (stronger than most schemes) and higher efficiency on computational and communication. We instantiate our design on real-world platform to highlight its practicability and efficiency.

We present in this paper an alternative method for understanding user-chosen passwords. In password research, much attention has been given to increasing the security and usability of individual passwords for common users. Few of them focus on the relationships between passwords; therefore we explore the relationships between passwords: modification-based, similarity-based, and probability-based. By regarding passwords as vertices, we shed light on how to transform a dataset of passwords into a password graph. Subsequently, we introduce some novel notions from graph theory and report on a number of inner properties of passwords from the perspective of graph. With the assistance of Python Graph-tool, we are able to visualize our password graph to deliver an intuitive grasp of user-chosen passwords. Five real-world password datasets are used in our experiments to fulfill our thorough experiments. We discover that (1) some passwords in a dataset are tightly connected with each other; (2) they have the tendency to gather together as a cluster like they are in a social network; (3) password graph has logarithmic distribution for its degrees. Top clusters in password graph could be exploited to obtain the effective mangling rules for cracking passwords. Also, password graph can be utilized for a new kind of password strength meter.

Despite three decades of intensive research efforts, it remains an open question as to what is the underlying distribution of user-generated passwords. In this paper, we make a substantial step forward toward understanding this foundational question. By introducing a number of computational statistical techniques and based on 14 large-scale data sets, which consist of 113.3 million real-world passwords, we, for the first time, propose two Zipf-like models (i.e., PDF-Zipf and CDF-Zipf) to characterize the distribution of passwords. More specifically, our PDF-Zipf model can well fit the popular passwords and obtain a coefficient of determination larger than 0.97; our CDF-Zipf model can well fit the entire password data set, with the maximum cumulative distribution function (CDF) deviation between the empirical distribution and the fitted theoretical model being 0.49%~4.59% (on an average 1.85%). With the concrete knowledge of password distributions, we suggest a new metric for measuring the strength of password data sets. Extensive experimental results show the effectiveness and general applicability of the proposed Zipf-like models and security metric.

Despite over two decades of continuous efforts, how to design a secure and efficient two-factor authentication scheme remains an open issue. Hundreds of new schemes have wave upon wave been proposed, yet most of them are shortly found unable to achieve some important security goals (e.g., truly two-factor security) and desirable properties (e.g., user anonymity), falling into the unsatisfactory "break-fix-break-fix" cycle. In this vicious cycle, protocol designers often advocate the superiorities of their improved scheme, but do not illustrate (or unconsciously overlooking) the aspects on which their scheme performs poorly. In this paper, we first use a series of "improved schemes" over Xu et al.'s 2009 scheme as case studies to highlight that, if there are no improved measurements, more "improved schemes" generally would not mean more advancements. To figure out why the measurement of existing schemes is invariably insufficient, we further investigate into the state-of-the-art evaluation criteria set (i.e., Madhusudhan-Mittal's set). Besides reporting its ambiguities and redundancies, we propose viable fixes and refinements. To our knowledge, we for the first time show that there are at least seven different attacking scenarios that may lead to the failure of a scheme in achieving truly two-factor security. Finally, we conduct a large-scale comparative evaluation of 26 representative two-factor schemes, and our results outline the request for better measurement when assessing new schemes.

To provide timely feedbacks to users, nearly every respectable Internet service now imposes a password strength meter (PSM) upon user registration or password change. It is a rare bit of good news in password research that well-designed PSMs do help improve the strength of user-chosen passwords. However, leading PSMs in the industrial world (e.g., Zxcvbn, KeePSM and NIST PSM) are mainly composed of simple heuristic rules and found to be highly inaccurate, while state-of-the-art PSMs from academia (e.g., probabilistic context-free grammar based ones and Markov-based ones) are still far from satisfactory, especially incompetent at gauging weak passwords. As preventing weak passwords is the primary goal of any PSM, this means that existing PSMs largely fail to serve their purpose. To fill this gap, in this paper we propose a novel PSM that is grounded on real user behavior. Our user survey reveals that when choosing passwords for a new web service, most users (77.38%) simply retrieve one of their existing passwords from memory and then reuse (or slightly modify) it. This is in vast contrast to the seemingly intuitive yet unrealistic assumption (often implicitly) made in most of the existing PSMs that, when user registers, a whole new password is constructed by mixing segments of letter, digit and/or symbol or by combining n-grams. To model users' realistic behaviors, we use passwords leaked from a less sensitiveservice as our base dictionary and another list of relatively strong passwords leaked from a sensitive service as our training dictionary, and determine how mangling rules are employed by users to construct passwords for new services. This process automatically creates a fuzzy probabilistic context-free grammar (PCFG) and gives rise to our fuzzy-PCFG-based meter, fuzzyPSM. It can react dynamically to changes in how users choose passwords and is evaluated by comparisons with five representative PSMs. Extensive experiments on 11 real-world password lists show that fuzzyPSM, in general, outperforms all its counterparts, especially accurate in telling apart weak passwords and suitable for services where online guessing attacks prevail.