11institutetext: Purdue University, West Lafayette IN, 47907, USA
11email: {bai104, jblocki<EMAIL_ADDRESS>
# Cost-Asymmetric Memory Hard
Password Hashing

Wenjie Bai 11 Jeremiah Blocki 11 Mohammad Hassan Ameri 11

###### Abstract

In the past decade billions of user passwords have been exposed to the
dangerous threat of offline password cracking attacks. An offline attacker who
has stolen the cryptographic hash of a user’s password can check as many
password guesses as s/he likes limited only by the resources that s/he is
willing to invest to crack the password. Pepper and key-stretching are two
techniques that have been proposed to deter an offline attacker by increasing
guessing costs. Pepper ensures that the cost of rejecting an incorrect
password guess is higher than the (expected) cost of verifying a correct
password guess. This is useful because most of the offline attacker’s guesses
will be incorrect. Unfortunately, as we observe the traditional peppering
defense seems to be incompatible with modern memory hard key-stretching
algorithms such as Argon2 or Scrypt. We introduce an alternative to pepper
which we call Cost-Asymmetric Memory Hard Password Authentication which
benefits from the same cost-asymmetry as the classical peppering defense i.e.,
the cost of rejecting an incorrect password guess is larger than the expected
cost to authenticate a correct password guess. When configured properly we
prove that our mechanism can only reduce the percentage of user passwords that
are cracked by a rational offline attacker whose goal is to maximize
(expected) profit i.e., the total value of cracked passwords minus the total
guessing costs. We evaluate the effectiveness of our mechanism on empirical
password datasets against a rational offline attacker. Our empirical analysis
shows that our mechanism can reduce significantly the percentage of user
passwords that are cracked by a rational attacker by up to $10\%$.

###### Keywords:

Memory Hard Functions Password Authentication Stackelberg Game.

##  1 Introduction

In the past decade data-breaches have exposed billions of user passwords to
the dangerous threat of offline password cracking. An offline attacker has
stolen the cryptographic hash $h_{u}=H(pw_{u},salt_{u})$ of a target user (u)
and can validate as many password guesses as s/he likes without getting locked
out i.e., given $h_{u}$ and $salt_{u}$111The salt value protects against pre-
computation attacks such as rainbow tables and ensures that the attacker must
crack each individual password separately. For example, even if Alice and Bob
select the same password $pw_{A}=pw_{B}$ their password hashes will almost
certainly be different i.e., $h_{A}=H(pw_{A},salt_{A})\neq
H(pw_{B},salt_{B})=h_{B}$ due to the different choice of values and collision
resistance of the cryptographic hash function $H$. the attacker can check if
$pw_{u}=pw^{\prime}$ by computing $h^{\prime}=H(pw^{\prime},salt_{u})$ and
comparing the hash value with $h_{u}$. Despite all of the security problems
text passwords remain entrenched as the dominant form of authentication online
and are unlikely to be replaced in the near future [16]. Thus, it is
imperitive to develop tools to deter offline attackers.

An offline attacker is limited only by the resources s/he is willing to invest
in cracking the password and a rational attacker will fix a guessing budget to
optimally balance guessing costs with the expected value of the cracked
passwords. Key-Stretching functions intentionally increase the cost of the
hash function $H$ to ensure that an offline attack is as expensive as
possible. Hash iteration is a simple technique to increase guessing costs
i.e., instead of storing $(u,salt_{u},h_{u}=H(pw_{u},salt_{u}))$ the
authentication server would store $(u,salt_{u},h_{u}=H^{t}(pw_{u},salt_{u}))$
where $H^{i+1}(x)\vcentcolon=H(H^{i}(x))$ and $H^{1}(x)\vcentcolon=H(x)$. Hash
iteration is the traditional key-stretching method which is used by password
hashing algorithms such as PBKDF2 [27] and BCRYPT [37]. Intuitively, the cost
of evaluating a function like PBKDF2 or BCRYPT scales linearly with the hash-
iteration parameter $t$ which, in turn, is directly correlated with
authentication delay. Cryptocurrencies have hastened the development of
Application Specific Integrated Circuits (ASICs) to rapidly evaluate
cryptographic hash functions such as SHA2 and SHA3 since mining often involves
repeated evaluation of a hash function $H(\cdot)$. In theory an offline
attacker could use ASICs to substantially reduce the cost of checking password
guesses. In fact, Blocki et al. [12] argued that functions like BCRYPT or
PBKDF2 cannot provide adequate protection against an offline attacker without
introducing an unacceptable authentication delay e.g., $2$ minutes.

Memory-Hard Functions (MHFs) [36] have been introduced to address the short-
comings of hash-iteration based key-stretching algorithms like BCRYPT and
PBKDF2. Candidate MHFs include SCRYPT [36], Argon2 (which was declared as the
winner of Password Hashing Competition [2] in 2015) and DRSample [5].
Intuitively, a password hash function is memory hard if any algorithm
evaluating this function must lock up large quantities of memory for the
duration of computation. One advantage of this approach is that RAM is an
expensive resource even on an ASIC leading to egalitarian costs i.e., the
attacker cannot substantially reduce the cost of evaluating the hash function
using customized hardware. The second advantage is that the Area-Time cost
associated with a memory hard function can scale quadratically in the running
time parameter $t$. Intuitively, the honest party can evaluate the hash
function $\mathsf{MHF}(\cdot;t)$ in time $t$, while any attacker evaluating
the function must lock up $t$ blocks of memory for $t$ steps i.e., the Area-
Time cost is $t^{2}$. The running time parameter $t$ is constrained by user
patience as we wish to avoid introducing an unacceptably long delay while the
honest authentication server evaluates the password hash function during user
authentication. Thus, quadratic cost scaling is desireable as it allows an
authentication server to increase password guessing costs rapidly without
necessarily introducing an unacceptable authentication delay.

Peppering [33] is an alternative defense against an offline password attacker.
Intuitively, the idea is for a server to store
$(u,salt_{u},h_{u}=H(pw_{u},salt_{u},x_{u}))$. Unlike the random salt value
$salt_{u}$, the random pepper value $x_{u}\in[1,x_{max}]$ is not stored on the
authentication server. Thus, to verify a password guess $pw^{\prime}$ the
authentication server must compute $h_{1}=H(pw^{\prime},salt_{u},1),\ldots
h_{x_{max}}=H(pw^{\prime},salt_{u},x_{max})$. If $pw^{\prime}=pw_{u}$ then we
will have $h_{x_{u}}=h_{u}$ and authentication will succeed. On the other
hand, if $pw^{\prime}\neq pw_{u}$ then we will have $h_{i}\neq h_{u}$ for all
$i\leq x_{max}$ and authentication will fail. In the first case (correct
login) the authentication server will not need to compute
$h_{i}=H(pw^{\prime},salt_{u},i)$ for any $i>x_{u}$, while in the second case
(incorrect guess) the authentication server will need to evaluate $h_{i}$ for
every $i\leq x_{max}$. Thus, the expected cost to verify a correct password
guess is lower than the cost of rejecting an incorrect password guess. This
can be a desirable property as a password attacker will spend most of his time
eliminating incorrect password guesses, while most of the login attempts sent
to the authentication server will be correct.

A natural question is whether or not we can combine peppering with Memory Hard
Functions to obtain both benefits: quadratic cost scaling and cost-asymmetry.

###### Question 1

Can we design a password authentication mechanism that incorporates cost-
asymmetry into ASIC resistant Memory Hard Functions while having the benefits
of fully quadratic cost scaling under the the constraints of authentication
delay and expected workload?

Naive Approach: At first glance it seems trivial to integrate pepper with a
memory hard function $\mathsf{MHF}(\cdot)$ e.g., when a new user $u$ registers
with password $pw_{u}$ we can simply pick our random pepper
$x_{u}\in[1,x_{max}]$, salt $salt_{u}$, compute
$h_{u}=\mathsf{MHF}(pw_{u},salt_{u},x_{u};t)$ and store the tuple
$(u,salt_{u},h_{u})$. Unfortunately, the solution above is overly simplistic.
How should this parameter be set? We first observe that the authenication
delay for our above solution can be as large as $t\cdot x_{max}$ since we may
need to compute $\mathsf{MHF}(pw,salt_{u},x;t)$ for every value of
$x\in[1,x_{max}]$ and this computation must be carried out sequentially to
reap the cost-asymmetry benefits of pepper. Similarly, the Area-Time cost for
the attacker to evaluate $\mathsf{MHF}(pw,salt_{u},x;t)$ for every value of
$x\in[1,x_{max}]$ would scale with $t^{2}\cdot x_{max}$. This may seem
reasonable at first glance, but what if the authentication server had not used
pepper and instead stored $h_{u}=\mathsf{MHF}(pw_{u},salt_{u};t\cdot x_{max})$
using the running time parameter $t^{\prime}=t\cdot x_{max}$? In this case the
authentication delay is identical, but the attacker’s Area-Time cost would be
$t^{\prime 2}=t^{2}\cdot x_{max}^{2}$ — an increase of $x_{max}$ in comparison
to the naive solution. Thus, the naive approach to integrate pepper and memory
hard functions loses much of the benefit of quadratic scaling.

Halting Puzzles: Boyen [17] introduced the notion of a halting puzzle where
the “pepper” value is replaced with a random running time parameter. In
particular, when a new user $u$ registers with a password $pw_{u}$ we can pick
our random running time parameter $t_{u}\in[1,t_{max}]$ along with $salt_{u}$
and store $(u,salt_{u},h_{u})$ where
$h_{u}=\mathsf{MHF}(pw_{u},salt_{u};t_{u})$. Given a password guess
$pw^{\prime}$ the authentication server will locate $salt_{u},h_{u}$ and
accept if and only if $h_{u}=\mathsf{MHF}(pw^{\prime},salt_{u};t)$ for some
$t\in[1,t_{max}]$. All memory hard functions $\mathsf{MHF}(w;t)$ we are aware
of generate a stream of data-labels $L_{1},\ldots,L_{t}$ where
$L_{i}=\mathsf{MHF}(w;i)$ and $L_{i+1}$ can be computed quickly once the prior
labels $L_{1},\ldots,L_{i}$ are all stored in memory. Thus, whenever the user
attempts to login with password $pw_{u}^{\prime}$ the honest server can simply
start computing $\mathsf{MHF}(pw_{u}^{\prime},salt_{u};t_{max})$ to generate a
stream of labels $L_{1}^{\prime},L_{2}^{\prime},\ldots$ and immediately accept
if we find some label $i\leq t$ which matches the password hash i.e.,
$L_{i}=h_{u}$. Observe that whenever the user enters the correct password
$pw_{u}^{\prime}=pw_{u}$ the honest authentication server will be able to halt
early after just $t_{u}\leq t_{max}$ iterations. By constrast, the only way to
definitely reject an incorrect password $pw_{u}^{\prime}$ is to finish
computing $\mathsf{MHF}(pw_{u}^{\prime},salt_{u};i)$. The authentication delay
is at most $t_{max}$ and it seems like the attacker’s area-time cost will
scale quadratically i.e., $t_{max}^{2}$. Thus, the solution ostensibly seems
to benefit from quadratic cost scaling and cost-asymmetry.

However, we observe that an attacker might not choose to compute the entire
function $\mathsf{MHF}(pw^{\prime},salt_{u};t)$ for each password guess. For
example, suppose that the running time parameter $t_{u}$ is selected uniformly
at random in the range $[1,t_{max}]$, but for each password guess
$pw^{\prime}$ in the attacker’s dictionary the attacker only computes
$\mathsf{MHF}(pw^{\prime},salt_{u};t_{max}/3)$. The attacker’s area-time cost
per password guess ($t_{max}^{2}/9$) would decrease by a factor of $9$, but
the attacker’s success rate only diminishes by a factor of $1/3$ — the
probability that $t_{u}\in[1,t_{max}/3]$. Motivated by this observation there
are several natural questions to ask. First, can we model how a rational
offline attacker would adapt his approach to deal with halting puzzles?
Second, if $t_{u}$ is picked uniformly at random is it possible that the
solution could have an adverse impact i.e., could we unintentionally increase
the number of passwords cracked by a rational (profit-maximizing) attacker?
Finally, can we find the optimal distribution over $t_{u}$ which minimizes the
success rate of a rational offline attacker subject to constraints on
(amortized) server workload and maximum authentication delay.

###  1.1 Our contributions

We introduce Cost-Asymmetric Memory Hard Password Hashing, an extention of
Boyen’s halting puzzles which can only decrease the number of passwords
cracked by a rational password cracking attacker. Our key modification is to
introduce cost-even breakpoints as random running time parameters i.e., we fix
$m$ values $t_{1}\leq\ldots\leq t_{m}=t$ such that $t_{m}^{2}=t_{i}^{2}(m/i)$
for all $1\leq i<m$. Now instead of selecting $x_{u}$ randomly in the range
$[1,t]$ (time-even breakpoints) we pick $x_{u}\in\\{t_{1},\ldots,t_{m}\\}$. We
can either select $x_{u}\in\\{t_{1},\ldots,t_{m}\\}$ uniformly at random or,
if desired, we can optimize the distribution in an attempt to minimize the
expected number of passwords that the adversary breaks. Then the
authentication server computes $h_{u}=\mathsf{MHF}(pw_{u},salt_{u};x_{u})$ and
store the tuple $(u,salt_{u},h_{u})$ as the record for user $u$.

We adapt the Stackelberg game theoretic framework of Blocki and Datta[10] to
model the behavior of a rational pasword cracking attacker when the
authentication server uses Cost-Asymmetric Memory Hard Password Hashing. In
this model the attacker obtains a reward $v$ for every cracked password and
will choose a strategy which maximizes its expected utility — expected reward
minus expected guessing costs. One of the main challenges in our setting is
that the attacker’s action space is exponential in the size of the support of
the password distribution. For each password $pw$ the attacker can chose to
ignore the password, partially check the password or competely check the
password. We define efficient algorithms to find a locally optimal strategy
for the attacker and identify conditions under which the strategy is also a
global optimum (these conditions are satisfied in almost all of our empirical
experiments). We can then use black-box optimization to search for a
distribution over $x_{u}$ which minimizes the number of passwords cracked by
our utility maximizing attacker.

When $x_{u}\in\\{t_{1},\ldots,t_{m}\\}$ is selected uniformly at random we
prove that cost-even breakpoints will only reduce the number of passwords
cracked by a rational attacker. By contrast, we provide examples where time-
even breakpoints increases the number of passwords that are cracked — some of
these examples are based on empirical password distributions.

We empirically evaluate the effectiveness of our mechanism with 8 large
password datasets. Our analysis shows that we can reduce the fraction of
cracked passwords by up to 10% by adopting cost-asymmetric memory hard
password hashing with cost-even breakpoints sampled from uniform distribution.
In addition, our analysis demonstrates that the benefit of optimizing the
distribution over $x_{u}$ is marginal. Optimizing the distribution over the
breakpoints $t_{1},\ldots,t_{m}$ requires us to accurately estimate many key
parameters such as the attacker’s value $v$ for cracked passwords and the
probability of each password in the user password distribution. If our
estimates are inaccurate then we could unintentionally increase the number of
cracked passwords. Thus, we recommend instantiating Cost-Asymmetric Memory
Hard Password Hashing with the uniform distribution over our cost-even
breakpoints $t_{1},\ldots,t_{m}$ as a _prior independent_ password
authentication mechanism.

###  1.2 Related work

Trade-off between usability and security lie in the core of mechanism design
of password authentication. Users tend to pick low-entropy passwords [15],
leaving their accounts insecure. Convincing them to select stronger passwords
is a difficult task [18, 30, 39, 40, 26, 38]. Password strength meters [29,
43, 19] are commonly embedded in website in the hope that users would select
stronger passwords after the strength of their original passwords being
displayed. However, it is found that users are often not persuaded by the
suggestion of password strength meters [43, 19]. In order to encourge users to
pick high-entropy passwords some sites mandate users to follow stringent
guidelines when users create their passwords. However, it has been shown that
these methods suffer from usability issues [26, 41, 23, 3], and in some cases
can even lead to users selecting weaker passwords [13, 30].

Password offline attacks have been a concern since the Unix system was devised
[35]. Various approaches are developed to expedite the cracking process by the
adversary or model password guessability by the hoesty party. Tools like
Hashcat [1] and John the Ripper [22] enumerate combinations of tokens as
dictionary candidates and are widely used by real-world attackers. Liu et al.
[31] analyzed these tools using techniques of rule inversion and guess
counting to retrive guessing number without explicit enumeration.
Probabilistic models like Probabilistic Context-Free Grammars [47, 28, 46],
Markov models [21, 20, 32, 44] have been applied and analyzed in password
cracking. Character-level text generation with Long-Short Term Memory (LSTM)
recurrent neural networks is fast, lean and accurate in modeling password
guessability [34].

Memory-hard functions (MHF) is a key cryptographic primitive. Evaluation of
MHF requires large amount of memory in addition to longer computation time,
making parallel computation and customized hardware futile to speed up
computation process. Candidate MHFs include SCRYPT [36], Balloon hashing [14],
and Argon2 [9] (the winner of the Password Hashing Competition[2]). MHFs can
be classified into two distinct categories or modes of operation - data-
independent MHFs (iMHFs) and data-dependent MHFs(dMHFs) (along with the hybrid
idMHF, which runs in both modes). dMHFs like SCRYPT are maximally memory hard
[7], but they have the issue of possible side-channel attacks. iMHFs, on the
other hand, can resist side-channel attakcs but the aAT (amortized Area Time)
complexity is at most $\mathcal{O}(N^{2}\log\log N/\log N)$. In construction
of a iMHF Alwen and Blocki showed that depth robustness, a property associated
with a DAG, is both necessary [4] and sufficient [6]. Recent work has proposed
candidate iMHF constructions that show resistance to currently-known attacks
[11].

##  2 Background and Notations

##### Password Dataset.

We use $\mathbb{P}$ to denote the set of all possible passwords, the
corresponding distribution is $\mathcal{P}$. The process of a user $u$
choosing a password for his/her account can be viewed as a random sampling
from the underlying distribution $pw_{u}\overset{\$}{\leftarrow}\mathcal{P}$.
Given a password dataset $D$ of $n_{a}$ accounts, we can obtain empirical
distribution $\mathcal{D}_{e}$ by approximating
$\Pr_{pw_{i}\sim\mathcal{D}_{e}}[pw_{i}]=\frac{f_{i}}{n_{a}}$, where $f_{i}$
is the frequency of $pw_{i}$ and $n_{a}$ is the number of accounts present in
$D$. Often the empirical distribution can be represented in compact form by
grouping passwords with the same frequency into an _equivalence set_ i.e.,
$D_{es}=\\{(f_{1},s_{1}),\ldots,(f_{i},s_{i}),\ldots,(f_{n_{e}},s_{n_{e}})\\}$,
where $s_{i}$ is the number of passwords which appear with frequency $f_{i}$
in $D$ and $n_{e}$ is the total number of equivalence sets. We use
$es_{i}=(f_{i},s_{i})$ to describe the $i$th equivalence set. In empirical
experiments it is often most convenient to work with the compact
representation $D_{es}$ of our distribution. We also use $n_{p}$ to denote the
number of distinct passwords in our dataset $D$. Observe that for any dataset
we have $n_{a}\geq n_{p}\geq n_{e}$. In fact, we will typically have $n_{a}\gg
n_{p}\gg n_{e}$.

##### Computation Cost of MHF.

The evaluation of MHF generates a sequence of labels $L_{1},L_{2},\ldots$, in
order to compute $L_{i}$, some of its predecessor are required. Each label is
associated with a running time parameter. We use
$T=\\{t_{1},t_{2},\ldots,t_{m}\\}$ to denote the set of possible running time
breakpoints and $q_{i}=\Pr[t_{i}]$ to denote the probability that $t_{i}$ is
chosen for user’s password $pw_{u}$. We model the (amortized) Area-Time cost
of evaluating $\mathsf{MHF}(\cdot;t)$ as $c_{H}t+c_{M}t^{2}$, where $c_{H}$
and $c_{M}$ are constants. Intuitively, $c_{H}$ denotes the area of a core
implementing the hash function $H$ and $c_{M}$ represents the area of an
individual cell with the capacity to hold one data-label (hash output). Since
the memory cost tend to dominate, we ignore the hash cost as simply model the
cost as $c_{M}t^{2}$.

##  3 Defender’s Model

In this section, we present the model of the defender. In particular, we show
how passwords are stored and verified on the authentication server.

##### Account Registration.

When a user $u$ proposes password $pw_{u}$ for his/her account at the time of
registration, the authentication would randomly generate a salt value
$salt_{u}$, sample a running time parameter $t_{u}$ from $T$, calculate the
memory hard function with parameter $t_{u}$, i.e.,
$h_{u}=\mathsf{MHF}(pw_{u},salt_{u};t_{u})$. In the end, the tuple
$(u,salt_{u},h_{u})$ is stored in the server as the record of $u$ while
$t_{u}$ is discarded.

##### Password Verification.

Later on, when user $u$ logs in his/her account by submitting
$(u,pw_{u}^{\prime})$ to the server interface, the authentication server would
first retrieve record $(u,salt_{u},h_{u})$, calculate
$h_{1}=\mathsf{MHF}(pw_{u}^{\prime},salt_{u};t_{1})$ and compare $h_{1}$ with
$h_{u}$. It they are equal, login request is granted. Otherwise, the server
would continue to calculate
$h_{2}=\mathsf{MHF}(pw_{u}^{\prime},salt_{u};t_{2})$, compare $h_{2}$ with
$h_{u}$, so on and so forth. If any of $h_{i}$ matches $h_{u}$, then user $u$
successfully logs in his/her account. However, If none of $h_{i}$ matches
$h_{u}$, the login request is rejected.

##### Workload Constraint

. The server is subject to maximum workload constraint which means that the
expected cost cannot exceed server’s workload ceiling $C_{max}$. Namely,

$\small\sum_{i=1}^{m}q_{i}c_{M}t_{i}^{2}\leq C_{max}.$ (1)

With probability $q_{i}$ the server will choose $t_{i}$, evaluate
$\mathsf{MHF}(\cdot;t_{i})$ incurs cost $c_{M}t_{i}^{2}$, thus the expected
cost of verifying a password is $\sum_{i=1}^{m}q_{i}c_{M}t_{i}^{2}$.

##  4 Attacker’s model

In this section, we first state the assumptions we use in our economic
analysis. Then we show how a rational attacker who steals the password hashes
from the server would run a dictionary offline attack. Finally, we present the
Stackelberg game in modeling the interaction between the defender and the
attacker within the framework of [10].

###  4.1 Assumptions of Economics Analysis

We made several assumptions about the attacker which facilitates our economic
analysis of the attacker’s behavior.

  * •

_rationality_. A rational attacker’s objective is to extract as much monetary
reward as possible from the cracking process, the only constraint is the
number of passwords the attacker is willing to guess.

  * •

_knowledge_. The attacker knows password distribution $\mathcal{P}$. In
practice, password dictionary list can be built using Probabilistic Context-
Free Grammars (PCFGs) [47, 28, 46], $n$-gram Markov Models [21, 20, 32, 44]
and Neural Networks [34].

  * •

_untarget_. We assume the attacker is untargeted, treats all users without
distinction and has universal password value expectation $v$ for all accounts.
One can derive a range of estimates for $v$ based on black market studies
e.g., Symantec reported that passwords generally sell for $4—$30 [24] and [42]
reported that Yahoo! e-mail passwords sell for $\approx\$1$.

###  4.2 Cracking Process

We now specify how an offline attacker would use the stolen hash to run a
dictionary attack. Password distribution and the breakpoint distribution
induce a joint distribution over pairs
$(pw,t)\in\mathbb{P}\times\\{t_{1},\ldots,t_{m}\\}$, we have
$\Pr[(pw_{i},t_{j})]=\Pr[pw_{i}]q_{j}$ because of independence between label
index and associated account.

The adversary’s strategy is to formulate a checking sequence
$\pi=\\{(pw_{i},t_{j})\\}$ with the purpose of finding the target
$(pw_{u},t_{u})$. In particular, the attacker will execute the first
instruction in $\pi$, then second instruction if the first execution fails,
etc,. An instruction $(pw_{i},t_{j})$ in $\pi$ means the adversary selects
$pw_{i}$ as current guess and compute the $j$th label for $pw_{i}$ i.e.,
evaluate $\mathsf{MHF}(pw_{i},salt_{u};t_{j})$. The cracking process
terminates when the adversary found the hidden target $(pw_{u},t_{u})$ or
timeout. Note that the order of instructions in a checking sequence $\pi$
matters. A checking sequence is subject to _legit restrictions_ :

  1. 1.

_Small label first_. If $(pw_{i},t_{j_{1}})$ appears before
$(pw_{i},t_{j_{2}})$ in $\pi$, then it should be the case
$t_{j_{2}}>t_{j_{1}}$.

  2. 2.

_Label backward continuity_. If $(pw_{i},t_{j})\in\pi$ then
$(pw_{i},t_{1}),\ldots,(pw_{i},t_{j-1})\in\pi$.

  3. 3.

_No inversions_. Inversions in the form of $(pw_{i_{1}},t_{j_{1}})$,
$(pw_{i_{2}},t_{j_{2}})$, $(pw_{i_{1}},t_{j_{1}}^{\prime})$ where
$t_{j_{1}}^{\prime}>t_{j_{1}}$ are not allowed.

The first two restrictions state that the attacker cannot advance to a larger
label without computing all previous labels. The third is an assumption that
we made, this assumption is valid because computing labels for $pw_{i_{2}}$
while storing labels for $pw_{i_{1}}$ will induce extra memory cost, which
should be avoided.

###  4.3 Attacker’s Utility

After specifying the restrictions for a legit checking sequence, we can
formulate the the attacker’s utility. Suppose the $k$th instruction in
checking sequence $\pi$ is $\pi_{k}=(pw_{i},t_{j})$, then
$\Pr[\pi_{k}]=\Pr[pw_{i}]\cdot q_{j}$. Define
$\lambda(\pi,B)=\sum_{k=1}^{B}\Pr[\pi_{k}]$, we write $\lambda(\pi,|\pi|)$ in
short form $\lambda(\pi)$. Also we use $c(\pi_{k})$ to denote the round cost
of executing instruction $\pi_{k}$ where
$c(\pi_{k})=c_{M}(t_{j}^{2}-t_{j-1}^{2})$, specifically, $t_{0}=0$ is
introduced for convenience of notations. Then the attacker’s utility is

$\small
U_{adv}(v,\vec{q},\pi)=v\cdot\lambda(\pi)-\sum_{k=1}^{|\pi|}c(\pi_{k})\left(1-\lambda(\pi,k-1)\right).$
(2)

Given a checking sequence $\pi$ the attacker’s success rate is
$P_{adv}(\pi)=\lambda(\pi)$, thus the gain (the first term of equation (2)) is
$v\cdot\lambda(\pi)$. The second term is the expected cost, the attacker only
pay cost $c(\pi_{k})$ if and only if all previous $k-1$ trials are in vain,
which happens with probability $1-\lambda(\pi,k-1)$.

Besides legit restrictions that make a checking sequence valid a rational
attacker would choose a checking sequence $\pi$ that satisfies _opt
restrictions_ :

  1. 1.

_Popular password first_. If $(pw_{i_{1}},t_{j})$ appears before
$(pw_{i_{2}},t_{j})$, then $\Pr[pw_{i_{1}}]>\Pr[pw_{i_{2}}]$.

  2. 2.

_Password backward continuity_. If $(pw_{i},t_{j})\in\pi$ for some $j$, then
$(pw_{i-1},t_{j^{\prime}})\in\pi$ for some $j^{\prime}$.

  3. 3.

_Stop at $es$ boundary_. If $(pw_{i},t_{j})$ is the last instruction in $\pi$
where $pw_{i}\in es_{k}$, then $pw_{i+1}\in es_{k+1}$.

It can be easily proved that an attacker who violates opt restrictions will
suffer utility loss. Legit restrictions, together with the first 2 opt
restrictions, determine a complete ordering, which we call _natural ordering_
, over all instructions $\\{(pw_{i},t_{j})\\}$, namely,

$\small\begin{cases}(pw_{i_{1}},t_{j_{1}})<(pw_{i_{2}},t_{j_{2}}),\text{ if
}\Pr[pw_{i_{1}}]>\Pr[pw_{i_{2}}],\\\
(pw_{i},t_{j_{1}})<(pw_{i},t_{j_{2}}),\text{ if }j_{1}<j_{2}.\end{cases}$ (3)

We use $\Pi(n,m)$ to denote the sequence of all instructions for top $n$
passwords with respect to natural ordering,

$\small\Pi(n,m)\vcentcolon=(pw_{1},t_{1}),\ldots,(pw_{1},t_{m}),\ldots,(pw_{n},t_{1}),\ldots,(pw_{n},t_{m}).$
(4)

We say a sequence containing consecutive instructions for a single password is
a _instruction bundle_ , which is denoted by

$\varpi_{i}(j_{1},j_{2})\vcentcolon=(pw_{i},t_{j_{1}}),\ldots,(pw_{i},t_{j_{2}}).$
(5)

Specifically, $\varpi_{i}(j_{1},j_{2})=\emptyset$ when $j_{1}=j_{2}=0$. Then
the attacker’s strategy $\pi$ is a sub-sequence of $\Pi(n_{p},m)$ (recall that
$n_{p}$ is the number of distinct passwords) in the form of

$\small\pi=\oplus_{i^{\prime}=1}^{\mathsf{Len}(\pi)}\varpi_{i^{\prime}}(1,\tau_{i^{\prime}})\vcentcolon=\varpi_{1}(1,\tau_{1})\circ\varpi_{2}(1,\tau_{2})\circ\cdots\circ\varpi_{\mathsf{Len}}(1,\tau_{\mathsf{Len}}),$
(6)

where $\circ$ denotes the concatenation of two disjoint instruction sequence
and $\mathsf{Len}(\pi)$ is the largest index of password for which the
attacker would check at least one label, which depends on the associated
checking sequence, when the context is clear it is just written as
$\mathsf{Len}$. Because of opt restriction 3, $\mathsf{Len}$ can only take
values in
$\left\\{0,|es_{1}|,|es_{1}|+|es_{2}|,\ldots,\sum_{k=1}^{n_{e}}|es_{k}|\right\\}$.
Notice that $\pi$ is fully specified by the largest label index $\tau_{i}$ for
$pw_{i}$.

###  4.4 Stackelberg game

We use Stackelberg game to model the interaction between the attacker and
defender.

stage 1: the server determines breakpoint distribution $\vec{q}$;

stage 2: The attacker’s strategy is to select checking sequence $\pi$, or
equivalently $\mathsf{Len}$ and $\\{\tau_{i}\\}$.

Define server’s utility to be $U_{ser}(v,\vec{q})=-\lambda(\pi^{*})$, where
$\pi^{*}$ is the attacker’s best response to defender’s strategy $\vec{q}$ and
password value $v$. At equilibrium no player has the incentive to deviate form
her/his strategy, thus equilibrium profile $(\vec{q}^{*},\pi^{*})$ satisfies,

$\small\begin{cases}U_{adv}(v,\vec{q},\pi^{*})\geq
U_{adv}(v,\vec{q},\pi),\,\forall\pi,\\\ U_{ser}(v,\vec{q}^{*})\geq
U_{ser}(v,\vec{q}),\,\forall\vec{q}.\end{cases}$ (7)

We use backward induction to find the equilibrium. First given password value
$v$ and a concrete breakpoint distribution $\vec{q}$ we formulate the
attacker’s optimal strategy which maximize $U_{adv}(v,\vec{q},\pi)$ (Section
5). Then taken the attacker’s reaction into consideration the server
determines $\vec{q}$ which minimizes attacker’s success rate (Section 6).

##  5 Attacker’s Optimal Strategy

In this section, we show how to compute the attacker’s optimal strategy for
both time-even breakpoints and cost-even breakpoints. Given password value $v$
and label distribution $\vec{q}$, the attacker would choose
$\pi^{*}=\operatorname*{arg\,max}U_{adv}(v,\vec{q},\pi)$.

Before we introduce our algorithm used to find the optimal checking sequence,
let us see why the native brute force algorithm is computationally infeasible.
If the attacker chose to check top $\mathsf{Len}$ passwords; for each password
$pw_{i}$ the attacker has $m$ choices, namely, selects
$\tau_{i}\in\\{1,\ldots,m\\}$. Thus the native brute force algorithm runs in
time
$\mathcal{O}\left(\sum_{\mathsf{Len}=1}^{n_{p}}m^{\mathsf{Len}}\right)\subseteq\mathcal{O}(m^{n_{p}})$
with a very large exponent ($n_{p}\approx 2.14\times 10^{7}$ for our largest
dataset Linkedin, and $n_{p}\approx 3.74\times 10^{5}$ for our smallest
dataset Bfiled). This is why we need to design polynomial time algorithms.

$\emptyset$ uniform breakpoint distribution
$\pi_{LO}=\mathsf{Extend}(v,\vec{q})$ cost-even breakpoints
($\beta_{i}=\sqrt{i}$) $\pi_{LOC}=\mathsf{ExtendbyConcat}(v,\vec{q},$)
$\pi_{LOC}=\pi^{*}$ $\mathsf{OptimalityTest}(v,\vec{q},\pi_{LO})$
$\beta_{i}=\sqrt{i}$ and $m\leq 3$ $\pi_{LO}=\pi^{*}$
$\pi_{LO}\subseteq\pi^{*}$ $\pi^{*}=\mathsf{FindOptSeq}(v,\vec{q},\pi_{LO})$
NoYesYesPassFailNoYesNo

Figure 1: Algorithm Flowchart

In the following subsections, we first specify a superset of $\pi^{*}$222We
use the concept and notation of subset and superset for ordered sequences the
way they were defined for regular set. If all elements of sequence $A$ are
also elements of sequence $B$ regardless the order, we say $A\subseteq B$,
setting a boundary within which we will gradually extend the checking sequence
from an empty one. Then we introduce our local search algorithm to find the
optimal checking sequence (for most of the time). Our key intuition in
designing algorithms is that an unchecked instruction bundle should be
included into the optimal checking sequence if it provides non-negative
marginal utility. Generally there are two local search directions, either
concatenate instructions at the end of current checking sequence or insert
instructions in the middle of current checking sequence. After the local
search algorithm terminates we reach a local optimum $\pi_{LO}$. Finally we
design algorithms to verify if the local optimum is also global optimum or
promote the local optimum to global optimum under specifc parameter settings.
As a overview we briefly summarize our results (also demonstrated in the
flowchart, see Figure 1) in this section as follows:

  * •

When we use cost-even breakpoints sampled from uniform distribution, namely,
$\beta_{i}=\sqrt{i}$ and $q_{i}=\frac{1}{m}$, we have a local search algorithm
$\mathsf{ExtendbyConcat}(v,\vec{q},\emptyset)$ which iteratively considers
instruction bundle that can be concatenated,
$\mathsf{ExtendbyConcat}(v,\vec{q},\emptyset)$ runs in time
$\mathcal{O}(n_{p}m)$ and gives optimal checking sequence;

  * •

When breakpoints are cost-even ($\beta=\sqrt{i}$) but the distribution is non-
uniform, we design an algorithm $\mathsf{Extend}(v,\vec{q})$ which returns a
locally optimal checking sequence $\pi_{LO}$ in time $\mathcal{O}(n_{p}m)$. By
locally optimal we mean that advancing any number of labels for any single
password on the basis of $\pi_{LO}$ will decrease attacker’s utility.

After obtaining $\pi_{LO}$, we can run a polynomial algorithm
$\mathsf{OptimalityTest}(v,\vec{q},\pi_{LO})$ to check if $\pi_{LO}$ is also a
global optimum. If $\mathsf{OptimalityTest}(v,\vec{q},\pi_{LO})$ returns PASS,
we know for sure that $\pi_{LO}=\pi^{*}$; otherwise, no conclusion can be
drawn. If $m\leq 3$ we will use an efficient brute force algorithm
$\mathsf{FindOptSeq}(v,\vec{q},\pi_{LO})$, which runs in time
$\mathcal{O}(n_{p}^{2})$, to the reach global optimum.

  * •

When $\beta\neq\sqrt{i}$, regardless of the breakpoint distribution we can
still run $\mathsf{Extend}(v,\vec{q})$ to obtain locally optimal $\pi_{LO}$,
and feed $\pi_{LO}$ to $\mathsf{OptimalityTest}(v,\vec{q},\pi_{LO})$. If
$\mathsf{OptimalityTest}(v,\vec{q},\pi_{LO})$ returns PASS, again we have
$\pi_{LO}=\pi^{*}$; if $\mathsf{OptimalityTest}(v,\vec{q},\pi_{LO})$ returns
FAIL, we cannot deduce any information about the global optimality of
$\pi_{LO}$; in this case, confirm that $\pi_{LO}=\pi^{*}$ or promote
$\pi_{LO}$ to $\pi^{*}$ will take exponential time.

###  5.1 Marginal Utility

Since we are going to use marginal utility as metrics of state transition in
local search, we first specify how to compute marginal utility.

$t_{1}$$t_{2}$$t_{3}$$t_{4}$$t_{5}$$\ldots$$t_{m-1}$$t_{m}$DAG($pw_{1}$)$\ldots$DAG($pw_{2}$)$\ldots$$\ldots$$\ldots$DAG($pw_{i*-1}$)$\ldots$DAG($pw_{i^{*}}$)$\ldots$$\ldots$$\ldots$DAG
($pw_{u}$)$\ldots$$\ldots$DAG ($pw_{n_{p}}$)

Figure 2: Password Cracking Process

Black nodes denote current checking sequence $\pi$. White nodes denote
unchecked instructions $\Pi(n_{p},m)-\pi$. Star denotes unknown target
$(pw_{u},t_{u})$.

###### Definition 1

Fixing $v$ and $\vec{q}$, define $\Delta(\pi_{1},\pi_{2})$ to be marginal
utility from strategy $\pi_{1}$ to $\pi_{2}$, namely,

$\Delta(\pi_{1},\pi_{2})\vcentcolon=U_{adv}(v,\vec{q},\pi_{2})-U_{adv}(v,\vec{q},\pi_{1}).$
(8)

For most of the time $\pi_{2}$ is the result of modifying $\pi_{1}$ which is
called _base_ , in order to avoid redundantly repeating base we often write
$\Delta^{\circ}\left(e\,\middle|\,\pi_{1}\right)$ and
$\Delta^{+}\left(e\,\middle|\,\pi_{1}\right)$ to denote
$\Delta\left(\pi_{1},\pi_{1}\circ e\right)$ and
$\Delta\left(\pi_{1},\pi_{1}+e\right)$, respectively, where $e$ is some
ordered set of instructions, referred to as _extension_. Recall that $\circ$
is concatenation operation, here we formally introduce insertion operation
$+$.

###### Definition 2

Given a checking sequence
$\pi=\oplus_{i=1}^{\mathsf{Len}}\varpi_{i}(1,\tau_{i})$ and an instruction
bundle $\varpi_{i^{\prime}}(j_{1},j_{2})$, define operation
$\pi+\varpi_{i^{\prime}}(j_{1},j_{2})$ to be the checking sequence

$\pi+\varpi_{i^{\prime}}(j_{1},j_{2})\vcentcolon=\oplus_{i=1}^{i^{\prime}}\varpi_{i}(1,\tau_{i})\circ\varpi_{i^{\prime}}(j_{1},j_{2})\circ\oplus_{i=i^{\prime}+1}^{\mathsf{Len}}\varpi_{i}(1,\tau_{i}).$

We discard superscript and comprehensively write
$\Delta\left(e\,\middle|\,\pi\right)$ to denote the marginal utility by
including $e$ into $\pi$, either through concatenation or insersion.
Operations are valid only if the extension is _compatible_ with the base. By
compatible we mean the resulting checking sequence also satisfy both legit
restrictions and opt restrictions.

When $e$ is a singleton, from equation (2) we can derive the marginal utility
by inserting instruction $e=(pw_{i},t_{j})\notin\pi$ to base $\pi$,

$\Delta^{+}\left(e\,\middle|\,\pi\right)=\Pr[pw_{i}]q_{j}\left(v+\sum_{e^{\prime}>e,e^{\prime}\in\pi}c(e^{\prime})\right)-\left(1-\sum_{e^{\prime}<e,e^{\prime}\in\pi}\Pr[e^{\prime}]\right)c_{M}(t_{j}^{2}-t_{j-1}^{2}).$
(9)

where $\Pr[pw_{i}]q_{j}\sum_{e^{\prime}>e,e^{\prime}\in\pi}c(e^{\prime})$ is
the influence of $e$ on future instructions since it eliminates some
uncertainty about the user’s password $pw_{u}$ thus reduces the _expected_
cost for future trials.

When $e$ is a singleton, marginal utility upon concatenation has no future
influence, hence,

$\Delta^{\circ}\left(e\,\middle|\,\pi\right)=\Pr[pw_{i}]q_{j}v-\left(1-\lambda(\pi)\right)c_{M}(t_{j}^{2}-t_{j-1}^{2}).$
(10)

When $e$ consists of multiple consecutive instructions, the marginal utility
can be computed by iteratively applying equation (9) and (10). Namely,

$\Delta\left(e\,\middle|\,\pi\right)=\sum_{i=1}^{|e|}\Delta\left(e_{i}\,\middle|\,\pi\cup\\{e_{0},\ldots,e_{i-1}\\}\right),$
(11)

where $e_{0}=\emptyset$, $e_{i}$ is the $i$th instruction of $e$ and $\cup$
denotes inclusion (whether through concatenation or insertion) while
maintaining natural ordering.

###  5.2 A Superset of the Optimal Checking Sequence

Before we present our algorithms we first show how to prune down the search
space for $\pi^{*}$. Particularly, fixing $v$ and $\vec{q}$ we find an index
$\mathsf{Len}_{max}$ such that $\pi^{*}\subseteq\Pi(\mathsf{Len}_{max},m)$
i.e., $\pi^{*}$ will not even partially check passwords with rank larger than
$\mathsf{Len}_{max}$. Thus there is no need to consider any instructions
beyond $\Pi(\mathsf{Len}_{max},m)$ in construction of the optimal checking
sequence.

######  Lemma 1 ()

$\Delta^{\circ}\left(\pi_{3}\,\middle|\,\pi_{1}\right)\leq\Delta^{\circ}\left(\pi_{3}\,\middle|\,\pi_{2}\right),\,\text{
if }\lambda(\pi_{1})\leq\lambda(\pi_{2}).$

###### Definition 3

Fixing $v$ and $\vec{q}$ we define

$\mathsf{Len}_{max}\vcentcolon=\begin{cases}\max_{i}\\{i:F(v,\vec{q},i)\geq
0\\},\text{ if such }i\text{ exists},\\\ 0,\text{ o.w.}\end{cases}$

where

$F(v,\vec{q},i)\vcentcolon=\begin{cases}\max_{1\leq j\leq
m}\\{\Delta\left(\emptyset,\varpi_{i}(0,j)\right)\\},\text{ if }i=1,\\\
\max_{1\leq j\leq
m}\\{\Delta^{\circ}\left(\varpi_{i}(0,j)\,\middle|\,\Pi(i-1,m)\right)\\},\text{
o.w.}\end{cases}$

Intuitively, $\mathsf{Len}_{max}$ is the largest possible password index for
which at least one of instruction bundles
$\varpi_{\mathsf{Len}_{max}}(1,j),1\leq j\leq m$ provide non-negative marginal
utility no matter what previous instructions are. We remark even though there
is no theoretical proof of monotonicity of $F(v,\vec{q},i)$, we have verified
that $F(v,\vec{q},i)$ is decreasing in $i$ for our empirical password
distribution. Note that by Lemma 1 we have

$\Delta^{\circ}\left(\varpi_{i}(0,j)\,\middle|\,\oplus_{i=1}^{i-1}\varpi_{i}(1,\tau_{i})\right)\leq
F(v,\vec{q},i),$

if $F(v,\vec{q},i)<0$, then $\varpi_{i}(0,j)$ would certainly provide negative
marginal utility, thus cannot be included in $\pi^{*}$. It is described in the
following theorem.

######  Theorem 5.1 ()

$\pi^{*}\subseteq\Pi(\mathsf{Len}_{max},m).$

###  5.3 Extension by Concatenation

We have established a superset of $\pi^{*}$ in last subsection, now we design
a local search algorithm that gives us a checking sequence $\pi_{LOC}$ which
is a subset of $\pi^{*}$. Here, LOC stands for “locally optimal with respect
to concatenation." The sequence $\pi_{LOC}$ will be helpful to further prune
down the search space for $\pi^{*}$. In fact, in the special case the
breakpoint distribution is uniform ($q_{i}=\frac{1}{m}$) and when we use cost-
even breakpoints ($\beta_{i}=\sqrt{i}$) we can prove that equality holds i.e.,
$\pi_{LOC}=\pi^{*}$ is the optimal solution.

To find our sequence $\pi_{LOC}$ we start with the empty sequence of
instructions and repeatedly include instructions that provide non-negative
marginal utility upon concatenation to the current solution. We design a local
search algorithm $\mathsf{ExtendbyConcat}(v,\vec{q},\emptyset)$ to find a
checking sequence $\pi_{LOC}$. Our local search algorithm
$\mathsf{ExtendbyConcat}(v,\vec{q},\emptyset)$ terminates after at most
$n_{p}$ rounds.

After the $i-1$th round we have $\pi_{LOC}\subseteq\Pi(i-1,m)$ i.e., the
current solution only includes checking instructions for the first $i-1$
passwords. In the $i$th round we find an instruction bundle for password $i$
which maximizes (marginal) utility upon concatenation. More specifically, in
round $i$ we compute $\tau_{i}=\arg\max_{0\leq j\leq
m}\\{\Delta^{\circ}\left(\varpi_{i}(0,j)\,\middle|\,\pi_{LOC}\right)\\}$ and
append this instruction bundle to obtain an updated checking sequence
$\pi_{LOC}=\pi_{LOC}\circ\varpi_{i}(0,\tau_{i})$. Details can be found in
Algorithm 1.

Input: $v$, $\vec{q}$

Output: $\pi_{LOC}$

1 $\pi_{LOC}=\pi$;

2 $start=i^{*}(\pi_{LOC})$;

3 for  _$i=start:n_{p}$_ do

4 for  _$j=0:m$_ do

5 Compute $\Delta^{\circ}\left(\varpi_{i}(0,j)\,\middle|\,\pi_{LOC}\right)$;

6

7 end for

8 $\tau_{i}=\arg\max_{0\leq j\leq
m}\\{\Delta^{\circ}\left(\varpi_{i}(0,j)\,\middle|\,\pi_{LOC}\right)\\}$;

9 if  _$\tau_{i} >0$_ then

10 $\pi_{LOC}=\pi_{LOC}\circ\varpi_{i}(1,\tau_{i})$;

11 else break;

12

13 end if

14

15 end for

return _$\pi_{LOC}$_

Algorithm 1 $\mathsf{ExtendbyConcat}(v,\vec{q},\pi)$

We can use equation (10) to compute the marginal utility in time
$\mathcal{O}(1)$ by caching previously computed values of $\lambda(\pi)$.
Thus, $\mathsf{ExtendbyConcat}(v,\vec{q},\emptyset)$ runs in time
$\mathcal{O}(\mathsf{Len}_{max}m)\subseteq\mathcal{O}(n_{p}m)$, recall that
$n_{p}$ is the number of distinct password.

######  Theorem 5.2 ()

$\pi_{LOC}\subseteq\pi^{*}.$

From Theorem 5.1 and Theorem 5.2, it is easy to derive the following
corollaries.

###### Corollary 1

$\mathsf{Len}(\pi_{LOC})\leq\mathsf{Len}(\pi^{*})\leq\mathsf{Len}_{max},$

and

$\mathsf{Len}(\pi_{LOC}),\mathsf{Len}(\pi^{*}),\mathsf{Len}_{max}\in\left\\{x_{0},x_{1},\ldots,x_{n_{e}}\right\\},$

where

$x_{k}=\begin{cases}0,\text{ if }k=0,\\\
\sum_{k^{\prime}=1}^{k}|es_{k^{\prime}}|,\text{ if }k=1,\ldots,n_{e}.\\\
\end{cases}$ (12)

###### Corollary 2

$\lambda(\pi_{LOC})\leq
P_{adv}=\lambda(\pi^{*})\leq\lambda\left(\Pi(\mathsf{Len}_{max},m)\right).$

Now we have a polynomial algorithm that returns a checking sequence
$\pi_{LOC}$ locally optimal with respect to concatenation. The following
theorem states that $\pi_{LOC}=\pi^{*}$ if breakpoints are cost-even and
follow uniform distribution.

######  Theorem 5.3 ()

When $q_{i}=\frac{1}{m}$ and $\beta_{i}=\sqrt{i}$,
$\mathsf{ExtendbyConcat}(v,\vec{q},\emptyset)$ returns the optimal checking
sequence, i.e., $\pi_{LOC}=\pi^{*}$.

Even though the attacker behaviors optimally—following strategy $\pi^{*}$. We
can guarantee that our mechanism results in lower (or equal if no passwords
are cracked) percentage of cracked passwords than deterministic cost hashing,
which is captured by Theorem 5.4.

######  Theorem 5.4 ()

When $\beta_{i}=\sqrt{i}$ and $q_{i}=\frac{1}{m}$ then, $\lambda(\pi^{*})\leq
P_{adv}^{d},$where $P_{adv}^{d}$ is the percentage of cracked passwords in
traditional deterministic cost hashing.

We have shown that our mechanism configured with cost-even breakpoints sampled
from uniform distribution will only decrease the percentage of cracked
passwords. In the next subsections we consider how the attacker would react to
general configuration of the mechanism.

###  5.4 Local Search in Two Directions

In the previous section we introduced an algorithm
$\mathsf{ExtendbyConcat}(v,\vec{q},\emptyset)$ to produce a locally optimal
solution $\pi_{LOC}$ with respect to concatenation. We showed the instruction
sequence $\pi_{LOC}$ is a subset of the instructions in $\pi^{*}$ and argued
that in specific cases the algorithm is guaranteed to find the optimal
solution. However, in more general cases the local optimum may not be globally
optimum. One possible reason for this is that there may be a missing
instruction from $\pi^{*}$ that we would like to insert into the middle of the
checking sequence $\pi_{LOC}$, while our local search algorithm only considers
instructions that can be appended to $\pi_{LOC}$.

In this subsection we extend the local search algorithm to additionally
consider insertions. Note that we can still use local search to test if
$\Delta^{+}\left(\varpi_{i}(j_{1},j_{2})\,\middle|\,\pi\right)\geq 0$
inserting instruction bundle $\varpi_{i}(j_{1},j_{2})$ improves the overall
utility. We define an algorithm $\mathsf{ExtendbyInsert}(v,\vec{q},\pi)$ which
performs such an update. Combining $\mathsf{ExtendbyConcat}(v,\vec{q},\pi)$
and $\mathsf{ExtendbyInsert}(v,\vec{q},\pi)$, we design an Algorithm
$\mathsf{Extend}(v,\vec{q})$ to construct a checking sequence $\pi_{LO}$
(LO=Locally Optimal) which is locally optimal with respect to both operations:
concatenation and insertions. Specifically, after each call of
$\mathsf{ExtendbyInsert}(v,\vec{q},\pi)$ we immediately run
$\mathsf{ExtendbyConcat}(v,\vec{q},\pi)$ to ensure that the solution is still
locally optimal with respect to concatenation. See Algorithm 3 for details.
The algorithms still maintains the invariant that $\pi_{LO}$ is a subset of
$\pi^{*}$ — see Theorem 5.5.

Given $\pi_{LOC}$ computed in time $\mathcal{O}(n_{p}m)$, the number of
unchecked instructions is upper bounded by
$|\Pi(\mathsf{Len}_{max},m)|-|\pi_{LOC}|$. By caching the probability
summation of previous and future instructions at each insertion position,
verify if an instruction bundle is profitable and update the checking sequence
take time $\mathcal{O}(1)$. One pass of repeat loop of Algorithm 3 takes time
$\mathcal{O}(|\Pi(\mathsf{Len}_{max},m)|-|\pi_{LOC}|)\subseteq\mathcal{O}(n_{p}m)$,
the execution time of repeat loop execution is finite (in experiment it
terminates after at most 3 passes). Therefore, $\mathsf{Extend}(v,\vec{q})$
runs in time $\mathcal{O}(n_{p}m)$.

Input: $v$, $\vec{q}$, $\pi$

Output: $\pi_{LOI}$

1 $\pi_{LOI}=\pi$;

2 while  _$e$ exists such that
$\Delta^{+}\left(e\,\middle|\,\pi_{LOI}\right)\geq 0$_ do

3 $\pi_{LOI}=\pi_{LOI}+e$

4 end while

return _$\pi_{LOI}$_

Algorithm 2 $\mathsf{ExtendbyInsert}(v,\vec{q},\pi)$

Input: $v$, $\vec{q}$

Output: $\pi_{LO}$

1 $\pi_{LO}=\mathsf{ExtendbyConcat}(v,\vec{q},\emptyset)$;

2 repeat

3 $\pi_{LO}=\mathsf{ExtendbyInsert}(v,\vec{q},\pi_{LO})$;

4 $\pi_{LO}=\mathsf{ExtendbyConcat}(v,\vec{q},\pi_{LO})$;

5

6until  _no single profitable instruction bundle exist_ ;

return _$\pi_{LO}$_

Algorithm 3 $\mathsf{Extend}(v,\vec{q})$

######  Lemma 2 ()

If $\pi\subseteq\pi^{*}$ and $\Delta^{+}\left(e\,\middle|\,\pi\right)\geq 0$
then $\pi+e\subseteq\pi^{*}$.

Lemma 2 guarantees that $+$ operation preserves the invariance that our
construction is subset of $\pi^{*}$. Naturally follows Theorem 5.5, which
states the output of $\mathsf{Extend}(v,\vec{q})$ is a subset of $\pi^{*}$.

######  Theorem 5.5 ()

Let $\pi_{LO}=\mathsf{Extend}(v,\vec{q})$, then $\pi_{LO}\subseteq\pi^{*}.$

Since we are using local search to construct $\pi_{LO}$, together with Theorem
5.5 we know $\pi_{LO}$ is a local optimum. When Algorithm 3 terminates,
advancing any number of labels for any single password cannot improve the
overall utility, but there is no guarantee of utility reduction upon inclusion
of multiple instruction bundles that associated with different passwords. In
the next subsection we will discuss how to verify if the local optimum
$\pi_{LO}$ is indeed the global optimum and design an efficient brute force
algorithm that improves local optimum to global optimum under specific
parameter settings.

###  5.5 Optimality Test and Globally Optimal Checking Sequence

In the previous subsections, we designed a polynomial algorithm
$\mathsf{Extend}(v,\vec{q})$ to construct locally optimal checking sequence
$\pi_{LO}$ with respect to insertions and concatenation. We also proved that
the sequence $\pi_{LO}$ is a subset of the optimal sequence $\pi^{*}$. In
practice we find that it is often the case that $\pi_{LO}=\pi^{*}$ and we give
an efficient heuristic algorithm which (often) allows us to confirm the global
optimality of $\pi_{LO}$. In particular, our procedure will never falsely
indicate that $\pi_{LO}=\pi^{*}$ though it may occasionally fail to confirm
that this is the case. When our optimality test fails, we design algorithms to
promote locally optimal solution to globally optimal solution for cost-even
breakpoints and $m\leq 3$, see full version of this paper for details.

##  6 Defender’s Optimal Strategy

When making decisions about breakpoint distribution, the defender will take
attacker’s best response into consideration. Specifically, the defender would
choose $\vec{q}^{*}=\arg\min\lambda(\pi^{*})$ where $\pi^{*}=\arg\max
U_{adv}(v,\vec{q},\pi))$. Formally, the optimization problem ($\mathsf{OPT}$)
is |s| →qλ(π^*) 0 ≤q_i ≤1, ∀1 ≤i≤m ∑_i=1^mq_i = 1 ∑_i=1^mq_i c_Mt_i^2 ≤C_max
The optimization goal is to minimize attacker’s success rate, the first two
constrains guarantee $q_{i}$ are valid probabilities, the third constraint
guarantees that the expected cost does not exceed maximum workload $C_{max}$.

We use black box optimization solvers to address $\mathsf{OPT}$ since there is
no closed form expression of $\lambda(\pi^{*})$. Notice that there are only
$m-1$ independent variables, we select $q_{2},\ldots,q_{m}$ to be optimization
variables to further prune down the search space. Define
$\alpha=\frac{C_{max}}{c_{m}t_{1}^{2}}$, then the workload constraint becomes
$\sum_{i=1}^{m}\beta_{i}^{2}q_{i}\leq\alpha$, together with probability
constraint, we have
$q_{i}\leq\min\left\\{1,\frac{\alpha-1}{\beta_{i}^{2}-1}\right\\}$. For fixed
$v$, define $f$ to be the function mapping $\vec{q}$ to $P_{adv}$. Therefore
$\mathsf{OPT}$ is reduced to $\mathsf{OPT}^{\prime}$: |s| q_2,…,q_m f +
penalty_1(q_2,…,q_m) + penalty_2(q_2,…,q_m) where

$\small\text{penalty}_{1}(q_{2},\ldots,q_{m})=\begin{cases}0,\text{ if
}\sum_{i=2}^{m}(\beta_{i}^{2}-1)q_{i}\leq\alpha-1,\\\
cons_{1}+cons_{2}*\sum_{i=2}^{m}(\beta_{i}^{2}-1)q_{i},\text{ ow},\\\
\end{cases}$

