Is this new server API authentication protocol secure?

Question

I need a secure protocol to authenticate client side users with my server which has an API. I am devising something more secure particularly to resist active MITM attacks where an attacker may modify the request and perform some damaging function on the server. The general username/password model doesn't suit my purpose if it can be intercepted and the data modified in transit potentially by state sponsored adversaries.

I'm not sure if this is the right place to post it, maybe security.stackexchange is a better fit, but here goes. Please recommend any changes or improvements. A "+" indicates concatenation.

Design goals:

• Authenticate all API requests to the server to verify they are from the legitimate user.
• Authenticate all API responses from the server to verify the response came from the legitimate server not an attacker.
• Don't allow one user to spoof another user's requests to the server.
• Avert passive MITM attacks where an attacker tries to snoop the API credentials in transit.
• Avert active MITM attacks where an attacker attempts to send fake responses to the server or from the server.
• Avert replay attacks or rejecting a request/response if the MAC does not match.
• Allow each user to create a private key on the server. Only certain people can do this and this is the reason behind the user having knowledge of the server shared key.
• Each user to have a unique key on the server that no other user can use.

Assumptions:

• Server admin will own the server and potentially a user of the server as well.
• The server admin is a trustworthy person not interested in compromising/interfering with any of the other user's communications.
• Users of the server have an interest in keeping the shared key on the server a secret to protect their own communications so they won't give that key to anyone else.

Initial setup:

• A random 256 bit key ("shared key") is created and put in the source code on a server hosted on the local network, serving to wider internet.
• This shared key is given to each user of the server in person (not using a key exchange protocol or sent via insecure network). Most likely it is just a small group of users using the server.
• The shared key on its own can only be used to create accounts on the server.
• Client creates a 256 bit random nonce ("nonce").

• Client creates 256 bit private key ("private key") using the hash based message authentication code with input in format HMAC(key, message):

  private key = HMAC-SHA-256(shared key, nonce)

• User creates a username ("username") which is just a random string of characters or psuedonym to uniquely identify their account.

• User creates a message authentication code to:

  a) verify they are allowed to create a user account on the server, and

  b) to sign all the details sent to server to make sure nothing was modified.

  MAC = HMAC-256(shared key, username + nonce)

• Data sent to server to create account:

  username
nonce
MAC

• Server verifies user is allowed to create an account on the server and that all details weren't modified in transit by verifying the MAC:

  MAC = HMAC-256(shared key, username + nonce)

• Server will reject incorrect MACs or if that username is already taken.

• Server will check if the nonce is re-sent to reject replay attack.

• If verified, server recreates the user's private key on server end using same process:

  private key = HMAC-SHA-256(shared key, nonce)

• If verified, server stores details in database for user:

  username
private key

To verify an API request:

