2
$\begingroup$

Is my protocol correct?

For fun, I tried to design a protocol that would allow off-the-record communication. I'm not sure it works, I have a feeling there might be a problem with it that I'm not seeing. Please tell me whether you see a problem with it.

Here's a dramatization of the protocol I'm imagining:

Alice wants to send a message to Bob such that Bob would know it was sent by Alice, but couldn't prove it to Dan.

Alice creates a disposable persona Charlie (an RSA keypair) and talks to Bob using Charlie.

Charlie: "Hello Bob! I wish to send you a message that you'll know is from Alice, but couldn't prove to anyone else!"

Bob: "Okay, here's a string X, it's the public key out of an RSA keypair I just randomly created, which I know for a fact you didn't tamper with."

Charlie: "Cool, I got X, but I'm not including it in this message. Here's Z, a random string I just came up with, which I know for a fact that you didn't tamper with."

Bob: "Cool, here's Y, which you can verify is the private key of X. Now let's take (Y xor Z) to be our W, which is a number we both know is random, but that none of us can prove to outside parties that it's not random. We're not sending W over the line because we both know what it is."

Charlie: "Here's the message M I want to prove to you is sent by Alice. I'm sending you (SHA1(M) xor W) signed by Alice's private RSA key."

From Bob's prespective, everything's legit. He knows that no one could know what the number W was before he revealed the private key Y. Thanks to RSA, he knows that Alice made the message (SHA1(M) xor W), meaning that Alice intended to send the message M.

But if Bob were to show these messages to Dan, he couldn't be sure that Alice indeed sent M; perhaps Bob is trying to cheat him? Perhaps Bob composed message M himself, with no connection to Alice, and built the Charlie persona himself just to make it look like Alice sent the message? Let's see how Bob could have done that.

Maybe Bob obtained, in some way, an arbitrary string F signed by Alice's keypair from a past communication with her. He calculated (SHA1(M) xor F) and called it W, so now he can say he has Alice's digital signature on (SHA1(M) xor W), which is just (SHA1(M) xor (SHA1(M) xor F)) which is just F. He created the random keypair X and Y, and calculated Z, which is (Y xor W), which makes W be (Z xor Y). Then he created the disposable Charlie persona and constructed the entire fictional thread of conversation between them which includes all these numbers.

Bob knows he didn't do all of that, but Dan can't be sure, and thus our objective is reached.

Are there any problems in this protocol that I didn't think of?

|improve this question|||||
$\endgroup$
  • $\begingroup$ Whether or not (Y xor Z) "is random" depends critically on what exactly you consider RSA private keys to be. $\:\:$ In any case, why are you suggesting RSA for that part rather than a commitment? $\hspace{1.47 in}$ $\endgroup$ – user991 Dec 25 '13 at 19:41
  • 2
    $\begingroup$ @RickyDemer: Good point. $\hspace{400px}$ But honestly, what's the deal with $\hspace{300px}$ the random $\hspace{240px}$ MathJax spaces, anyway? $\hspace{200px}$ $\hspace{200px}$ You know it doesn't really look the same $\hspace{100px}$ to anyone who doesn't have the exact same browser and fonts as you $\hspace{250px}$ anyway, right? $\endgroup$ – Ilmari Karonen Dec 25 '13 at 19:53
  • $\begingroup$ The deal was imagining that the SE software worked somewhat sensibly, even though, as far as I know, it doesn't have any other way to put line-breaks in comments. $\endgroup$ – user991 Dec 25 '13 at 19:57
  • 1
    $\begingroup$ Alice wants to send a message to Bob such that Bob would know it was sent by Alice, but couldn't prove it to Dan. That sounds a bit like a zero-knowledge proof $\endgroup$ – rath Dec 25 '13 at 21:05
  • $\begingroup$ @RickyDemer Different browsers and operating systems render text differently which leads to line breaks at different points. For example I'm using Opera, and all of your answers/comments contain large spaces in inappropriate places. Html is a dynamic format where you can't control the output precisely, unlike say PDF. $\endgroup$ – CodesInChaos Dec 25 '13 at 22:37
1
$\begingroup$

Both Ram's and Ilmari's protocols allow forgery.


(The "other party" is either Charlie or Alice, depending on
whether Ram's or Ilmari's protocol is being attacked.)

Mallory receives either "Alice" or $m_{real}$, and sends to Bob either "Alice" or $m_{fake}$, respectively.
Mallory receives from Bob either an RSA public key or
a hash, and sends the same thing to the other party.
Mallory receives a random string the other party, and
sends $\:$ that_string $\oplus \hspace{.02 in}H(m_{fake}) \oplus H(m_{real}) \;$ to Bob.
Mallory forwards the next two messages (without changing them).


(Incidentally, I came up with that attack when I was formalizing the content-deniability proof.)

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Gotcha. So what if, instead of building W as (Y xor Z), we'll build W as H(y+z)? Would that solve the problem and make the algorithm secure? $\endgroup$ – Ram Rachum Dec 26 '13 at 10:04
  • $\begingroup$ @RamRachum: No, because that would lose the deniability property we wanted in the first place: for a given $W' = W \oplus SHA(m) \oplus SHA(m')$, finding $Y'$ and $Z'$ such that $W' = H(Y' + Z')$ (for any meaning of $+$) would require breaking the preimage resistance of $H$. $\endgroup$ – Ilmari Karonen Dec 27 '13 at 14:18
  • $\begingroup$ Right, I stand corrected. $\endgroup$ – Ram Rachum Dec 28 '13 at 11:34

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.