1
$\begingroup$

What is the minimum number of unique pairs of digests and inputs to a one-time pass needed to verify that a secret is equal to a given s where the output is an integer with of at most digits base-10 digits.

My back-of-a-napkin calculation is the ceiling of:

log(cardinality(s)) ÷ log10(digits)

For example, in the case where the secret is a 64 bit integer (264 cardinality) and the number of base-10 digits is 6 (106 cardinality), then ceiling(64/6) = 11 pairs of unique inputs that result in the same known digests indicates that the secrets are equal.

Similarly, if s is from the ASCII set and a maximum length of 100 characters then the cardinality would be 127100 and there are 6 base-10 digits then the number of digest/input pairs needed to verify equality of secrets be ~ 127100 / 106 (i.e. "hard")?

I might be way off in my calculations here, but I was just curious.


Edit: Here is my rationale for the napkin calculation.

With every successive input that equals a digest we can reduce the space of the secret accordingly. The question is whether the space decreases linearly, exponentially, polynomially, or otherwise.

Where the cardinality of both the secret and output are the same, then we can verify that we have the secret with one pair of input and output.

If the cardinality of the secret is an iota larger than the output, we need two pairs.

If the cardinality of the secret is double the cardinality of the output, we still need two pairs.

If the cardinality of the secret is double plus an iota, we need three pairs.

And so on.

It would seem to be provable inductively.

In other words, there is an homomorphism from each pair of (input, digest) that maps to a space the size of the output cardinality on the secret space. Each pair therefore reduces the secret space by the size of the homomorphism (i.e. the cardinality of the output).

So the calculation to be answered is how many times the cardinality must be reduced in order to cover the entire secret space, and my thinking is: cardinality(s) / 10digits?

This is just a brute-force method; there are ways to reduce the space by examining the hash algorithm (which in the case linked above, for Google Authenticator, is SHA1 – with known weaknesses).


EDIT Upon consideration the cardinality of the secret is at most the cardinality of the resultant hash, which for the OTP linked example is SHA1 and known to be reducible to around 261.

Thus the napkin-based complexity, if correct, would be log2(2^60) ÷ log10(6) ~= 10.167.

The answer then to the specific example of the OTP linked (the one used by Google Authenticator and others) is: One will need eleven inputs and digests to confirm that one has the secret-as-hashed.

$\endgroup$
5
  • $\begingroup$ To be honest, I don’t get some of your “digits”. When you write 64 bit integer (2^{64} cardinality) and the digits is 10, do you mean $10$ binary digits (which would mean 10 bits) or $10$ in decimal notation (which would merely take 4 bits to represent)? Same question for your 127^{100} and the digits of length 10… $10$ what? Individual elements of the set, $10$ as a numeric representation of an ASCII character (which would be 0x0A in hexadecimal notation), or $10$ as an integer string (which translates to 0x31 and 0x30 in hexadecimal notation in the ASCII table), or is that 10 bits? $\endgroup$
    – e-sushi
    Sep 3 '14 at 13:04
  • $\begingroup$ Sorry for any confusion @e-sushi. The digits is base-10 digits, as it is the human-legible component of the OTP to be provided to and entered by the user. You can see this from the linked (or any canonical) OTP code, but I will clarify the question in any case. Please let me know if it remains unclear or there are other potential improvements you see. $\endgroup$ Sep 3 '14 at 13:47
  • $\begingroup$ I would also note that the digits need not strictly be base-10 integers, but that is one conventionally accepted practice for HCI/UX reasons. A more generic OTP napkin calculation would be ceiling(cardinality(s) / cardinality(o)) where o is the output. It just so happens that by the above convention the o is 6 base-10 digits, so there are a million permutations (cardinality) of output. I hope that clarifies. $\endgroup$ Sep 3 '14 at 13:52
  • $\begingroup$ I forgot to add the appropriate log too. I left my napkin at home. :) $\endgroup$ Sep 3 '14 at 14:06
  • $\begingroup$ Then suddenly… things start to make sense. ;) Thanks for the comments and edit, that really helps. $\color{gray}{^{(+1)}}$ $\endgroup$
    – e-sushi
    Sep 3 '14 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.