6

I'm building an high velocity auth system, used both for user to machine and machine to machine authentication and authorization. To prevent a replay attack I'm adding a nonce to each request, but in order to avoid a roundtrip the nonce is generated by the client using a one time password mechanism:

  1. Negotiate secret between client and server at the beginning of the session
  2. Generate nonce as hash(rounded_timestamp, secret)
  3. Use nonce in request signing

Anyhow this doesn't completely prevent replay attacks, as there is a tolerance in the clock precision. Using an HOTP mechanism seems unfeasible as it would require expensive coordination in a distributed system.

My idea would be to add a salt to the TOTP which would be unique for each nonce:

  1. Negotiate secret between client and server at the beginning of the session
  2. Generate nonce as hash(rounded_timestamp, salt + secret)
  3. Use the tuple (nonce,salt) in request signing

The server could then use a very efficient bloom filter to verify the absence of replay attacks.

Does it make sense? Why can't I find references to the use of cryptographic salt in TOTP generation?

3
  • 1
    Nonce is a value that can only be used once. How are you going to implement the check on the server side that this nonce was not used yet? If you are going to use some storage (short time cache or long time storage), then time stamp is superfluous. If you are going to use timestamp, then adding further salt does not change anything.
    – mentallurg
    Commented Apr 15, 2023 at 20:56
  • 1
    Obviously the result would be more secure in a cryptographic sense, but because I have the feeling that the problem is more with system specific restrictions & communication overhead I'll move it to Information Security. Commented Apr 15, 2023 at 20:57
  • I didn't think too hard or long about this: but why not replace the timestamp with an increasing counter? Then the server can refuse any counter value it's seen before.
    – marcelm
    Commented Apr 16, 2023 at 11:44

1 Answer 1

7

The question's method can works, but

  1. 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.
  2. 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).
  3. 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.
  4. 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.
  5. 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:
      • u ← t'//2k-5

      • if u//2k-6 ≠ b then

        • if b=0 then u ← u+1 else u ← u-1

        Note: it's advisable to perform the above adjustments of u in constant time

    • 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.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .