l17-authentication.html

<h1>User authentication</h1>

<p><strong>Note:</strong> These lecture notes were slightly modified from the ones posted on the 6.858 <a href="http://css.csail.mit.edu/6.858/2014/schedule.html">course website</a> from 2014.</p>

<p><strong>Core challenge:</strong> How can human users prove their identity to a program?</p>

<ul>
<li>Is there any solution that totally dominates
passwords?</li>
<li>At first glance, passwords seem wretched.
<ul>
<li>Low entropy <code>--&gt;</code> easy for attackers to 
guess them.</li>
<li>Back-up security questions for passwords
are low entropy too.</li>
<li>A user often employs a single password
for multiple sites.</li>
</ul></li>
<li>As the paper for today's class states, <em>"The
continued domination of passwords over all
other methods of end-user authentication is
a major embarrassment to security researchers."</em></li>
<li>But... is there actually an authentication
scheme which totally dominates passwords?</li>
<li>Plan for today's lecture:
<ol>
<li>See how current password schemes work.</li>
<li>Talk about desirable properties for an
authentication scheme.</li>
<li>See how other authentication schemes
compare to passwords.</li>
</ol></li>
</ul>

<h2>Passwords</h2>

<p>A password is a secret that is shared between
the user and a server.</p>

<ul>
<li><strong>Naive implementation:</strong> server has a table that
maps usernames to plaintext passwords.</li>
<li><strong>Problem:</strong> If attacker compromises the server,
can recover all user/password pairs.</li>
<li><strong>Improved solution:</strong> Server stores this table:
<code>user_name --&gt; hash(user_password)</code></li>
<li>User client supplies cleartext password to
server, the server hashes the cleartext and
does a table lookup.</li>
<li><strong>Advantage:</strong> Hash functions are difficult to
invert, so it's difficult for attacker to
perform a brute force attack. However...</li>
<li><strong>Problem:</strong> Attacker doesn't have to launch
an inefficient brute force search over all
possible passwords -- the set of strings that
are actually used as passwords is quite small!
<ul>
<li>Skewed distribution: top 5000 password
values cover 20% of users.</li>
<li>Yahoo password study: Rule-of-thumb
passwords contain 10-20 bits of entropy.</li>
<li>Hash functions are optimized performance;
this helps attackers!
<ul>
<li><em>Example:</em> A laptop can calcuate SHA1s over
small blocks at ~2M SHA1 ops/sec.
Even if password has 20 bits of
entropy, can crack one account/sec.</li>
</ul></li>
</ul></li>
<li>Server can use a computationally expensive
<em>key-derivation function</em> (e.g., PBKDF2 or
BCrypt).
<ul>
<li>These functions have adjustable costs,
so they can be arbitrarily slow.</li>
<li>Ex: can make hash cost be 1 second -- O(1M)
times slower than SHA1.</li>
<li>Internally, often performs repeated
hashing using a slow hash.</li>
<li><strong>Problem:</strong> adversary can build "rainbow
tables".
<ul>
<li>Table of password-to-hash mappings.</li>
<li>Expensive to compute, but allows the
attacker to efficiently invert hashes
afterwards.</li>
<li>To maximize cost/benefit trade-off,
the attacker only need to build
a rainbow table for dictionary of
common passwords.</li>
<li>Roughly: 1-second expensive hash
<code>|-&gt; 1M seconds = 10 days</code>
to hash common passwords. After that, can
very quickly crack common passwords
in any password db.</li>
</ul></li>
</ul></li>
<li><strong>Better solution:</strong> server can use <em>password salts</em>.
<ul>
<li>Input some additional randomness into
the password hash: H(salt, pw).</li>
<li>Where does the salt value come from? It's
stored on the server in plaintext.</li>
<li><strong>Q:</strong> Why is this better if the adversary
can compromise the salt too?</li>
<li><strong>A:</strong> The attacker cannot use a single
rainbow table to check for hash
matches -- the same password with
different salts will have a different
hash value!</li>
<li><strong>Best practices:</strong>
<ul>
<li>Choose a long random salt.</li>
<li>Choose a fresh salt each time user
  changes password.</li>
