The question's method can works, but
- Usually a heavy constraint in Time-based One-Time Passwords is reducing the size of the authenticator, to limit keypresses by users. Having to send a salt is antagonist to that.
- The risk of false rejection due to nonce duplication within the same time period must be mitigated, either by a largish nonce, or some deterministic nonce generation (see 4).
- Use of a Bloom filter is complex. The risk of false rejection by a Bloom filter collision must be kept negligible, which requires a largish Bloom filter. In practice, for heavy use, we'll need to reset the Bloom filter at some point, so we need at least two for continuous operation.
- We can solve 2 and 3 by replacing the salt by a counter, reset at each change of
rounded_timestamp. That allows the receiver to replace the Bloom filter with a bitmap (we still need one for each currently valid
rounded_timestamp). And we can compress the counter/nonce by not transmitting leading bits/digits/bytes when these are zero, mitigating 1.
- The risk of false rejection due to hash collision exists, especially for smallish hash. It's not fully mitigated by entering the nonce in the input of the Bloom filter's input, or by 4: with hash-based TOTP, there's the risk that the same authenticator value can be generated for several
rounded_timestamp, including consecutive, causing false rejection and/or potentially misidentification of the time drift.
I suggest an encryption-based TOTP:
- We select a time unit such that there will be no need for two authenticators within this time unit. Time t is expressed in that unit.
- Allowed time drift is within an interval of width d time units.
- The authentication tag is k-bit, with k ≥ log2(d)+14 (larger k are possible and improve security, that's advisable if bandwidth is not a major issue).
- The side preparing the authenticator does:
- v ← t mod 2k-1
- u ← t//2k-5 (there's a 4-bit overlap of u and v)
- b ← u//2k-6 (b is the high-order bit of u)
- derive a time-dependent key K' from the shared secret K and u
- encrypt v with K' and a (k-1)-bit block cipher, leading to bitstring c or k-1 bits
- encrypt b || c with K and a k-bit block cipher, leading to the authenticator a.
- The receiving end does:
- decrypt a with K yielding b and c
- from t' at the receiving end, and b, deduce the only u that could have been used by the receiver:
- derive K' from K and u
- decrypt c yielding v
- t ← (u//24)⋅2k-1+v
- check t'-t is within an appropriate interval of d values, perhaps (-d/2+Δ,d/2+Δ], where Δ is some (optional) expected delay.
Advantages of this encryption-based TOTP:
- No guesswork on the receiver side even with wide time drift.
- The authenticator a never repeats within time interval 2k-5, much wider than d (removing the risk of false rejection in 5 above).
- Receiver can refuse out-of-order authenticators and refuse replay of the last authenticator, merely by keeping the last authenticated t.
- Alternatively, receiver can accept out-of-order authenticators and still resist replay by keeping the highest t that was accepted and a single short bitmap of recent already used t.
- Time drift can be accounted for to adjust acceptance interval and reduce probability of false acceptance.
- Near-optimal security for a given k: Residual probability of false authentication for a random a is d/2k. A better attack strategy (like not repeating an earlier authenticator) can increase that probability by at most a factor of 32/31 (less than 0.05 bit of security loss) up to 2k-5 examples. With unlimited examples (or/and if we remove the k-bit block cipher), the probability can increase by at most a factor 32/15 (less than 1.1 bit of security loss) as long as there is no wraparound of t (a factor of two is gained after learning the 2k-1 possible values of a for a given b; and then a factor of at most 16/15 can be gained by exploiting that the same key is reused for the (k-1)-bit block cipher).
The two block ciphers can be built using standard techniques for Format-Preserving Encryption.
If the desirable time unit varies depending on circumstance, it's possible to have short authenticator with a coarser time unit, and a larger one with finer time unit, using keys derived according to size of authenticator. It's also possible to use a short authenticator for the first in a time period, then increasingly wider authenticator for the others (as in 4 above to mitigate 1).
Whatever technical novelty there may be in this post is hereby placed in the public domain by the author.