Proposed unidirectional authentication scheme

I've been looking around for a way to authenticate a client to the server and deliver a message, but in a unidirectional fashion - that is, the client sends messages to the server, but the server cannot send anything to the client. I want to both deliver the message and also convince the server that the client does indeed know a PSK.

When two way communication is available, the trivial solution would be to use something like SRP, or to simply have the server generate a nonce and the client then uses the encrypted nonce as a verification tag for the message:

M = message
K = pre-shared key
N = <random> (nonce)

C --> S: <request nonce>
S --> C: N
C --> S: Enc(K, N | M)


As long as the nonce is indeed unique, the client will be able to prove to the server that it has possession of K.

However, in the case of a one-way client to server communication, having the client generate the nonce allows an eavesdropper to replay a previous message:

C --> S: N | Enc(K, N) | Enc(K, M)


Without the channel back from the server to the client, the server has to accept the client's choice of a nonce and therefore a passive attacker can choose a previously-sent message while an attacker that manages MitM can intercept messages and resend them at will.

Here is my proposal:

M = message
K = pre-shared key
N = <random> (nonce generated by the client)
R = time slice size (the length of time the nonce will be valid)
T = time-stamp / R

C --> S: N | Enc(K, N | T) | Enc(K, M)


The server can validate the signature by calculating Enc(K, N | T) from the clear-text N and its own time-stamp and comparing to the message from the client - possibly allowing the previous and next time slices in case of clock drift. Once confirmed, the server can safely Dec(K, M) to get the message.

This scheme is still vulnerable to an attacker replaying a message within the time window R, so the server has to maintain a cache of all nonces used within the time window, and ignore any message that starts with a nonce that has already been cached. The cache can be discarded when its time has expired.

I've spent a couple of hours turning this around in my mind, and so far other than the obvious need to have an accurate time source, I don't see an issue with this scheme. I'd appreciate it if someone could verify my design.

Edited: Thanks to a comment, I'll mention that an assumption I've made is that both client and server can get accurate time using, for example, NTP.

• The point of a nonce is that it's never reused. Why not have the server just verify that the nonce wasn't reused (for instance, by making it a counter and having the server keep track of the highest counter value seen in a valid message)? Aside from that, this is roughly how Kerberos does authenticators; one big negative is that you need fairly synced clocks (the standard way, incidentally, is to put the actual timestamp in the message directly and have the server check that the timestamp isn't too long ago). – cpast May 16 '15 at 2:18
• @cpast because: 1. I don't want the server to have to remember all used nonces for all times 2. A counter would have to be tracked by both the client and the server, and they could go out of sync without any facility to get them back into sync. Time is more-or-less universal, and both client and server could sync with time servers. I didn't mention that in my post, but both client and server are able to get accurate time, they're both on-line. I'll edit. – Arik Baratz May 16 '15 at 11:15