and

$\small\text{penalty}_{2}(q_{2},\ldots,q_{m})=\begin{cases}0,\text{ if
}\sum_{i=2}^{m}q_{i}\leq 1,\\\ cons_{3}+cons_{4}*\sum_{i=2}^{m}q_{i},\text{
ow}.\\\ \end{cases}$

$cons_{i}$ are constants larger than 1. We refer to the black box solver as
$\mathsf{FindOptDis}()$, detailed discussion about $OPTDIS$ can be found in
the full version of this paper.

##  7 Experiments

###  7.1 Experiment Setup

In this section, we design experiments to validate our mechanism. In
particular, we consider 8 datasets (Bfield, Brazzers, Clixsense, CSDN,
Linkedin, Neopets, Rockyou, Webhost) with various size and they are given in
format of equivalence sets $D_{es}=\\{(f_{i},s_{i})\\}$. We only report
results of top 2 largest datasets (in terms of $n_{p}$): Linkedin and Neopets
due to length limit and move results of other 6 datases to full version of
this paper. For each dataset we plot attacker’s success rate
$\lambda(\pi^{*})$ (there are a few exceptions where
$\mathsf{OptimalityTest}(v,\vec{q},\pi)$ fails thus $\pi^{*}$ is not
available) against $v/C_{max}$, where $\pi^{*}$ is computed by algorithms
specified in the flow chart. Since the attacker is playing the same
Stackelberg game against all accounts, success rate of cracking one account
can also be interpreted as percentage of cracked passwords in that dataset.

