Talk:Three-pass protocol

Definition of Three-pass protocol

In cryptography a three pass protocol can generally be any protocol where the parties involved exchange three messages. Currently the following definition is given:

In cryptography the Three-Pass Protocol is a framework which allows two parties to securely exchange messages without the need to exchange or distribute encryption keys.

This definition is too restrictive, as it claims that the Three-pass protocol refers to a specific class of protocols. In a Google book search I could find not a single source that defines the term Three-pass protocol as it is defined in this article. As a possible remedie, that would not require this article to be deleted, I propose to add a short definition of Three-pass protocol that reflect the current use in the literature, and to append the current article in one large section titled A three-pass protocol based on commutative ciphers. 85.2.50.189 (talk) 09:13, 13 December 2007 (UTC)

I understand the problem. We could coin a term Three-pass message protocol that would be specific to this particular method of exchanging messages. However, I have never seen the term Three-pass message protocol in the literature, and I have certainly never seen the term A three-pass protocol based on commutative ciphers. There is little chance that anyone interested in this subject would search on either term. So these are not suitable titles for the article.

The problem is a general one. When I looked for the term period I found a plethora of articles in Wikipedia: historical period, orbital period, menstrual period, wave period, geological period, periodic table, and even hockey period.

We don't need to solve this problem ourselves because Wikipedia already has a mechanism. I could click any of the links under period to find the article I wanted, if one existed. What we need to do in this case is to find the term that a user of Wikipedia interested in this area of cryptography is most likely to use in a search. So far as I can tell, that term is three-pass protocol. The term was probably coined by Konheim before 1980, is used in several books, and appears on several websites.

The term is defined with the same meaning as I have used it in A Cryptographic Compendium by John J. G. Savard at http://www.quadibloc.com/crypto/pk0504.htm (However Savard mistakenly attributes Shamir's prime-modulus method to Massey and Omura, which is a widespread confusion that I am trying to remedy with this Wiki article.)

As far as your proposed remedy, I have already added a sentence in the first paragraph explaining that there are authentication schemes that are also called 3-pass algorithms. If you wish, you could create an article entitled "Three-pass authentication protocol" and perhaps a second one entitled "Three-pass protocol (authentication)" both of which redirect the reader to the existing Wiki article on Authentication. However I don't believe it is helpful to include any extensive material about authentication in this article.

Remember that the purpose of this article is to bring together the Shamir algorithm and the Massey-Omura algorithm because they both fall within the same three-pass protocol. This avoids having to explain the 3-pass concept twice. Contestcen (talk) 00:47, 14 December 2007 (UTC)

You need to learn the difference between the words the and a. Savard's artile clearly uses the name Shamir's three-pass protocol. It does NOT define the term The three-pass protocol. I did a Google book search and did not find a single book that even defines The three-pass protocol. The term is generally used just to describe a property rather than given a definition. Three pass protocols have not much in common other than they all exchange three messages.

Your definition of three-pass protocol is (besides being new) also inexact. E.g. Merkle's puzzles would satisfy the definition. Hence Shamir would not have been first. But Shamir's protocol is much more efficient and elegant and may in fact be the first protocol that exploits ciphers that commute.

Yes, the Massey-Omura cryptosystem is often misrepresented. But that does not mean we have to fix this mistake by introducing an even larger number of mistakes instead.

Btw, you are also wrong about the wikipedia disambiguation pages. They do not appear automatically, rather they have to be written like other pages too. Just check the edit history of an ambiguation page. 85.2.48.141 (talk) 09:25, 18 December 2007 (UTC)

I just happened upon a reference that uses both of the terms no-key protocol and three-pass protocol for the type of message exchange used here. Yoshito Kanamori, Seong-Moo Yoo, Mohammad Al-Shurman (2005) A quantum no-key protocol for secure data communication Proceedings of the 43rd annual ACM Southeast regional conference. 2: 92-93. They use QTPP for Quantum Three-Pass Protocol. Contestcen (talk) 08:34, 14 December 2007 (UTC)

Since quantum key-exchange and Massey-Omura do not have much in common this only shows that the term three-pass protocol is a property and not a name. By pointing out that their protocol is a three pass protocol the authors merely claim that their protocol is efficient. Other quantum key-exchange protocols use much more than three passes. 85.2.48.141 (talk) 09:25, 18 December 2007 (UTC)

Commutative encryption

