Identification Protocols, Password Security, and One-Time Passwords

Corresponds to Chapter 18 (basic password-based authentication is introduced at a high level in access-control-and-authentication; this note covers the chapter’s full depth). Formalizes interactive identification protocols in general before specializing to passwords, where the dominant threat if a password database is ever stolen is an offline dictionary attack — trying every likely password against the stored hash — defended against by salting (public salts stop precomputed-table attacks; secret salts/“peppers” raise the bar further), and deliberately slow (and, better, memory-hard) hash functions that make each guess expensive even for an attacker with specialized hardware. One-time passwords (HOTP/TOTP, built from a PRF keyed by a counter or the time, and the older S/key hash-chain scheme) protect against an eavesdropper who observes one login, since each password is used only once. Challenge-response protocols go further, defending against an active attacker who can inject messages, not just eavesdrop. Rainbow tables (a time-memory tradeoff for inverting hashes at scale) and hardening password storage in practice round out the note.

Outline (TODO — flesh out each)

• Interactive protocols — general notions
• ID protocols — definitions
• Password protocols — security against direct (dictionary) attacks
• Making dictionary attacks harder — public/secret salts
• Slow hash functions; slow memory-hard hash functions
• One-time passwords — HOTP, TOTP, the S/key system
• Challenge-response protocols — security against active attacks
• Fun application: rainbow tables
• Fun application: hardening password storage