Identity Authentication

Dr. Ron Rymon Efi Arazi School of Computer Science Computer Security Course, 2010/11

Pre-requisites: Basic Cryptography

Overview
Identity Authentication Principles

Passwords
Challenge-Response

Zero Knowledge Identification Protocols

Authentication Using Physical Devices Biometrics

Identity Authentication Principles

Main Source: Menezes et al

Main Objectives
If Alice and Bob are both honest, then Alice

should be able to successfully authenticate herself to Bob, and vice versa (correctness)
Charles cannot present himself as Alice to Bob

(impersonation)
Bob cannot utilize an identification exchange with

Alice to impersonate Alice to a third party Charles (transferability)

Stronger Requirements
We require also that all three requirements (correctness,

impersonation prevention, and protection against transferability) hold

even if Charles was exposed to a large number of previous authentication exchanges between Alice and Bob even if Charles has participated in a large number of authentication exchanges with either or both Alice and Bob even if Charles is allowed to run a large number of concurrent authentication attempts

Zero Knowledge protocols require further that even many

executions of an authentication protocol provide NO INFORMATION to adversarial impersonator

Basis of Identification (Factors)

Something you know
Passwords, PINs, Secret or key

Something you possess

Physical devices: magnetic cards, smart cards, tokens, bluetooth, password generators, cellphones

Something you are

Biometrics (fingerprints, iris recognition, voice, handwriting), keyboarding characteristics

Others
Someplace you are (e.g. GPS location) Some way you behave

Ideally, more than one factor (Two-factor authentication) In some applications real-time identification is required

Properties of ID Methods & Protocols

Reciprocity of authentication Complexity Computational efficiency Communication efficiency Cost Use of third party Whether a third party is needed Whether a third party is needed in real-time Nature of trust required from third party What security guarantees are made False positive and false negative How and where secrets and keys are kept

Passwords
(weak authentication)

Main source: Menezes et al

Passwords
String of 6-8 characters that allows identification Fixed password/PINs, one-time passwords something you know Properties No reciprocity only unilateral identification Low complexity very efficient, both computationally and communication-wise Usually, no third party is used (exception: SSO) Key is usually kept by user in memory, and by system in a password file

Fixed Passwords Attacks

Replay attacks
Observe typing, find written or in another system, key loggers Eavesdropping on a cleartext or hashed communication channel

Exhaustive search
Randomly or systematically trying passwords against online verifier Offline search against password file enough that one user chose a weak password

Password guessing or Dictionary attack

Assumes that not all passwords are equally likely

Attack password distribution

Some systems come with fixed out-of-the-box passwords

Many tools for password cracking/auditing

http://www.password-crackers.com
Wireless key logger

Example: Focused Dictionaries

Use variations on related words

Password Space
Entropy
n 5 6 7 26 lowcase 23.5 28.2 32.9 36 alphanum 25.9 31.0 36.2 62 95 mixed case keyboard 29.8 35.7 41.7 32.9 39.4 46.0

(log 2)

8
n 5 6 7 8

37.6
26 lowcase 0.67hr 17hr 19dy 1.3yr

41.4
36 alphanum 3.4hr 120hr 180dy 18yr

47.6

52.6

Time

62 95 mixed case keyboard 51hr 130dy 22yr 1400yr 430hr 4.7yr 440yr 42000yr

To Search
(5000/sec)

Password Space Conclusions

Short, letters-only, passwords are easily breakable
Adding to the alphabet is important Adding to password length is important

Easier password spaces

A password from a lower-entropy space (dictionary) reduces the (expected) size of the search space Simpler password comparison functions allow more trials per second

In a simultaneous password file attack, it is enough that

one password is weak

Choose longer random passwords !

Fixed Passwords Security

Many systems enforce password rules
Goal: high-entropy passwords Usually, syntactic and procedural rules
Password must have at least 8 characters Password must include digits and special characters Password should not have a meaning (generators of pronounceable but long and not meaningful passwords) Must change password every 30 days Cannot repeat same password in multiple systems

Encrypted password files

Goal: avoid making the pwd file itself a target, e.g., to internal staff Usually, password is not encrypted using symmetric key, but rather using a one-way hash function
e.g., Alices password is stored as

h(Alice,pwd)

Fixed Passwords Security (cont.)