In Figure 3 we consider time-even breakpoints with uniform distribution. We
are essentially plotting $\lambda(\pi_{LO})$ against $C_{max}$ and have
$\pi_{LO}=\pi^{*}$ for most of the time; if $\pi^{*}$ fails
$\mathsf{OptimalityTest}(v,\vec{q},\pi_{LO})$, the corresponding point is
marked with $\times$. Figure 4 shows the results under cost-even breakpoints
and uniform distribution. In Figure 5, we fix $m=3$ and breakpoints being
cost-even, and run our algorithm $\mathsf{FindOptDis}()$ whose optimization
solver is implemented with BITEOPT [45], to find the optimal breakpoint
distribution.

In experiments we use empirical distribution $\mathcal{D}_{e}$ (namely,
$\Pr_{pw\sim\mathcal{D}_{e}}[pw]=f_{i}/n_{a}$ where $f_{i}$ is the frequency
of $pw$) to approxmiate password distribution $\mathcal{P}$. The drawback is
that the tail of empirical distribution $\mathcal{D}_{e}$ would significantly
diverge from real distribution $\mathcal{P}$. We follow the approach of [8]
and use Good-Turing Frequency estimation to upbound the CDF divergence $E$
between $\mathcal{D}_{e}$ and $\mathcal{P}$. In particular, we use yellow
(resp. red) to denote the unconfident region where $E>0.01$ (resp. $E>0.1$).
We only report results within the confident region.

$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$10^{8}$$0$$0.2$$0.4$$0.6$$0.8$$1$

uncertain region

$v/C_{max}$ Percentage of Cracked Passwords Deterministic$m=3$Fails Optimality
Test$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$10^{8}$$0$$0.2$$0.4$$0.6$$0.8$$1$

uncertain region

$v/C_{max}$ Percentage of Cracked Passwords Deterministic$m=3$Fails Optimality
Test (a) Linkedin

$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$10^{8}$$0$$0.2$$0.4$$0.6$$0.8$$1$

uncertain region

$v/C_{max}$ Percentage of Cracked Passwords Deterministic$m=3$Fails Optimality
Test$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$10^{8}$$0$$0.2$$0.4$$0.6$$0.8$$1$

uncertain region

$v/C_{max}$ Percentage of Cracked Passwords Deterministic$m=3$Fails Optimality
Test (b) Neopets

Figure 3: Time-Even Breakpoints, Uniform Breakpoint Distribution

$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$10^{8}$$0$$0.2$$0.4$$0.6$$0.8$$1$

uncertain region

$v/C_{max}$ Percentage of Cracked Passwords
deterministic$m=2$$m=3$$m=7$$m=99$improvement: black-blue (a) Linkedin

$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$10^{8}$$0$$0.2$$0.4$$0.6$$0.8$$1$

uncertain region

$v/C_{max}$ Percentage of Cracked Passwords
deterministic$m=2$$m=3$$m=7$$m=99$improvement: black-blue (b) Neopets

Figure 4: Cost-Even Breakpoints, Uniform Breakpoint Distribution

$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$10^{8}$$0$$0.2$$0.4$$0.6$$0.8$$1$

uncertain region

$v/C_{max}$ Percentage of Cracked Passwords deterministic$m=3$, uniform$m=3$,
biteopt (a) Linkedin

$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$10^{8}$$0$$0.2$$0.4$$0.6$$0.8$$1$

uncertain region

$v/C_{max}$ Percentage of Cracked Passwords deterministic$m=3$, uniform$m=3$,
biteopt (b) Neopets

Figure 5: Cost-Even Breakpoints, Optimized Breakpoint Distribution

