Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question

migrated from math.stackexchange.com Mar 29 '12 at 5:18

This question came from our site for people studying math at any level and professionals in related fields.

add comment

1 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.

share|improve this answer
    
Damn, you just beat me to it. +1 :-) –  Ilmari Karonen Mar 29 '12 at 10:04
    
@IlmariKaronen: Sorry, I started to type this about an hour earlier, and then forgot to finish my answer and submit it immediately. Then you wouldn't have to start typing yours. –  Paŭlo Ebermann Mar 29 '12 at 11:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.