Commutative encryption and commutative binary operations are not the same. Commutative encryption means that it does not matter in which order two encryptions are made, i.e. $E_{K_{1}}(E_{K_{2}}(m))=E_{K_{2}}(E_{K_{1}}(m)$ while claiming that an encrytion function is commutative would mean $E_{K}(m)=E_{m}(K)$. Some encryptions (e.g. the One-time pad) are both commutative encryptions and commutative binary operations. Hence the text should clearly reflect which concept is meant. This is especially improtant since the described protocol would be insecure if the encryption satisfies both types of commutativity. Personally I'd use commuting encryption in a paper, but unfortunately wikipedia goes with the most commonly used term and that is commutative encryption or commutative cipher. 85.2.48.141 (talk) 09:25, 18 December 2007 (UTC)

I said "commutative encryption" not "commutative binary function." You seem to be complaining about something I never said. Your term "commuting encryption" appears to be your own coinage and not a term in general use. You keep criticising me for doing that.

Using single-byte binary XOR for the one-time pad is merely the simplest version. In practice, quite complex block ciphers may be used, even AES. There is no inherent restriction in the one-time pad to encipher only one character at a time, nor to use only one key byte per message byte. It came out during the Rudolf Abel spy trial that the Russians were using TWO key characters per message character as far back as the 1940's (even before Claude Shannon's "Communications Theory of Secrecy Systems") and since there were no computers involved it is very unlikely they used XOR. It was probably a well-mixed tableau cipher, thus not commutative. Your claim that the one-time pad uses a commutative binary function is simply your belief. Contestcen (talk) 07:37, 19 December 2007 (UTC)

Security of the protocol

The following claim appears to be original research by Contescen:

When the encryption function satisfies the conditions just described, the three-pass protocol is secure against passive attacks in which an eavesdropper can read the messages transmitted between the parties.

Before making claims that the protocol is secure against passive attacks it would be necessary to define secure against passive attacks. E.g., is there an equivalent to semantic security for the protocol defined here? I can't find one. But even without a definition it appears that Shamir's three-pass protocol is not semantically secure, since it is always possible to distinguish messages with different Legendre symbols. 85.2.48.141 (talk) 09:42, 18 December 2007 (UTC)

Combined response

I must tell you that I am getting truly angry over your incessant opposition. Ideally this editing process should be a cooperative effort aimed at producing the clearest, most accurate article possible. Let's try to get back to that ideal.

Repeatedly inserting "citation needed", "may be original research" or worse, "dubious" tags after every point which you cannot find stated explicitly in the literature, is neither helpful nor constructive. That may have been acceptable when this article was new and starting to take shape, but now after 20 or more rounds of editing and refinement it is petty and petulant. If you have such concerns at this late stage, they should be expressed in the discussion, not in the body of the article out in the public eye.

More importantly, I do not see why I need to explain the same points over and over. It gets wearing. I don't like you putting words in my mouth, and complaining about things I never said or did. I don't like you doing the selfsame things that you upbraid me for doing.

You raise so many points I barely know where to start. I have covered most of these points already, but perhaps you need them explained again.

Let me begin with your paragraph on the Talk page, then move on to the article itself, and finally deal with your newest postings on the Discussion page.

You: your repeated edits and reverts based on belief rather than verifiable sources are becoming increasingly annoying.

I believe that YOU were the person who originally created the Security section and wrote that the security depends on the Discrete Logarithm problem. If that is doubtful, YOU are the one who needs to supply a citation. On the other hand, if it is accurate (as I believe) then it confirms that the protocol is secure, as I stated.

You: you should refer to source if you want to claim an attack against a cryptosystem (such as you did with Massey-Omura cryptosystem) or if you want to claim that a scheme is secure against a certain type of attack.

Same response as above.

You: In fact, your claims can shown to be incorrect.

If you have solved the Discrete Logarithm problem, then you should publish this result immediately. If you have something else in mind, explain.

You: Please stop removing requests for citations, just because you might think that certain facts are true.

If you look down at the bottom of the page you will see that I supplied the citations you requested. Weeks ago. They are Konheim, and 2 places in Menezes et al.

You: There are quite a few editors on wikipedia having a PhD, working on one or having similar education and could help out.

Don't be patronizing. I will gladly match my credentials against yours or theirs.

You: Finally, note that removing contested edits and marking such reverts as minor edits is considered to be rude.

Rude? You dare to call me rude? How about reinserting such tags after weeks of mutual review, refinement and revision. Now THAT is rude!