###  7.2 Experiment Analysis

##### Time-Even Breakpoints and Uniform Distribution.

First we would like to demonstrate time-even breakpoints are not suitable. In
Figure 3, we show attacker’s success rate against $v/C_{max}$ when the
attacker plays locally optimal strategy $\pi_{LO}$ and breakpoint distribution
is uniform, namely $\beta_{i}=i$ and $q_{i}=\frac{1}{m},\forall i\leq m$. For
most $v/C_{max}$ ratios we have $\pi_{LO}=\pi^{*}$, only a few points fails
$\mathsf{OptimalityTest}(v,\vec{q},\pi_{LO})$ and they are in unconfident
region. Since the attacker is playing the same game against every account,
success rate can be interpreted as the percentage of cracked accounts.

From Figure 3, we observe that time-even breakpoints can reduce attacker’s
success rate for most of the time. Unfortunately, this is not always the case.
Take Linkedin as example, when $v/C_{max}=100$, no account is cracked in
deterministic cost hashing. However, there are 0.2% accounts that would be
cracked if time-even breakpoints were used. Similar phenomenon can be observed
in other datasets, which is amplified by circles in Figure 3. When we
randomize the label index in password hashing with MHF, we have
$\frac{\Pr[pw_{u}]\Pr[t_{1}]}{\Pr[pw_{u}]}=1/m$ while
$\frac{c_{M}t_{1}^{2}}{C_{max}}=\frac{1}{(m+1)(2m+1)}\in\mathcal{O}(\frac{1}{m^{2}})$.
In other words, the probability that the attacker successfully guesses the
first label drops lineally while the cost of making that guess drops
quadratically. This is the reason that time-even breakpoints might have
negative effect at the beginning of these plots.

Here we also give a contrived example to show that time-even breakpoints could
be harmful. Suppose a dataset has 2 passwords, each occurs with probability
$\frac{1}{2}$, and password value $v=1.5-\epsilon$, hash cost $c=1$. In this
case, the attacker will not try to check any password (if only one guess is
made the attacker will obtain expected gain $v/2$ with cost 1, resulting in
negative expected utility; if the attacker guesses at most twice, gain is $v$
and cost is 1.5, the expected utility is still negative). On the other hand,
if breakpoints are time-even, we have $c_{1}=0.4$ (hash cost of evaluating MHF
to the first label), $c_{2}=1.6$ (hash cost of evaluating MHF to the second
label) with expected cost being $c$; checking the first label of both
passwords gives the attacker utility $0.05-\epsilon/2$, as long as
$\epsilon<0.1$ the attacker will crack the password with probability at least
$\frac{1}{4}$.

##### Cost-Even Breakpoints and Uniform Distribution.

We have proved that cost-even breakpoints with uniform distribution always
yields lower (or equal if no passwords are cracked) attacker’s success rate in
Theorem 5.4. Experiment results (see Figure 5) also verified our therotical
conclusion.

Another observation is that increasing $m$ can further reduce the percentage
of cracked passwords. In confident region there is up to 10% of passwords that
would have been cracked can be now saved when $m=99$. However, the marginal
benefit is diminishing, that is to say, the reduction in $\lambda(\pi^{*})$
from $m=i$ to $m=i+1$ is decreasing as $i$ grows larger. From Figure 5, we see
that success rate reduction by increasing $m$ from 3 to 7 is roughly the same
as that by increasing $m$ from 7 to 99. In full version of this paper, we
prove that the marginal cost of checking $\varpi_{i}(1,m)$ given
$\oplus_{i^{\prime}=1}^{i-1}\varpi(1,m)$ already been checked is roughly
proportional to $\frac{m}{m+1}$, thus the advantage of increasing $m$ is
significant when $m$ is small, but there is barely any improvement by
increasing $m$ when $m$ is already large. Since
$\frac{7}{8}-\frac{3}{4}\approx\frac{99}{100}-\frac{7}{8}$, performance
improvement of increasing $m$ from 3 to 7 is roughly the same as that of
increasing $m$ from 7 to 99.

##### Optimized Distribution and Cost-Even Breakpoints.

We use BITEOPT[45] to find the optimal distribution $\vec{q}^{*}$, the results
are shown in Figure 5. It can be seen that the performance of optimal
distribution is almost identical to that of uniform distribution in term of
attacker’s success rate. This can be observed in all of the datasets in our
experiments. Adopting $\vec{q}^{*}$ has comparatively small advantage and
require the server to know password distribution in advance, which is
difficult in practice. Thus we recommend to use cost-even break points with
uniform distribution as a _prior independent_ password hashing mechanism.

##  8 Conclusion

In this paper, we introduce cost-asymmetric memory hard password
authentication, a prior independent authentication mechanism, to defend
against offline attacks. As traditional hash function are replaced by memory
hard functions, we propose to use random breakpoints in evaluation of an MHF
in order to have the benefit of both cost asymmetry and cost quadratic
scaling. The interaction between the defender and the attacker is modeled by a
Stackelberg game, within the game theory framework we formulate the optimal
strategies for both defender and attacker. We theoretically proved that cost-
asymmetric memory hard password authentication with cost-even breakpoints
sampled from uniform distribution will reduce attacker’s cracking success
rate. In addition we set up experiments to validate the effectiveness of our
proposed mechanism for arbitrary parameter settings, experiment results show
that the reduction of attacker’s success rate is up to 10%.

## References

  * [1] Hashcast: advanced password recovery, https://hashcat.net/hashcat/
  * [2] Password hashing competition, https://password-hashing.net/
  * [3] Adams, A., Sasse, M.A.: Users are not the enemy. Communications of the ACM 42(12), 40–46 (1999)
  * [4] Alwen, J., Blocki, J.: Efficiently computing data-independent memory-hard functions. In: Robshaw, M., Katz, J. (eds.) Advances in Cryptology – CRYPTO 2016, Part II. Lecture Notes in Computer Science, vol. 9815, pp. 241–271. Springer, Heidelberg, Germany, Santa Barbara, CA, USA (Aug 14–18, 2016). https://doi.org/10.1007/978-3-662-53008-5_9
  * [5] Alwen, J., Blocki, J., Harsha, B.: Practical graphs for optimal side-channel resistant memory-hard functions. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 2017: 24th Conference on Computer and Communications Security. pp. 1001–1017. ACM Press, Dallas, TX, USA (Oct 31 – Nov 2, 2017). https://doi.org/10.1145/3133956.3134031
  * [6] Alwen, J., Blocki, J., Pietrzak, K.: Depth-robust graphs and their cumulative memory complexity. In: Coron, J., Nielsen, J.B. (eds.) Advances in Cryptology – EUROCRYPT 2017, Part III. Lecture Notes in Computer Science, vol. 10212, pp. 3–32. Springer, Heidelberg, Germany, Paris, France (Apr 30 – May 4, 2017). https://doi.org/10.1007/978-3-319-56617-7_1
  * [7] Alwen, J., Chen, B., Pietrzak, K., Reyzin, L., Tessaro, S.: Scrypt is maximally memory-hard. In: Coron, J., Nielsen, J.B. (eds.) Advances in Cryptology – EUROCRYPT 2017, Part III. Lecture Notes in Computer Science, vol. 10212, pp. 33–62. Springer, Heidelberg, Germany, Paris, France (Apr 30 – May 4, 2017). https://doi.org/10.1007/978-3-319-56617-7_2
  * [8] Bai, W., Blocki, J.: Dahash: Distribution aware tuning of password hashing costs. In: Financial Cryptography and Data Security. Springer International Publishing (2021)
  * [9] Biryukov, A., Dinu, D., Khovratovich, D.: Argon2: new generation of memory-hard functions for password hashing and other applications. In: Security and Privacy (EuroS&P), 2016 IEEE European Symposium on. pp. 292–302. IEEE (2016)
  * [10] Blocki, J., Datta, A.: CASH: A cost asymmetric secure hash algorithm for optimal password protection. In: IEEE 29th Computer Security Foundations Symposium. pp. 371–386 (2016)
  * [11] Blocki, J., Harsha, B., Kang, S., Lee, S., Xing, L., Zhou, S.: Data-independent memory hard functions: New attacks and stronger constructions. In: Annual International Cryptology Conference. pp. 573–607. Springer (2019)
  * [12] Blocki, J., Harsha, B., Zhou, S.: On the economics of offline password cracking. In: 2018 IEEE Symposium on Security and Privacy. pp. 853–871. IEEE Computer Society Press, San Francisco, CA, USA (May 21–23, 2018). https://doi.org/10.1109/SP.2018.00009
  * [13] Blocki, J., Komanduri, S., Procaccia, A., Sheffet, O.: Optimizing password composition policies. In: Proceedings of the fourteenth ACM conference on Electronic commerce. pp. 105–122. ACM (2013)
  * [14] Boneh, D., Corrigan-Gibbs, H., Schechter, S.E.: Balloon hashing: A memory-hard function providing provable protection against sequential attacks. In: Cheon, J.H., Takagi, T. (eds.) Advances in Cryptology – ASIACRYPT 2016, Part I. Lecture Notes in Computer Science, vol. 10031, pp. 220–248. Springer, Heidelberg, Germany, Hanoi, Vietnam (Dec 4–8, 2016). https://doi.org/10.1007/978-3-662-53887-6_8
  * [15] Bonneau, J.: The science of guessing: Analyzing an anonymized corpus of 70 million passwords. In: 2012 IEEE Symposium on Security and Privacy. pp. 538–552. IEEE Computer Society Press, San Francisco, CA, USA (May 21–23, 2012). https://doi.org/10.1109/SP.2012.49
  * [16] Bonneau, J., Herley, C., van Oorschot, P.C., Stajano, F.: The quest to replace passwords: A framework for comparative evaluation of web authentication schemes. In: 2012 IEEE Symposium on Security and Privacy. pp. 553–567. IEEE Computer Society Press, San Francisco, CA, USA (May 21–23, 2012). https://doi.org/10.1109/SP.2012.44
  * [17] Boyen, X.: Halting password puzzles: Hard-to-break encryption from human-memorable keys. In: Provos, N. (ed.) USENIX Security 2007: 16th USENIX Security Symposium. USENIX Association, Boston, MA, USA (Aug 6–10, 2007)
  * [18] Campbell, J., Ma, W., Kleeman, D.: Impact of restrictive composition policy on user password choices. Behaviour & Information Technology 30(3), 379–388 (2011)
  * [19] Carnavalet, X., Mannan, M.: From very weak to very strong: Analyzing password-strength meters. In: ISOC Network and Distributed System Security Symposium – NDSS 2014. The Internet Society, San Diego, CA, USA (Feb 23–26, 2014)
  * [20] Castelluccia, C., Chaabane, A., Dürmuth, M., Perito, D.: When privacy meets security: Leveraging personal information for password cracking. arXiv preprint arXiv:1304.6584 (2013)
  * [21] Castelluccia, C., Dürmuth, M., Perito, D.: Adaptive password-strength meters from Markov models. In: ISOC Network and Distributed System Security Symposium – NDSS 2012. The Internet Society, San Diego, CA, USA (Feb 5–8, 2012)
  * [22] Designer, S.: John the ripper password cracker (2006)
  * [23] Florêncio, D., Herley, C., Van Oorschot, P.C.: An administrator’s guide to Internet password research. In: Proceedings of the 28th USENIX Conference on Large Installation System Administration. pp. 35–52. LISA’14 (2014)
  * [24] Fossi, M., Johnson, E., Turner, D., Mack, T., Blackbird, J., McKinney, D., Low, M.K., Adams, T., Laucht, M.P., Gough, J.: Symantec report on the underground economy (November 2008), retrieved 1/8/2013.
  * [25] Hansen, N.: The cma evolution strategy: A comparing review (2006)
  * [26] Inglesant, P.G., Sasse, M.A.: The true cost of unusable password policies: Password use in the wild. In: Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. pp. 383–392. CHI ’10, ACM, New York, NY, USA (2010). https://doi.org/10.1145/1753326.1753384, http://doi.acm.org/10.1145/1753326.1753384
  * [27] Kaliski, B.: Pkcs# 5: Password-based cryptography specification version 2.0 (2000)
  * [28] Kelley, P.G., Komanduri, S., Mazurek, M.L., Shay, R., Vidas, T., Bauer, L., Christin, N., Cranor, L.F., Lopez, J.: Guess again (and again and again): Measuring password strength by simulating password-cracking algorithms. In: 2012 IEEE Symposium on Security and Privacy. pp. 523–537. IEEE Computer Society Press, San Francisco, CA, USA (May 21–23, 2012). https://doi.org/10.1109/SP.2012.38
  * [29] Komanduri, S., Shay, R., Cranor, L.F., Herley, C., Schechter, S.: Telepathwords: Preventing weak passwords by reading users’ minds. In: 23rd USENIX Security Symposium (USENIX Security 14). pp. 591–606. USENIX Association, San Diego, CA (Aug 2014), https://www.usenix.org/conference/usenixsecurity14/technical-sessions/presentation/komanduri
  * [30] Komanduri, S., Shay, R., Kelley, P.G., Mazurek, M.L., Bauer, L., Christin, N., Cranor, L.F., Egelman, S.: Of passwords and people: measuring the effect of password-composition policies. In: CHI. pp. 2595–2604 (2011), http://dl.acm.org/citation.cfm?id=1979321
  * [31] Liu, E., Nakanishi, A., Golla, M., Cash, D., Ur, B.: Reasoning analytically about password-cracking software. In: 2019 IEEE Symposium on Security and Privacy (SP). pp. 380–397. IEEE (2019)
  * [32] Ma, J., Yang, W., Luo, M., Li, N.: A study of probabilistic password models. In: 2014 IEEE Symposium on Security and Privacy. pp. 689–704. IEEE Computer Society Press, Berkeley, CA, USA (May 18–21, 2014). https://doi.org/10.1109/SP.2014.50
  * [33] Manber, U.: A simple scheme to make passwords based on one-way functions much harder to crack. Computers & Security 15(2), 171–176 (1996)
  * [34] Melicher, W., Ur, B., Segreti, S.M., Komanduri, S., Bauer, L., Christin, N., Cranor, L.F.: Fast, lean, and accurate: Modeling password guessability using neural networks. In: Holz, T., Savage, S. (eds.) USENIX Security 2016: 25th USENIX Security Symposium. pp. 175–191. USENIX Association, Austin, TX, USA (Aug 10–12, 2016)
  * [35] Morris, R., Thompson, K.: Password security: A case history. Communications of the ACM 22(11), 594–597 (1979)
  * [36] Percival, C.: Stronger key derivation via sequential memory-hard functions. In: BSDCan 2009 (2009)
  * [37] Provos, N., Mazieres, D.: Bcrypt algorithm. USENIX (1999)
  * [38] Shay, R., Komanduri, S., Durity, A.L., Huh, P.S., Mazurek, M.L., Segreti, S.M., Ur, B., Bauer, L., Christin, N., Cranor, L.F.: Can long passwords be secure and usable? In: Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. pp. 2927–2936. CHI ’14, ACM, New York, NY, USA (2014). https://doi.org/10.1145/2556288.2557377, http://doi.acm.org/10.1145/2556288.2557377
  * [39] Shay, R., Komanduri, S., Kelley, P.G., Leon, P.G., Mazurek, M.L., Bauer, L., Christin, N., Cranor, L.F.: Encountering stronger password requirements: user attitudes and behaviors. In: Proceedings of the Sixth Symposium on Usable Privacy and Security. pp. 2:1–2:20. SOUPS ’10, ACM, New York, NY, USA (2010). https://doi.org/10.1145/1837110.1837113, http://doi.acm.org/10.1145/1837110.1837113
  * [40] Stanton, J.M., Stam, K.R., Mastrangelo, P., Jolton, J.: Analysis of end user security behaviors. Comput. Secur. 24(2), 124–133 (Mar 2005)
  * [41] Steves, M., Chisnell, D., Sasse, A., Krol, K., Theofanos, M., Wald, H.: Report: Authentication diary study. Tech. Rep. NISTIR 7983, National Institute of Standards and Technology (NIST) (2014)
  * [42] Stockley, M.: What your hacked account is worth on the dark web (Aug 2016), https://nakedsecurity.sophos.com/2016/08/09/what-your-hacked-account-is-worth-on-the-dark-web/
  * [43] Ur, B., Kelley, P.G., Komanduri, S., Lee, J., Maass, M., Mazurek, M., Passaro, T., Shay, R., Vidas, T., Bauer, L., Christin, N., Cranor, L.F.: How does your password measure up? the effect of strength meters on password creation. In: Proceedings of USENIX Security Symposium (2012)
  * [44] Ur, B., Segreti, S.M., Bauer, L., Christin, N., Cranor, L.F., Komanduri, S., Kurilova, D., Mazurek, M.L., Melicher, W., Shay, R.: Measuring real-world accuracies and biases in modeling password guessability. In: Jung, J., Holz, T. (eds.) USENIX Security 2015: 24th USENIX Security Symposium. pp. 463–481. USENIX Association, Washington, DC, USA (Aug 12–14, 2015)
  * [45] Vaneev, A.: BITEOPT - Derivative-free optimization method. Available at https://github.com/avaneev/biteopt (2021), c++ source code, with description and examples
  * [46] Veras, R., Collins, C., Thorpe, J.: On semantic patterns of passwords and their security impact. In: ISOC Network and Distributed System Security Symposium – NDSS 2014. The Internet Society, San Diego, CA, USA (Feb 23–26, 2014)
  * [47] Weir, M., Aggarwal, S., de Medeiros, B., Glodek, B.: Password cracking using probabilistic context-free grammars. In: 2009 IEEE Symposium on Security and Privacy. pp. 391–405. IEEE Computer Society Press, Oakland, CA, USA (May 17–20, 2009). https://doi.org/10.1109/SP.2009.8

