\pdfpagewidth=8.5in
\pdfpageheight=11in
\documentclass{sig-alternate}
\usepackage{url}

% I hate overfull hboxes protruding into the right margin!
\pretolerance=500
\tolerance=1000
\setlength{\emergencystretch}{30pt}
\begin{document}

% This metadata appears in the ACM copyright box in the lower-left corner.
\permission{Copyright is held by the author/owner.
Permission to make digital or hard copies of all or part of this work
for personal or classroom use is granted without fee.}
\conferenceinfo{Symposium On Usable Privacy and Security (SOUPS) 2006,}{July 12--14, 2006, Pittsburgh, PA, USA}
\toappear{\the\boilerplate\par {\confname{\the\conf}} \the\confinfo.}

\title{Passpet: Convenient Password Management\\and Phishing Protection}
\numberofauthors{2}
\author{
\alignauthor
Ka-Ping Yee\\
\affaddr{University of California, Berkeley}\\
\email{ping@zesty.ca}
\alignauthor
Kragen Sitaker\\
\email{kragen@pobox.com}
}
\date{7 March 2006}
\maketitle

\begin{abstract}
We describe Passpet, a tool that
improves both the convenience and security of website logins
through a combination of techniques.
Password hashing 
helps users manage multiple accounts by
turning a single memorized password
into a different password for each account.
User-assigned site labels (petnames)
help users securely identify sites
in the face of determined attempts at impersonation (phishing).
Password-strengthening measures
defend against dictionary attacks.
Customizing the user interface
defends against user-interface spoofing attacks.
We propose new improvements to these techniques,
discuss how they are integrated into a single tool,
and compare Passpet to other solutions
for managing passwords and preventing phishing.
\end{abstract}

\category{C.2.0}{Computer-Communication Networks}{General---Security and protection}
\category{H.3.5}{Information Storage and Retrieval}{Online Information Services---Web-based services}
\category{H.4.3}{Information Systems Applications}{Communications Applications---Information browsers}
\category{H.5.2}{Information Interfaces and Presentation}{User Interfaces---Graphical user interfaces}

\section{Introduction}

Passwords are the most commonly used type of authentication on the Web,
but they have many usability problems and security weaknesses.
Password security
depends on choosing passwords that are unique and hard to guess,
yet long passwords can be difficult to remember and retype correctly.
The passwords that are easiest to choose and memorize
tend to be vulnerable to {\em dictionary attacks},
in which an attacker tries to guess the password
by constructing likely possibilities
from lists of words and common passwords.
Changing passwords frequently helps to resist attack,
but makes the task of memorizing passwords even harder.
Using the same password or related passwords at multiple sites
compromises password secrecy,
yet memorizing a different password for every site
imposes an unrealistic burden on human users.
Password login forms are also vulnerable to {\em phishing attacks},
in which the user is fooled into entering a password at an imitation site.
Some of the more sophisticated phishing attacks
also corrupt or mimic parts of the browser's user interface
to mislead the user about a site's true identity.

\begin{figure}
\centering
\scalebox{0.60}[0.60]
{\includegraphics*[viewport=72 520 472 720]{figure-1.pdf}}
\caption{One click on the Passpet button fills in a login form
with a site-specific password.}
\end{figure}

%As this paper will review,
%Many different password management tools
%and anti-phishing mechanisms have been proposed and implemented.
%These problems are closely related ---
%they both involve managing trust relationships with websites.
%Therefore,
%we have reason to believe
%that an integrated approach would be useful.

Passpet improves upon and combines several previously devised techniques ---
password hashing, petnames, password strengthening, and UI customization ---
to mitigate all of the problems just mentioned,
helping users manage website logins
both more conveniently and more securely.
Whereas most other solutions improve password security
at the cost of some extra effort to log in,
Passpet improves password security
while making the process of logging in more convenient.
With Passpet,
the user clicks a button to fill in a password,
in login forms (Figure 1) and in other contexts.

As with any system that tries to address many competing requirements,
Passpet incorporates some tradeoffs in its design.
Passpet makes logging in more convenient
at the cost of a more involved process to change the user's secret;
it reduces the user's memory burden
at the cost of introducing an external dependency;
it supports non-SSL sites
at the cost of some risk if non-SSL site passwords are intercepted.
We have made these tradeoffs in a way that we believe
improves security and usability for most users,
keeping in mind that phishing attacks and dictionary attacks
tend to be high-volume attacks.

In addition to describing Passpet as a specific point
in the design space,
this paper also contributes some ideas in secure interaction design
that are separable and could be reapplied in other contexts:
\begin{itemize}
\item
Using user-assigned site labels for password hashing.
\item
Continuously estimating the dictionary-attack time
while the user enters a new password.
\item
Variable levels of password strengthening,
configured by the user simply by waiting.
\item
Associating a security tool with a persona
that differs from user to user.
\item
Customizing the button for activating a security tool
in order to prevent spoofing.
\end{itemize}
Below, we will describe in more detail
how these techniques are applied in Passpet,
how Passpet generates passwords,
how the usage of Passpet fits in with current practices,
and how Passpet's security and usability
compare to existing alternatives.

\section{Problem and Goals}

In the following discussion of the problems surrounding passwords,
we identify several goals for a password tool.

In the current password regime,
the security goal of keeping passwords different from site to site
competes with the limitations of human memory.
Users tend to reuse passwords
because memorizing many passwords is difficult
and choosing many passwords is inconvenient.
We would like the user to only have to memorize one secret
instead of many,
but still have a unique password at each site
to reduce the user's vulnerability
in the case of a break-in at one account
or a malicious administrator at a site hosting an account.

Because any human-chosen secret is likely to have much less entropy
than a truly random secret,
we would like to provide
a defense against dictionary attacks on such secrets.
Since offline dictionary attacks depend on computational speed,
we would also like this defense to remain effective
in future years as faster computers become available.

The reason phishing works is that
users are constantly asked to enter passwords
without a convenient, reliable way to know
whom they're giving their passwords to.
The user interface they use to enter secrets
is completely controlled by an unidentified party.
Today's login forms {\em train} users to be excellent targets
for phishing attacks.
Any effective phishing solution
must provide a way to identify the other party
and must get users out of the habit
of giving secrets to strangers.
Some attacks try to fool users by imitating login forms,
and some attacks imitate parts of the browser's user interface;
we would like to address both of these kinds of attacks.

For robustness and flexibility,
we would like our password scheme
to avoid centralized external dependencies.
We also prefer not to store the user's passwords,
in order to reduce the user's exposure to risk
in the event of theft or break-in of a system where passwords are stored.

%Avoid relying on users to attend to secondary indicators.
%users will not adopt something that's less convenient
%users can't distinguish real from fake webpage content

%--- can be divided:
%user effort per computer; user effort per session;
%user effort per login
%(effort to activate, effort to notice secondary indicators)
%
%--- possible additional goal:
%avoid relying on the user to attend to secondary indicators

We must also consider
several compatibility and deployability constraints
for a password tool.
We assume that it is impractical to require websites
to change their login functionality to accommodate a new tool,
and further that it is impractical to expect users
to migrate all their accounts to a new scheme at once.
Currently, users can change their passwords at individual sites;
we want users to still have this ability
and to be able to use sites
that require periodic password changes.
Also, users can currently log in to websites from anywhere ---
such as from a computer at the office,
from a friend's computer,
or in an emergency while travelling.
Retaining this ability is important.

Finally, we note that 
any password management tool
will require some changes in user behaviour,
however slight.
Voluntary adoption of a tool will be much less likely
if it offers no convenience benefit
(or, worse, if it imposes additional inconvenience
compared to current practice);
therefore, we seek a design
that improves convenience at least for the most common user task,
which is logging in.

In summary, we aim to achieve the following:\\
\\
{\em Usability Goals}
\begin{enumerate}
\setlength{\itemsep}{0pt}
\setlength{\parskip}{0pt}
\item Improve the convenience of logging in to websites.
\item Work with existing websites and login forms.
\item Allow site-by-site migration to the new scheme.
\item Allow the user to change passwords for individual sites.
\item Allow the user to log in from more than one computer.
\item Let the user only have to memorize one secret.
\item Allow the user to change the master secret.
\end{enumerate}
{\em Security Goals}
\begin{enumerate}
\setlength{\itemsep}{0pt}
\setlength{\parskip}{0pt}
\setcounter{enumi}{7}
\item Use a unique password for each site.
\item Resist offline dictionary attacks on user-chosen secrets.
\item Adapt to the development of faster computers.
\item Avoid storing passwords in long-term storage.
\item Avoid introducing a centralized dependency.
\item Resist attacks based on fake website login forms.
\item Resist attacks based on imitating the browser UI.
\item Help the user reliably identify websites.
\item \em Break the habit of entering passwords into webpages.
\end{enumerate}

\section{Background and Related Work}

\subsection{Password Management}

