I'm developing own protocol for secure message exchanging. Each message contains the following fields: HMAC, time, salt, and message itself. HMAC is computed over all other fields using known secret key.
Protocol should protect against reply attack. On large time interval "time" record protects against replay attack (both sides should have synchronized clocks). But for protection against replay attack on short time intervals (clocks are not too accurate) I'm planning replace "salt" field with counter increasing every time, when new message is send. Receiving party will throw away messages with counter value less or equal to the previous message counter.
What I'm doing wrong?
Initial counter value can be different (I can use party identifier as initial value), but it will be known to the attacker (party identifier transmitted in unencrypted form). (What is a good enough salt for a SaltedHash?)
But attacker can precompute rainbow tables for counter+1, counter+2, counter+3... if I will not use really random salt?