</ul></li>
</ul></li>
</ul>

<p>How should a client <em>transmit a password to
a server?</em></p>

<ul>
<li><strong>Bad idea:</strong> send the password in the clear.</li>
<li><strong>Slightly better:</strong> send password over an
encrypted connection.
<ul>
<li><strong>Drawback:</strong> Connection may be intercepted
by an attacker who pretends to be the
server (encryption doesn't necessarily
mean that the server has authenticated
to the client!). MITM attacker can then
use the stolen password to impersonate
the user.
<ul>
<li><strong>Q:</strong> What if client sends the hash of the
password instead of the raw password?</li>
<li><strong>A:</strong> Doesn't provide us with any extra
power, since the hash can still be
replayed by the attacker.</li>
<li><strong>Moral of the story:</strong> Encryption and hashing do not automatically
add security -- you need to think about
what security properties you want to
achieve, and specific ways that encryption
and hashing can achieve those goals.</li>
</ul></li>
</ul></li>
<li><strong>Better idea:</strong> Challenge/response protocol.</li>
</ul>

<p><em>Example:</em></p>

<pre><code>   Client             Server

        Hi, I'm Alice.
       ----------------&gt;

          Challenge C
       &lt;----------------

        H(C || password)
       -----------------&gt;

                     - Server checks whether the
                       response is H(C || password).
</code></pre>

<ul>
<li>Ignoring man-in-the-middle (MITM) attacks, the server is now confident
 that the user is Alice.</li>
<li>If server is an attacker and didn't
 already know password, the attacker
 still doesn't know password.
<ul>
<li><strong>Q:</strong> How can we prevent server from  brute-force guessing password
based on <code>H()</code> value?</li>
<li><strong>A1:</strong> Expensive hash + salting.</li>
<li><strong>A2:</strong> Allow client to choose some randomness too: guard against rainbow tables.</li>
</ul></li>
<li>To avoid storing the real password on the
 server, use a protocol like <a href="http://en.wikipedia.org/wiki/Secure_Remote_Password_protocol">SRP</a></li>
<li><strong>High-level idea:</strong> Given a security parameter
 <code>g</code>, the client computes <code>v = g^(hash(salt, password))</code>
 and sends <code>v</code> and the <code>salt</code> to the
 server. The client and the server can
 then establish an ephemeral key with
 their shared knowledge of <code>g</code> and <code>v</code>
 (protocol takes advantage of the fact
 that it's difficult for the attacker to
 perform discrete logarithms modulo <code>N</code>;
 RSA also takes advantage of this
 observation).</li>
<li>Implementing challenge/response often
 means changing the client and the server.</li>
</ul>

<p>To prevent brute force attacks, we can implement
<em>anti-hammering defenses</em>.</p>

<ul>
<li><em>Example</em>: Rate-limit the number of password guesses;
implement time-out periods after too many
incorrect guesses.</li>
<li>It's really important to throttle guess rate
because passwords have so little entropy!
<ul>
<li>Many sites impose requirements on
passwords (e.g., length, the use of
special chars like punctuation).</li>
<li>In reality, what matters is <em>entropy</em>!
Format requirements rarely translate
into higher entropy.</li>
<li>A competent dictionary attacker can
model password constraints and still
generate rainbow tables; even with
constraints, people will still pick
passwords that adhere to a priori
character distributions. </li>
<li><em>Telepathwords:</em> <a href="https://telepathwords.research.microsoft.com/">https://telepathwords.research.microsoft.com/</a>
<ul>
<li>As you type in a potential password
letter, tries to guess the next letter
using heuristics!
<ul>
<li>Common passwords (e.g., via leaks  of password databases)</li>
<li>Popular phrases from web sites</li>
<li>Common user biases in selecting characters (e.g., using adjacent
keys for adjacent password characters)</li>
</ul></li>
</ul></li>
</ul></li>
<li>Kerberos v4, and v5 without preauth were
vulnerable to offline guessing:
<a href="http://www.gnu.org/software/shishi/wu99realworld.pdf">http://www.gnu.org/software/shishi/wu99realworld.pdf</a>
<ul>
<li>Anyone could ask the KDC for a ticket
encrypted with the user's password, i.e.,
the KDC did not authenticate requests
(although the response would be encrypted
with <code>K_c</code>).</li>
<li>Attacker can try brute-force to guess
the user's password -- this is easy to
parallelize. Since the ticket-granting-ticket
has a known format, the attacker can
determine when a decryption is successful.</li>
<li>In Kerberos v5, ticket requestor must
include <code>{ timestamp }_{K_c}</code> along with
request, to prove knowledge of <code>K_c</code>.</li>
</ul></li>
</ul>

