Current schemes to protect user passwords like bcrypt, scrypt, and iterative hashing are insufficient to resist attacks when password digests are stolen. We present a modern cloud service, called Pythia, which protects passwords using a cryptographically keyed pseudorandom function (PRF). Unlike existing schemes like HMAC, Pythia permits key updates as a response to compromises. Key updates nullify stolen password digests, enable digests to be updated to the new key, and don't require users to change their passwords. The keystone of is a new cryptographic construction called a partially-oblivious PRF that provides these new features.