###  0..1 Marginal Cost

Let $\sum_{i^{\prime=1}}^{i-1}\Pr[pw_{i}]=\lambda$,
$c_{M}(t_{i}^{2}-t_{i-1}^{2})=c$, then

$\displaystyle C_{adv}^{u}(\varpi_{i}(1,m)|\Pi(i-1,m))=(1-\lambda)c$ (13)
$\displaystyle+\left(1-\lambda-\Pr[pw_{i}]\frac{1}{m}\right)c+,\ldots,$
$\displaystyle+\left(1-\lambda-\Pr[pw_{i}]\frac{m-1}{m}\right)c$
$\displaystyle=(1-\lambda)mc-\frac{\Pr[pw_{i}]c(m-1)}{2}.$

Because of workload constraint we have,

$\alpha=\sum_{i=1}^{m}\beta_{i}^{2}/m=\frac{m+1}{2}.$

thus, $c=C_{max}/\alpha=\frac{2C_{max}}{m+1}$, substitute it into equation
(16), we have

$\displaystyle C_{adv}^{u}(\varpi_{i}(1,m)|\Pi(i-1,m))$ (14)
$\displaystyle=\frac{2m}{m+1}(1-\lambda)C_{max}-\frac{(m-1)\Pr[pw_{i}]C_{max}}{m+1}.$

On the other hand, we have

$C_{adv}^{d}(pw_{i}|\oplus_{i^{\prime}=1}^{i-1}pw_{i^{\prime}})=(1-\lambda)C_{max}.$
(15)

Take the difference of equation (14) and equation (15),

$\displaystyle
C_{adv}^{u}(\varpi_{i}(1,m)|\Pi(i-1,m))-C_{adv}^{d}(pw_{i}|\oplus_{i^{\prime}=1}^{i-1}pw_{i^{\prime}})$
$\displaystyle=\frac{m-1}{m+1}C_{max}\left((1-\lambda)-\Pr[pw_{i}]\right)\geq
0.$

###  0..2 Optimality Test

Since $\pi_{LO}$ is locally optimal adding any instruction bundle for a single
password $e=\varpi_{i}(j_{1},j_{2})$ into $\pi_{LO}$ will decrease the overall
utility, namely, $\Delta\left(e\,\middle|\,\pi\right)<0$, recall that
$\Delta\left(e\,\middle|\,\pi\right)$ denotes the marginal utility by
including $e$ into $\pi$, either through concatenation or insersion. However,
there is no guarantee $\Delta\left(S\,\middle|\,\pi_{LO}\right)<0$ where $S$
is an ordered set of instruction bundles $\\{e_{1},e_{2},\ldots,e_{b}\\}$
since marginal utility is not _additive_ with respect to instruction bundles.
To see this, from equation (2) we can derive

$\small\Delta\left(S\,\middle|\,\pi_{LO}\right)=\sum_{e\in
S}\Delta\left(e\,\middle|\,\pi_{LO}\right)+\sum_{e_{2}\in
S}\overbrace{c(e_{2})\sum_{\begin{subarray}{c}e_{1}\in S\\\
e_{1}<e_{2}\end{subarray}}\Pr[e_{1}]}^{\text{cost reduction for $e_{2}$}},$
(16)

where $\Pr[e]$ and $c(e)$ are probability summation and round cost summation
of instructions in $e$, respectively. Equation (16) shows that the marginal
cost by including a ordered set $S$ to $\pi_{LO}$ stems from 2 parts. The
first is the summation of individual contribution and the second is cost
reduction when checking $e_{2}\in S$ because previously included instruction
bundles $e_{1}<e_{2},e_{1}\in S$ have already eliminate some uncertainty. Even
though every instruction bundle solely contributes negative marginal utility
i.e, $\Delta\left(e\,\middle|\,\pi_{LO}\right)<0,\,e\in S$, the sign of
$\Delta\left(S\,\middle|\,\pi_{LO}\right)$ is not decisive because of the cost
reduction term. If a set $S$ exists such that
$\Delta\left(S\,\middle|\,\pi\right)\geq 0$, we will refer it to as a _good
set_.

By definition of good set and Theorem 5.5, we have

$\small\pi^{*}=\pi_{LO}\cup S^{*},\text{ s.t.
}S^{*}=\operatorname*{arg\,max}_{S}\Delta\left(S\,\middle|\,\pi_{LO}\right).$
(17)

Recall that $\cup$ denotes inclusion (whether through concatenation or
insertion) while maintaining natural ordering. 333Technically,
$\operatorname*{arg\,max}_{S}$ returns a set of solutions $S^{*}$. However, if
this set contains multiple elements we can break ties according to the size of
$|S^{*}|$ and followed by an arbitrary lexicographic ordering over solutions
with same size.

Verify if $S$ is a good set of $\pi_{LO}$ is easy but find one is hard. We
design a polynomial algorithm to check if the local optimum $\pi_{LO}$ is in
fact a global optimum, i.e., $\pi_{LO}=\pi^{*}$. Our algorithm utilizes the
following observation.

###### Observation 1

if $S=\\{e_{1},\ldots,e_{b}\\}$ is a good set for $\pi_{LO}$, then its last
element $e_{b}$ must provide non-negative utility (otherwise, it can be safely
removed from $S$ without hurting marginal utility), namely

$\Delta\left(e_{b}\,\middle|\,\pi_{LO}\cup{S\setminus e_{b}}\right)\geq 0,$

where $S\setminus e_{b}$ is the ordered set excluding $e_{b}$.

It is not clear which elements are inside $S\setminus e_{b}$ but we know
$S\setminus
e_{b}\subseteq\mathsf{Before}\left(e_{b}\,\middle|\,\pi_{LO}\right)$ where
$\mathsf{Before}\left(e_{b}\,\middle|\,\pi_{LO}\right)$ is the ordered set of
all unchecked instructions that appear before $e_{b}$ in natural ordering,
given $\pi_{LO}$ already being checked, namely,

$\mathsf{Before}\left(e_{b}\,\middle|\,\pi_{LO}\right)\vcentcolon=\\{e:e<e_{b}\text{
and }e\not\in\pi_{LO}\\}.$

We use following Lemma to negate the existence of a good set ending with
$e_{b}$.

######  Lemma 3 ()

For a unchecked instruction bundle $e_{b}$, define

$\mathsf{test}(e_{b})\vcentcolon=\Delta\left(e_{b}\,\middle|\,\pi_{LO}\right)+\sum_{e\in\mathsf{Before}\left(e_{b}\,\middle|\,\pi_{LO}\right)}\Pr[e]c(e_{b}),$

if $\mathsf{test}(e_{b})<0$ then a good set $S$ for $\pi_{LO}$ ending with
$e_{b}$ does not exist.

###### Proof

$\displaystyle\Delta\left(e_{b}\,\middle|\,\pi_{LO}\cup{S\setminus
e_{b}}\right)=\Delta\left(e_{b}\,\middle|\,\pi_{LO}\right)+\sum_{e\in
S\setminus e_{b}}\Pr[e]c(e_{b}),$
$\displaystyle\leq\Delta\left(e_{b}\,\middle|\,\pi_{LO}\right)+\sum_{e\in\mathsf{Before}\left(e_{b}\,\middle|\,\pi_{LO}\right)}\Pr[e]c(e_{b})$
$\displaystyle=\mathsf{test}(e_{b}).$

If $\mathsf{test}(e_{b})<0$, then
$\Delta\left(e_{b}\,\middle|\,\pi_{LO}\cup{S\setminus e_{b}}\right)<0$, $S$
cannot be a good set.

We can interpret the term
$\sum_{e\in\mathsf{Before}\left(e_{b}\,\middle|\,\pi_{LO}\right)}\Pr[e]c(e_{b})$
as the maximum possible cost reduction when checking $e_{b}$, then
$\mathsf{test}(e_{b})$ is the maximum marginal utility $e_{b}$ can provide as
the last instruction bundle in $S$. If $\mathsf{test}(e_{b})<0$, a set ending
with $e_{b}$ cannot be a good set; if this is the case for all instructions
$e_{b}\in\Pi(\mathsf{Len}_{max},m)\setminus\pi_{LO}$ that might be added to
$\pi_{LO}$, then a good set ending with any unchecked instruction bundle does
not exist. Thus, in Equation (17) we have $S^{*}=\emptyset$ and
$\pi_{LO}=\pi^{*}$. We use $\mathsf{OptimalityTest}(v,\vec{q},\pi_{LO})$ to
examine if $\pi_{LO}=\pi^{*}$ — see Algorithm 4.

Input: $v$, $\vec{q}$, $\pi_{LO}$

Output: $\pi^{*}$

1 foreach  _$e_{b}\in\Pi(\mathsf{Len}_{max},m)\setminus\pi_{LO}$_ do

2 if  _$\mathsf{test}(e_{b})\geq 0$_ then

3 return _FAIL_ ;

4

5 end if

6

7 end foreach

return _PASS_

Algorithm 4 $\mathsf{OptimalityTest}(v,\vec{q},\pi_{LO})$

######  Theorem 0..1 ()

If $\mathsf{OptimalityTest}(v,\vec{q},\pi_{LO})$ returns PASS, then
$\pi_{LO}=\pi^{*}$.

###### Proof

Since $\mathsf{OptimalityTest}(v,\vec{q},\pi_{LO})$ returns PASS, then we have

$\Delta\left(e_{b}\,\middle|\,\pi_{LO}\cup{S\setminus
e_{b}}\right)\leq\mathsf{test}(e_{b})<0,\,\forall S.$

For any $S$ it would only increase overall utility by repeatedly removing the
last element in $S$ until it is empty. Therefore, a good set is a empty set.
In other words, $\pi_{LO}=\pi^{*}$.

By storing of $\lambda(\pi_{LO},i)$ and
$\sum_{i^{\prime}=1}^{i}\Pr[pw_{i^{\prime}}]$ for all $i$, which are
intermidiate values in execution of $\mathsf{Extend}(v,\vec{q})$, in amortized
sense we can evaluate $\mathsf{test}(e_{b})$ in time $\mathcal{O}(1)$, then
$\mathsf{OptimalityTest}(v,\vec{q},\pi_{LO})$ runs in time
$\mathcal{O}(n_{p}m)$. We remark that even if $\pi_{LO}$ fails
$\mathsf{OptimalityTest}(v,\vec{q},\pi_{LO})$, it does not imply
$\pi_{LO}\neq\pi^{*}$, since $\mathsf{test}(e_{b})<0$ is a sufficient
condition of no good set ending with $e_{b}$, not a necessary one.
Fortunately, $\mathsf{OptimalityTest}(v,\vec{q},\pi_{LO})$ returns PASS for
most of the time in our experiments, confirming $\pi_{LO}=\pi^{*}$ for most
$v/C_{max}$ ratios; otherwise, we might discard
$\mathsf{OptimalityTest}(v,\vec{q},\pi_{LO})$ as well.

###  0..3 Finding $\pi^{*}$ for cost-even breakpoints when $m\leq 3$

If $\pi_{LO}$ fails $\mathsf{OptimalityTest}(v,\vec{q},\pi_{LO})$, we cannot
deduce any conclusions about the optimality of $\pi_{LO}$, but when
$\beta_{i}=\sqrt{i}$ and $m\leq 3$ we can design an efficient brute force
algorithm to find $\pi^{*}$.

###### Definition 4

Given a vector of real numbers $\vec{q}=(q_{1},\ldots,q_{m})$ we call $q_{j}$
a peak of $\vec{q}$ if (1) $j=m$, or (2) $j=1$ and $q_{1}>q_{2}$, or (3)
$q_{j-1}\leq q_{j}$ and $q_{j}>q_{j+1}$. We use $\mathsf{peak}(\vec{q})$ to
denote the set of all peak indices in $\vec{q}$.

######  Lemma 4 ()

Fix an arbitrary breakpoint distribution $\vec{q}=(q_{1},\ldots,q_{m})$.
Suppose that $\beta_{j}=\sqrt{j}$ for all $j\leq m$ and
$\pi_{LO}=\oplus_{i=1}^{\mathsf{Len}(\pi_{LO})}\varpi_{i}(1,\tau_{i})$, then
for all $i\leq\mathsf{Len}(\pi_{LO})$ we have
$\tau_{i}\in\mathsf{peak}(\vec{q})$.

###### Proof

Suppose $\tau_{i}=j\neq m$, since $(pw_{i},t_{j})\in\pi_{LO}$, then

$\Delta\left(\pi_{LO}-(pw_{i},t_{j}),\pi_{LO}\right)\geq 0,$

where $-$ is removal operation. Since $j$ is not a peak, then we have
$q_{j+1}\geq q_{j}$ which leads to

$\Delta\left((pw_{i},t_{j+1}),\pi_{LO}\right)>\Delta\left(\pi_{LO}-(pw_{i},t_{j}),\pi_{LO}\right).$

Therefore $\Delta\left(\pi_{LO},\pi_{LO}+(pw_{i},t_{j+1})\right)>0$. It is
still profitable to advance a label for $pw_{i}$ i.e., check
$(pw_{i},t_{j+1})$, so $(pw_{i},t_{j+1})$ should have been included into
$\pi_{LO}$ in local search. Contradiction.

######  Lemma 5 ()

Fix an arbitrary breakpoint distribution $\vec{q}=(q_{1},\ldots,q_{m})$.
Suppose that $\beta_{j}=\sqrt{j}$ for all $j\leq m$ and
$\pi^{*}=\oplus_{i=1}^{\mathsf{Len}(\pi^{*})}\varpi_{i}(1,\tau_{i}^{*})$, then
for all $i\leq\mathsf{Len}(\pi^{*})$ we have
$\tau_{i}^{*}\in\mathsf{peak}(\vec{q})$.

###### Observation 2