<p><strong>Password recovery</strong> is extremely important, but
often overlooked.</p>

<ul>
<li>People often focus on the entropy of passwords,
but if recovery questions can be used to reset
passwords, the strength of a password authentication
scheme is <code>min(password_entropy,
             recovery_question_entropy)</code>.</li>
<li>Recovery questions are often easily guessable.
In one famous example, somebody got access to
Sarah Palin's Yahoo address by guessing answers
to her security questions.
<ul>
<li>Intrinsically low entropy (<em>"What's
your favorite color?" "What's the
name of your best friend?"</em>)</li>
<li>Answers leaked via social media
profiles (<em>"What's your favorite
movie?"</em>)</li>
<li>Self-generated questions are typically
easy to answer (<em>"What is 5 + 5?"</em>)</li>
</ul></li>
</ul>

<h2>The quest to replace passwords</h2>

<p>In the reading for today, the authors propose
a bunch of factors that can be used to evaluate
authentication schemes (the goal is to determine
whether passwords are as bad as they seem). The
authors consider three high-level metrics:
usability, deployability, and security.</p>

<ul>
<li><strong>Usability:</strong> How easy is it for users to
interact with the authentication scheme?
<ul>
<li><em>Easy-to-Learn:</em> 
<ul>
<li>"Users who don't know the scheme can figure it out and learn
it without too much trouble."</li>
<li>This is a key reason why password schemes are so popular!</li>
</ul></li>
<li><em>Infrequent errors:</em> 
<ul>
<li>"The task that users
must perform to log in usually succeeds
when performed by a legitimate and
honest user."</li>
<li>This is an important reason why users pick easy-to-guess passwords.</li>
</ul></li>
<li><em>Scalable-for-Users:</em> 
<ul>
<li>"Using the scheme
for hundreds of accounts does not
increase the burden on the user."</li>
<li>... explains why people often
reuse passwords or create a simple
per-site uniquifying scheme for a
base password.</li>
</ul></li>
<li><em>Easy recovery from loss of the
authentication token:</em>
<ul>
<li>A win for passwords -- they're easy
to reset.</li>
</ul></li>
<li><em>Nothing to carry</em>
<ul>
<li>Another win for passwords.</li>
</ul></li>
</ul></li>
<li><strong>Deployability:</strong> How easy is it to incorporate
the authentication method into real systems?
<ul>
<li><em>Server-Compatible:</em> 
<ul>
<li>"At the verifier's end,
the scheme is compatible with text-based
passwords. Providers don't have to change
their existing authentication setup to
support the scheme."</li>
</ul></li>
<li><em>Browser-Compatible:</em> 
<ul>
<li>"Users don't have
to change their client to support the
scheme. Schemes fail to provide
this benefit if they require the
installation of plugins or any kind of
software whose installation requires
administrative privileges."</li>
</ul></li>
<li><em>Accessible:</em> 
<ul>
<li>"Users who can use passwords
are not prevented from using the scheme
by disabilities or other physical (not
cognitive) conditions."</li>
</ul></li>
<li>Deployability is extremely difficult:
it's difficult to get users or servers
to update en masse!</li>
<li>Passwords do well in this category by
default, since the authors define
"deployability" as how well a system
integrates with current password
infrastructure. However, passwords
don't do very well in the next
category...</li>
</ul></li>
<li><strong>Security:</strong> What kinds of attacks can the
authentication scheme prevent?
<ul>
<li><em>Resilient-to-Physical-Observation:</em> 
<ul>
<li>"An attacker cannot impersonate a user after
observing them authenticate one or more
times. We grant Quasi-Resilient-to-
Physical-Observation if the scheme could
be broken only by repeating the observation
more than, say, 10-20 times. Attacks
include shoulder surfing, filming the
keyboard, recording keystroke sounds, or
thermal imaging of keypad."</li>
<li>Passwords fail this test, since,
e.g., they can be captured by
filming the keyboard or recording
keystroke sounds.</li>
</ul></li>
<li><em>Resilient-to-Targeted-Impersonation:</em> 
<ul>
<li>"It is not possible for an acquanitance (or
skilled investigator) to impersonate a
specific user by exploiting knowledge of
personal details (birth date, names of
relatives etc.). Personal knowledge
questions are the canonical scheme that
fails on this point."</li>
<li>The authors say that passwords
are "quasi-resistant" b/c they
couldn't find any studies saying
that your friends or acquaintances
can easily guess your password.</li>
</ul></li>
<li><em>Resilient-to-Throttled-Guessing:</em> 
<ul>
<li>"An attacker whose rate of guessing is
constrained by the verifier cannot
successfully guess the secrets of a
significant fraction of users . . .
Lack of this benefit is meant to
penalize schemes in which it is frequent
for user-chosen secrets to be selected
from a small and well-known subset."</li>
<li>Passwords fail because they
have low entropy + skewed
distributions.</li>
</ul></li>
<li><em>Resilient-to-Unthrottled-Guessing:</em>
<ul>
<li>"An attacker whose rate of guessing is
constrained only by available computing
resources cannot successfully guess the
secrets of a significant fraction of users.
We might for example grant this benefit if
an attacker capable of attempting up to 2^40
or even 2^64 guesses per account could
still only reach fewer than 1% of accounts.
Lack of this benefit is meant to penalize
schemes where the space of credentials is
not large enough to withstand brute force
search from a small and well-known subset."</li>
<li>Passwords fail because they
have low entropy + skewed
distributions.</li>
</ul></li>
<li><em>Resilient-to-Internal-Observation:</em>
<ul>
<li>"An attacker cannot impersonate a user by
intercepting the user's input from inside
the user's device (e.g., by keylogging
malware) or eavesdropping on the cleartext
communication between prover and verifier
(we assume that the attacker can also
defeat TLS if it is used, perhaps through
the CA) . . . This penalizes schemes that
are not replay-resistant, whether because
they send a static response or because
their dynamic response countermeasure can
be cracked with a few observations. This
benefit assumes that general-purpose devices
like software-updatable personal computers
and mobile phones may contain malware,
but that hardware devices dedicated
exclusively to the scheme can be made
malware-free."</li>
<li>Passwords fail because they
are static tokens: once you
have one, you can use it until
it expires or is revoked.</li>
</ul></li>
<li><em>Resilient-to-Phishing:</em>
<ul>
<li>"An attacker who
simulates a valid verifier (including
by DNS manipulation) cannot collect
credentials that can later be used to
impersonate the user to the actual verifier.
This penalizes schemes allowing phishers
to get victims to authenticate to look-alike
sites and later use the harvested
credentials against the genuine sites."</li>
<li>Passwords fail: phishing attacks
are very common!</li>
</ul></li>
<li><em>No-Trusted-Third-Party:</em> 
<ul>
<li>"The scheme does
not rely on a trusted third party (other
than the prover and the verifier) who
could, upon being attacked or otherwise
becoming untrustworthy, compromise the
prover's security or privacy."</li>
<li>This property makes an important
point: a lot of authentication
problems would become easier if
we could just trust one party
to store passwords, run the password
servers, etc. However, single
points of failure are bad, since
attackers can focus all of their
energy on that point!</li>
</ul></li>
<li><em>Resilient-to-Leaks-from-Other-Verifiers:</em>
<ul>
<li>"Nothing that a verifier could possibly
leak can help an attacker impersonate the
user to another verifier. This penalizes
schemes where insider fraud at one
provider, or a successful attack on one
back-end, endangers the user's accounts
at other sites."
<ul>
<li>This property is related to
No-Trusted-Third-Party. To avoid
a central point of failure, we'd
like to introduced some notion
of distributed authentication:
however, does this mean that the
system is only as strong as its
weakest link?
<ul>
<li>Think back to HTTPS,
and how a bad certificate authority
can convince a browser to accept
fake certificates for arbitrary
sites. Security depends on the
strength of the least secure CA!</li>
</ul></li>
<li>Authors say that passwords fail
because people often reuse passwords
across sites.</li>
</ul></li>
</ul></li>
</ul></li>
</ul>