{\em Password databases} are a component of most modern browsers,
including Firefox, Safari, Internet Explorer, and Opera.
Mac~OS~X also includes a password database at the operating system level.
These databases maintain a list of the user's usernames and passwords,
usually stored encrypted on the user's computer.
Typically, the user is prompted to decide
whether or not each password should be stored.
When the browser detects that it has returned to a site
for which it knows a stored password,
it automatically fills in the login form
with the stored username and password.
One drawback to this scheme is
that the stored passwords are only available on one computer (Goal~5).
Introducing a remote service to provide access to one's passwords
would pose the additional risk of remotely storing passwords (Goal~11).
Finally, password databases do not address the problem
of using the same password at multiple sites (Goal~8).

{\em Password hashing} refers to the practice
of hashing a fixed, secret string (the ``master secret'')
together with a variable, non-secret string
to produce a password.
Different values for the variable part
yield different hash values,
thus generating many different passwords,
each with about as much entropy as the master secret.
Using a one-way hash makes it difficult for an attacker
who obtains one of the generated passwords
to determine the master secret.
Password hashing
allows the user to only have to memorize one secret (Goal~6),
but still use a unique password for each account (Goal~8).
Since the login passwords are computed,
they don't have to be stored (Goal~11).
This scheme also leaves open the possibility of
storing the non-secret strings elsewhere,
allowing the user to move from computer to computer (Goal~5).

Among the many implementations of password hashing are
the Lucent Personalized Web Assistant~\cite{lpwa},
HP Site Password~\cite{ssp}, and PwdHash~\cite{pwdhash}.
LPWA is an HTTP proxy that manages usernames, passwords, and e-mail addresses
to anonymize and protect the user's website accounts.
At the beginning of a session the user enters a master secret;
in login forms, the user enters ``$\backslash$U'' as the username
and ``$\backslash$P'' as the password,
which the LPWA proxy replaces with computed values.
HP Site Password is a standalone tool
that accepts a master password and a site name
and puts the computed site password on the system clipboard
so the user can paste it into a password field.
PwdHash is an implementation of password hashing in Firefox.
Whenever the user enters a password beginning with ``@@'',
PwdHash hashes the password together with the domain name of the website
before submitting it.

\subsection{Password Strength}

Although the entire space of possible passwords
may be very large,
the attacker in a dictionary attack
reduces the search space
by making assumptions
about how passwords are commonly chosen ---
for example, that they contain
natural-language words, proper names, dates, and so on.
If the user's password fits those assumptions,
the attacker may hit upon the password in a tractable length of time.
To help users choose better passwords,
some password selection forms
% such as those at Google and Hotmail,
now provide a simple strength indicator (weak, medium, or strong)
that updates while the user is typing.

Increasing the amount of work required
for an attacker to check each guess
can also help improve resistance to dictionary attack (Goal~9).
Abadi, Lomas, and Needham~\cite{strengthening}
suggested that a user's chosen password
can be strengthened by appending a random supplement of a fixed length.
The random supplement is never stored;
every login attempt requires searching for the value of the supplement.
Kelsey, Schneier, Hall, and Wagner~\cite{stretching}
proposed a scheme called {\em key stretching}
in which the password must be hashed repeatedly a fixed number of times
before it can be used.
Halderman, Waters, and Felten~\cite{multiplier}
refined this scheme in a tool called Password Multiplier,
which caches an intermediate hashing result on the user's machine
to make logins faster for valid users.
Passpet uses a further refinement of this scheme
in which the amount of hashing is variable
so that it can keep up with increases in computing power (Goal~10).

\subsection{Anti-Phishing Measures}

{\bf Blocked site lists} are a popular response to the phishing problem.
In such schemes, a single central database
maintains a list of fraudulent sites;
browsers check this database before proceeding to a site.
Earthlink~\cite{earthlink} and Netcraft~\cite{netcraft}
both provide these services,
implemented on the client by a browser toolbar.
Microsoft's published plans for Internet Explorer 7~\cite{ie7-certs}
include a coloured indicator in the address bar
that shows the status of the current site in Microsoft's database.
These approaches can prevent phishing attacks
if fraudulent sites are discovered and listed quickly (Goals 13 and 14),
but they demand universal trust in a single authority
and centralize vulnerability to failure (Goal~12).
A centralized blocking list
also ignores the possibility
of honest differences in opinion among users ---
to choose a recent example,
there has been some controversy
about whether Claria belongs on spyware lists~\cite{eweek}.
Finally, there are significant privacy problems
with any scheme in which many clients
send browsing information to a central authority.

\smallskip

{\bf Site information indicators} provide information
about the site in the browser toolbar or status bar.
The URL field is an indicator already present in all browsers;
in theory, a user could check the domain name
in the URL to avoid phishing attacks,
but in practice, the URL bar provides little protection.
Most of the participants 
in a recent study~\cite{whyworks}
were fooled by misleading domain names
(such as {\tt www.bankofthevvest.com},
which may be visually mistaken for {\tt www.bankofthewest.com},
or {\tt www.paypal-signin03.com},
which may seem to be associated with {\tt www.paypal.com}).

SpoofStick~\cite{spoofstick} is a browser extension
that displays the current site's domain name
in large letters in the toolbar
to make the identification task a bit easier,
but it still relies on the user's ability
to distinguish legitimate and illegitimate domain names.
Firefox displays the domain name of the SSL certificate
in the status bar when a secure connection is present.
However, even a perfectly competent expert user
can be fooled by {\em homograph attacks}~\cite{homograph},
in which the illegitimate domain name contains Unicode characters
that are visually indistinguishable from their legitimate counterparts.

Instead of relying on the correctness of the domain name,
some approaches rely on the SSL certificate authority.
A browser extension called TrustBar~\cite{trustbar}
and the design for Internet Explorer 7~\cite{ie7-certs}
both offer a toolbar indicator
that displays the name of the certificate authority
and the site's name in the SSL certificate.
It is not clear whether the name of the CA
will be meaningful to users,
and the displayed site name
remains susceptible to homograph attacks.

Some anti-phishing schemes employ {\em visual customization}
of the login form,
making the form look different for each user
so that it will be hard to attackers to imitate accurately.
The SiteKey feature~\cite{sitekey} currently deployed by Bank of America
displays a user-selected image and ``image title'' with the login form,
in the hope that the user will notice
when an attacker tries to imitate the login form
but fails to display the correct image.
Another scheme called Dynamic Security Skins~\cite{dss}
transparently overlays a user-selected image
over the entire login form
and relies on a new login protocol, SRP,
for securing the authentication process.

\smallskip

{\bf Petname systems}
let a user assign {\em petnames} (local labels) to objects,
then translate global (or other) identifiers for objects
into the user's local namespace of petnames~\cite{petnames}.
Though the ``petname'' moniker is more recent,
the concept is old and familiar.
For example, when a mobile phone rings with an incoming call,
and the caller's number is in the phone's contact list,
most phones will translate the caller's number (the global identifier)
into the caller's name (the user's local identifier).
In instant messaging systems such as ICQ or AIM,
each user has a unique number or username in a global namespace.
% Although users initially contact each other using this global identifier,
Most IM clients let the user assign ``friendly names'' to other users;
thereafter, the IM client refers to the other user
using the locally assigned name instead of the global identifier.

A Firefox extension called the Petname Tool~\cite{petname-tool}
lets users securely assign labels to websites.
TrustBar~\cite{trustbar} allows users to assign logo images as well as labels.
When logging in, users can check the displayed site label
to ensure that they are at the intended site.
In addition to helping users detect imitation websites (Goal~13),
petnames also enable users to identify sites and tell them apart (Goal~15).

\section{Design}

We first describe how Passpet looks and works
from the user's point of view;
the next section will describe the underlying mechanisms.
When we mention ``Passpet'',
we are referring to the most recent version of Passpet,
which is an extension to the Firefox browser.
(There is also an earlier implementation of Passpet for Internet Explorer
that provides only a subset of this functionality.)

\subsection{Setup}

After the Passpet Firefox extension is installed,
the ensuing setup procedure has three steps:

\begin{figure}
\centering
\scalebox{0.81}[0.81]
{\includegraphics*[viewport=72 538 338 720]{figure-2.pdf}}
\caption{The user is introduced to a new Passpet.}
\end{figure}

\begin{enumerate}
\item
The user is asked to enter a master address
in the form {\tt $username$@$hostname$},
where $hostname$ identifies a Passpet server.
\item
A random icon is automatically chosen from a set of animal icons
and the animal is given a random name.
The name and icon form Passpet's {\em persona}
for interacting with the user (Figure 2).
\item
The user chooses a master secret (Figure 3).
A progress bar shows an estimate of how long it would take
for an attacker to guess the secret.
The attack time changes as the user types the secret
and also increases while the user waits.
When the user finds the attack time sufficiently large,
the user confirms the secret by entering it again, then clicks ``OK''.
\end{enumerate}

\begin{figure}[t]
\centering
\scalebox{0.81}[0.81]
{\includegraphics*[viewport=72 538 338 720]{figure-3.pdf}}
\caption{As the user waits, the attack time grows.} 
\end{figure}