when $m=2$, $\mathsf{peak}(\vec{q})$ is in
$\left\\{\\{2\\},\\{1,2\\}\right\\}$; when $m=3$, $\mathsf{peak}(\vec{q})$ is
in $\left\\{\\{3\\},\\{1,3\\},\\{2,3\\}\right\\}$;

$\lvert\mathsf{peak}(\vec{q})\rvert=1$ correspons to uniform breakpoint
distribution for which $\mathsf{ExtendbyConcat}(v,\vec{q},\emptyset)$ already
gives the optimal checking sequence $\pi^{*}$.

Lemmas 4 and 5 imply that if a good set $S$ _with respect to insertion_ exists
for $\pi_{LO}$, every instruction bundle in $S$ must start at a peak position
and end with another peak position. Specially, when
$\mathsf{peak}(\vec{q})=\\{peak_{1},m\\}$, the only tentative insertion
operation to promote locally optimal $\pi_{LO}$ to global optimal $\pi^{*}$ is
to check a password to completion, i.e., change the largest label index
$\tau_{i}$ from $peak_{1}$ to $m$.

The following theorem states that we can efficiently construct an ordered set
$S_{c}(i,\pi)$ which provides larger marginal utility upon insertion than any
other ordered set of the same size.

######  Theorem 0..2 ()

If $\mathsf{peak}(\vec{q})=\\{peak_{1},m\\}$ and $\beta_{i}=\sqrt{i}$ for
$i\leq m$, given $\pi=\oplus_{i=1}^{\mathsf{Len}}\varpi_{i}(1,\tau_{i})$ with
$\tau_{i}\in\mathsf{peak}(\vec{q})$ and
$\mathsf{unchecked}(\pi)=\\{\varpi_{i}(peak_{1},m):i\leq\mathsf{Len}(\pi)\text{
and }\tau_{i}=peak_{1}\\}$—the set of unchecked instruction bundles spanning
two peaks, we define

$S_{c}(i,\pi)\vcentcolon=\begin{cases}\emptyset,\text{ if }i=0,\\\
\\{e_{1},\ldots,e_{i}\\},\text{ if }i>0.\\\ \end{cases}$

where $e_{i},\,\forall i>0$ is recursively defined as

$e_{i}\vcentcolon=\operatorname*{arg\,max}_{e\in\mathsf{unchecked}(\pi+S_{c}(i-1,\pi))}\Delta^{+}\left(e\,\middle|\,\pi+S_{c}(i-1,\pi)\right).$

Then we have

$\displaystyle\Delta^{+}\left(S_{c}(i,\pi)\,\middle|\,\pi\right)$
$\displaystyle\geq\Delta^{+}\left(S\,\middle|\,\pi\right),$
$\displaystyle\forall i,\,\forall S\subseteq\mathsf{unchecked}(\pi)\text{ s.t.
}|S_{c}(i,\pi)|=|S|.$

We first prove the following Lemma, which is utilized in proof of Theorem
0..2.

###### Lemma 6

When $\beta_{i}=\sqrt{i}$, suppose $e_{1}=\varpi_{i1}(j_{1},j_{2})$, and
$e_{2}=\varpi_{i_{2}}(j_{1},j_{2})$, if
$\Delta^{+}\left(e_{1}\,\middle|\,\pi\right)\geq\Delta^{+}\left(e_{1}\,\middle|\,\pi\right)$,
then $\Pr(e_{1})\geq\Pr(e_{2})$.

###### Proof

Proof by contradiction. Let $c_{M}(t_{j_{2}}^{2}-t_{j_{1}}^{2})=c$. Suppose
$\Pr(e_{1})<\Pr(e_{2})$, then $e_{1}>e_{2}$, we have

$\displaystyle\Delta^{+}\left(e_{1}\,\middle|\,\pi\right)-\Delta^{+}\left(e_{2}\,\middle|\,\pi\right)$
$\displaystyle=\Pr(e_{1})\left(v+\sum_{e>e_{1},e\in\pi}c\right)-\left(1-\sum_{e<e_{1},e\in\pi}\Pr(e)\right)c$
$\displaystyle-\Pr(e_{2})\left(v+\sum_{e>e_{2},e\in\pi}c\right)+\left(1-\sum_{e<e_{2},e\in\pi}\Pr(e)\right)c$
$\displaystyle=\left(\Pr(e_{1})-\Pr(e_{2})\right)\left(v+\sum_{e>e_{1},e\in\pi}c\right)$
$\displaystyle-\Pr(e_{2})\sum_{e_{2}<e\leq e_{1},e\in\pi}c+c\sum_{e_{2}\leq
e<e_{1},e\in\pi}\Pr(e)$
$\displaystyle=\left(\Pr(e_{1})-\Pr(e_{2})\right)\left(v+\sum_{e>e_{1},e\in\pi}c\right)$
$\displaystyle+c\sum_{e_{2}<e<e_{1}}\Pr(e)-\Pr(e_{2})$
$\displaystyle\leq\left(\Pr(e_{1})-\Pr(e_{2})\right)\left(v+\sum_{e>e_{1},e\in\pi}c\right)<0,$

which contradicts the precondition
$\Delta^{+}\left(e_{1}\,\middle|\,\pi\right)\geq\Delta^{+}\left(e_{2}\,\middle|\,\pi\right)$

Now we prove Theorem 0..2.

###### Proof

In this proof $S_{c}(i,\pi)$ is written in $S_{c}(i)$ for simplicity. Let
$S=\\{e_{1}^{\prime},e_{2}^{\prime},\ldots,e_{i}^{\prime}\\}$. Since
$S\subseteq\mathsf{unchecked}(\pi)$ and
$S_{c}(i)\subseteq\mathsf{unchecked}(\pi)$, instruction bundles in $S$ and
$S_{c}(i)$ have the same size. Let $c(e)=c,\forall e\in S_{c}(i),\,\forall
e\in S$. Therefore, by definition of $e_{i}$ and Lemma 6 we have
$\Pr(e_{j})\geq\Pr(e_{j}^{\prime}),\,\forall j\leq i$.

Theorem 0..2 equivalently claims

$\Delta^{+}\left(S_{c}(i)\,\middle|\,\pi\right)\geq\Delta^{+}\left(S_{c}(i-n)\cup\\{e_{i-n+1}^{\prime},\ldots,e_{i}^{\prime}\\}\,\middle|\,\pi\right),\forall
n.$

We will use mathematical induction to prove the above inequalities. Base case
$n=1$:

$\displaystyle\Delta^{+}\left(S_{c}(i)\,\middle|\,\pi\right)$
$\displaystyle=\Delta^{+}\left(S_{c}(i-1)\,\middle|\,\pi\right)+\Delta^{+}\left(e_{i}\,\middle|\,\pi+S_{c}(i-1)\right)$
$\displaystyle\geq\Delta^{+}\left(S_{c}(i-1)\,\middle|\,\pi\right)+\Delta^{+}\left(e_{i}^{\prime}\,\middle|\,\pi+S_{c}(i-1)\right)$
$\displaystyle=\Delta^{+}\left(S_{c}(i-1)\cup\\{e_{i}^{\prime}\\}\,\middle|\,\pi\right).$

The inequality holds because of the definition of $e_{i}$ i.e.,
$e_{i}=\arg\max_{e}\Delta^{+}\left(e\,\middle|\,\pi+S_{c}(i-1)\right)$.

Inductive hypothesis: equation (0..3) holds true for $n=k$.

Inductive step: in the following we prove that equation (0..3) holds true for
$n=k+1$.

$\displaystyle\Delta^{+}\left(S_{c}(i)\,\middle|\,\pi\right)$
$\displaystyle\geq\Delta^{+}\left(S_{c}(i-k)\cup\\{e_{i-k+1}^{\prime},\ldots,e_{i}^{\prime}\\}\,\middle|\,\pi\right)$
$\displaystyle=\Delta^{+}\left(S_{c}(i-k-1)\,\middle|\,\pi\right)+\Delta^{+}\left(e_{k}\,\middle|\,\pi+S_{c}(i-k-1)\right)$
$\displaystyle+\Delta^{+}\left(\\{e_{i-k+1}^{\prime},\ldots,e_{i}^{\prime}\\}\,\middle|\,\pi+S_{c}(i-k-1)+e_{k}\right)$
$\displaystyle\geq\Delta^{+}\left(S_{c}(i-k-1)\,\middle|\,\pi\right)+\Delta^{+}\left(e_{k}^{\prime}\,\middle|\,\pi+S_{c}(i-k-1)\right)$
$\displaystyle+\Delta^{+}\left(\\{e_{i-k+1}^{\prime},\ldots,e_{i}^{\prime}\\}\,\middle|\,\pi+S_{c}(i-k-1)+e_{k}\right)$
$\displaystyle\geq\Delta^{+}\left(S_{c}(i-k-1)\,\middle|\,\pi\right)+\Delta^{+}\left(e_{k}^{\prime}\,\middle|\,\pi+S_{c}(i-k-1)\right)$
$\displaystyle+\Delta^{+}\left(\\{e_{i-k+1}^{\prime},\ldots,e_{i}^{\prime}\\}\,\middle|\,\pi+S_{c}(i-k-1)+e_{k}^{\prime}\right)$
$\displaystyle=\Delta^{+}\left(S_{c}(i-k-1)\cup\\{e_{i-k}^{\prime},\ldots,e_{i}^{\prime}\\}\,\middle|\,\pi\right).$

The first inequality is inductive hypothesis; the second inequality holds
because of the definition of $e_{k}$; the third inequality is the result of
Lemma 1 given $\Pr[e_{k}]\geq\Pr[e_{k}^{\prime}]$.

We can loop over all candidates $S_{c}(i,\pi_{LO}),\,\forall i$ and find the
_good set w.r.t insertion_ $S_{c}^{*}(\pi_{LO})$, which provides the largest
marginal utility for $\pi_{LO}$, namely,

$S_{c}^{*}(\pi_{LO})=\operatorname*{arg\,max}_{S_{c}(i,\pi_{LO})}\Delta^{+}\left(S_{c}(i,\pi_{LO})\,\middle|\,\pi_{LO}\right).$
(18)

A good set $S^{*}$ might contain instruction bundles that can be concatenated
to $\pi_{LO}$, to handle this case we also need to loop over $len$—possible
length of $\pi^{*}$. The efficient brute force algorithm
$\mathsf{FindOptSeq}(v,\vec{q},\pi)$ is present in Algorithm 5.

Input: $v$, $\vec{q}$, $\pi$

Output: $\pi^{*}$

1

2$U^{*}=\Delta\left(\emptyset,\pi\right)$;

3 for  _$len=\mathsf{Len}(\pi):\mathsf{Len}_{max}$_ do

4 if  _$len >\mathsf{Len}(\pi)$_ then

5 $\pi=\pi\circ\varpi_{len}(1,peak_{1})$;

6

7 end if

8 foreach  _$i$_ do

9 construct $S_{c}(i,\pi)$;

