Identification Protocols
the login problem
SYK: Something You Know
Passswords, PINs, and security questions
SYH: Something You Have
Hardware or software tokens, cetificates, email, SMS, and phone calls
SYA: Something You Are
Fingerprints, facial recognition, Iris scans and handprint scans
Location
Source IP ranges and geolocation
Attacks
ordered from weakest to strongest
Direct attacks
Suppose that adversary cannnot eavesdrop on the conversation.
A prover and a verifier are in close physical proximity.
using no information other than what is publicly available
Simple password is sufficient.
Eavesdropping attacks
the adversary passively eavesdrop messages as a observer
An adversary can eavesdrop on the conversation.
one-time passwords is secure.
Active attacks
the adversary actively impersonates a legitimate verifier
The adversary uses the interaction to try and learn something that will let it later impersonate the prover to the verifier.
Comparisons
Secret vs Public verification keys
Protocols where vk can be public are preferable since no damage is caused if the verifier is compromised.
Stateless vs stateful protocols
Protocols where vk and sk are fixed forever are called stateless, wheares ones where those are updated are called stateful.
stateful protocols provide higher levels of security at lower cost. However, stateful protocols can be harder to use because the prover and verifier must remain properly synchronized.
One-sided vs mutual identification
MiTM attack
ID protocols, however, are not sufficient for establishing a secure session between a client and a server.
The adversary uses client to authenticate to the server and then hijacks the session to send his own messages.
To defeat MiTM attacks, one can combine an identification protocol with a session key exchange protocol.
Interactive protocols
The configuration size of a running protocol instance and round complexity of a protocol is poly-bounded.
the config data can be encoded as a bit string whose length is always bounded by some fixed polunomial.
Definition of ID protocol
a triple $ I = (G, P, V)
$ I: an interactive protocol algorithm, which is an efficient probabilistic algorithm.
$ G: a probabilistic ket generation algorithm
$ P:an interactive protocol algorithm called the prover.
$ V: an intective protocol algorithm called the verifier.
Password protocols
$ sk := pw
This protocol should only be used if the adversary cannnot envesdrop on the interaction between prover and verifier.
$ vk := pw
a compromise of the verifier will expose all passwords stored at the verifier in the clear.
should use a slow hash to pw
Security against direct attacks game
key generation phase:
the challenger gen vk and sk from G alg, and sends vk to adversary
Impersonation attempt:
adversary playing the role of a prober but not necessarily following the prover's alg.
Online dictionary attacks
the attacker can sort $ D by popularity and try the most popular paswords first and then one after the other.
One who attempts for a specic user ID or from a specific IP address many times is denied access.
Attackers, however, can try a single common password across many different usernames.
Password Spraying attacks
should be recognized if the accessing user is a bot or not.
reCAPTURE
Offline dictionary attacks
If an attacker can get a list of hased paswords by compromising a loing server, he can try computing hashes value.
with preprocessing
In preprocessing phase, an attacker can prepare tons of hashes of password and just look up the obtained hased value. It's only taking constant time.
batch offline dictionary attacks
rainbow tables
a type of precomputed table
a time-space tradeoff
traded a smaller table for incrased attack time
the table size is reduced from O(n) to O(n^{2/3}), however the time to attack is increased from O(1) to O(n^{2/3}).
for SHA1 of size 460GB is designed to find preimages in the set of all 8-char passwords and takes about an hour.
リスト型攻撃
入手したID/Passwordを他のサービスへ利用
salt
public salt
included in the hash computation and the password file when registering a new password.
makes the preprocessing approach no longer feasible.
secret salt
small salt space is included in the hash, but not included in the password file.
a typical choice for the secret salt space is {0, 1}^12.
slows down password verification on the server by a factor of 4096.
PBKDF2
as a slow hash function
often implemented using HMAC-SHA256 as the underlying PRF.
vulnerable to parallel harware attacks
in the case of d = 10,000, 500 chips will run through all 2^52 eight character passwords in less than a day.
bitwarden
default difficulty is set to 10,001
bcrypt:
a threat model with offline cracking.
自動ログインではMD5を使用
scrypt
a sound memory-hard password hashing functions
vulnerable to a a side-channel attack.
if the adversary also has the memory access pattern of process P as it was computing the Scrypt hash of pw, then the adversary can mount a dictionary attack on pw with very little memory.
litecoin
winner of PHC'15
data-oblivious memory-hard functions
KeePass, Signal
Common password problem
Despite all the precautions taken at the high-security server, the security of that server can be compromised by the poor security of some completely unrelated, low-security server.
"client-side salt" as a solution.
Biometrics
Users tend to forget their passwords.
not generally secret
iirevocable
should not be used as the only means of identifying users.
One time passwords protocols
MFA
Eavesdropping attack game
Key generation phase
Eavesdropping phase
Impersonation attempt
weakly secure againt eavesdropping attacks
vk and sk must be kept secret
stateful protocol
eacedrop: obtain a transcript
impersonate
HOTP
incrementable counter
6 digit value as a security token
needed minimize the number of digit
needed explicit syncing the counter.
only updated when the user initiates the protocol.
TOTP
key-recovery attack within very small time window.
the counter i is incremented by one every 30 seconds implicitly.
Within the 2c + 1 clock-skew window, the server prevents replay attacks by rejecting passowords that have been used before.
Google Authenticator
https://gyazo.com/85af550736206fe3ce6d273a0f50938b
F(sk, counter)はonetimeでバレても良いのでeavesdroppingに耐えられる
kは攻撃者にバレない前提
eavesdroppingできたとしても
リストを用意しておけない
30sごとに一方向性関数を解かなければならない
iが30sごとに変わる
UNIX time
H = HMAC-SHA-1(K, T)
K: 80bits
T: 64bits
S/key protocol
t needs to be at least 128 bits to ensure that $ H is one-way.
at least 22 characters as a one-time password
Google authenticator
Challenge-response protocols
Instead of simply observing the messages, he will actively alter messages, dropping some, duplicating others, or inserting messages of its own.
スミッシング
An attacker impersonate a verifier and interact with the prover, and send the prover arbitrary messages of its choice.
The adversary's goal is to gain information about the prover's key.
攻撃者はサーバーになりますましクライアントとやり取りを行い、最終的にHonestなサーバーの検証関数が通るようにトライする
If a challenge is intercepted by an adversary and send an invalid challenge to a client, S_mac(key, challenge) will be diffirent, so the mac verification returns false.
攻撃者はChallengeがわからないのでS_mac(key, challenge)の正しい値を作ることができない
challengeをinterceptできていてもkeyが分からない
Challenge mus be randommness to prevent a replay attack.
あらかじめクライアントから予期したchallengeに対するレスポンスを取得しておきそれを利用
phishing attacks
クライアントのRPIDもサーバー検証時に検証
In active probing phase, an attacker can attack concurrently, not just sequential attack model.
require vk to be secret for a weakly secure model.
the key is chosen at random from the key space of the underlying MAC system.
using hash of password
replacing the MAC with a signature scheme to be public vk:
ssh, FIDO, EMV, kerberos(KCRAP), SASL(SCRAM) the length of challenge and response are longer.
FIDO using secuirty key such as yubico, google titan key or TEE with android, iphones https://gyazo.com/b1ff602492434f4f7eb95f2544f78caf
https://gyazo.com/731d611ddbac8648bc57cfecdbebae06
~appendix~
Attacks
Reflection attack
Bob can send a valid response to alice without knowing K by communication with Charlie who has a valid K.
1: Alice > Bob: n
2: Bob > Charlie: n <-- reflection attack
3: Charlie > Bob: E(K, n) <-- bob receives the correct response to Alice's challenge
4: Bob > Alice: E(K, n) <-- and authenticates himself to Alice
Replay attack
a challenge generated by server prevents from replay attack, impersonating a legitimate client.
a token should be chosen by a random process (usually, pseudorandom processes are used). Otherwise Eve may be able to pose as Bob, presenting some predicted future token, and convince Alice to use that token in her transformation.
Eve can then replay her reply at a later time (when the previously predicted token is actually presented by Bob), and Bob will accept the authentication.
Relay attack
Pre-play attack
Notes
If one can find collisions in H, then the hash-then-MAC construction is completely broken.
HMAC: Two-key nest method
Refs: