Authentication
SFL @ TU Dortmund
Authentication = Proving an Identity
Copyright By PowCoder代写 加微信 powcoder
Answer to questions that only you know
Certificate
Electronic ID
Biometrics
Fingerprint
Location (physical / virtual)
Typing habit
Password (Shared-Secret) Authentication (“What you know”)
Password Authentication
• Basic idea
• User has a secret password
• System checks password to authenticate user
• Challenges
• How “strong” is a password?
• How can we securely communicate passwords? • How can we securely store passwords?
• How does a system validate the password?
Other Aspects
• Usability
• Hard-to-remember passwords?
• Carry a physical object all the time?
• Denial of service
• Attacker tries to authenticate as you, and account locked after three failures
• Availability
• Password recovery
Choosing Strong Passwords
• Number of possible password combinations is |A|L • Alphabet A: Set of possible characters
• Length L: Number of characters in password
• Shannon entropy measures bits of security: h = log2(|A|L)
Alphabet (A)
Number of combinations (k)
Entropy (h)
A-Z, a-z, 0-9
626 = 56.800.235.584
A-Z, a-z, 0-9
218.340.105.584.896
A-Z, a-z, 0-9,
()[]{}?!$%&/=*+
2.992.179.271.065.856
A-Z, a-z, 0-9,
()[]{}?!$%&/=*+
163.674.647.745.587.512.938.496
Securely Storing Passwords
• Authentication services have to store passwords to authenticate users
g0d!sh3_is_s0%Cut3
bvb09_borussia
• But: Storing passwords in plaintext is a bad idea
• Experience has shown that password databases leak
(e.g., via SQL injection attacks, insiders, or service compromises)
https://haveibeenpwned.com/
Hack (2009)
• “Social gaming” company
• Database with 32M user passwords from partner social networks • Passwords stored in the clear
• December 2009: entire database hacked using an SQL injection attack and posted on the Internet
Password length distribution
Adobe Password Leak (2013)
• 153 million account passwords
• 56 million of them unique (i.e., ~2/3 of users had a non-unique password!)
• Encrypted using 3DES (a symmetric cipher) in ECB mode
• Two problems:
• Decryption of all passwords possible once decryption key was bruteforced • ECB mode pertains patterns of passwords in plaintext
Anatomy of a password disaster – Adobe’s giant-sized cryptographic blunder
Storing Passwords Securely
• Storing plaintext passwords is a bad idea. Can we just encrypt them with a private key instead (that is known to the application, and is never revealed to the attacker)?
A: No, there must be better ways than this.
B: Sounds like a nice solution.
C: Depends on encryption mode. ECB would be a nightmare.
Password Hashing
• Hash password with collision-resistant hash function: H(password) • When user enters a password, compute its hash and compare with
the entry in the password file
• System does not store actual passwords
• Cannot infer password from hash except by guessing (assuming a preimage-resistant hash function)
Dictionary Attacks (1/3)
• Problem: Users tend to choose non-random passwords
• With 52 upper- and lower-case letters, 10 digits and 32 punctuation symbols:
– ≈ 6 quadrillion possible 8-character passwords
• Humans like to use dictionary words, human and pet names:
– ≈ 1 million common passwords
• Dictionary attack doable if many passwords come from a small set • Attacker can pre-compute H(word) for every word in the dictionary
– This only needs to be done once and can be done in an offline fashion
– Once password file is obtained, cracking is instantaneous
• Sophisticated password guessing tools are available
– Take into account frequency of letters, password patterns, etc.
Dictionary Attacks (2/3)
• Typical password dictionary
• 1,000,000 entries of common passwords
• Suppose you generate and analyze just 10 guesses per second
– Dictionary attack in at most 100,000 seconds =
28 hours, or 14 hours on average
– This may be reasonable for a web site; offline is much faster
• Random passwords
• Assume six-character password
– Upper- and lowercase letters, digits, 32 punctuation characters
– 689,869,781,056 password combinations.
– Exhaustive search requires 1,093 years on average
• Dictionary attack vs exhaustive search: 14 hours vs. 1000 years
Dictionary Attacks (3/3)
• Custom GPU-based hardware
• Example from LinkedIn hack
• 8 commodity GPUs in “normal” server • 210M SHA1 hashes per second
• Cloud-based cracking tools
• CloudCracker, Cloud Cracking Suite (CCS)
nonce = number used once
Salting: Append random nonce (salt) to password before hashing Compute H(PasswordAlice | saltAlice) and store hash and salt
Salt is chosen at random for every new user
Rule of thumb: salt should be as long as the hash function’s output
Password hash
5F 3B C7 7E 2C .. 39
FA 9C 13 5A A8 .. 0D
29 41 F5 95 89 .. D2
10 29 C6 3B 39 .. EC
60 4E D9 89 E1 .. BF
02 EE 74 CF 18 .. 1B
• Before: Attacker can pre-compute hashes of common passwords once
• With salt: Attacker must compute hashes of common passwords for each possible salt value
• x-bit salt slows dictionary attack by factor of 2x
• e.g., 256-bit salt results in 1077 different hash values for a single password
Pepper is a secret password used when hashing the password Pepper is not stored in the password database, only in server application
Pepper complements salt to make it impossible to reverse a hash without knowing the pepper password, even if salts and hashes have leaked
Example of peppering: H(PasswordAlice | saltAlice | pepperS)
Peppering helps if password DB is compromised, but app is not: Imagine you wrote a web application that stores users in a SQL database Assume an attacker can steal the database (e.g., SQL injection attacker) Attacker however cannot compromise your application (pepper unknown)
→Database compromise just reveals peppered (+ salted) passwords
Hash Stretching (1/2)
• Hash stretching exploits a tradeoff
• Benign password verifications do not need to be rapidly fast • Malicious password bruteforce attempts have to be efficient
• Basic idea: Slow down hash computations
• Enhance effort of computing a single hash
• Optimize software-based computation (and then cascade multiple runs)
• Try to make hardware hashing implementations harder – e.g., require expensive resources such as memory
• Examples
• bcrypt: variable number (>> 1) of Blowfish hash rounds • scrypt: similar, but uses 16 MB vector for computation
Hash Stretching (2/2)
• Custom (non-standard) hash stretching is dangerous
• Consider you build H(H(…H(H(pw))…)))
• Feeding back H’s output to H as input reduces the input space significantly
• scrypt and bcrypt therefore increase number of rounds
(instead of calling a hash multiple times) • One potential solution:
• Include password to every hash as input: H(pw, H(pw, H(pw, H(…)))) • This way you keep the original input space
Password-Based Authentication Schemes (1/2)
• Alice and server know Alice’s password (or a value derived from it) • Alice claims identity (claimant) and server has to verify it (verifier)
• But how can Alice securely prove its identity to the server?
• Negative example (password in plain):
pw: Password of Alice
Password-Based Auth.
• Is this modified password-based authentication proposal secure?
A: Yep. The password is not transmitted in plain text.
B: No. Gimme dat dictionary.
C: Depends on the cryptographic strength of the hash function.
Password-Based Authentication Schemes (2/2)
为了安全地传输pw，因此有了这个方案。
• What are good unilateral password-based authentication schemes?
• We already discussed several challenge-response handshake protocols
• Dozens of other industry standards propose even more schemes (PAP, CHAP, CRAM-MD5, CRAM-SHA1)
• Example of CRAM-SHA1 (“Challenge Response Authentication Mechanism”):
pw: Alice‘s Password at S n: Nonce chosen by S
Alice HMACSHA1(n, pw)
• Not all authentication protocols are compatible with peppering and salting and thus may require adjustments.
Password-Authenticated Key Exchange
• How do we turn a (weak) password into a (strong) secret key?
• Password has too low entropy to be used as cryptographic key
• Derive values from password, but do not provide usable information about it • Use this derived value as strong(er) key
• Negative example (that is not secure against password bruteforce): • Adversary knowing n can tell when they succeeded in decrypting {n}pw
{}: Symmetric encryption
n: Server-chosen nonce
pw: Password (encryption key)
DH-EKE – Encrypted Key Exchange based on DH (1/2)
• DH-based EKE (originally by Bellovin, Merritt 1992)
• Perform password-encrypted Diffie- Exchange (DHKE)
Alice, {X = gx mod p}pw {Y = gy mod p}pw
k=Yx modp=Xy modp
{}: Symmetric encryption pw: Password
g: Public generator (base) k: Strong key (derived) NB: Nonce chosen by B NA: Nonce chosen by A
步骤4-5:只是为了验证双方是否已经派生了正确 的密钥。
{NB}k {NA}k
DH-EKE – Encrypted Key Exchange based on DH (2/2)
• Main ideas of EKE:
前向保密性:指的是长期使用的主密钥泄漏不会导致过去的会话密钥 泄漏。[2]前向保密能够保护过去进行的通讯不受密码或密钥在未来暴 露的威胁。如果系统具有前向保密性，就可以保证在私钥泄露时历史 通讯的安全，即使系统遭到主动攻击也是如此。
• Low entropy shared secret becomes a high entropy shared key
• Prevents dictionary attack against the password
• Prevents man-in-the-middle attack by authenticating the DH key exchange
• Provides perfect forward secrecy (PFS): if past sessions were recorded and password is then compromised, the session key still remains unknown
• Finally, after a ‘91 patent expired in 2011, people could adopt EKE.
SPEKE – Simple Password Exponential Key Exchange
• SPEKE (Jablon, 1996)
• Use (converted) password as base for exponentiation
A, QA = f(pw)x mod p
B, QB = f(pw)y mod p
k = h(QBx mod p) = h(QAy mod p)
Legend (see DH):
{}: Encryption
pw: Password
f: Function (converts pw to base) h: Hash function
k: Password-derived strong key
Kerberos (1/2)
• Kerberos is a secure single sign-on solution
• Users authenticate only once (e.g., per day) and can transparently
access an arbitrary number of services without reentering their secret • Default authentication mechanism for Active Directory (since Windows 2000) • Probably the most widely used authentication protocol for end users
• Basic idea
• Obtain a session ticket from authentication server
• Use session ticket to obtain service ticket to access a server
Kerberos (2/2)
Key Distribution Center
· c a 袄 ~s 、“` – . , ‘ t a u t ” e ` ` ` 妇.
飞ne心，，你心et
The client forwards TGT to TGS and gets a “Service Ticket”
The c/· /ent”0rwardss,tos
Authentication Service (AS)
Ticket Granting Svc. (TGS)
Authentication: Biometrics (“What you are”)
Biometrics
• Use a person’s physical characteristics • fingerprint, voice, face, keyboard timing, …
• Advantages
• Cannot be disclosed, lost, forgotten
• Disadvantages
• Cost, installation, maintenance
• Reliability of comparison algorithms
– False positive: Allow access to unauthorized person
– False negative: Disallow access to authorized person
• Privacy?
• If forged, how do you revoke?
Voluntary Fingerprint Cloning
• Select the casting material
• Softened, free molding plastic (used by Matsumoto)
• Part of a large, soft wax candle (used by Willis; Thalheim)
• Push the fingertip into the soft material and let it harden • Select the finger cloning material
• Gelatin: “gummy fingers”, used by Matsumoto
• Silicone: used by Willis; Thalheim
• Pour a layer of cloning material into the mold
• Let the clone harden
Involuntary Fingerprint Cloning
• Clone without victim knowledge or assistance
• Appears in Hollywood movies
• Sneakers (1992) “My voice is my passport” • Never Say Never Again (1983) cloned retina
• Charlie’s Angels (2000)
– Fingerprints from beer bottles
– Eye scan from oom-pah laser
• Bad news: Cloning attacks work
Fingerprint of former of the Inner Dr. ̈uble, stolen by CCC and published in 2008.
Involuntary Fingerprint Cloning: Example
• Capture clean, complete fingerprint on a smooth surface (e.g., glass) • Pick it up using tape and graphite
• Scan it into a computer at high resolution
• Etch fingerprint image onto printed circuit board (PCB) material
• Use the PCB as a mold for a “gummy finger”
Authentication: Tokens (“What you have”)
Authentication Tokens
• General idea: Token and server share a key
• User does not need to remember any password
• One-time passcode: password theft is no longer an issue
• Can in principle be implemented in smartphones (using „trusted hardware“)
• Risk of loss
• Requires to carry the token • Relatively expensive
Adversarial model and security goal
• Adversarial model:
• One-time passcode tokens assume an eavesdropping / passive adversary
• Security goal:
• Assume that the adversary learns an arbitrarily long sequence of passcodes
P1, P2, … Pn.
• We want adversary not to be able to guess Pn+1.
• Ideally, adversary cannot do better than random guess at Pn+1.
Time-based token
• Prerequisite: Alice and the server share secret key K • Synchronization is done implicitly by the clock T
PT (e.g., 707410)
PT = F(K,T)
PT = F(K,T)
Counter-based token
• Prerequisite: Alice and the server share secret key K
• Synchronization is explicit by counter C
• Token and server increment counter after each authentication
PC (e.g., 707410)
PC = F(K,C)
PC = F(K,C)
What is the function F ?
• Some (simplified) variants used in practice:
• F(K,C) = H(C || K)
• Old RSA SecurID used proprietary hash: Alleged SecurID Hash Function (ASHF)
– 64-bit key of 10% of tokens recoverable with two months of passcodes
– Biryukov, A., Lano, J., & Preneel, B. (2004, January). Cryptanalysis of the alleged SecurID hash function. In Selected Areas in Cryptography (pp. 130-144).
• F(K,C) = AESK(C)
• RSA SecurID today (simplified)
• F(K,T) = HMAC(T,K)
• In OATH standard, RFC 6238 Time-Based One-Time Password Algorithm
• Google Authenticator
Truncation
• Output needs to be truncated for passcode display
• E.g., PC = F(K,C) = H(C || K) mod 1,000,000 (for 6 digits)
– OATH approach
• Let P’C denote untruncated passcode
• We’ll come back to this…
What happens if Alice pushes the button but does not authenticate?
• The counter C is no longer in sync
• Server increases C after successful authentication only
PC (e.g., 707410)
PC = F(K,C)
PC-1 = F(K,C-1)
The Fix: Accept a Window of Passwords
• General idea: Server accepts range of tokens
• Compute window of s+1 valid counters (n, n+1, …, n+s)
• Solves desynchronization unless Alice skips more than s generated passwords • Increases chances that attacker guesses correct password
• Thus, optionally, expect sequence of multiple correct passwords from C
PC = F(K,C)
PC = F(K,C1) PC = F(K,C2) …
PC = F(K,Ck)
Two-Factor Authentication
Two-Factor Authentication (2FA)
• 2FA combines two factors to increase authentication strength
• Motivation: Attackers might compromise one authentication factor
• Typically: Prove What you know and What you have
• 2FA examples in practice
Personal Identification Number (PIN)
• PIN adds a security layer to tokens • Token: “something-you-have”
• PIN: “something-you-know”
• But how do you securely transmit the PIN? • PIN is just like a password
• Sniffing reveals the PIN
• Bad example:
PC (e.g., 435678) | PIN (1234)
Problem: PIN transmission
• Consider a 6-digit token with keyed-in 4 digit PIN
• Is there some way to build a token that displays a 6-digit one-time
passcode QC such that:
• QC can be checked by the server;
• PIN can be verified by the server;
• PIN is not revealed to eavesdropper Eve?
• Remember without PIN:
• P’C = H(C || K) (untruncated)
• PC = H(C || K) mod X (truncated)
Naïve idea (insecure)
• How about QC = H(PC | PIN) (truncated to 6 digits)?
• The hashed value PC | PIN is 6 + 4 = 10 digits long • 1010 = 10,000,000,000 possible values for PC | PIN
• Small search space—equivalent to ∼33-bit key
• Such a QC can be cracked and PIN extracted in less than an hour
Secure PIN Transmission Alternatives
• Idea 1: Check the PIN on the token.
• If PIN wrong, do not emit passcode (or emit incorrect data)
• Idea 2: Include counter into hash • QC = H(K || C || PIN)
• Alternatively QC = H(P’C || PIN)
• Idea 3: Digit-wise addition • QC = PC + PIN
• A form of encryption of the PIN under the passcode
Lunchtime attack
• You leave your token on your desk during lunch.
• Mallory steals into your office, opens your token, and extracts key
• Mallory fixes your token so you do not notice the attack.
• Mallory uses your passcodes and impersonates you…
• Countermeasure
• Tamper-resistance (e.g., delete key if tampering detected)
• Tamper-detection (covert channel in passcode to alert server)
• Many other sophisticated attacks, e.g., based on differential power analysis to measure key-dependent operations and leak key
• Password storing
• Storing passwords in plain, encrypted or hashed form allows offline attacks • Use salt and stretch (maybe pepper) password to store it securely
• Do not use passwords as keys, but derive stronger keys from them
• Biometrics authentication works, but is not bullet-proof either
• Two-factor authentication, and esp. tokens, improve security • Passwords cannot be easily leaked
• Per-service generation of strong passwords
Further Reading
• Boyd/Mathuria: Protocols for Authentication and Key Establishment • Password-Based Protocols (Chapter 7 up to 7.2.1, plus 7.2.3)
• Menezes et al.: Handbook of Applied Cryptography • Passwords (Chapter 10.2 up to 10.2.4)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com