Slow down password mapping
Goal is to limit the use of exhaustive search programs, and hardware implementations Usually achieved by recursively applying a simple hash function Must be acceptable to legitimate users, e.g., one second

Salting
Goal: limit use of simultaneous dictionary attack Add a few bits to the password before hashing Usually, a time stamp or something based on the user id
Unix takes timestamp-based salt, Novells Netware takes serverassigned user ID

Salt is kept in cleartext in password file

Example: Unix Passwords

Unix keeps all passwords in a password file, /etc/passwd The user password serves as key to encrypt 64 zero bits,

and the ciphertext is kept

truncated/padded user password

0000

modified DES

ciphertext

First 8 characters are used, padded with 0s if needed, and

only first 7 bits of each taken to a create a 56-bit DES key

Example: Unix Password (cont.)

Cryptographically, note that the algorithm is

known and the plaintext is known DES is repeated 25 times, to slow down breaker Password is salted
12 randomly chosen bits from system clock are used to salt the password. They are used in the DES expansion function Thus, 212=4096 variations need checked in any simultaneous dictionary attack Because of the internal change to DES, one cannot use off-the-shelf DES hardware

Case Study: Password Cracking (Wu)

Tried to crack passwords of 25,000 corporate Kerberos users In two weeks, using 8 Sun machines, broke 2,045 passwords Length Percent 2 3 4 5 6 11 7 8 8 54 9 8 10 >10

0.1 0.6

3.8 7

4.5 3

Only 4% used at least one non-alphanumeric character 86% did not require using the shift key Some accounts used dates, telephone numbers Some passwords were common to more than one account 24% were combinations of two words 25% resulted from simple transformations of single words, e.g., capitalizing, reversing, or doubling of a word
Lowercasing a word was the most common transformation 1 was the most common suffix/prefix

Password Management Systems

Business problem: difficult for end-users to manage
Many passwords Weak passwords 40% of help desk calls are for password reset

Solution:
Centralized enterprise system Synchronize one or few passwords into many systems Self-service password reset Audit trail for password changes

Single Sign On (SSO) uses an agent on each target system

Passwords to privileged accounts
Business problem: lack of accountability since single password is shared by some/many people Solution: use intermediary to assign individual one-time passwords

Personal ID Number (PIN)

Usually used as a something you know in conjunction

with a something you possess

Most often, a credit card or ATM card Typically short (4 digits), so that can be memorized

To prevent exhaustive search, account is locked and/or

card is confiscated after 3-4 unsuccessful trials

To enable use of offline machines, the PIN may be stored

on the card, sometimes encrypted by a master key second high-entropy key is stored on the card

This is a form of two-stage authentication, where the

Passphrases and Passkeys

Passphrase can serve as a long password
E.g., this will let me to the dark side of the moon Pros: long; Cons: usually simple words and phrases, so effective search space is not very large

Or, a passphrase/sentence can be mapped to a pseudo-

random key (passkey)

The passkey can then be used as a regular symmetric key, e.g., to encrypt communication A userid-based salt may also be added A running counter may be added to the password to obtain a timevariant passkey

Example: WPA
Passphrase is concatenated with SSID and then hashed 4096 times to create a symmetric key

One-time Passwords
A solution against eavesdropping and replay

attack
Option 1: shared list of one-time passwords Use password i+k after password i (k can be randomly agreed in real-time) Or, Sequentially updated one-time passwords New password i+1 is agreed after first authenticating with password i E.g., use a one-way hash function to create a sequence
Lamport: Pi= H(Pi+1), where H is a OWF
Note 1: authentication requires a counter Note 2: it would not be secure if sequence was going forward

Graphical Passwords
Select certain points in a picture
Image can be user-specific Password=points and click order

To protect from shoulder surfing

Do not select points themselves Rather, select triangles that contain them Icons are reordered between selections

Knowledge of Personal History

Example: In which of the following addresses did you live in the past (or none of the above) Which of these places have you visited in the past What is last transaction made on your credit card Requires knowledge of a persons history, normally within a

certain area Can serve for a first time authentication (assuming access to history data)
Used by service providers in the credit card industry, e.g., credit

bureaus, or new credit grantors Security is reasonable but not substantial, as adversary may know or collect information about target

Challenge-Response Identification
(strong authentication)

Main source: Menezes et al

Challenge-Response (The Bad Version)

In enterprise and web applications, it is common to ask

users to provide one or more pairs of questions and answers

E.g., Q: Name of my dog, A: Saddam

When the user forgets her password, she can

authenticate herself to the system using these questions (and reset her password) weak authentication
Questions are often trivial, with a small set of possible answers, and the answer may be known to someone who knows the person

This is a variation on passwords and is considered very

Cryptographic Challenge-Response Protocols

Structure: Alice wishes to authenticate to Bob
Bob sends Alice a challenge Alice responds to the challenge Bob verifies the answer

Parties may use time-variant parameters (confounders) for

freshness

Confounders are good against replay attacks, chosen-text attacks Examples: timestamps, random numbers, sequence numbers, other one-time numbers (nonces), Generated by one party, and then the other party cryptographically binds response to this number to ensure freshness

Challenge-Response with Symmetric Keys

Parties may have agreed apriori on a key, or a key may be

provided by trusted server

e.g., KDC protocols like Kerberos, Needham-Schroeder

Example 1: one way authentication using a time-stamp

Alice authenticates herself to Bob by sending an encryption of her own time-stamp, using the shared key, EK(tA) Better yet, Bob sends Alice a challenge tB and she responds EK(tB) Problem: Eve can get Alice to encrypt a chosen text So Alice may add a random number and/or her own identifier, e.g., EK(tB, rA,Alice4Bob).

Example 2: using random numbers

First, Bob sends to Alice a random number rB Then, Alice sends to Bob EK(Alice4Bob, rB)

Mutual Authentication with Symmetric Keys

Mutual authentication requires one more step (can be done

with either timestamps or random numbers)

Challenge: rB A Response: EK (rA , rB ,AlBo) B Response: EK (rB , rA)

A variation on this authentication could also work with

HMAC instead of encryption

E.g., when encryption is not available (e.g., export restriction)

Challenge Response with Public Keys

To authenticate herself, Alice must show knowledge of her private key Can decrypt a challenge that was encrypted using Alices public key Or, sign digitally the challenge Potential issues with digitally signing a challenge Bob may ask Alice to sign a fraudulent message (pay Bob) Cannot use fixed certificate for risk of replay attack Solution: use a nonce to foil chosen-text attack in authentication, and a

timestamp to limit lifespan of possible attack Challenge: H(rB),Bob,EPubA(rB,tB,Bob) Response: rB

Or, have Alice sign same using her private key

X.509 Mutual Authentication

Use private/public keys to encrypt/prove and vice versa Use random nonces, time stamps, and public data (certificates)

Alice,EPrivA(rA,tA,Bob,XA,EPubB(YA)) Bob,EPrivB(rB,tB,Alice,rA,XB,EPubA(YB)) EPrivA(rB))

Public data (Xs) can be a certificate that contains the public key

of the user, and are themselves signed by a CA The Ys correspond to secret information, which may be keys (Kab and Kba) or key exponents for a key exchange The third step is required if it is difficult to synchronize clocks, and with it timestamps need not be checked

Defenses Against Attacks on Challenge-Response

Replay attack
Use nonces, embed target identity in response

Interleaving attack
Chaining protocol messages

Man-in-the-middle attack
Mutual authentication to foil adversary impersonating system

Reflection attack
Embed target identity, use uni-directional keys

Chosen text attack

Use confounder in each message Use Zero-knowledge protocols

Zero-Knowledge Identification Protocols

Main source: Menezes et al

Overview
Passwords may reveal Alices secret to Bob, who may then

impersonate her
With challenge-response protocols, Alice only reveals

knowledge of the secret

But, a strategic adversary may choose challenges that would reveal some aspects of this secret (or may choose from available interactions)

ZK protocols allow Alice to prove knowledge of the secret

without fearing that she may be providing anyone (Bob included) with any information about it
Note: RSA is also ZK, but most ZK protocols are more

efficient than RSA

On the other hand, they cannot be used for encryption/signature

ZK Properties and General Structure

Required ZK properties Completeness: all legitimate parties succeed Soundness: non-legitimate parties cannot succeed (actually: chances to succeed are arbitrarily small) ZK: the exchange does not reveal the secret

