Rapidly changing passwords?

Question

Suppose you need to authenticate yourself to a program with the password - but the program's source code is public, the program doesn't have access to any private information and all your communications with the program are public. The only privacy you have is the information that you have but don't send.

No fixed password could work because the first time you used it, everyone would know it, and all subsequent runs of the program would be compromised. One partial solution would be to have a different password every second. But naive password generation wouldn't work, since both the source code of the program and any information it has access to are known.

Is there a (secure) way for the program to quickly generate password hashes, so that a trusted user with the right information could quickly generate passwords matching those hashes? This would be difficult to attack iff it is hard to predict the next password given the next hash and all the previous passwords. It is easy to make it so that nobody can come up with passwords (just randomly generate hashes), but making it actually possible for one person to generate passwords (quickly) given a little secret information seems much harder to me.

Answer 1

This is a case for public-key cryptography (in the form of digital signatures, or a key exchange algorithm).

In the simplest case, the program (Alice) would know (embedded in the source or in a configuration file) a public key, and the user (Bob) would have the corresponding private key.

Bob would then send the message which should be authenticated, and sign it using the private key. The program (as well as anyone who has the public key) can then verify that the message really came from you.

This authenticated message should include a timestamp and/or nonce, and the program should make sure not to accept the same timestamp/nonce twice (this will prevent a replay attack).

If you want something where the user actually uses a password, have a look at the secure remote password protocol (SRP). In this case, the server stores a password verifyer instead of the password itself, and the exchanged messages are a Diffie-Hellman-like key exchange, which don't give any clue about the password. You also get a shared secret between Bob and Alice, though I'm not sure how secure this is against man-in-the-middle attacks when Alice can't be authenticated due to missing secret.