Timelessness

Timelessnessless?

© 2025. All rights reserved.

Analysis: are HOTP-based one-time passwords zero-knowledge proofs?

Thu, Oct 2, 2025 ❝Analyzing the characteristics of HOTP-based one-time passwords and the requirements for zero-knowledge proofs.❞
Contents

I found surprisingly little information on this topic. Even just searching for the terms “HOTP” and “zero-knowledge proof” resulted in very few entries. So I decided to evaluate this for myself. If it turns out bad or redundant, at least I spent some time investigating an interesting topic and learning why I was wrong. If it turns out to have some truth to it, it would be an interesting find. The post itself is likely more elaborate than strictly necessary due to also investigating Zero-Knowledge and related properties.

HOTP, or HMAC-based One-Time Passwords, are a mechanism for generating one-time passwords based on some previously shared secret key. The secret key itself is only shared initially between the two parties, to arrange for a common secret. At any moment, one-time passwords can be generated given some input by performing the HOTP computation with shared secret.

Intuitive understanding of zero-knowledge proofs

The idea of a zero-knowledge proof is to prove something without disclosing anything other than a true/false conclusion as a result of proper execution. There are two parties, prover and verifier. The prover (attempts to) convince the verifier that it knows some secret without disclosing said secret. Something is considered a zero-knowledge proof if the following properties hold:

  1. completeness if the statement is true, then an honest verifier (that is, one following the protocol properly) will be convinced of this fact by an honest prover.
  2. soundness if the statement is false, then no cheating prover can convince an honest verifier that it is true, except with some small probability.
  3. proof of knowledge verifier is ensured that prover knows a particular bit of knowledge.
  4. zero-knowledge if the statement is true, then no verifier learns anything other than the fact that the statement is true. In other words, just knowing the statement (not the secret) is sufficient to imagine a scenario showing that the prover knows the secret.

In addition, the following properties will be discussed as these also apply.

Analysis

assumption for this analysis we assume that HOTP itself is secure. The goal is to evaluate the properties of zero-knowledge proofs.

The algorithm:

HOTP(K,C) = Truncate(HMAC-SHA-1(K,C))

HMAC-SHA-1(K,C) = SHA1(K XOR opad, SHA1(K XOR ipad, C))

HOTP(K,C) produces a value [0, 1000000) in case of 6-digit results, the recommended minimum for HOTP. (specification, Appendix A.) HMAC-SHA-1, ipad and opad are defined in the RFC for HMAC.

The goal is to prove that both verifier and prover know the same (shared) secret, without disclosing the secret. HOTP generates one-time values from a secret K and a (varying) counter value C. The secret is considered an agreement between e.g. a service (verifier) and a user (prover). The fact that response values, i.e. one-time passwords, are exposed poses no risk to the secret.

Statement prover declares that they can produce a proof for secret belonging to account A, for some identifier A.

With the statement predeclaring (committing to) a specific secret, prover cannot cheat by selecting a suitable secret a posteriori.

note In many uses of HOTP, the statement is more or less fixed, assuming that a user typically only has one account for a service. This is not necessarily a problem. Whether by choice or lack thereof, the statement provides the necessary commitment all the same.

Inputs C into HOTP are usually described as sequential, i.e. monotonically increasing values. This is important for typical use cases in which two parties must stay reasonably in sync. (There is a sync-window to account for some drift.) Whether or not inputs are produced in sequence (or otherwise depend on state), is of no consequence for the purpose of zero-knowledge proof verification.

Zero-knowledge proofs are often defined with a binary challenge input. This is not the case here. The definition originally states (x,w) ∊ R, with challenge input x and witness w (i.e. response, instance-proof), such that (the type of) x can be defined relatively freely.

Our domain is any x satisfying conditions of C, with the exception of the specific usage instructions of sequential monotonically increasing generation as this is irrelevant, for input into HOTP(K,C) and w any output corresponding to some x.

w = HOTP(K, x)

K is a secret, referred to by the statement of prover, which is committing thus fixed for the proving-process.

Completeness

If the statement is true, then an honest verifier will be convinced of this fact by an honest prover.

Pr[⟨P, V⟩(1^λ, x) = 1] = 1