Do I need to remind you that before I created this Wiki page I ran the idea past you and you agreed to it? Or that I gave you more than a week for your comments before I took the page live?

That covers the Talk page. Let's move on to the article itself:

(1) Let me begin by reminding you, once again, what this article is about, and what it is supposed to cover. This article is intended to cover the two best-known 3-pass message algorithms, namely the Shamir algorithm and the Massey-Omura algorithm. It is not intended to cover ALL 3 pass algorithms in general, and specifically not intended to cover any 3-pass authentication algorithms. This point is clearly made in the first paragraph.

This is not an entry in some cryptographic dictionary. I am not defining the term "three pass protocol". I am describing two well-known historically important algorithms which are three-pass algorithms, both of which fit within the three-pass protocol. (The concept of "protocol" is much more general than the concept of "algorithm". This is discussed briefly in Menezes.) In the future I intend to add further three-pass algorithms that fit within the three-pass protocol.

(2) You object to the phrase "without the need to exchange or distribute encryption keys". You label it "original research". Fine, that's your opinion. Now look at the description of the protocol. No keys are exchanged or distributed. It's not "original research", it's part of the protocol. If you can point out where in the protocol keys are exchanged, then I will remove or revise that claim.

(3) You object to the claim "The sender and receiver exchange three encrypted messages". You claim that is "dubious". Okay, that's your belief. Let's look at the protocol again. The sender sends E(s,m). That is ONE encrypted message. The receiver sends back E(r,E(s,m)). That is TWO encrypted messages. The sender returns E(r,m). That makes THREE encrypted messages. Count 'em. One. Two. Three. Do you get a different count?

(4) Finally you object to the claim "When the encryption function satisfies the conditions just described, the three-pass protocol is secure against passive attacks in which an eavesdropper can read the messages transmitted between the parties" Let me first remind you that the condition in question is it is not feasible for an attacker to determine the message m from the three transmitted messages E(s,m), E(r,E(s,m)) and E(s,m). Now you say that even if the encryption function meets that condition it is still possible to read the message. Why don't you explain how?

That covers your posts in the article. Now on to your posts on this Discussion page itself.

Let's start with this: "Savard's artile clearly uses the name Shamir's three-pass protocol. It does NOT define the term The three-pass protocol." If the article described "Shamir's three-pronged pitchfork" that means there is such a thing as a three-pronged pitchfork. If the article described "Shamir's three-legged stool" that would mean there is such a thing as a three-legged stool. The article does not need to define the exact phrases "three-pronged pitchfork" or "three-legged stool" for those things to exist. Logical people will understand the existence of a "three-pronged pitchfork" from the existence of "Shamir's three-pronged pitchfork."

Next: "I did a Google book search and did not find a single book that even defines The three-pass protocol." A negative result doesn't prove anything. Either the corpus excludes that exact term, or you framed the search so it failed to find the references that were there. Or, perhaps you rejected any use of the term which was not a formal definition. (See my remarks above about three-pronged pitchforks.)

Again: "The term is generally used just to describe a property rather than given a definition." I have no idea what you mean.

Then: "Three pass protocols have not much in common other than they all exchange three messages." It looks like you finally got the concept. Now just erase all those "dubious" tags and let's get on with our lives.

You continue: "Your definition of three-pass protocol is (besides being new) also inexact." As I pointed out several posts ago, I did not coin the term "Three-pass protocol." I believe it was coined by Alan Konheim, and is used in his 1981 book. To my knowledge, it has been in general use ever since.

Further: "Yes, the Massey-Omura cryptosystem is often misrepresented. But that does not mean we have to fix this mistake by introducing an even larger number of mistakes instead." That's why there are discussion pages. If you find anything that you believe is wrong, explain it here. If I can, I will correct or at least improve it.

Next: "Btw, you are also wrong about the wikipedia disambiguation pages. They do not appear automatically, rather they have to be written like other pages too. Just check the edit history of an ambiguation page." I said that Wikipedia had a mechanism for disambiguation, but I never claimed the disambiguation pages are automatic.

You go on: "Since quantum key-exchange and Massey-Omura do not have much in common this only shows that the term three-pass protocol is a property and not a name. By pointing out that their protocol is a three pass protocol the authors merely claim that their protocol is efficient. Other quantum key-exchange protocols use much more than three passes." So far as I know, the article that I cited describes a quantum version of the three-pass protocol as I use the term. The authors were consciously using the three-pass protocol, with the advantage that the quantum realization is self-authenticating.