\subsection{Everyday Use}

Passpet appears as a toolbar button next to a text field
in the browser toolbar.
The image and text on the toolbar button
are the icon and name of Passpet's persona.

\begin{enumerate}
\item
When the browser starts, Passpet's persona
is initially ``sleeping'' (Figure 4).
\item
To ``wake up'' the persona,
the user clicks on it and enters the master secret (Figure 5).
Passpet identifies the persona when asking the user for the secret.
The persona keeps the master secret in memory
until the user puts it back to sleep or quits the browser.
\item
To fill in a password, the user clicks the Passpet button (Figure 1).
The Passpet text field flashes,
then the password is filled in on the webpage.
If the cursor is in a password field, that field is filled in;
otherwise if there is a login form on the page, it is filled in.
If there is a username field paired with the password field,
Passpet remembers its previous contents and fills it in as well.
\end{enumerate}

\begin{figure}[b]
\centering
\scalebox{0.50}[0.50]
{\includegraphics*[viewport=72 630 522 720]{sleeping.pdf}}
\caption{The Passpet persona is initially sleeping.}
\vspace{12pt}
\scalebox{0.50}[0.50]
{\includegraphics*[viewport=72 655 522 720]{requesting.pdf}}
\caption{The user enters the master secret.}
\end{figure}

If the user is using Passpet on a new machine
to handle previously established passwords,
the user skips the secret-selection step (step 3 of setup).
When the new persona is awakened for the first time,
it will pause
for about the same length of time
that the user waited during setup.
Thereafter, the persona awakens instantly.

\subsection{Managing Relationships}

\begin{figure}
\centering
\scalebox{0.45}[0.45]
{\includegraphics*[viewport=72 450 504 720]{toolbar-states.pdf}}
\caption{The four states of the site label.}
\end{figure}

The Passpet text field displays
the user's {\em site label} for the current site,
or ``unknown'' if the user has not assigned a label (Figure 6).
For non-SSL sites, the text field has a pink background
and the site label is displayed with a question mark
to show that the site's identity is not verified.
For SSL sites, the text field has a yellow background
when the site is unlabelled,
and a green background
when the site is labelled.
(Tooltips on the text field explain what these states mean.)

The user assigns a site label by clicking in the text field and typing;
the site label can also be edited in place there.
If a site label is created or edited so that
it duplicates an existing site label,
Passpet notifies the user of the name collision (Figure 7)
and displays information about the colliding sites.
When both sites have SSL certificates,
the label collision warning also indicates
whether both certificates
were issued on behalf of the same root CA (according to its public key),
to indicate when an attacker
might be trying to impersonate a CA (Figure 7).

\begin{itemize}
\item When setting up an account with a new site,
the user enters a site label in the Passpet text field.
On the account registration page,
the user clicks on Passpet to fill in the new password.
\item To start using Passpet with an existing account (Goal~3),
the user enters a site label in the Passpet text field.
On the site's ``change password'' page,
the user enters the current password,
then clicks on Passpet to fill in the new password.
\item To change the password for a site (Goal~4),
the user visits the site's ``change password'' page.
The user clicks on Passpet to fill in the old password,
changes the site label in the text field,
then clicks on Passpet to fill in the new password.
\item To change the master secret (Goal~7),
the user asks for a new Passpet persona,
yielding a second button and text field.
The user can migrate a site to the new secret
by going to the site's ``change password'' page,
clicking on the old persona to fill in the old password
and the new persona to fill in the new password.
When the user is done with the old secret,
the old persona can be discarded.
\end{itemize}

\section{Mechanism}

\begin{figure}
\centering
\scalebox{0.81}[0.81]
{\includegraphics*[viewport=72 570 319 720]{collision.pdf}}
\caption{Passpet warns about a site label collision.}
\end{figure}

\subsection{Variable Appearance}

To make the Passpet user interface hard to imitate,
it has no standard icon.
The Passpet button is the only way to activate Passpet,
and the button icon and button text differ from user to user.

\subsection{Site Identification}

Passpet associates the site label entered by the user
with a {\em site identifier} consisting of three parts:
$(root\_key,$ $field\_name,$ $field\_value)$,
following the scheme used
by the Petname Tool \cite{petname-tool} for SSL sites.

For SSL sites,
$root\_key$ is the fingerprint
of the root certificate authority's public key.
If the site's SSL certificate has an Organization Name field,
then $field\_name$ is ``O'' and $field\_value$ contains the Organization Name.
Otherwise, $field\_name$ is ``CN'', and $field\_value$ contains
the certificate's Common Name instead.
If the user assigns the label ``my bank'' to a bank's SSL site,
another site can only cause the site label ``my bank'' to appear
if it can obtain a certificate 
with a certificate chain ultimately signed
by the same root authority and which yields the same site identifier.

For non-SSL sites, the $root\_key$ is empty,
the $field\_name$ is ``D'' (for domain),
and the site identifier is
the last $n + 1$ levels of the domain name
when the domain name ends in a $n$-level top-level domain (TLD).
For example, {\tt .com} is a single-level TLD,
so the site identifier for {\tt www.subdomain.example.com}
is {\tt example.com}.
However, {\tt .mb.ca} is a two-level TLD,
so the site identifier for {\tt www.gov.mb.ca}
is {\tt gov.mb.ca}.
Passpet uses a list of two-level TLDs to make this determination.
The intention is that the site identifier
refers to the domain at the level of specificity
where domains are usually purchased and owned,
so that sites like {\tt www.example.net},
{\tt example.net},
and {\tt server2.example.net} will get the same label.

The site label is allowed to contain Unicode characters
so that it can be written in the user's own language.
Homographs (similar-looking glyphs) in Unicode
are not a security vulnerability in site labels,
since the site labels are supplied only by the user, not an external source.

\subsection{Password Generation}

To generate passwords,
Passpet employs the two-level iterated hashing strategy
of Halderman, Waters, and Felten's Password Multiplier~\cite{multiplier}.
$k_1$ and $k_2$ are parameters
that control the degree of resistance to dictionary attack.