An honest prover that knows the secret will be able to generate the same value as an honest verifier. Verifier is convinced for this witness, i.e. this instance-proof, if prover submits the same value as verifier generates themselves. An honest prover works with the provided challenge value C and their own knowledge of the secret.

This is trivial if both share the same secret, as the algorithms themselves are public knowledge.

Soundness

If the statement is false, then no cheating prover can convince an honest verifier that it is true, except with some small probability.

Pr[⟨P*, V⟩(1^λ, x) = 1] ≤ 2^-λ

An honest prover cannot generate the same values without knowing the same secret. A prover can attempt to guess, making it a 1 in 1,000,000 guess for 6-digit results, i.e. very small probability.

Given knowledge of previous witnesses, it takes on the complexity of computing a pre-image or second pre-image (of an incomplete result) of keyed HMAC computations with secret value K. This is already known to be harder than computing a pre-image for its underlying primitive SHA-1, due to nested uses and distinct paddings.

Furthermore, given its computational nature, any value that successfully verifies is a (valid) witness. In case of 6-digit responses, it is the one expected value out of 1,000,000 for a challenge input (and committed-to secret).

Internal mechanisms of HOTP isolate secret K from response values, therefore a verification of a witness can be computationally exact, instead of merely a probability of uncovering failure / exposing deception. Consequently, the only probabilistic components are in brute-forcing, guessability and access to prior knowledge, which a verifier would need to take into consideration.

Proof of Knowledge

Definition: completeness + soundness.

Proof of Knowledge verifier is ensured that prover knows a particular bit of knowledge.

Both prover and verifier generate the same value assuming the same secret, or have great difficulty generating the expected value otherwise. Verifier, being in decision-making position, determines the secret that is authoritative, thus which response value is expected.

Verifier is expected to be efficient, bounded to polynomial-time verification.

The principle of the Extractor seems to hold only to some extent for HOTP. Even if a verifier acquires witnesses for every value of C allowed, they still do not have all information necessary to extract, i.e. directly acquire, secret knowledge K.

note I have not investigated possible weaknesses of HOTP or HMAC specifically, for this post. SHA-1 is no longer recommended, although HMAC mitigates weaknesses in the hash algorithm because of its nested uses of the hash algorithm, in this case SHA-1, and distinctly padded uses of K thus adding complexity.

Zero-Knowledge

(P,V) is (computationally) zero-knowledge if for every (probabilistic) polynomial-time V* there is an expected polynomial-time simulator S_V* such that:

Zero-knowledge prover is ensured that there is no risk in producing witnesses to convince verifier.

Intuition: Given the existence of a simulator that can produce a similar (computationally indistinguishable) transcript, it cannot be that secret information is used, as otherwise one would not be able to produce a simulator.

{⟨P(w), V*⟩(1^λ, x)} for (x,w)∊R  ≈  {S_V* (1^λ, x)} for (x,w)∊R

That is, (the transcript of) the interaction of the prover with any verifier can be simulated.

Security considerations of HOTP include a security evaluation that the 31 bits truncated SHA-1 hash may be considered uniformly distributed. Consequently, also the 6-digit result. The slight bias originating from the modulo reduction is considered negligible accoring to the security considerations (HOTP specification, chapter 6), i.e. brute-forcing remains the best approach. By properties of HMAC and SHA-1 hash-function, it is infeasible to reverse the computation. Consequently, K is secure even when (non-truncated) results are exposed.

note There is a symmetric (knowledge) relationship between verifier and prover. Both could take either role and both know the (shared) secret. This is not strictly speaking an issue for zero-knowledge proofs, as roles are defined based on required properties for their role. Both sides satisfy requirements for both roles.

note Emphasis on any verifier, as verifier in possession of the secret would be able to inadvertently use/disclose secret information, therefore successfully produce a transcript this way. However, any verifier if they have access to a secret, will not necessarily have access to the same secret. They can still produce a transcript with any other arbitrary value.

Both prover and verifier generate the same value given the same secret. Prover cannot know if verifier has malicious intent. Given properties of HOTP, response values do not reveal anything about the secret or their relationship to the input (challenge). Only when corresponding secret is known (as well as challenge input), can a response be verified, i.e. only then does a response value have meaning. Hence, prover can produce many responses without revealing information to a malicious (unknowing) verifier, or any observing third-parties.

