My computer security professor uses the following notation, where S denotes a server and A denoted Alice. Alice wants to authenticate herself to the server. The hash function is a hash chain where $h^n(x)$ denotes a hash function $h(h(h(..h_n(x)..)))$. $n$ is stored on the server.

Assignment:

The following authentication protocol makes use of the Lamport hash construction (sometimes simply called ‘hash chain’). The construction simply consists of repeat- edly applying a hash function to an input value. We write h n (x) to denote hashing x n times, e.g. h 3 (x) = h(h(h(x))). Each user chooses a password pw and hashes this n times. He/she then sends it to the server. Let us assume that initially, n = 10 000. The server then stores a tuple (user, n, Y = h n (pw)) for each user in a database. Users can now authenticate to the server using the following protocol: The server checks if h(X) = Y , then decrements n and sets Y := X. So, after a successful run of this protocol the server holds a new tuple (user, n − 1, Y = h n−1 (pw)).

$ A \longrightarrow S : \text{I want to authenticate} \\ S \longrightarrow A : n\\ A \longrightarrow S : X = h^{n-1}(\text{password}) $

So now the hash is calculated on the device Alice uses. I am a bit confused now, because I always would receive the user's plain-text password and then hash it and store it in a database instead of receiving the password from the user. Also, I don't think this is possible at all in a web application.

My question is whether or not this protocol is used, and if so how would it be implemented. Also, what is more secure, hashing on the user side or the server side?

  • Well, this more suits to security.stackexchange. also, the $h^n$ is stored on the server. Hint: if the server uses different $n$ for each user, the rainbow table will be completely impossible to build for this server. – kelalaka Nov 16 at 13:46
  • 2
    Related answer from SE Information Security. – AleksanderRas Nov 16 at 13:52
  • @AleksanderRas not exactly, The question missing, I think, here Alice send $h^{n-1}$ and the $h^n$ is calculated at the server. Otherwise there is no meaning of $h^{n-1}$ – kelalaka Nov 16 at 14:09
  • I altered the question with a more precise definition.. – Abdulahi Nov 16 at 14:14
  • 1
    @kelalaka If $h$ is unsalted then unique $n$ doesn't prevent pre-computation based attacks. – Future Security Nov 16 at 19:12
up vote 1 down vote accepted

I can imagine a protocol like this, where $n$ starts from a high value, and gets decremented by the server at each login attempt. Characteristically:

  • The system has a degree of resistance against passive eavesdropping, which is no more susceptible to password search than server-side iterated hash is should the hashed password leak. That's a significant security benefit (especially if the client implements a minimum on $n$, which at least prevents a Man-in-the-Middle to find the password without heavy search; beware however that it does not prevent the MitM from obtaining a hash allowing to log-in many times).
  • The server can verify the password with one hash (or $k+1$ hashes if there has been $k$ consecutive failed logins). The bulk of the password hashing work is on the client side, which is a benefit for the server.
  • As long as $n$ remains high, and salt is used (there's none in the question), leak of the password database is no worse than in a normal system with hash on the server.

I have never seen this used. Main problem is, there's no support in browsers, thus the code doing the hashing on the client side will be JavaScript (for acceptability by users/prescriber), thus

  • that code is at best authenticated using https, and then there is little security benefit compared to password in clear over https, which is the norm.
  • JavaScript is sizably less efficient than native (the difference used to be huge, and still is on many platforms/devices), and the number of iterations much be chosen low enough to be acceptable on the less efficient platform.

About the same issues have killed all attempts to use PAKE that I have seen.

Also, the question's system is not really immune against active attackers able to impersonate the server, which is a serious drawback compared to some other PAKE. And password search is still possible from passive eavesdropping, which other PAKE manage to avoid.

  • For the first point; If the password is spoofed it will not allow to use it even once more. Because, whenever Alice loged in, the server updated. – kelalaka Nov 16 at 15:05
  • @kelalaka: but an active attacker (MitM) can present $n-1000$ to the client, and obtain $h^{n-1001}(\text{password})$ that will allow $1000$ later logons to the server. – fgrieu Nov 16 at 15:09
  • of course that is why two way authentication is important. – kelalaka Nov 16 at 15:13
  • What if Eve impersonates S and sends a huge value for n, then the client-side will be stuck calculating hashes (in theory) – Abdulahi Nov 16 at 15:22

I would do it on the server for a couple of reasons:

  1. If you hash on the client either you must not salt the password (generally a bad idea) or the server must transmit the salt for that user to the client.
  2. If you hash on the client then you need some sort of additional "wait" on the server to thwart brute force attacks. When you hash on the server then the client is forced to wait, but if you hash on the client many clients running multiple threads can easily flood a server with authentication requests.
  • You should still rate limit for either client or server side. You do not want almost 100% of your CPU time going to hashing on a server meant to do other things. (And the electric bill will be lower.) – Future Security Nov 16 at 19:24

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.