2
$\begingroup$

As far as I understand, OTP usually works on a superficial layer by having two parties both know of a key and then authenticate each other by sharing a hash of the key and some sort of counter (e.g. currentTime mod someNumber) with each other. In theory, this means both parties can verify each other, as both have the capabilty to generate a OTP and both have the the capability to verify the integrity OTP given to them.

I'm looking for an OTP scheme between two parties where both parties can verify the validity of an OTP, but only one party can generate it. To my understanding, this would not work with the logic described above. Does such a protocol already exist? If not, is such a system even mathematically realizable?

$\endgroup$
8
  • $\begingroup$ Welcome to Cryptography. The OTP key can be generated by the one party, however, the distribution must be performed physically. OTP is malleable i.e. one can modify the content on the way or it is due to a transmission error. Your main question is how to prevent this so that OPT messages have an integrity? $\endgroup$
    – kelalaka
    Jun 15 '20 at 12:32
  • 1
    $\begingroup$ @kelalaka: actually, you could have integrity guarantees with an OTP (by using a universal hash keyed by some bits from the OTP pad). However, I don't think that's what Nicolas is asking... $\endgroup$
    – poncho
    Jun 15 '20 at 12:35
  • $\begingroup$ @poncho yes, one can use the keystream to use in keyed hash functions. If OP asking one party generates then the problem is how it is distributed. $\endgroup$
    – kelalaka
    Jun 15 '20 at 14:06
  • $\begingroup$ Nicolas, where do you get this definition of OTP? The elements you describe are not all part of a basic OTP. $\endgroup$ Jun 16 '20 at 3:38
  • $\begingroup$ I think OP is talking about one time passwords, not one time pads. It was even tagged as such until @kelalaka removed the tag. Why did you do that? $\endgroup$
    – Maeher
    Jun 16 '20 at 10:17
1
$\begingroup$

I'm looking for an OTP scheme between two parties where both parties can verify the validity of an OTP, but only one party can generate it.

The obvious way to do this is for one party (Alice) to select the one-time password and send the hash of that password to the other party (Bob). Then, Bob can verify that Alice has the correct password (as Alice actually sends it), but Bob himself cannot generate it.

If Alice and Bob need to do this $n$ times based on the same exchanged key, then what Alice can do is select the base key, and hash that $n$ times, that is, compute $H^n(\text{base key}) = \underbrace {H(H(H(…H(\text{base key})))))}_{n \text{ times}}$, and send that to Bob. Then, to authenticate the first time, she would send $H^{n-1}(\text{base key})$, which Bob can verify with his copy of the base key (but could not compute beforehand). To authenticate the second time, she would send $H^{n-2}(\text{base key})$, and keep on doing this up to $n$ times.

$\endgroup$
6
  • $\begingroup$ This is a really cool solution, except that it requires Alice and Bob to know they will exchange a OTP n (or less) times. If Alice and Bob want to exchange a OTP an arbitrary amount of times, is there a solution different than setting n to a very large number? $\endgroup$ Jun 17 '20 at 13:15
  • $\begingroup$ @NicolasSchapeler: if we're constrained from increasing the size of the password too much, the only other thing that comes to mind it is use a tiny signature (e.g. BLS), and have the password be the signature of the next integer. $\endgroup$
    – poncho
    Jun 17 '20 at 13:37
  • $\begingroup$ Could you eleborate this solution a bit (if this goes beyond the scope of this question, I can open another question with that constraint and accept your answer here)? $\endgroup$ Jun 17 '20 at 14:01
  • $\begingroup$ @NicolasSchapeler: the idea was that the sender of the OTP creates a public signature key, and send that to the verifier. Then, when he needs to send an OTP, he would generate a signature, and send that, and the verifier would verifier it (using the public key). Of course, no one would call this a "one-time password solution", however if the goal is to minimize communication and to prevent the verifier from generating his own passwords (why that's a problem, I'm not sure), this is the obvious approach $\endgroup$
    – poncho
    Jun 17 '20 at 19:43
  • $\begingroup$ That makes sense to me, thank you for both those solutions @Poncho! $\endgroup$ Jun 17 '20 at 19:52

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.