Perfect Zero-Knowledge refers to the special case in which a simulator offers a distribution of values equal to the view of prover-verifier interaction and witness verification. HOTP and underlying mechanisms are public knowledge and results differ only because of varying inputs K and C. Anyone can trivially create the same probability distribution for a simulator by picking any arbitrary K.

In addition to the core principle of zero-knowledge, the following additional properties hold: computational indistinguishability and equal probability distribution.

Additional properties

Considering the following characteristics of HOTP, we benefit from two additional properties. The following characteristics are relevant:

Computational indistinguishability holds given that both simulator and real interaction work with the same computations and the same logic. The only difference is input K. Computational steps are effectively the same. Consequently, the only way to distinguish between computations, is to observe minute variations in computation that occur with different input values. And even these can be virtually eliminated with constant-time implementation.

note Under the assumption of constant-time implementations, to my knowledge, the best you can do is observe minute power fluctuations to try and discern different inputs, which is far outside of the scope of this analysis.

Equal probability distribution holds given that there is effectively no difference between a computation with “right” and with “wrong” secret, it is possible to produce exactly the same class of results, with the only exception being that resulting values are different due to different input K. Any simulator (presumably producing “wrong” results) and a true interaction (producing “right” results) are effectively no different, except for input K. Consequently, this also results in an equal distribution of probabilities.

Zero-Knowledge Proof (of Knowledge)

If the statement is true, then no verifier learns anything other than the fact that the statement is true.

Verifier is authority on deciding the correct (shared) secret. Prover either knows the same secret or does not.

Zero-knowledge proof of knowledge: Proof of Knowledge + Zero-Knowledge.

note As remarked at the start of this post, prover and verifier essentially work with a true/false result. Verifier and prover both know secret K, therefore the 6-digit response value itself is not revealed knowledge. The only knowledge revealed by prover to verifier interaction, is whether the result is equal to expectation, i.e. true or false. Although actual values are exposed to the world, those values are meaningless without K. With counter C being 64 bits large, the challenge values used during the proving-process can be considered one-time use “throw-away” values.

note Implicit assumption that there is no benefit for prover to intentionally produce (another) arbitrary value if they know the secret. Prover has a vested interest in proving their possession of the knowledge.

Knowledge Extractor

A (rewindable) knowledge extractor can be used to extract the witnesses that prove access to “the solution”, in which the solution is the secret known to verifier and supposedly to prover.

With each challenge there is a different response that serves as a witness to prove knowledge. Theoretically, when all challenges are evaluated and all witnesses obtained, you would have obtained the knowledge. However, given the use of one-way functions in HOTP, we do not yet have direct access to the secret itself. Instead, you have acquired merely a complete derivative representation of the knowledge, for the purpose of HOTP-based authentication. Furthermore, considering that the 6-digit codes are derivations of a MAC-value, there is no direct path towards the secret.

If one would have access to all challenges and responses, one could effectively, reliably gain access to a service which uses HOTP (to prove authorization through knowledge of the secret), even though one merely has access to a (special-purpose) lookup-table instead of the secret itself.

Third-party observers

Given the symmetric nature of HOTP, both verifier and prover know the secret. However, this secret is never exposed. During the procedure, a commitment is declared, then only two values are exposed: a challenge and a response. Only participants in possession of the secret are able to determine whether challenge and response correspond. Others obtain two values without having sufficient knowledge to compute response from challenge, thus are unable to verify for themselves.

Responses are deliberately seemingly arbitrary values. Challenges may be sequential, though not necessary for this particular purpose, but this does not affect responses in any useful way, as per requirements for HOTP.

Conclusion

In my understanding, HOTP (and by extension TOTP, also known for their use as “authenticators”, which build upon HTOP by using a time-component for the counter-value) should be considered zero-knowledge proofs. I mention several differences with typical zero-knowledge proofs, although definitions seem to allow for these differences. In my current understanding, HOTP satisfies all the necessary requirements.

note I have not previously looked as deeply into zero-knowledge proofs. If it turns out I missed something in this analysis or was otherwise too optimistic, I will update the post accordingly.

References

Along the way I also found various lecture notes, although Jonathan Katz’s introduction covered the basics quite nicely for the purpose of this analysis.

Changelog

This article will receive updates, if necessary.