A typical ZK protocol consists of n iterations Alice presents Bob a witness of her secret (commitment) Bob presents a challenge to Alice Alice responds to the challenge Bob checks that the answer is correct
Probability of Alice cheating in each iteration < 1 After n iterations, to get arbitrarily small probability

Example: Isomorphic Graphs

G1 is isomorphic to G2 iff there is a vertex mapping
Really, G2 is just a permutation of the names of G1 nodes No known polynomial algorithm to reverse engineer

Proposed ZK Protocol
Alice chooses G1, and creates G2 that is isomorphic (using P1)
The graphs G1,G2 are public key, P1 is secret

Witness: Alice generates G3 that is isomorphic to G1 (using P2) Bob chooses Gi randomly and requires Alice to show mapping Alice responds
If G1, then the mapping is the generating permutation (P2) If G2, then the mapping requires applying both permutations (P1oP2)

Note:
Someone who didnt know P1 could have cheated in half the cases When run n times chances of cheating is exponentially low

The Fiat-Shamir ZK Protocol

Setup
Trusted server chooses n=pq, primes Alice selects a secret s<n, co-prime to n private key Alice computes v=s2 mod n public key

To authenticate Alice, Bob repeats

Commitment/witness: Alice chooses random r, and sends x=r2 mod n Challenge: Bob selects e=0/1 Proof: Alice computes and sends y=rse mod n, i.e., either r or rs Verification: Bob computes y2=x or y2= r2s2 = xv mod n

Note 1. Charles cannot impersonate Alice without knowing s because in

the cases (e=1), he may be asked to compute rs Note 2. Bob cannot replay the communication he had with Alice to impersonate Alice to Charles, because in the cases Charles may present a different challenge

Properties of ZK Protocols
No degradation of the protocol with usage No information is revealed in polynomial runs Compared with Symmetric keys or HMAC Resist chosen-text attacks Compared to Public-Key Lower computation costs Usually higher communication costs (# of iterations) Relies on same unproven math assumptions

Authentication Using Physical Devices

Using Physical Devices

A something you possess identification

Physical keys Regular keys Tokens

Credit cards Sometimes with PIN (something you know) Sometimes with picture ID (for people) Smartcards and passcode generators Protected memory Sometimes with CPU challenge response Using a computer physical MAC Combined with passwords Use computer fingerprint

Attack on ATM Cards (2003)

Cards must also work in offline mode
A Master key is used by ATM and bank Account number is encrypted using DES Last 4 digits (decimalized) are PIN PIN is verified by tamper-proof hardware

Bond (student in Cambridge) has shown that PIN can be

discovered with high likelihood within 15 trials (on avg)

Assumes access to a PIN verifier (e.g., corrupt insider) Manipulates the decimalization table to learn more from each trial
Use table with all 0s except i-th place to check if i-th digit is present Check all remaining possibilities Worst case is 10+36; average case is 24

Can be improved through adaptation

Illustration
Scanned Magnetic Stripe Scanned Magnetic Stripe

Encryption
0123456789012345

Encryption
0000100000000000

Decimalization
Keyed Number

Decimalization
0000

Comparison
OK/Not

Comparison
OK/Not

Smartcards and Passcode Generators

Calculators: Devices that store key(s) and can compute a time-

variant response to a challenge

Used in physical access and VPN apps, e.g., private banking
Smartcards: used to store identity authentication information, keys,

and other crypto applications

Many National ID projects around the world (Israel Mimshal Zamin) Applications: border control, healthcare system, anti-fraud, and other authentication apps Dual-factor: something you possess and something you know RFID in Physical Access Control Systems (PACS), as well as to

resist counterfeiting of high-ticket items (e.g., luxury watches)

Passcode Generator

Smartcard

Smartcard Reader

Biometrics

Biometrics
Biometrics measure innate characteristics
something you are, hence hard to impersonate

Can be Physiological:
Fingerprints Retinal or Iris scanning Face recognition Hand geometry recognition

Or behavioral
Voice recognition (both physiological and behavioral) Handwriting/signature recognition Typing dynamics

Biometrics-based Authentication
Usually uses a pattern recognition approach
A profile is constructed for the true person A matching score is computed in each authentication attempt

Processes

Threshold-based Decision
Real-time matching score is thresholded (T)

Error types
(A) False alarms (False Positive, Type 2 error) (B) Misidentification (False Negative, Type 1 Error)

Two Generic Applications

Easier: Verification One-to-One: given a real-time authentication attempt, try to match to a specific profile Requires a second form of identification, e.g., login, token. Harder: Identification Many-to-One: given a real-time authentication attempt, try to match to one of several profiles in a database Difficulty stems from birthday paradox unless a high separation can be attained between candidates Usually not attempted except in applications where two-factor authentication is not feasible

Fingerprints Analysis
Shapes:
ARCH WHORL LOOP

Minutiae:
END BIFURCATION ISLAND LAKE DOT

unique arrangement of minutiae for different people Non-intrusive, Reliable, Inexpensive Semiconductor or Optical Useful mostly for verification and less for identification

US stores experimented with payment by fingerprint

Hand Geometry
One of the first practically implemented techniques
physical access control: airports, secured corporate areas, etc. time and attendance monitoring

Reader uses CCD camera and a number of mirrors to

measure the shape of the hand perimeter, in <1 sec

Length, width, thickness, surface areas

Used for verification, in conjunction with another identifier

E.g., magnetic card

Non-intrusive

Palm Vein Authentication

Vein patterns are unique to an individual (even twins) Scanned with infrared rays, using reflective photography False rejection rate <0.01

PalmSecure (Fujitsu, CES 2006)

Iris Scanning
Human eye encodes 3.4bits/sqmm Extremely accurate: chance of duplication (including twins) < 1072 Fast comparison: Identification takes 2sec per 100,000 people in DB Sub-$1000 systems are available, but expensive to enroll many Considered a little intrusive / dangerous by some people Growing in market share vs. other solutions (patents expired)

Retinal Scanning
Works by identifying patterns in retinal blood vessels

Uses light source to take 400 measurements, which are

then reduced to a signature of 96 bytes Preceded Iris scanning, but is less prevalent
considered more intrusive requires precise positioning of the eye requires removal of glasses

Face Recognition
Controlled scene access control Frontal view, similar distance, reasonable lighting Compare live image to an original, captured in similar environment Usually for verification purposes, with another ID Algorithms extract features, and compare relative positions of eyes,

nose, and mouth, nose width, and other factors Relatively user-friendly Not very accurate, and requires frequent updates

Very difficult in a random scene street, airports Much more difficult Law enforcement applications Privacy issues: a bill that makes this unlawful was shelved in March 2002

Voice Verification
Principle: speech dynamics are affected by physical

structure of mouth, vocal chords, sinus, etc. A voice signature can typically be formed from speech features, with relatively high accuracy
Each syllable typically has few dominant frequencies (formants) More accurate when user repeats a previously recorded sentence

Weaknesses: taped replay, environmental noise, illness,

richness of spoken language Applications: access control, call centers Example: www.verivoice.com
User is requested to spell a random string of digits

Signature Verification
Static verification Dynamic verification
Curvature, changes in x-y sign, acceleration, pen up time

Weaknesses of Biometrics
Possibility of false positives, and sometimes

unacceptable FP rate In identification applications: misidentification Replay attack, e.g., tape replay, cut finger
Health concerns Privacy concerns

Biometric Market
Intl Biometric Group

The 5th Factor: How you behave

Idea: a users behavior may help identify, or at least authenticate her For example What time of the day you access a certain application? At what frequency do you perform a certain operation What type of access to which information you require? Did you login from home or work? Premise for authentication: a users behavioral pattern changes only

slowly over time. Advantage: relatively cheap (software) Typically shall be used in conjunction with another factor
e.g., use behavior profiling to supplement password authentication I believe that acceptance to this new form will grow, especially in

areas like intrusion detection and access control It also plays into the general trend of combining physical security and IT security

Choosing the Right Authentication Method

Choice of Authentication Methods

CAPTCHA

CAPTCHAs
Problem: robotic form filling can be used to
Guess passwords Abuse free services, primarily for spamming and phishing

Goal: Distinguish between a human user and a robot Method: Completely Automated Public Turing test to tell

Computers and Humans Apart (CAPTCHA)

Usually, asking the user to interpret letters and digits from

an image

Counter-Captcha Methods
Guessing, e.g., if space is small, e.g., 4 digits

Use OCR to recognize

And the prize goes to a man-in-the-middle

attack, asking a real person to authenticate.