10 compute $\Delta^{+}\left(S_{c}(i,\pi\,\middle|\,\pi\right)$;

11

12 end foreach

13
$S_{c}^{*}(\pi)=\operatorname*{arg\,max}_{i}\Delta^{+}\left(S_{c}(i,\pi\,\middle|\,\pi\right)$;

14 if  _$\Delta\left(\emptyset,\pi+S_{c}^{*}(\pi)\right)\geq U^{*}$_ then

15 $\pi^{*}=\pi+S_{c}^{*}(\pi)$;

16 $U^{*}=\Delta\left(\emptyset,\pi+S_{c}^{*}(\pi)\right)$;

17

18 end if

19

20 end for

return _$\pi^{*}$_

Algorithm 5 $\mathsf{FindOptSeq}(v,\vec{q},\pi)$

Suppose $|\mathsf{unchecked}(\pi)|=n$, finding $e_{1}$ takes time
$\mathcal{O}(n)$; finding $e_{2}$ takes time $\mathcal{O}(n-1)$, etc. Thus,
the inner loop in Algorithm 5 takes time
$\mathcal{O}(n^{2})\subseteq\mathcal{O}(n_{p}^{2})$, and the total running
time is
$\mathcal{O}(n_{p}^{2}\left(\mathsf{Len}_{max}-\mathsf{Len}(\pi)\right)$.
444In implementation we can exploit opt restriction 3 and the fact that
ordering of $e_{i}$ is mainly unchanged after update $\mathsf{Len}(\pi)$ to
further reduce running time. We also remark in experiments it is (almost)
always the case $\pi^{*}=\pi_{LO}+S_{c}^{*}(\pi_{LO})$ and for most of the
time $S_{c}^{*}(\pi_{LO})=\emptyset$.

######  Theorem 0..3 ()

When $|\mathsf{peak}(\vec{q})|=2$ and $\beta_{i}=\sqrt{i}$,
$\mathsf{FindOptSeq}(v,\vec{q},\pi_{LO})$ returns the optimal checking
sequence.

###### Proof

Lemma 4 and 5 restrict a good set to be a subset of $\mathsf{unchecked}(\pi)$.
Theorem 0..2 guarantees that $S_{c}(i,\pi)$ is “better” than any other set $S$
of the same size, namely,

$\Delta\left(\emptyset,\pi+S_{c}(i,\pi)\right)\geq\Delta\left(\emptyset,\pi+S\right),\forall
S\subseteq\mathsf{unchecked}(\pi).$

By definition of $S_{c}^{*}(\pi)$, we have
$\Delta\left(\emptyset,\pi+S_{c}^{*}(\pi)\right)\geq\Delta\left(\emptyset,\pi+S_{c}(i,\pi)\right),\forall
i.$ The outer loop of $\mathsf{FindOptSeq}(v,\vec{q},\pi)$ traverses all
possible $\mathsf{Len}(\pi^{*})$ and returns the $\pi+S_{c}^{*}(\pi)$ with
largest utility. By equation (17) the the returned checking sequence is
optimal.

We could potentially run $\mathsf{FindOptSeq}(v,\vec{q},\emptyset)$ to find
the optimal checking sequence $\pi^{*}$. As a shortcut, we run
$\mathsf{FindOptSeq}(v,\vec{q},\pi_{LO})$ instead to reduce the running time.

###### Corollary 3

When $m\leq 3$ and $\beta_{i}=\sqrt{i}$, There are polynomial algorithms that
always find the optimal checking sequence.

If $|\mathsf{peak}(\vec{q})|=1$,
$\mathsf{ExtendbyConcat}(v,\vec{q},\emptyset)$ returns the optimal checking
sequence; if $|\mathsf{peak}(\vec{q})|=2$,
$\mathsf{FindOptSeq}(v,\vec{q},\pi_{LO})$ returns the optimal checking
sequence.

###  0..4 Proof of Other Lemmas

####  0..4.1 Proof of Lemma 1

See 1

###### Proof

Suppose $e_{i}$ is the $i$th instruction bundle in $\pi_{3}$, from equation 10
we have

$\Delta^{\circ}\left(e_{1}\,\middle|\,\pi_{1}\right)=\Pr[pw_{i}]q_{j}v-\left(1-\lambda(\pi_{1})\right)c_{M}(t_{j}^{2}-t_{j-1}^{2}),$

and

$\Delta^{\circ}\left(e_{1}\,\middle|\,\pi_{2}\right)=\Pr[pw_{i}]q_{j}v-\left(1-\lambda(\pi_{2})\right)c_{M}(t_{j}^{2}-t_{j-1}^{2}).$

Thus,

$\Delta^{\circ}\left(e_{1}\,\middle|\,\pi_{1}\right)\leq\Delta^{\circ}\left(e_{1}\,\middle|\,\pi_{2}\right),$

similarly,

$\Delta^{\circ}\left(e_{i}\,\middle|\,\pi_{1}\circ\oplus_{i^{\prime}=1}^{i-1}e_{i^{\prime}}\right)\leq\Delta^{\circ}\left(e_{i}\,\middle|\,\pi_{2}\circ\oplus_{i^{\prime}=1}^{i-1}e_{i^{\prime}}\right).$

Therefore, we have

$\displaystyle\Delta^{\circ}\left(\pi_{3}\,\middle|\,\pi_{1}\right)$
$\displaystyle=\sum_{i}\Delta^{\circ}\left(e_{i}\,\middle|\,\pi_{1}\circ\oplus_{i^{\prime}=1}^{i-1}e_{i^{\prime}}\right)$
$\displaystyle\leq\sum_{i}\Delta^{\circ}\left(e_{i}\,\middle|\,\pi_{2}\circ\oplus_{i^{\prime}=1}^{i-1}e_{i^{\prime}}\right)=\Delta^{\circ}\left(\pi_{3}\,\middle|\,\pi_{2}\right)$

###  0..5 Proof of Other Theorems

####  0..5.1 Proof of Theorem 5.1

See 5.1

###### Proof

Given
$\pi^{*}=\oplus_{i^{\prime}=1}^{i^{*}}\varpi_{i^{\prime}}(1,\tau_{i^{\prime}})$,
suppose there exists $\varpi_{i}(1,\tau_{i})\subseteq\pi^{*}$, for some
$i>\mathsf{Len}_{max},\tau_{i}>0$, we have

$\displaystyle\Delta^{\circ}\left(\varpi_{i}(1,\tau_{i})\,\middle|\,\oplus_{i=1}^{i-1}\varpi_{i}(1,\tau_{i})\right)$
$\displaystyle\leq\max_{1\leq j\leq
m}\\{\Delta^{\circ}\left(\varpi_{i}(1,j)\,\middle|\,\oplus_{i=1}^{i-1}\varpi_{i}(1,\tau_{i})\right)\\}$
$\displaystyle\leq\max_{1\leq j\leq
m}\\{\Delta^{\circ}\left(\varpi_{i}(1,j)\,\middle|\,\Pi(i-1,m)\right)\\}$
$\displaystyle<0,$

we can safely remove instructions $\varpi_{i}(1,\tau_{i})$ for all
$i>\mathsf{Len}_{max}$ from $\pi^{*}$ to obtain another checking sequence that
yields a better utility. Contradiction.

####  0..5.2 Proof of Theorem 5.2

See 5.2

###### Proof

Suppose $\pi^{*}=\oplus_{i=1}^{i^{*}}\varpi_{i}(1,\tau_{i})$ and
$\varpi_{i}(\tau_{i}+1,j)\in\pi_{LOC}$ is the first instruction bundle that
$\pi^{*}$ and $\pi_{LOC}$ disagree.

Split $\pi^{*}$ into two parts $\pi_{a}^{*}$ and $\pi_{b}^{*}$ where
$\pi_{a}^{*}$ is the sub-sequence from the beginning of $\pi^{*}$ to
instruction $(pw_{i},t_{\tau_{i}})$ inclusive and $\pi_{b}^{*}$ is remaining
checking sequence. Formally,

$\pi_{a}^{*}\vcentcolon=\oplus_{i^{\prime}=1}^{i}\varpi_{i^{\prime}}(1,\tau_{i^{\prime}}),$

and

$\pi_{b}^{*}\vcentcolon=\oplus_{i^{\prime}=i+1}^{i^{*}}\varpi_{i^{\prime}}(1,\tau_{i^{\prime}}).$

Since $\varpi_{i}(\tau_{i}+1,j)\in\pi_{l0}$

$\Delta^{\circ}\left(\varpi_{i}(\tau_{i}+1,j)\,\middle|\,\pi_{a}^{*}\right)\geq
0.$

The attacker can obtain another checking sequence
$\sigma=\pi_{a}^{*}\circ\varpi_{i}(\tau_{i}+1,j)\circ\pi_{b}^{*}$. Note that
by Lemma 1, we have

$\Delta^{\circ}\left(\pi_{b}^{*}\,\middle|\,\pi_{a}^{*}\circ\varpi_{i}(\tau_{i}+1,j)\right)>\Delta^{\circ}\left(\pi_{b}^{*}\,\middle|\,\pi_{a}^{*}\right)$

Adding both sides of above two inequalities, then both sides of the obtained
inequality are added by $\Delta\left(\emptyset,\pi_{a}^{*}\right)$, we have

$\displaystyle U_{adv}(v,\vec{q},\sigma)$
$\displaystyle=\Delta\left(\emptyset,\pi_{a}^{*}\right)+\Delta^{\circ}\left(\varpi_{i}(\tau_{i}+1,j)\,\middle|\,\pi_{a}^{*}\right)$
$\displaystyle+\Delta^{\circ}\left(\pi_{b}^{*}\,\middle|\,\pi_{a}^{*}\circ\varpi_{i}(\tau_{i}+1,j)\right)$
$\displaystyle>U_{adv}(v,\vec{q},\pi^{*}),$

contracting optimality of $\pi^{*}$.

####  0..5.3 Proof of Theorem 5.3

See 5.3

###### Proof

Given these parameters it is easy to verify that

$\displaystyle\Delta^{\circ}\left(\varpi_{i}(1,1)\,\middle|\,\oplus_{i=1}^{i-1}\varpi_{i}(1,\tau_{i})\right)$
$\displaystyle<\Delta^{\circ}\left(\varpi_{i}(2,2)\,\middle|\,\oplus_{i=1}^{i-1}\varpi_{i}(1,\tau_{i})\circ\varpi_{i}(1,1)\right)$
$\displaystyle<\cdots$
$\displaystyle<\Delta^{\circ}\left(\varpi_{i}(m,m)\,\middle|\,\oplus_{i=1}^{i-1}\varpi_{i}(1,\tau_{i})\circ\varpi_{i}(1,m-1)\right)$

Therefore

$\displaystyle\max_{0\leq j\leq
m}\left\\{\Delta^{\circ}\left(\varpi_{i}(0,m)\,\middle|\,\oplus_{i=1}^{i-1}\varpi_{i}(1,\tau_{i})\right)\right\\}$
$\displaystyle=\max\left\\{0,\Delta^{\circ}\left(\varpi_{i}(1,m)\,\middle|\,\oplus_{i=1}^{i-1}\varpi_{i}(1,\tau_{i})\right)\right\\}$

Algorithm $\mathsf{ExtendbyConcat}(v,\vec{q},\emptyset)$ will set $\tau_{i}=m$
for $i\leq\mathsf{Len}(\pi_{LOC})$ and $\tau_{i}=0$ for
$i>\mathsf{Len}(\pi_{LOC})$. In other words,

$\begin{cases}\Delta^{\circ}\left(\varpi_{i}(1,m)\,\middle|\,\Pi(i-1,m)\right)\geq
0,\text{ if }i\leq\mathsf{Len}(\pi_{LOC}),\\\
\Delta^{\circ}\left(\varpi_{i}(1,m)\,\middle|\,\Pi(i-1,m)\right)<0,\text{ if
}i>\mathsf{Len}(\pi_{LOC}).\end{cases}$

Those are also the criterion of defining $\mathsf{Len}_{max}$ under current
parameter settings, hence $\mathsf{Len}(\pi_{LOC})=\mathsf{Len}_{max}$.
Moreover, the superset and subset of $\pi^{*}$ are identical, i.e.,
$\Pi(\mathsf{Len}_{max},m)=\pi_{LOC}$. Since there are no unchecked
instruction bundle $\varpi_{i}(j_{1},j_{2})$ for $i\leq\mathsf{Len}_{max}$, we
have $\pi_{LOC}=\pi^{*}=\Pi(\mathsf{Len}_{max},m)$.

####  0..5.4 Proof of Theorem 5.4

See 5.4

###### Proof

When using uniform breakpoint distribution, the execution trace of the
attacker’s cracking process is similar to deterministic hashing, i.e.,
sequentially eliminating the possibility of $pw_{u}=pw_{i}$ (or verifying it
with any luck) for $i=1,2,\ldots$. It can be verified (see Appendix 0..1) that

$C_{adv}^{u}(\varpi_{i}(1,m)|\Pi(i-1,m))\geq
C_{adv}^{d}(pw_{i}|\oplus_{i^{\prime}=1}^{i-1}pw_{i^{\prime}}),\;\forall i,$

where $C_{adv}^{u}(\varpi_{i}(1,m)|\Pi(i-1,m))$ is the marginal cost of
checking $\varpi_{i}(1,m)$, given $\Pi(i-1,m)$ has already been checked.
$C_{adv}^{d}(pw_{i}|\oplus_{i^{\prime}=1}^{i-1}pw_{i^{\prime}})$ is the
marginal cost of checking $pw_{i}$ under deterministic cost hashing given
passwords $pw_{1},\ldots,pw_{i-1}$ have been checked. In order to achieve the
same success rate, uniform cost-even breakpoints would incur more cost than
deterministic cost hashing. See it in another way, when $v/C_{max}$ is fixed
for both cases uniform cost-even breakpoints results in a lower adversary
success rate.

####  0..5.5 Proof of Theorem 5.5

See 5.5

###### Proof

In proof of Theorem 5.2 we already know $\circ$ operation preserves the
following invariant

$\pi\circ e\subseteq\pi^{*},\text{ if }\pi\subseteq\pi^{*}\text{ and
}\Delta^{\circ}\left(e\,\middle|\,\pi\right)\geq 0.$

Lemma 2 states

$\pi+e\subseteq\pi^{*},\text{ if }\pi\subseteq\pi^{*}\text{ and
}\Delta^{+}\left(e\,\middle|\,\pi\right)\geq 0.$

$\pi_{LO}$ is obtained by iteratively applying $\circ$ and $+$ operation,
hence is a subset of $\pi^{*}$

###  0..6 Derivative-Free Optimization

There are many derivative-free optimization solvers available in the
literature, generally they fall into two catagorites, deterministic algorithm
(such as Nelder-Mead) and evolutionary algorithm (such as BITEOPT [45] and
CMA-EA [25]). $\mathsf{OptPepperDis}()$ takes password value $v$ as input and
outputs optimal pepper distribution $\vec{q}^{*}$ and attacker’s success rate
$P_{adv}^{*}$ when playing with best response given defender’s strategy
$\vec{q}^{*}$. During one iteration of $\mathsf{OptPepperDis}()$, some
candidate pepper distributions $\\{\vec{q}_{c_{i}}\\}$ are proposed, together
they are referred as _population_. Then the algorithm
$\mathsf{BestRes}(v,\vec{q}_{c_{i}})$ is called as a subroutine for each
member of population, and the returned $P_{adv}$ is recorded as “fitness”. At
the end of each iteration, the population is updated according to fitness of
its’ members, the update could be either through deterministic transformation
(Nelder-Mead) or randomized evolution (BITEOPT, CMA-EA). When the iteration
number reaches a pre-defined value $ite$, the best fit member $\vec{q}^{*}$
and its fitness $P_{adv}^{*}$ are returned.

###  0..7 Results of other datasets

$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$10^{8}$$0$$0.2$$0.4$$0.6$$0.8$$1$

uncertain region

$v/C_{max}$ Percentage of Cracked Passwords Deterministic$m=3$Fails Optimality
Test (a) Bfield

$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$10^{8}$$0$$0.2$$0.4$$0.6$$0.8$$1$

uncertain region

$v/C_{max}$ Percentage of Cracked Passwords Deterministic$m=3$Fails Optimality
Test (b) Brazzers

$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$10^{8}$$0$$0.2$$0.4$$0.6$$0.8$$1$

uncertain region

$v/C_{max}$ Percentage of Cracked Passwords Deterministic$m=3$Fails Optimality
Test (c) Clixsense

$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$10^{8}$$0$$0.2$$0.4$$0.6$$0.8$$1$

uncertain region

$v/C_{max}$ Percentage of Cracked Passwords Deterministic$m=3$Fails Optimality
Test (d) CSDN

$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$10^{8}$$0$$0.2$$0.4$$0.6$$0.8$$1$

uncertain region

$v/C_{max}$ Percentage of Cracked Passwords Deterministic$m=3$Fails Optimality
Test (e) Rockyou

$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$10^{8}$$0$$0.2$$0.4$$0.6$$0.8$$1$

uncertain region

$v/C_{max}$ Percentage of Cracked Passwords Deterministic$m=3$Fails Optimality
Test (f) Webhost

Figure 6: Time-Even Breakpoints, Uniform Pepper Distribution

$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$10^{8}$$0$$0.2$$0.4$$0.6$$0.8$$1$

uncertain region

$v/C_{max}$ Percentage of Cracked Passwords
deterministic$m=2$$m=3$$m=7$$m=99$improvement: black-blue (a) Bfield

$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$10^{8}$$0$$0.2$$0.4$$0.6$$0.8$$1$

uncertain region

$v/C_{max}$ Percentage of Cracked Passwords
deterministic$m=2$$m=3$$m=7$$m=99$improvement: black-blue (b) Brazzers

$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$10^{8}$$0$$0.2$$0.4$$0.6$$0.8$$1$

uncertain region

$v/C_{max}$ Percentage of Cracked Passwords
deterministic$m=2$$m=3$$m=7$$m=99$improvement: black-blue (c) Clixsense

$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$10^{8}$$0$$0.2$$0.4$$0.6$$0.8$$1$

uncertain region

$v/C_{max}$ Percentage of Cracked Passwords
deterministic$m=2$$m=3$$m=7$$m=99$improvement: black-blue (d) CSDN

$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$10^{8}$$0$$0.2$$0.4$$0.6$$0.8$$1$

uncertain region

$v/C_{max}$ Percentage of Cracked Passwords
deterministic$m=2$$m=3$$m=7$$m=99$improvement: black-blue (e) Rockyou

$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$10^{8}$$0$$0.2$$0.4$$0.6$$0.8$$1$

uncertain region

$v/C_{max}$ Percentage of Cracked Passwords
deterministic$m=2$$m=3$$m=7$$m=99$improvement: black-blue (f) Webhost

Figure 7: Cost-Even Breakpoints, Uniform Pepper Distribution

$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$10^{8}$$0$$0.2$$0.4$$0.6$$0.8$$1$

uncertain region

$v/C_{max}$ Percentage of Cracked Passwords deterministic$m=3$, uniform$m=3$,
biteopt (a) Bfield

$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$10^{8}$$0$$0.2$$0.4$$0.6$$0.8$$1$

uncertain region

$v/C_{max}$ Percentage of Cracked Passwords deterministic$m=3$, uniform$m=3$,
biteopt (b) Brazzers

$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$10^{8}$$0$$0.2$$0.4$$0.6$$0.8$$1$

uncertain region

$v/C_{max}$ Percentage of Cracked Passwords deterministic$m=3$, uniform$m=3$,
biteopt (c) Clixsense

$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$10^{8}$$0$$0.2$$0.4$$0.6$$0.8$$1$

uncertain region

$v/C_{max}$ Percentage of Cracked Passwords deterministic$m=3$, uniform$m=3$,
biteopt (d) CSDN

$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$10^{8}$$0$$0.2$$0.4$$0.6$$0.8$$1$

uncertain region

$v/C_{max}$ Percentage of Cracked Passwords deterministic$m=3$, uniform$m=3$,
biteopt (e) Rockyou

$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$10^{8}$$0$$0.2$$0.4$$0.6$$0.8$$1$

uncertain region

$v/C_{max}$ Percentage of Cracked Passwords deterministic$m=3$, uniform$m=3$,
biteopt (f) Webhost

Figure 8: Cost-Even Breakpoints, Optimized Pepper Distribution

$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$10^{8}$$0$$0.2$$0.4$$0.6$$0.8$$1$

uncertain region

$v/C_{max}$ Percentage of Cracked Passwords deterministicTime-Even
BreakpointsCost-Even Breakpoints (a) Linkedin

$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$10^{8}$$0$$0.2$$0.4$$0.6$$0.8$$1$

uncertain region

$v/C_{max}$ Percentage of Cracked Passwords deterministicTime-Even
BreakpointsCost-Even Breakpoints (b) Neopets