<h2>Biometrics</h2>

<p><strong>Biometrics:</strong> Leverage the unique aspects of a
person's physical appearance or behavior.</p>

<ul>
<li>How big is the keyspace?
<ul>
<li><em>Fingerprints:</em> ~13.3 bits.</li>
<li><em>Iris scan:</em> ~19.9 bits.</li>
<li><em>Voice recognition:</em> ~11.7 bits.</li>
<li>So, bits of entropy are roughly the same
as passwords.</li>
</ul></li>
</ul>

<h3>Biometrics vs. passwords</h3>

<pre><code>    Usability metric     Passwords        Biometrics
    ---                  ---              ---
    Easy-to-learn:       Yes              Yes
    Infrequent errors:   Quasi-yes        No
    Scalable for users:  No               Yes
    Easy recovery:       Yes              No
    Nothing to carry:    Yes              Yes

                       Usability score: 3.5 vs 3    

    Deployability metric Passwords        Biometrics
    ---                  ---              ---
    Server-compatible:   Yes              No
    Browser-compatible:  Yes              No
    Accessible:          Yes              Quasi-yes (entering biometrics is error-prone)    

                       Deployability score: 3 vs 0.5

    Security metric         Passwords        Biometrics
    ---                     ---              ---
    Res-to-Phys-Obs:        No               Yes
    Res-to-Trgtd-Imp:       Quasi-yes        No (e.g., replaying voice recording, lifting fingerprints from surfaces)
    Res-to-Thrtld-Guess:    No               Yes
    Res-to-UnThrtld-Guess:  No               No (key space isn't much bigger than that of passwords)
    Res-to-Internal-Obv:    No               No (captured biometric data can be replayed)
    Res-to-Phishing:        No               No
    No-trusted-3rd-Party:   Yes              Yes
    Res-Other-Ver-Leaks:    No               No (same biometrics are used by all verifiers)

                        Security score: 1.5 vs 3
</code></pre>

<p>So, final score is 8 vs 6.5. Of course,
one could assign non-unity weights to
each category, but the point is that it's
not obvious that biometrics are "better"
than passwords!</p>

<p>Some sets of goals seem difficult to achieve
at the same time.</p>

<pre><code>    Memorywise-Effortless + Nothing-to-Carry.
    Memorywise-Effortless + Resilient-to-Theft.
         // Either the user remembers something, or
         // it can be stolen (except for biometrics).

    Server-Compatible + Resilient-to-Internal-Observation.
    Server-Compatible + Resilient-to-Leaks-from-Other-Verifiers.
         // Server compatible means sending a password.
         // Passwords can be stolen on user machine,
         // replayed by one server to another.
</code></pre>

<h2>Multi-factor authentication (MFA): defense using depth</h2>

<ul>
<li>Requires users to authenticate themselves using
two or more authentication mechanisms.</li>
<li>The mechanisms should involve different modalities!
<ul>
<li>Something you know (e.g., a password)</li>
<li>Something you possess (e.g., a cellphone, a hardware token)</li>
<li>Something you are (e.g., biometrics)</li>
</ul></li>
<li>Idea is that an attacker must steal/subvert
multiple authentication mechanisms to
impersonate a user (e.g., attacker might guess
a password, but lack access to a user's phone).</li>
<li>Example: Google's two-factor authentication
requires a password plus a cellphone which
can receive authorization codes via text
message.</li>
<li>Example: AWS two-factor authentication requires
a password and an "MFA device" (a smartphone
running an authentication app, or a
special-purpose security token or security
card). <a href="http://aws.amazon.com/iam/details/mfa/">Amazon MFA</a></li>
<li>MFA is a good idea, but empirical studies
show that if users are given a second
authentication factor in addition to
passwords, users pick much weaker passwords!</li>
</ul>

<h2>Homework Q</h2>

<p>What are potential answers to the homework
questions? What factors matter?</p>

<ul>
<li>Logging into public Athena machine?
<ul>
<li>Resilient-to-Internal-Observation: easy to install malware on machine.</li>
<li>Resilient-to-Physical-Observation? + MIT IDs could be a good thing to leverage (use them as a smartcard).</li>
<li>Biometrics? Untrusted terminals, probably not a great plan.</li>
</ul></li>
<li>Accessing Facebook from Internet cafe?
<ul>
<li>Password managers not a good idea here.</li>
<li>How sensitive is the data?
<ul>
<li>Might be leveraged to authenticate
to other sites! (Either "Login with
Facebook" or by answering personal
security questions to reset a
password.)</li>
</ul></li>
</ul></li>
<li>Withdrawing cash from ATM?
<ul>
<li>Security matters highly.
<ul>
<li>Resilient-to-Physical-Observation.</li>
<li>Resilient-to-Theft.</li>
</ul></li>
<li>Possibly trusted terminal: biometrics  might be worth considering. (However,
 in practice, bank may not want to trust the terminals.)</li>
<li>You also might care about authenticating individual transactions!
<ul>
<li>Prevent the adversary from using
stolen credentials for different,
attacker-chosen operations.</li>
<li>Ex: Maybe user can examine balance
using just a password, but if she
wants to withdraw money, she uses
two-factor authentication using
her phone.</li>
</ul></li>
</ul></li>
</ul>

<h2>Conclusions</h2>

<p>Conclusion of paper: There is no authentication
scheme which clearly dominates passwords! For
example, according to the authors, the CAP
reader has perfect scores on security!</p>

<ul>
<li>The CAP reader was designed by Mastercard
to protect online banking transactions.</li>
<li>Usage:
<ol>
<li>Put your credit card into the CAP
reader (which looks like a hand-held
calculator).</li>
<li>Enter PIN (bypassing keyloggers!).</li>
<li>Reader talks to the card's embedded
processor, outputs an 8-digit code
which the user supplies to the
web site.</li>
</ol></li>
</ul>

<p><em>Analysis:</em></p>

<pre><code>                            CAP reader
        Easy-to-learn:      Yes
        Infrequent errors:  Quasi-yes
        Scalable for users: No (users require card+PIN per verifier)
        Easy recovery:      No
        Nothing to carry:   No
                            Score: 1.5

                            CAP reader
       Server-compatible:   No
       Browser-compatible:  Yes
       Accessible:          No (blind people can't read 8-digit code)
                            Score: 1

                            CAP reader
    Res-to-Phys-Obs:        Yes\
    Res-to-Trgtd-Imp:       Yes \__ One-time codes!
    Res-to-Thrtld-Guess:    Yes /
    Res-to-UnThrtld-Guess:  Yes/
    Res-to-Internal-Obv:    Yes     Dedicated device
    Res-to-Phishing:        Yes     One-time codes
    No-trusted-3rd-Party:   Yes     Each site is its own verifier
    Res-Other-Ver-Leaks:    Yes     One-time codes
                            Score: 8
</code></pre>

<ul>
<li>So, <code>passwords=8</code> and <code>CAP reader=10.5</code>. However,
there are reasons why CAP readers haven't
taken over the world (see the low usability
and deployability scores).</li>
<li>In practice, deployability and usability are
often more important than security.
<ul>
<li>Migration costs (coding+debugging effort,
user training) make developers nervous!</li>
<li>The less usable a scheme is, the more
that users will complain (and try to
pick easier authentication tokens that
are more vulnerable to attackers).</li>
</ul></li>
<li>Some situations may assign different weights
to different evaluation metrics.
<ul>
<li><em>Example</em>: On a military base, the security
benefits of a hardware-based token might
outweigh the problems with usability
and deployability.</li>
</ul></li>
</ul>