1

I am wondering, why web sites do not use one-time passwords generated by hash chain. By that I mean that a client chooses a secret and after being salted, he applies some secure hash function F() on it n times (e.g. n=1000000) in a row.

F(salted secret,n)=F(F(F(...F(salted secret)...)))).

Client then sends the result and the name of the hash function to the server in a secure way.

Then, when he needs to authenticate himself against the server, he applies hash function n-1 times on a his secret in a row F(salted secret,n-1) and use this hash as a one time password for the log in process. The server authenticates the client only if F(F(salted secret, n-1)) == F(secret, n). Next time, the process repeats itself for n-2...

Manishearth
  • 8,237
  • 5
  • 34
  • 56
bobo
  • 43
  • 1
  • 4

4 Answers4

10

The method you describe is indeed a classic algorithm for one-time passwords, but it has some drawbacks:

  • It is good only for N passwords, where N must be chosen at initialization time.
  • The client must invoke the hash function R times, where R is the number of remaining passwords in the chain, i.e. initially R = N. This limits the size of N, otherwise the cost becomes unbearable for the client system.
  • The server must retain some state, which is either the last successful password, or a counter. The counter has the problem that the cost on the server becomes proportional to the number of used password: if the user has used 1000 passwords, then the server must invoke the hash function 1000 times to validate the next password. On the other hand, saving the last password works only if the last password is the complete hash output, not a derived subset -- which makes for very bulky one-time passwords, hard to type (think 20+ random characters...).

For one-time passwords, common practice is to use HOTP, which uses a counter on both sides (client and server) and a single HMAC invocation. It also relies on the underlying hash function being secure, but it does so in a much easier to use way, avoiding the problems described above.

Summary: the method you describe is not used because much better methods are known -- not that they are more secure, but they induce much lower overhead on the client, the server and the human user.

Community
  • 1
Thomas Pornin
  • 320,799
  • 57
  • 780
  • 949
2

What you're describing sounds vaguely similar in it's aims to the one-time password scheme, HOTP.

However, after many thousands of logins, my login attempt under your scheme consumes more CPU time than the first login I attempted. With HOTP, the time to attempt login is constant.

It is also the case with this scheme that I cannot protect the secret on the server side in the same way that I can with a password (i.e. by using a KDF), therefore, a server-side breach will grant access to all user's secrets immediately, allowing the attacker to impersonate all users with impunity.

Any attacker who conducts a man in the middle attack, and finds OTP value x_n can then also compute all future x_i such that i > n by simply using F on x_i

This is a major issue if the secret is likely to be used by multiple sites (e.g. if expensive hardware tokens are used, or the user has to remember the secret)

Tinned_Tuna
  • 1,018
  • 7
  • 12
  • Why would the server CPU time requirement increase? If the server starts out holding H[1,000,000] it will only need that value until it receives H[999,999]. Then when it receives H[999,998] it won't need H[999,999] anymore. Adding lg(N) storage to the client will reduce the client's CPU time per login to lg(N). – supercat Aug 22 '14 at 22:11
  • Also, HOTP requires a shared secret; the approach referred to by the OP does not. – supercat Aug 22 '14 at 22:12
1

Firstly, the system is complicated and brings up other issues: Does the user have to remember how many times he logged in? If not, who does? Not his browser, he should be able to log in from anywhere.

Secondly, any form of client side encryption in HTTP connections is useless. A man in the middle can easily modify the javascript, remove the hashing function, and get the plaintext password. Almost all MITM attacks have the capability to modify data (not just read it), so this is always an option.

In the end, if you want to make your login form more secure, just use HTTPS. Client side encryption doesn't add much security(if at all it adds any security) and isn't worth the other problems it brings in.

Community
  • 1
Manishearth
  • 8,237
  • 5
  • 34
  • 56
0

I was looking for an answer to the question "why Lamport's reverse hash chain are forgotten in favor of shared-secret schemes like TOTP".

It is clear people do not like keeping track of state, that's why time-based auth won.

But now memory and CPU cycles are cheaper than ever, so typical embedded hardware has enough to keep the reverse chain needed for its full physical life span.

It turns out, I am not the only one who was thinking about it! Everything I came up with was already proposed in the T/Key paper:

https://arxiv.org/pdf/1708.08424

schroeder
  • 123,438
  • 55
  • 284
  • 319
ArkanoiD
  • 11
  • 1