When the master secret is first entered on a particular machine,
Passpet computes \label{Vdefinition}
$$ V = H^{k_1}(master\_address\ ||\ ``\backslash{}0"\ ||\ master\_secret) $$
where $H$ is a secure hash function to be iterated $k_1$ times
%$master\_username$ is the $username$ part of the master address,
and $``\backslash{}0"$ is a single null byte used as a separator.
The value $V$ is then cached on the machine for future use.

In order to fill in a password field, Passpet computes
$$ P = H^{k_2}(site\_label\ ||\ ``\backslash{}0"\ ||\ master\_secret\ ||\ ``\backslash{}0"\ ||\ V) $$
where the $site\_label$ is the user-assigned label for the site.
$V$ and $P$ depend on the $master\_address$
in order to prevent an attacker from precomputing a table
of common $master\_secret$ values with corresponding $P$ values.

In our implementation, the hash function $H$ is SHA-256.
To meet the password format requirements of most websites,
Passpet generates passwords
that always contain a digit, a lowercase letter, and an uppercase letter.
Many sites do not permit characters
other than letters and digits
in passwords;
for the relatively few sites
that require punctuation in passwords,
the user will need to hit a punctuation key
after clicking on Passpet.

Passpet converts $P$ into a site password string
by taking the $n$ least significant digits
of the base-62 representation of $P$,
using characters in the set {\tt [0-9a-zA-Z]} as digits.
$n$, the length of the site password,
is the number of characters allowed in the password field
(as specified by the {\tt maxlength} attribute
of its {\tt $<$input$>$} tag), up to maximum of 12.
If this password string does not include
at least one digit, one lowercase letter, and one uppercase letter,
then Passpet computes $P' = H(P)$, $P'' = H(H(P))$,
and so on, until it arrives at a password string
that contains all three types of characters.

Passpet permits any Unicode characters
to be used in the master secret,
to allow the possibility of greater password entropy.
For these hash computations,
the master secret and site label are encoded in UTF-8.

\subsection{Variable Strengthening}

The computation of $V$ and $P$ above
are the same as in Password Multiplier;
Password Multiplier uses fixed values for $k_1$ and $k_2$,
where $k_1$ can be much larger
because it only incurs a one-time delay per machine,
whereas $k_2$ incurs a delay for each login attempt.
In our scheme, $k_1$ is variable and $k_2$ is fixed.
The setup procedure repeatedly hashes the master address and master secret,
allowing $k_1$ to increase for as long as the user is willing to wait.
In other words, $k_1$ is limited only by the user's patience.

As the user enters the master secret during the setup procedure,
Passpet makes a rough estimate of the entropy in the secret.
This entropy value is used together with $k_1$ and an estimate of
the attacker's computing power, in hashes per second,
to calculate the average time required for a successful dictionary attack.
As computers become faster, the estimate of the attacker's computing
power can be updated without changing the rest of the software.

%When a user uses Passpet on a new machine for the first time,
%Passpet needs to determine $k_1$.
%However, it is better to keep $k_1$ secret
%to prevent attackers from targeting the easiest victims.
%Instead, our scheme requires clients to discover $k_1$
%by actually performing the computation.
%This discovery process will be described in the next section.

%To make such discovery feasible,
%$k_1$ is quantized in the following manner.
%The setup process initially chooses a target value for $k_1$
%that requires about one second of computation,
%and computes $V$ for that $k_1$.
%Then it multiplies $k_1$ by $13/12$ and continues hashing
%until it has $V$ for this new $k_1$.
%It repeats this process, multiplying $k_1$ by $13/12$
%(and rounding down to an integer) each time,
%so that $k_1$ increases geometrically.
%This allows $k_1$ to take on a wide dynamic range of values,
%while reducing the number of guesses
%that a client must make to discover $k_1$
%and wasting at most $1/13$ of the user's waiting time.

%For reasons that will become clear in the next section,
%To make feasible the process for discovering $k_1$
%that will be described in the next section,
%$k_1$ is quantized in the following manner.
%The setup process initially chooses a target value for $k_1$
%that requires about one second of computation,
%and computes $V$ for that $k_1$.
%Then it multiplies $k_1$ by $13/12$ and continues hashing
%until it has $V$ for this new $k_1$.
%It repeats this process, multiplying $k_1$ by $13/12$
%(and rounding down to an integer) each time,
%so that $k_1$ increases in a geometric sequence.
%This allows $k_1$ to take on a wide dynamic range of values,
%while reducing the number of possible values that $k_1$ can take,
%and wasting at most $1/13$ of the user's waiting time.

\subsection{Local Storage}

While a Passpet persona is awake,
it maintains the list of site labels in memory;
each entry in the list is a pair
$(site\_identifier, site\_label)$.
The list of site labels is saved locally on disk in a file
containing the encrypted list
and a message authentication code (MAC):
$$site\_label\_file = E_{W_1}(site\_label\_list)\ ||\ M_{W_2}(site\_label\_list)$$
where $E$ is AES-CBC, $M$ is AES-CMAC, and
\begin{eqnarray*}
W &=& H^{k_2}(master\_secret\ ||\ ``\backslash{}0"\ ||\ V) \\
W_1 &=& high\ 128\ bits\ of\ W \\
W_2 &=& low\ 128\ bits\ of\ W
\end{eqnarray*}

Passpet keeps a cache on the local disk for each persona.
The cache contains
$master\_address$, $index$ (see next section), $V$, and $site\_label\_file$.
A persona that knows its $index$ and $V$ is said to be {\em initialized}.
When the user removes a persona from the toolbar, its cache is deleted.
% Is there a more specific term than ``initialized''?  How about ``logged in''?
% I'd expect ``initialized'' to mean that it knows its master_secret.

For completeness, we note that the inputs to $H$
used for computing $V$, $W$, and $P$
can be uniquely decomposed into their constituent parts
because the strings $master\_address$, $master\_secret$, and $site\_label$
cannot contain null bytes and $V$ has a fixed length.

\subsection{Remote Storage}

To regenerate the correct passwords on another computer,
Passpet needs to know the master address, master secret,
$k_1$, $k_2$, and the site label.
The master address and master secret are entered by the user
and $k_2$ is fixed.

Passpet relies on a remote server to store $k_1$ and 
a copy of the site label file.
The master address is in the same format as an \hbox{e-mail} address,
{\tt $username$@$hostname$},
which allows the user to choose the storage server.
Access to the file is authenticated
using the Secure Remote Password protocol~\cite{srp}.
The storage server keeps a set of six-item records in the form:
$$(username, index, k_1, salt, verifier, site\_label\_file)$$
where $index$ is an integer
and $salt$ and $verifier$ are used for SRP authentication.
The purpose of $index$ is to let one user store multiple files
during the process of
changing from an old master secret to a new master secret.

The server supports two unauthenticated commands:
\begin{itemize}
\item
{\tt create}($username$, $k_1$, $salt$, $verifier$) \\
The server picks a new $index$
such that ($username$, $index$) is not among its records,
creates a new record with an empty $site\_label\_file$,
and returns $index$.
\item
{\tt list}($username$) \\
The server returns a list of ($index$, $k_1$) pairs
for all the records with the given $username$.
\end{itemize}

To begin an authenticated session,
the client selects a record by sending ($username$, $index$)
and carries out the SRP protocol
to authenticate against the $salt$ and $verifier$ in that record.
In the encrypted SRP session,
the server accepts one of three commands
and terminates the session after completing the command:
\begin{itemize}
\item
{\tt delete}() \\
The server deletes the record.
\item
{\tt read}() \\
The server returns the record's $site\_label\_file$.
\item
{\tt write}($old\_mac,$ $site\_label\_file$) \\
If the MAC at the end of the record's $site\_label\_file$
matches $old\_mac$,
the server atomically replaces the $site\_label\_file$.
Otherwise, it returns a failure message.
\end{itemize}

When the user initializes a persona with a new master secret,
the strengthening process yields $k_1$.
Passpet then determines $salt$ and $verifier$ according to SRP,
using $username$ as the SRP username and $W$ as the SRP password.
It then sends a {\tt create} command to the server
and caches the returned $index$,
yielding an initialized persona.

When the user awakens an initialized persona,
it computes $W$ from its cached $V$ and the entered $master\_secret$.
It authenticates with the server
using its cached $username$ and $index$ and this $W$,
issues a {\tt read} command to get the site label file,
and checks the MAC on the file.

To start using Passpet on another machine,
the user creates a persona
without choosing a new master secret,
yielding an uninitialized persona.

The first time an uninitialized persona is awakened,
Passpet issues a {\tt list} command to the server
and makes a login attempt for each ($index$, $k_1$)
in the returned list until a login succeeds.
At this point the persona caches $index$ and $V$ and becomes initialized;
the persona issues a {\tt read} command to get the site labels, as before.

When changes are made to the site labels,
Passpet encrypts the updated site labels
and sends them back to the storage server with a {\tt write} command.
Because the database is fairly small
(perhaps 40 to 80 bytes per site),
it is feasible to transmit the entire database in a single transaction.
If the {\tt write} fails because the MAC has changed
since the last {\tt read},
the persona issues another {\tt read}
to get the server's current $site\_label\_file$,
reapplies the changes made since the last successful {\tt write},
and retries the {\tt write}.

\section{Security Analysis}

This section examines Passpet's effects
on four classes of attacks:
dictionary attacks against the user's passwords,
attacks against the user's site label file,
phishing attacks intended to fool the user
into revealing site-specific passwords,
and spoofing attacks intended to fool the user
into revealing the master secret.
(For the purposes of this discussion,
``phishing'' refers to an attack
that imitates a website,
whereas ``spoofing'' refers to an attack
that imitates some other part of the user interface.)

We also discuss Passpet's design
with regard to cross-site login forms and cross-site scripting issues.
%Our analysis considers various attack scenarios
%based on the attacker's level of access before conducting the attack.
%However, we exclude one scenario against which Passpet offers no protection: 
%
%{\bf Case $\Omega$: Attacker has compromised the user's machine
%without the user's knowledge.}
%An attacker of this type
%can capture anything the user types, including the master secret.
%This is a weakness of any scheme that involves typing in a secret.

\subsection{Dictionary Attacks}

Here we analyze the effort required for various types of attackers
to guess the user's password.
The previously published analysis of Password Multiplier~\cite{multiplier}
covers the following cases:

\vspace{1em}

{\bf Case 1: Attacker has no information.}
The attacker can perform only an online attack
on the password at a particular site.
The target site can impede the attack
by limiting the rate of login attempts
or disabling an account after some number of failures.

{\bf Case 2: Attacker has obtained one or more site passwords.}
\label{SitePasswordSniffing}
The attacker can perform an offline attack against the master secret,
costing at least $k_1 + k_2$ hash computations for each guess.

{\bf Case 3: Attacker has obtained the cached value of $V$.}
The attacker can perform an offline attack against the master secret,
costing at least $k_1$ hash computations for each guess.

{\bf Case 4: Attacker has obtained $V$ and one or more site passwords.}
The attacker can perform an offline attack against the master secret,
costing at least $k_2$ hash computations for each guess.

\vspace{1em}

To the Password Multiplier scheme,
we have added the remote storage of the site label file.
Since the SRP password $W$ depends on the master secret,
an attacker who doesn't know the master secret
cannot authenticate with the storage server
(even if the attacker has $V$ or one or more site passwords).
So, unless the attacker has insider access to the storage server,
the four cases above apply.

What if the attacker has broken into the storage server,
or the owner of the storage server is malicious?
In this case, the attacker has access to a file
that has been encrypted with $W$,
and can conduct an offline dictionary attack
against the master secret.
For each guess at the master secret,
the attacker performs $k_1$ hashes to obtain $V$
and $k_2$ more hashes to obtain $W$,
then attempts to decrypt the file,
then examines whether the result yields the correct MAC.
The total number of hashes per guess is
$k_1 + k_2$, the same as Case 2 above.

If the attacker has obtained the cached value of $V$
as well as the data on the storage server,
then a faster offline dictionary attack is possible.
For each guess at the master secret,
the attacker performs $k_2$ hashes to compute $W$
and then attempts decryption.
The number of hashes per guess is $k_2$, the same as Case 4 above.

Thus, obtaining a copy of the remotely stored data
offers about the same benefit to an attacker as obtaining a site password.
With respect to dictionary attacks,
the storage server can be considered
just another site where the user has an account,
since a break-in or malicious administrator
at the storage server
incurs no more risk
than a break-in or malicious administrator
at any other site where the user has an account.

We conclude that Passpet provides resistance to dictionary attacks
that is about as strong as Password Multiplier for the same value of $k_1$,
and can be stronger,
if the user waits long enough to obtain a larger $k_1$.
If the user's patience remains more or less constant,
then as the user periodically upgrades to new computers
and updates the master secret,
$k_1$ will increase to track increases in computing power.

\subsection{Attacks on the Storage Server}

We do not consider the user's site labels themselves to be secret,
since the secrecy of site passwords depends on the master secret.
However, the entire list of sites where the user has an account
does pose a privacy risk,
since it reveals information about the user's browsing habits.
The site label file is stored encrypted
so that the user's privacy remains protected
even if the storage server is compromised
or the owner of the storage server is untrustworthy.

Applying a MAC to the site label file
prevents others from altering the list of site labels.
Even though the server owner can modify the file itself,
no one can produce a valid altered file without the key $W$.
If the server owner corrupts the file,
the client will detect
that the MAC at the end of the file does not match,
so this would merely be equivalent to denying service.

Access to the user's file is authenticated
in order to prevent attackers from getting a copy of the encrypted file
to use for a dictionary attack against the master secret via $W$,
and to prevent attackers from corrupting or erasing the data.
Again, write access
would not allow an attacker to make a valid change to the site label list,
but would allow an attacker to erase it;
authentication prevents this type of denial-of-service attack.

What repercussions are there when the storage server is unavailable?
If the user attempts to use Passpet on a new computer for the first time,
Passpet will fail to log in and will be unable to determine $k_1$.
However, in all other cases,
Passpet has a local copy of the site label file and the cached value of $V$.
Thus, after the user enters the master address and master password,
Passpet can still function
(although some site labels may be out of date
and updates to the site labels will not be stored).

\subsection{Phishing Attacks on Site Passwords}

In a typical phishing attack,
the user is lured to an impostor webpage
that looks like the login page for the target website.
Believing it to be the actual target website,
the user logs in, and in the process submits a password to the attacker.

If the user is using Passpet to manage the password for a particular site,
then the user never types or sees the password;
the password is always generated by clicking on the Passpet button.
So the user is incapable of actually typing in the password
to give to an attacker.

Therefore, to steal a site password,
an attacker must cause Passpet to generate the password.
The password depends on the site label,
and the site label is associated with the SSL certificate.
It follows that the attacker must either 
(a) modify Passpet's site label file
to associate the attacker's SSL certificate
with the target's site label,
(b) obtain an SSL certificate
that Passpet recognizes as associated with the same site label,
or (c) convince the user
to assign the same site label to the attacker's site.

To achieve (a), the attacker has to make a coherent change
to the user's site label file,
which can only be achieved if the attacker obtains the key $W$,
as explained in the preceding section.

In case (b),
the SSL certificate must have exactly the same Organization Name (or
Common Name, if the original had no Organization Name)
and have a signing chain
ultimately signed by the same root CA (certificate authority).
The attacker must either steal a legitimate certificate
with its private key,
or convince some CA authorized to act on behalf of the same root CA
to issue another certificate with the same name.
It is reasonable to consider secure websites responsible
for protecting their own private keys,
and we consider it outside of Passpet's scope
to prevent CAs that act on behalf of the same root authority
from issuing duplicate certificates.

Consider case (c).
To support our claim that Passpet reduces the risk of phishing attacks,
we argue that it is more difficult
for an attacker to persuade a Passpet user
to reassign an existing site label to the attacker's site
than to fool a non-Passpet user into filling in an imitation login form.

Today's phishing attacks depend on repeating a familiar login process
that users go through all the time:
the user recognizes the login form,
types in the username and password,
and submits the form.
The perceived user experience of being phished
is the same as the perceived user experience of legitimately logging in.

On the other hand, being asked to reuse an existing site label
is an unusual request,
and assigning the site label requires more effort than logging in normally.
In the event that the user actually does edit a site label
to collide with an existing site label,
Passpet warns the user (see Figure 7).
We expect that legitimate situations
requiring reuse of an existing site label will be quite rare;
this expectation has been confirmed so far
by the fact that users of Passpet for IE have never needed
to assign the same label to two different sites.
Based on further experience with deploying Passpet,
we may adjust the intrusiveness of the site label collision warning,
or forbid collisions altogether
to prevent any possibility of success for this type of attack.

\subsection{Spoofing Attacks on the Master Password}

An attacker could also try to fool the user
by spoofing the browser interface.
For example, past attacks have used
JavaScript to hide the browser address bar
and replace it with a convincing image of an address bar
to make the user think the site is at a legitimate domain.

With Passpet in use, password security no longer depends on the address bar,
but it is conceivable that an attacker
might try to imitate the Passpet user interface
in order to get the user to enter the master secret.
Passpet obstructs this type of attack in three ways:

\begin{enumerate}
\item The Passpet user interface component is recognized by its icon.
Since the icon is randomly selected on installation
and differs from user to user,
the attacker is less likely to be able to produce a convincing replica.
\item When the user clicks on the icon,
Passpet requests the secret using the customized persona name,
for example, ``Betty wants your secret:''.
Since this name is also different from user to user,
the attacker is less likely to be able to produce the correct label.
\item The user enters the master secret only once per session,
and only after clicking on the button, never upon external prompting.
\end{enumerate}

The purpose of the Passpet persona is
to create a specific trust relationship
between the user and the Passpet tool.
The Passpet interface is intentionally minimal:
Passpet is to be recognized by its icon, unlike password forms,
which are recognized by the presence of two text fields
labelled ``username'' and ``password''.
The customized icon is a direct part of the workflow ---
the user is reminded of the icon every time he or she clicks on it,
and is therefore less likely to use a Passpet tool with the wrong icon.

\subsection{Cross-Site Issues}

Some websites have pages
containing login forms
that submit to a different target website.
Since Passpet's label is associated with current SSL certificate,
the label identifies the source of the page, not the form target.
We argue that this is a better choice from a security perspective,
because the purpose of the label is to help the user make trust decisions
about the visible page, not the invisible form target.
For example, in a phishing attack,
it is the page that misleads the user,
not the form target.
If the label were to identify the form target,
an attacker could gain the appearance of legitimacy
simply by creating a fraudulent page that points at the same target.

Since the site password is generated from the site label,
it also corresponds to the page and not the form target.
Again this is the safer option,
since any information entered on the page
is vulnerable to JavaScript commands in the page.
If the site password were to correspond to the form target,
an attacker could steal a site password
by putting a legitimate login form
on a page with some JavaScript
to capture the password that Passpet will paste in.

Even though it is possible for legitimate organizations
to have login forms at two different sites (say, A and B)
that submit to the same target site C,
site A and site B will have independent site labels.
This is as it should be,
since the form at site B could just as well be
a page containing JavaScript designed to capture passwords
from users who believe they are logging in at site A.
For unusual cases like this,
the user can choose to give the same label to A and B
after inspecting their certificate information (Figure 7).

In a ``cross-site scripting'' attack,
an attacker injects JavaScript code
into a page on the target site itself
(for example, by supplying it as a query parameter
or posting it on a message board).
Passpet has no effect on these attacks;
it is up to the site administrator
to make sure that the site itself does not attack its own users.

\section{Usability Analysis}

Passpet's most obvious advantage is the improved convenience of logging in.
Instead of having to enter a username and password for every login,
the user only has to enter the master secret once in a browser session
and can thereafter fill in login forms with a single click.

According to a Pew Internet Research study in 2000 \cite{pew},
68\% of users use multiple different passwords
when registering at websites.
A survey in 2003 conducted by Protocom Development Systems \cite{protocom}
found that over 64\% of corporate users
memorize more than five passwords for their work.
Therefore,
most users would benefit
from only having to memorize one master secret instead of many passwords.

Another advantage that Passpet provides
is the ease of generating new passwords.
When faced with an account registration form,
users must take a moment to choose
which password to use for the new account,
or think about whether they should make up a new password.
Entering a site label and clicking on Passpet
is more convenient than deciding on a password and typing it in.

For users that change passwords periodically
or sites that require password changes,
Passpet provides a significant improvement in convenience.
The Protocom survey reported that 68\% of corporate users
change their passwords at least once a year,
and half of those (34\%) did so once a month or more.
With Passpet,
the user can generate a completely new password
by editing the site label
(for example, by appending or incrementing a number).
After changing a password,
the user doesn't have to remember that it was changed;
upon returning to the website,
the new site label automatically reappears.

The earlier implementation of Passpet,
an extension to Internet Explorer,
has been informally tested in a deployment to 15 users at HP Labs.
Feedback was very positive;
one user even wrote to say, ``Passpet has changed my life.
No longer do I agonize with passwords... it is so easy!''
After three months, ten of the users are still using Passpet for IE regularly.
The main complaint from those who stopped using it
was that it's inconvenient to use on multiple machines,
a problem addressed by Passpet for Firefox.
Passpet for IE
includes the site labelling and password hashing features
but not the password strengthening and customized icon,
and it only supports SSL sites.
Passpet for IE
has a very similar user interface
to the current Firefox implementation,
though it pops up a separate dialog window
to request the master secret,
whereas Passpet for Firefox
does this in the toolbar area
for improved convenience and security.

We are planning to conduct a usability study
to compare the effectiveness
of a standard installation of Firefox,
Firefox with the Passpet extension,
and at least one other anti-phishing alternative.
Effectiveness will be evaluated by
measuring subjects' speed, error rate, and level of satisfaction
at four tasks:
registering for new accounts,
logging in to accounts,
changing account passwords,
and detecting phishing attacks.
We are particularly interested in testing two hypotheses of our design:
(a) that users will be less likely to proceed
when presented with the wrong persona icon or persona name;
and (b) that having to click on the Passpet button
during the login process
makes the user more likely to notice the site label
(in comparison with other tools
that offer indicators in the toolbar area).

\section{Evaluation and Comparison}

In this section, we evaluate Passpet in terms of the 16 goals
we originally listed,
and compare Passpet to a representative sample
of other password management and anti-phishing tools.
Refer to Figure 7 for a table that summarizes our findings.
The first column, labelled ``plain browser'', is a baseline condition ---
a browser that has no password management or anti-phishing tools added,
with the password autofilling feature turned off.
The remaining columns describe various other tools
that address these problems;
each one was described briefly in Section 3.

\begin{figure*}
\centering
\scalebox{0.70}[0.70]
{\includegraphics*[viewport=36 228 756 540]{comparison.pdf}}
\caption{Comparison of password management and anti-phishing tools.}
\end{figure*}

\smallskip
{\bf Goal 1.  Improve the convenience of logging in to websites.}
Only password autofilling, LPWA~\cite{lpwa},
Password Multiplier~\cite{multiplier}, and Passpet
enable users to log in with less effort
than the standard login procedure
of typing in a username, typing in a password, and clicking a button.
With autofilling,
the user doesn't have to do anything to have the password field filled;
with LPWA, the user types in ``$\backslash{}$P'' instead of a password;
and with Passpet, the user clicks a button.
HP Site Password~\cite{ssp} and PwdHash~\cite{pwdhash}
require slightly more effort than a normal login,
as the user has to perform an activation step
(clicking a button or pressing a key combination)
before typing in a password.

With Password Multiplier,
the user double-clicks in the password field
to pop up a dialog box;
by default the user has to re-enter the master secret for each login.
However, the user can ask Password Multiplier to remember the master secret,
and then filling in a password only requires a double-click
in the password field followed by a click on the dialog's ``OK'' button.

The remaining tools leave the login procedure itself unchanged,
though SpoofStick, the Netcraft Toolbar, the Earthlink Toolbar,
SiteKey, DSS, the Petname Tool, TrustBar, and IE7
all expect users to check an additional indicator
if they want to avoid being phished.

\smallskip
{\bf Goal 2.  Work with existing websites and login forms.}
All the tools work with unmodified websites
except for SiteKey~\cite{sitekey} and DSS with SRP~\cite{dss}.
SiteKey requires the website to switch to a two-stage login process
with a custom image displayed in the second stage;
DSS with SRP involves switching
to a new cryptographic authentication protocol.

\smallskip
{\bf Goal 3.  Permit site-by-site migration to using the tool.}
All the tools allow the user to start using them
with existing accounts one at a time.

\smallskip
{\bf Goal 4.  Allow the user to change passwords for individual sites.}
LPWA generates passwords solely based
on the user's identity, secret, and the website domain name,
so the only way to change any password is to change the secret,
which changes all the passwords.
PwdHash and Password Multiplier do not prevent the user
from changing individual site passwords,
but doing so conflicts with Goal 6.
With PwdHash, the only way to change a site password
is to enter a different password into the login form to be hashed;
then the user will have to remember multiple secrets.

Password Multiplier's dialog box
contains text entry fields for both the master secret
and the site's domain name,
so the user could conceivably change a site password
by editing the domain name.
However, the dialog box comes up with the original domain name each time,
so the user would have to re-edit the domain name every time.
Thus, exercising the ability to change individual site passwords
introduces an additional memory burden on the user.

\smallskip
{\bf Goal 5.  Allow the user to log in from more than one computer.}
None of the tools prevent a user from logging in with another computer.
However, the ones marked with an asterisk become less useful:
Password autofilling and the site labelling features
of the Petname Tool and TrustBar
depend on locally stored information
that is not carried over when the user switches to another computer.

\smallskip
{\bf Goal 6.  Let the user only have to memorize one secret.}
The password hashing schemes
(LPWA, HP Site Password, PwdHash, Password Multiplier, and Passpet)
are designed to enable the user to have to memorize only one secret.
For PwdHash, there is a conflict with Goal 4;
if the user wants to memorize only one secret,
then the user cannot change a single site's password
without also changing all the others.
For the remaining tools,
keeping to just one secret
would mean having the same password for all sites.
None of them prevent the user from doing this,
but we have marked them ``no''
because in practice most users use multiple passwords \cite{pew,protocom}.

\smallskip
{\bf Goal 7.  Allow the user to change the master secret.}
A change in the master secret
affects all of the site-specific passwords,
which must be changed one at a time at their websites.
During the changeover process,
some passwords will be based on the new secret and some on the old.
Of the five schemes that support hashing,
all but Passpet require the user
to remember which ones use the new secret
and which are still using the old secret.

HP Site Password and PwdHash
let the user enter any master secret
each time a site-specific password is generated.
On each account's ``change password'' page,
the user would enter the old master secret
when filling in the ``old password'' field
and the new master secret
when filling in the ``new password'' field.

With LPWA, the user can end the current session
and start a new session with a different secret,
but only one master secret can be active at a time.
Thus, it is not possible to get LPWA
to fill in both the ``old password''
and the ``new password'' fields on a password change page,
one using the old master secret and one using the new master secret.

With Password Multiplier,
changing the master secret would require
bringing up the Password Multiplier dialog
to fill in the ``old password'' field,
then ``deauthorizing'' the current session
and ``reauthorizing'' with a different master secret,
then bringing up Password Multiplier again
to fill in the ``new password'' field.
Because it takes about 100 seconds to perform each reauthorization,
it would be tedious to repeat this process for every account.

With Passpet,
the user creates a new Passpet persona with the new master secret.
When the user is at a site that has not yet been changed over,
the old persona will show a site label 
but the new persona will show that the site is ``unknown''.
The user updates an account by entering a site label,
clicking on the old persona to fill in the ``old password'' field,
and clicking on the new persona to fill in the ``new password'' field.
The user doesn't have to memorize
which sites have already been changed over
because the new persona will keep track of their site labels.

\smallskip
{\bf Goal 8.  Use a unique password for every site.}
The password hashing schemes
(LPWA, HP Site Password, PwdHash, Password Multiplier, and Passpet)
all use cryptographic algorithms to generate site passwords
that impede an attacker who has obtained one or more site passwords
from finding the master secret or any other site password.
The other tools allow users to choose the same password
or related passwords for many sites.

\smallskip
{\bf Goal 9. Resist offline dictionary attacks on user-chosen secrets.}
Only Password Multiplier and Passpet take password-strengthening measures
to provide resistance against dictionary attacks.

\smallskip
{\bf Goal 10. Adapt to the development of faster computers.}
Assuming that the user is willing to wait
for about the same length of time,
Passpet's password-strengthening scheme
increases in strength when the user upgrades to a faster computer
and selects a new master password.
In order for this adaptation to keep up
with increases in the computing power of attackers,
the user must upgrade and change passwords from time to time.

\smallskip
{\bf Goal 11.  Avoid storing passwords in long-term storage.}
Password autofilling involves storing passwords on the local disk;
the other schemes do not.
None of the schemes store passwords remotely.

\smallskip
{\bf Goal 12.  Avoid introducing a centralized dependency.}
The site rating features in
the Earthlink Toolbar, Netcraft Toolbar, and Internet Explorer 7
refer to a single authority that dictates whether sites are good or bad.
This introduces a central point of failure for the entire system,
as well as a central locus of trust
that not all users may be willing to accept.
The Earthlink Toolbar downloads the list
to the local machine~\cite{earthlink-faq},
but the others collect information
on the user's browsing history:
the Netcraft Toolbar collects
plaintext domain names and hashes of visited URLs~\cite{netcraft-privacy};
Internet Explorer 7 sends URLs (with query strings removed)
in real-time to Microsoft,
except URLs on a client-side list of ``known good'' sites~\cite{ie7-phishing}.

\smallskip
{\bf Goal 13.  Resist attacks based on fake website login forms.}
For this goal we have classified
some tools as ``yes'' and others as ``maybe'',
depending what happens to a user
who proceeds with normal login workflow.
SpoofStick, the Netcraft Toolbar, SiteKey, DSS, Petname,
TrustBar, and IE7 are all marked ``maybe''
because their defense against phishing
relies upon the user to notice an indicator
and respond with a change in behaviour.
LPWA, PwdHash, Password Multiplier, and Passpet
are marked ``yes''
because, even if the user attempts to log in, oblivious to an attack,
the user's password is not sent to the attacker.

\smallskip
{\bf Goal 14.  Resist attacks based on imitating the browser UI.}
Only DSS and Passpet customize the browser UI
to protect it from being spoofed.
We hypothesize that Passpet's customization of the button icon
is more effective than the custom image overlaid on the login form in DSS.
Our reasoning is that filling in the DSS login form
isn't directly related to the image;
the user's task can be described as ``type into the two text fields'',
a task that can be performed just as well
when the image is different or missing.
However, Passpet's custom button icon is a way of identifying
which button to click.
If the persona is a giraffe,
then we hypothesize that many users will conceptualize their task
as ``click on the giraffe'',
a task that cannot be carried out if there is no giraffe visible.
Our planned user tests will help us understand
whether our expectations are valid.

\smallskip
{\bf Goal 15.  Help the user reliably identify websites. }
It is useful not only to protect the user's password
but also to prevent the user from being misled as to the identity
of the site.
For example, if the user is using PwdHash
and is lured to a phishing site that imitates the user's bank,
PwdHash will fill in a different password than the real bank password,
so the user's bank password is safe.
However, the phishing site can still accept the login,
continue to masquerade as the bank,
and proceed to ask the user for private information.
If the user believes that the browser
has successfully logged in to the bank's website,
the user is vulnerable to attack.

SpoofStick, the Netcraft Toolbar, the Petname Tool, TrustBar,
Internet Explorer 7, and Passpet
all provide some kind of identifier for the website
that is easier to read than a plain URL.
However, they are marked with an asterisk
because the identifier (domain name or certificate name)
is provided by the website,
and so could be chosen by an attacker to be misleading.
The Petname Tool and Passpet
use an identifier that is under the user's control.
TrustBar displays both kinds of identifiers.

Of all these schemes,
only Passpet incorporates clicking right next to the site label
and flashing the site label
%a button
%right next to the site identifier
as part of the login process.
%and flashes the site label .
We hypothesize that drawing the user's attention
to the site label in this way
improves the likelihood of noticing an impostor site,
for which the text field
will show the word ``unknown'' or the wrong site label.


\smallskip
{\bf Goal 16.  Break the habit of entering passwords into webpages.}
Training users to enter secrets into webpages
leaves users highly vulnerable to phishing,
since any aspect of a webpage's appearance
can be imitated by an attacker.
HP Site Password and Password Multiplier
pop up a separate window for entering the master secret,
but these windows could also be imitated by webpages.
DSS with SRP uses a separate pane in the browser window, and
Passpet uses part of the toolbar in the browser chrome area.

\section{Limitations}

As explained in section \ref{Vdefinition}, $V$ and $P$ depend on 
$master\_address$, in order that an attacker cannot detect that different
users have the same $master\_secret$ and $k_1$ and cannot precompute
values of $V$ or $P$ for common master secrets.
This has the unfortunate side effect that moving to a different storage server
changes every site password --- the effect is similar to choosing a
new master secret.
To avoid this problem,
Passpet could use SRP's salt in place of $master\_address$
and instead define $V = H^{k_1}(salt\ ||\ master\_secret)$.

Attacks on DNS (``pharming attacks'') can hijack
connections to non-SSL sites and steal their site passwords;
Passpet does not reduce this inherent vulnerability of non-SSL sites.

Since the {\tt list} command applied to a
nonexistent username returns an empty list, 
an attacker can repeatedly query a server
to determine which of a list of likely usernames actually exist.
A smart server could detect and prohibit
exhaustive querying from a single source.

The storage server makes $k_1$ available to anyone who asks,
which enables an attacker who knows some usernames
to choose the most vulnerable users
when conducting a dictionary attack.
An earlier design of Passpet avoided this weakness
by requiring the client to try progressively larger values of $k_1$
until authentication succeeds.
However, in such a scheme,
a user initializing a Passpet persona on a new computer
might never find out whether they mistyped their master secret,
so we decided to make $k_1$ available to the client.

If the user initially sets up Passpet on a fast computer, they
might choose a larger $k_1$ than they would have the patience for on a
slow computer.  They may find this frustrating if they later try to
initialize a Passpet persona on a slow computer.

Finally, like all password-hashing systems, 
Passpet is vulnerable to an offline
dictionary attack against the master secret from an attacker who has
captured some site passwords --- for example, the administrator of 
a site where the user has an account
(see section \ref{SitePasswordSniffing}).
A few possible ways to provide additional security against this attack are:
\begin{enumerate}
\addtolength{\itemsep}{-3pt}
\item
Passwords transmitted to non-SSL sites are more vulnerable to being captured.
One way to further protect SSL site passwords
would be to keep two master secrets,
one for non-SSL sites and one for SSL sites,
so that capture of any non-SSL site passwords
would not help an attacker obtain SSL site passwords.

\item
Most password-hashing systems, including Passpet,
impose some arbitrary limit on site password length.
This limit could provide some additional
security against this attack, at the cost of easier
online dictionary attacks against any particular site.
If the site passwords known to the attacker
contain less entropy than the master secret,
the attacker would have to perform an online test
of each apparent hit from the offline dictionary attack.
In the case of Passpet,
the site password usually contains 12 base-62 characters,
so it gives an attacker up to 71 bits of information.
Most users' master secrets will contain less entropy.

\item
If we were to relax Goal 11,
another way to defend against these attacks
would be to abandon password hashing,
generate truly random site passwords,
and store them with the site labels;
then, captured site passwords would convey
no information at all about the master secret.

\end{enumerate}

\section{Future Work}

As described in section 7,
we are planning a usability study
to evaluate Passpet.

We also plan to develop a version of Passpet
that is implemented with HTML pages and unprivileged JavaScript,
so that Passpet users can obtain their site passwords
even on computers where they are not able to install software.

The password entropy estimator in Passpet
is somewhat unrefined, and we hope to improve it.
We would also like to let users
choose their own images to use for the persona icon,
and to expand the included set of available icons.

The current Firefox extension is entirely platform-independent,
but we are considering adding platform-specific binary modules
to speed up hash computations,
to make Passpet stronger against dictionary attacks.

\section{Conclusion}

Passpet builds on Password Multiplier and the Petname Tool,
also drawing upon ideas from Dynamic Security Skins and HP Site Password.
The result is a practical, convenient tool that
relieves users of the burden of choosing
and memorizing many passwords,
protects users' other accounts when some accounts are compromised,
and reduces the risks of phishing and dictionary attacks,
while addressing a wider range of real-world use cases
than other website password security tools.
We plan to make Passpet available for public download at
\url{http://passpet.org/}.

\section{Acknowledgements}

Thanks to Alan Karp for conducting
the preliminary user tests of Passpet for IE
and to David Wagner for extremely helpful feedback
on drafts of this paper. % and on Passpet's use of cryptography.
We are grateful to David Wagner, Tyler Close, and Alan Karp
for their contributions to Passpet's design.

{\small
%\bibliographystyle{plain}
%\bibliography{passpet}
%
% The .bbl file generated by bibtex is inserted here so that
% we can add the \vspace command before the first item.

\begin{thebibliography}{10}
\bibitem{strengthening}
\vspace{10pt}
M.~Abadi, T.~M.~A. Lomas, and R.~Needham.
\newblock {Strength- ening Passwords}.
\newblock Technical Report 1997-033, SRC, 2005.

\bibitem{petname-tool}
T.~Close.
\newblock {Petname Tool}.
\newblock \url{http://petname.mozdev.org/}.

\bibitem{spoofstick}
CoreStreet.
\newblock Spoofstick.
\newblock \url{http://www.spoofstick.com/}.

\bibitem{dss}
R.~Dhamija and J.~D. Tygar.
\newblock {The battle against phishing: Dynamic Security Skins}.
\newblock In {\em Proc. 2005 Symposium on Usable Privacy and Securtiy}, pages
  77--88, 2005.

\bibitem{whyworks}
R.~Dhamija, J.~D. Tygar, and M.~Hearst.
\newblock {Why Phishing Works}.
\newblock In {\em Proc. CHI 2006 Conference on Human Factors in Computing
  Systems}, 2006.

\bibitem{earthlink-faq}
Earthlink.
\newblock {Earthlink Toolbar and ScamBlocker FAQ}.
\newblock \url{http://kb.earthlink.net/case.asp?article=30492}.

\bibitem{earthlink}
Earthlink.
\newblock {Earthlink Toolbar Featuring ScamBlocker for Windows Users}.
\newblock \url{http://www.earthlink.net/software/free/toolbar/}.

\bibitem{pew}
S.~Fox, L.~Rainie, J.~Horrigan, A.~Lenhart, T.~Spooner, and C.~Carter.
\newblock {Trust and privacy online: Why Americans want to rewrite the rules}.
\newblock August 2000.
\newblock \url{http://www.pewinternet.org/report_display.asp?r=19}.

\bibitem{ie7-certs}
R.~Franco.
\newblock {Better Website Identification and Extended Validation Certificates
  in IE7 and Other Browsers}.
\newblock November 2005.
\newblock \url{http://blogs.msdn.com/ie/archive/2005/11/21/495507.aspx}.

\bibitem{lpwa}
E.~Gabber, P.~B. Gibbons, Y.~Matias, and A.~Mayer.
\newblock {How to Make Personalized Web Browsing Simple, Secure, and
  Anonymous}.
\newblock In {\em Proc. Financial Cryptography 1997}. Springer-Verlag, February
  1997.

\bibitem{homograph}
E.~Gabrilovich and A.~Gontmakher.
\newblock {The Homograph Attack}.
\newblock {\em Comm. of the ACM}, 45(2):128, February 2002.

\bibitem{multiplier}
J.~A. Halderman, B.~Waters, and E.~W. Felten.
\newblock {A Convenient Method for Securely Managing Passwords}.
\newblock In {\em Proc. 14th International World-Wide Web Conference}, 2005.
\newblock \url{http://www.cs.princeton.edu/~jhalderm/projects/password/}.

\bibitem{trustbar}
A.~Herzberg and A.~Gbara.
\newblock {TrustBar: Protecting (even Na\"ive) Web Users from Spoofing and
  Phishing Attacks}.
\newblock Cryptology ePrint Archive, Report 2004/155, 2004.
\newblock \url{http://www.cs.biu.ac.il/~herzbea/TrustBar/}.

\bibitem{ssp}
A.~Karp.
\newblock {Site-Specific Passwords}.
\newblock Technical report, HP Labs.
\newblock \url{http://www.hpl.hp.com/personal/Alan_Karp/site_password/}.

\bibitem{stretching}
J.~Kelsey, B.~Schneier, C.~Hall, and D.~Wagner.
\newblock {Secure Applications of Low-Entropy Keys}.
\newblock {\em Lecture Notes in Computer Science}, 1396:121--134, 1998.

\bibitem{eweek}
R.~Naraine.
\newblock {Microsoft Downgrades Claria Adware Detections}.
\newblock July 2005.
\newblock \url{http://www.eweek.com/article2/0,1895,1834607,00.asp}.

\bibitem{netcraft}
Netcraft.
\newblock {Netcraft Anti-Phishing Toolbar}.
\newblock \url{http://toolbar.netcraft.com/}.

\bibitem{netcraft-privacy}
Netcraft.
\newblock {Netcraft Toolbar Privacy Policy}.
\newblock \url{http://toolbar.netcraft.com/privacypolicy.html}.

\bibitem{sitekey}
Bank of~America.
\newblock {Sign up for the SiteKey Service}.
\newblock \url{http://www.bankofamerica.com/privacy/passmark/}.

\bibitem{pwdhash}
B.~Ross, C.~Jackson, N.~Miyake, D.~Boneh, and J.~C. Mitchell.
\newblock {Stronger Password Authentication Using Browser Extensions}.
\newblock In {\em Proc. 14th Usenix Security}, 2005.

\bibitem{ie7-phishing}
T.~Sharif.
\newblock {Phishing Filter in IE7}.
\newblock September 2005.
\newblock \url{http://blogs.msdn.com/ie/archive/2005/09/09/463204.aspx}.

\bibitem{petnames}
M.~Stiegler.
\newblock {An Introduction to Petname Systems}.
\newblock \url{http://www.skyhunter.com/marcs/petnames/IntroPetNames.html}.

\bibitem{protocom}
Protocom~Development Systems.
\newblock {Global Password Usage Survey}.
\newblock September 2003.
\newblock
  \url{http://www.protocom.com/html/whitepapers/biz_password_survey.html}.

\bibitem{srp}
T.~Wu.
\newblock {The Secure Remote Password Protocol}.
\newblock In {\em Proc. 1998 Internet Society Network and Distributed System
  Security Symposium}, pages 97--111, March 1998.

\end{thebibliography}
}

\end{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Usability}

\subsubsection{Compatibility}

\subsubsection{Migration}

Can't require a wholesale switch at once, or it won't be adopted.

\subsubsection{Multiple Computers}

Many computer users use more than one computer.
Some own multiple computers at home;
some use a home computer as well as a work computer.

In a pinch, there has to be a way to log in to websites
from another computer (whether it's a friend's computer
or a computer at an Internet cafe).

\subsubsection{Convenience}

\subsection{Security}

\subsubsection{Spoofing Protection}

\subsubsection{Phishing Protection}

It must be {\em inconvenient} and {\em unusual} to give your password away.

  - user *doesn't know* site passwords, can't give them away

never give a secret to a spoofable entity
(even if the secret itself is never *really* given to the spoofable entity,
the user must not even *believe* he is giving the secret away)

\section{Comparison}

  - phishing workflow: request password -> enter password.
    no identification step!

  - therefore: id step is *necessary* for entering password

      - visual proximity to passpet button

      - passpet button disabled if no petname assigned

  - key advantage: get out of the habit of entering secrets on webpages

  - key advantage: just click to log in (cf. plain browser, pwdhash, dss)

  - key advantage: passwords are never stored (cf. browser autofill)

  - key advantage: user cannot be spoofed (cf. pwdhash)

  - key advantage: user protected against impersonation (cf. pwdhash,
        fake site could accept any password and pretend login succeeded)

  - better user understanding of risk of giving passwords to other computers

cf. IDN spoofing issue


The key problem at the core of phishing attacks is that
{\em users are constantly being asked to give away passwords
in situations where they have no reliable, convenient way
of knowing who they are giving their passwords to}.

  - storage server is compromised or malicious

  - spoof passpet tool, fool user into entering master password
      - defended by unique pet icon and name

  - intercept site password on the wire
      - easy with HTTP
      - protected by SSL with HTTPS
      - requires dictionary attack against both master password and petname
          to reveal master password, made more difficult by repeated hashing

  - impersonate site to steal password
      - can't steal password because passpet won't work

  - impersonate site to fool user
      - login procedure requires user to click, failure of passpet will
        interrupt the workflow and help the user notice something is wrong

  - intercept conversation between browser and petname database
      - rely on SRP to prevent discovery of master password

  - try to read or modify petname database
      - rely on SRP to authenticate

  - break into petname database server
      - can't decrypt or produce a coherent change without master password
      - must do dictionary attack against master password, made more
          difficult by key stretching


\section{Comparison to Other Solutions}

The use of animal icons and character names
may seem silly and cute,
but it has an important purpose:
to create a specific trust relationship
between the user and the Passpet tool.
Using different icons for each installed instance of Passpet
makes the Passpet interface difficult to spoof:
an attacker cannot fully imitate the Passpet interface
without knowing the correct icon and name.
Moreover, because the customized icon is a direct part of the workflow
(the user must click on the icon),
the user is less likely to use a spoofed Passpet tool.
The Passpet interface is intentionally minimal:
Passpet is to be recognized by its icon,
unlike password forms, which are recognized merely by the fact
that they have two text fields labelled ``username'' and ``password''.

Referring to the master password as ``Betty's secret''
facilitates a mental association
with the fact that it is a secret revealed only to ``Betty''.
The fact that one user thinks of the master password as ``Betty's secret''
while another user thinks of it as ``Donald's secret''
impedes an attacker from even {\em asking} for the master password.

The only way to identify Passpet is by its persona.

In particular,
the instructions emphasize
that ``Betty's secret'' is only for ``Betty the Zebra''
(or whatever persona was chosen for Passpet)
and never for entering into a webpage,
and that, if forgotten, it is unrecoverable.
There is no restriction on the length or characters permitted
in the master password.

The feedback provided during the setup process
allows the user to adjust the master secret

\subsection{Installation}

\subsection{Usage}

\section{Mechanism}


% LocalWords:  SRP LocalWords Passpet phishing DSS webpages username usernames
% LocalWords:  SRP's petname viewport pdf petnames UI Passpet's behaviour pt
% LocalWords:  enumi PwdHash LPWA Abadi Lomas Halderman Felten Netcraft Claria
% LocalWords:  coloured bankofthevvest bankofthewest paypal signin SpoofStick
% LocalWords:  TrustBar SiteKey unlabelled Felten's mac webpage phished Karp
% LocalWords:  Protocom IE autofilling deauthorizing reauthorizing webpage's
% LocalWords:  pharming