• User creates 256 bit per request nonce ("request nonce".
• User creates API request or group of variables to send to the server ("message packet"). This contains the variables that the server will process or store.
• Each request is sent with an API action "api action" to perform on the server. This prevents the attacker from changing what action to perform on the server with the same MAC.

• User signs packet using:

  MAC = HMAC-SHA-256(private key, nonce + sent timestamp + api action + username + message packet)

• Client sends to server:

  nonce
sent timestamp
api action
username
message packet
MAC

• Server receives the request, looks up the username and retrieves the private key for the user.

• Server verifies the request by:

  MAC = HMAC-SHA-256(private key, nonce + sent timestamp + api action + username + message packet)

• Server rejects invalid MACs, which will also mean any attempt to modify the nonce, timestamp, API action, message packet or MAC will fail.

• Server rejects messages received outside the UNIX timestamp range (5 seconds). The server and client are synchronized with UTC time.
• Server rejects duplicate messages/replay attacks received within same window (5 seconds) with same timestamp by storing the nonce temporarily.
• If the nonce is the same and same request is received twice, then the second one will be invalid. Sent nonces are kept on the server for 10 seconds and then discarded. A delay longer than this will obviously not be accepted due to the time delay.
• Failed requests are re-sent by the client using a different nonce, sent timestamp and MAC.

Server response:

• On any server responses (including error responses for failed requests), the server signs the response with the user's private key so that the user knows the response is valid from the server.

  nonce
sent timestamp
message packet
MAC = HMAC-SHA-256(private key, nonce + timestamp + message packet)

• If MAC does not match on the client then the response is not actually from the server and will be discarded. A warning will be shown to the user that interference has occurred.

• Client will retain sent response nonces for 10 seconds to detect resent responses from attacker.

Answer 1

We consider a server $S$ and a bunch of users $U_1, \dots, U_n$.

What you want:

Users should be able to send queries to the server and receive replies. The users should be able to register identities with the server.

• Any reply $m'$ that a user accepts as coming from the server in response to a query $m$ from that user, really came from the server in response to a query $m$ by the user.
• Once an identity $id$ has been registered by a user $U$, any query that the server accepts as coming from $id$ came from $U$.

What you don't care about:

Confidentiality of queries and replies.

What you have to work with:

• The server $S$ and its users $U_1,\dots, U_n$ share a symmetric key $mk$.
• The server can store pairs $(id, k)$ securely, in the sense that nobody but $S$ can extract $k$ from the storage.
• There are no active insider attacks during registration.

What you don't want:

Any solution that uses TLS. TLS sucks.

Possible solution:

Let $MAC(key,msg)$ be a secure MAC. Let $G$ be a group suitable for Diffie-Hellman with generator $g$. We denote concatenation by $||$.

Registration protocol where $U$ registers the identity $id$: $$U \rightarrow S: id, g^x, MAC(mk, id || g^x) $$ $$S \rightarrow U: g^y, MAC(mk, 0 || id || g^x || g^y) $$ $$U \rightarrow S: MAC(mk, 1 || id || g^x || g^y) $$ After the server has accepted the second message (no record $(id, whatever)$ is known), it stores $(id, g^{xy})$ securely. After $U$ has accepted the third message, it remembers $(id, g^{xy})$. The values $x$ and $y$ are random numbers, chosen by $U$ and $S$, respectively.

Query-reply protocol where $U$ issues the query $m$ under the identity $id$ and the server replies with $m'$, and the user and the server both agree on $k$: $$U \rightarrow S: id, n_1, m$$ $$S \rightarrow U: n_2, MAC(k, 0 || id || n_1 || n_2 || m)$$ $$U \rightarrow S: MAC(k, 1 || id || n_1 || n_2 || m)$$ $$S \rightarrow U: m', MAC(k, 2 || id || n_1 || n_2 || m || m')$$ The server runs the query only after it has accepted the third message. The terms $n_1$ an $n_2$ are nonces.

Variations:

If you are willing to assume that there are no passive attacks during registration, you can replace the entire registration protocol by: $$U \rightarrow S: id, k$$ This seems too optimistic, however.

If you want to use time stamps, you can get by with a somewhat simpler query-response protocol: $$U(ts) \rightarrow S: id, n, m, MAC(k, 0||id||n||ts||m)$$ $$S \rightarrow U: m', MAC(k, 1||id||n||ts||m||m')$$ The term $n$ is a nonce and the term $ts$ is the time of $U$'s query. Here, $S$ needs to keep track of the nonces used by the users within the time stamp window. $S$ should probably also keep track of time stamps seen from each user, to be able to reject reordered messages.

If you have sequence numbers, you can use them as well: $$U(seq) \rightarrow S: id, m, MAC(k, 0||id||seq||m)$$ $$S \rightarrow U: m', MAC(k, 1||id||seq||m||m')$$ The term $seq$ is a sequence number that is strictly increasing. Now $S$ needs to keep track of the largest sequence number seen from an identity, to be able to reject reordered messages.

The sequence number solution has stronger security properties than the other solutions, but sequence numbers may not always be feasible.

Word of warning:

Don't expect this to be useful for any specific purpose without very careful thought. There are lot's of ways to mess up an application built on top of such a protocol.