Even if I were wrong about their algorithm, they still use the phrase "three-pass protocol" which shows this term is in use among cryptographers. If they don't define it, that means they believe it is widely understood, and therefore does not need to be defined.

Following: You talk about the terms "commutative encryption" versus "commutative function." I have answered that in-place above, so I won't repeat my answer here.

Continuing: "Before making claims that the protocol is secure against passive attacks it would be necessary to define secure against passive attacks." I think anyone with good reading skills can understand the concept without a formal definition. However, two paragraphs earlier in the article I describe what is meant.

Same thread: "E.g., is there an equivalent to semantic security for the protocol defined here? I can't find one." Like I said, look back 2 paragraphs for a reasonable informal definition.

And on: "But even without a definition it appears that Shamir's three-pass protocol is not semantically secure, since it is always possible to distinguish messages with different Legendre symbols." Finally something concrete. Hooray!! I think what you mean is that the Legendre symbol can be evaluated to determine whether or not each of the 3 messages m^s, m^sr and m^r is a quadratic residue. The Legendre symbol will be 1 for all 3 messages if m is a quadratic residue, or if both r and s are even. So if all 3 messages have the Legendre symbol 1, then you know nothing about whether m is a quadratic residue. But if either s or r is odd, and if m is not a quadratic residue then either m^s or m^r or both will be -1. This will happen 3/8 of the time, so you have a 3/8 chance of discovering that m is not a quadratic residue, and no chance of learning the m is a quaradtic residue. That provides you with 1 bit of information about m, not nearly enough to make the Shamir algorithm insecure. Moreover, quadratic residues are distributed nearly randomly in the range 0..p-1, so you really don't know anything about the actual contents of the message.

Oh, just for chuckles, that is clearly ORIGINAL RESEARCH on your part, so even if you had found a real flaw in the Shamir algorithm, you couldn't put it on Wikipedia. Shame on you for criticising me (incorrectly) for putting orginal research into my article, and then trying to put in your own original research.

Contestcen (talk) 07:43, 20 December 2007 (UTC)

That's a lot of anger. But I'm only going to response to the security claims since that is an important issue. First, note that your reply to my comment about the semantic security of the Shamir three pass protocol is incorrect: you missed that r and s can never be even. Hence encrypting a quadratic nonresidue will result in a quadratic nonresidue and encrypting a quadratic residue will result in a quadratic residue. Hence my claim was correct. Furthermore, this isn't a new argument. The same argument is often used to show that RSA, ElGamal over some groups or Diffie-Hellman over some groups are not semantically secure. This does not mean that those cryptosystems are broken. It just means that certain precautions such as an appropriate padding are necessary when these schemes are used.

Back to the claim: It is only a necessary condition that the message is not computable from the three messages that were exchanged, but like my counterexample above shows not a sufficient condition. One example is usually enough to disprove a claim, but here is another example, which may be easier to understand. Assume that we have a commutative encryption, which encrypts k-bit messages and has the property that it is not feasible to find a message m given E(r,m), E(r,E(s,m)) and E(s,m). Now we construct another commutative encryption E' for 2k-bit messages simply as follows: The first k bits of the message are encrypted with E, and the other k bits are simply sent as plaintext. Given E'(r,m), E'(r,E'(s,m)) and E'(s,m) it is generally not possible to find m, because finding the first k bits would require to break E, which was assumed infeasible. However, an attacker can easily find the second k bits of the message, since these bits are sent in clear text. Thus E' certainly is not secure against passive attacks, but it satisfies your preconditions. I hope, that you will finally admit that your security claim is wrong. 85.1.101.232 (talk) 21:27, 23 December 2007 (UTC)

If my response was long, it's because you made so many claims, and I wanted to be thorough.

As far as Legendre symbols, all that you get is whether m is a quadratic residue or not. That's only 1 bit of information about m, and not a very useful bit, since quadratic residues are fairly randomly distributed among all of the residues. Legendre symbols still provide negligible information about m.

As far as your example of an E', my statements about E (which are essentially similar to what I find in the literature) are correct. The portion of the message which is sent in clear does not satisfy the security condition. If you want to make a more precise statement of the security condition which will cover mixed encryption methods, feel free. I think that will make the article harder to read, and would very likely be original research. Contestcen (talk) 02:36, 30 December 2007 (UTC)