Talk:Diffie–Hellman key exchange

Template:CryptographyReader

Rename this article from "Diffie-Hellman key exchange" to "Diffie-Hellman-Merkle Key Agreement", place redirect

Per https://en.wikipedia.org/wiki/Talk:Diffie%E2%80%93Hellman_key_exchange/Archive_1#key_exchange_-.3E_key_agreement.3F , this system is more a key-agreement protocol than an arbitrary-key-exchange protocol. I propose renaming this article to 'agreement' and leaving a redirect.

As well, the 2002 quote by Diffie cited on the page itself says that he (at least) calls it Diffie-Hellman-Merkle. I think that this would be a good thing to rename the article itself to as well. Instead of doing two steps (rename to Agreement, rename to Diffie-Hellman-Merkle), it might be easier done as one step.

Aerowolf (talk) 18:50, 12 February 2014 (UTC)

Renaming the article would not be a good idea in my opinion. Diffie may call it Diffie-Hellman-Merkle, and would hide the article from those interested in reading it. As far as I know, Wikipedia is supposed to reflect the real world, not influence it. If the protocol is reffered to as Diffie-Hellman key exchange by the people that study Cryptography, then the article should remain named that way. Dottn (talk) 18:38, 4 May 2014 (UTC)

Misleading information?

This is the sentence that seems to suggest that Diffie-Hellman is not vulnerable to MITM:

The Diffie–Hellman key exchange method allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure communications channel.

Either the article shoud define "insecure communications channel" as a **signed** communication channel, which -- to me -- doesn't make much sense, or it should be removed/rephrased.

Moebius eye (talk) 20:38, 6 June 2014 (UTC)

The general idea does hold, sort of, and signing is not required. The only security property that is needed from the channel is that the protocol message in at least one direction reach the other mostly unmodified. That is to say, any party that can be assured that one of the two messages reached the other side without substitution (but not necessarily error-free) has the assurance that the resultant key is either junk or confidentially shared between only the two parties. This can also be reinterpreted that on any channel, the key will be shared with the communicating party (whether this is an attacker interposing themselves or some intended party). But in a sense I agree: it might make sense to note in the article that the comparatively mild security property of assured nonsubstitution is required of the channel if a MITM attack is to be thwarted. —Quondum 22:58, 4 April 2015 (UTC)

DH is not vulnerable to MITM per se

the Diffie–Hellman exchange by itself does not provide authentication of the communicating parties and is thus vulnerable to a man-in-the-middle attack.

Given that Diffie–Hellman key exchange is anonymous, the example of a MITM attack between Alice, Bob and Mallory doesn't make sense, because Alice doesn't know who she is talking to!

g^b mod p when searching for a?

Shouldn't

"even the fastest modern computers cannot find a given only g, p, g^b mod p and g^a mod p"

read

"even the fastest modern computers cannot find a given only g, p and g^a mod p" ?

Holding no information concerning a, g^b mod p isn't of any help for finding a - or is it? --FePo2 (talk) 11:25, 27 March 2015 (UTC)

It’s true $a$ doesn’t depend in any way on $b$ or $g^{b}$, but the claim as currently written is stronger than the one you are suggesting substituting it with (namely, it assumes the attacker knows more quantities and still can’t win), and still true, so I would prefer it be left as is. Hawk777 (talk) 05:40, 30 March 2015 (UTC)

The text is indeed a bit confusing. It mixes the discrete logarithm problem and the Diffie-Hellman problem. 2A02:120B:2C4F:7900:DFF:1343:2858:ECA0 (talk) 19:41, 4 April 2015 (UTC)

DH is not public-key cryptography

"Public-key cryptography, also known as asymmetric cryptography, is a class of cryptographic algorithms which requires two separate keys, one of which is secret (or private) and one of which is public."

I acknowledge that some people falsely classify it as such but it is missing two essential details. First, it is not crypto, as it does not involve encrypting data at all. It is an agreement protocol where two parties agree on a secret. Second, it does not use "two separate keys" where one is secret and one is public. I edited the page to clarify that and User;Quondom reverted. I edited the page again to note the fact that some people (at least User:Quondom if no one else) believe it is public-key crypto and this was promptly reverted by an anonymous user.

There are no citations for the belief that DH is public-key crypto and even my CN tags were removed. I am restoring just the CN tag since the fact that there is no citation for a claim in an article is not a matter of opinion. Note that there is a citation on that paragraph but it backs up my version of this page, not the reverted version.

Note that if this tag is removed, that will constitute a violation of WP:3RR. --- Vroo (talk) 20:12, 4 April 2015 (UTC)

Take a breath, and realize that we'll only get somewhere if we approach this in a spirit of cooperation. I'll just make a few (hopefully relatively neutral, non-reactive) comments:

• Your perception of what constitutes a cryptographic algorithm is too narrow. The terms "cryptography" and "encryption" are by no means synonymous. You will see in the first few sentences of Cryptography that addresses security properties in addition to confidentiality, which is the defining property of encryption.
• Public-key cryptography says: "Some public key algorithms provide key distribution and secrecy (e.g., Diffie–Hellman key exchange), some provide digital signatures (e.g., Digital Signature Algorithm), and some provide both (e.g., RSA)." Your edit comment "DH is not public-key cryptography reading definition there; it does not use public & private key" seems to ignore this, and it does use what is called a public and private key for each party (see further down in the article), albeit ephemeral ones.
• The Diffie–Hellman key exchange protocol is considered to be a public-key protocol, and the algorithms used in it have all the defining features of a public-key algorithm.
• Also note the distinction between a protocol and an algorithm. D–H is the former, not the latter, though this is a side issue.
• Talking about the issue on this talk page is the right approach; user talk pages not so much when it is discussing article content and edits.

—Quondum 21:07, 4 April 2015 (UTC)

Just tried to add similar comments. Despite the fact that there are many references, here is a concrete citation: "Handbook of Applied Cryptography", by A. Menezes, P. van Oorschot, and S. Vanstone, Chapter 1, page 1: "The most striking development in the history of cryptography came in 1976 when Diffie and Hellman published New Directions in Cryptography. This paper introduced the revolutionary concept of public-key cryptography... " 2A02:120B:2C4F:7900:DFF:1343:2858:ECA0 (talk) 21:16, 4 April 2015 (UTC)

I too was a bit confused about whether it is public-key cryptography or not, but this stackexchange answer seems to shed some light. Tony Tan⁹⁸ · talk 23:23, 4 April 2015 (UTC)

Perhaps the choice of names is part of what causes confusion. The terms public-key cryptography and asymmetric cryptography are synonyms, and the latter is possibly the better one to avoid confusion, though the former is more widely used. It is essentially distinguished from symmetric cryptography by the use of two (or more) blobs of information ("keys") by two (or more) parties in a protocol, one or more of which cannot feasibly be derived from the other(s). This separation of a "key" into two "keys" in this way is the core feature. D–H exploits this property, and thus fits the category. The discussion you link here makes reference to the subsequent symmetric use of the agreed key, but this is not part of the D–H key agreement, and might confuse things a little. —Quondum 00:08, 5 April 2015 (UTC)

Incidentally, that link ends with the statement "This is an asymmetric encryption scheme – to encrypt, the sender needs to know only g^x, while for decryption x itself is needed" is incorrect. D–H is not an encryption scheme at all, and no extension to an encryption scheme (e.g. as described using a symmetric algorithm) fits this description. —Quondum 00:15, 5 April 2015 (UTC)

The Menezes, van Oorschot, Vanstone quote doesn't say the DH algorithm is public-key crypto but that the paper introduced public-key crypto (I'm not sure that's accurate given the earlier Merkle work, but that's a different issue). There's a difference between introducing the concept and making that concept practical. Consider: clearly, Merkle introduced the concept of secure key agreement over an insecure channel but the proposed algorithm was impractical. DH introduced a practical solution to key agreement.

The Public-key cryptography page says "The distinguishing technique used in public-key cryptography is the use of asymmetric key algorithms, where the key used to encrypt a message is not the same as the key used to decrypt it." This is the common interpretation. But then take a look at the illustration on that page regarding DH (this is much less informative than the paint illustration on the DH page). It describes DH as having public and private keys. The so-called keys (intermediate values) in the DH algorithm are not used to encrypt or decrypt messages. In fact, there is no way to use the DH algorithm to communicate information at all. The result of the algorithm is agreement on a shared secret but neither party has any way to influence the value of the secret in a way that would allow communication (otherwise, the algorithm would be fundamentally flawed). A dictionary definition of cryptography is "the process of writing or reading secret messages".

Yes, it is a cryptographic algorithm in the sense that it is used in cryptography bit it's not cryptography by itself. Similarly, a cryptographic random number generator is not cryptography but it is cryptographic.

P.S. Regarding "take a breath" it is frustrating to make a simple edit to a page and have it immediately reverted by you and then having my next change immediately reverted by an anonymous user. Frankly, I'm tired of editors protecting pages from anyone else editing them by reverting changes they disagree with. Your comments here seem that you are willing to edit this page to address this issue. I don't know if the anonymous user will concur. --- Vroo (talk) 06:30, 5 April 2015 (UTC)

Not sure what you haven't understood. In the article the private keys are a and b. The public keys are g^a mod p and g^b mod p. Possibly the article doesn't state this clearly enough. Anyway, another reference that clearly states that the Diffie-Hellman protocol is a public key protocol is the paper "New Directions in Cryptography" itself. Diffie and Hellman define in section III, "Public key cryptography" what a public key cryptosystem and what a public key distribution system is and then introduce DH as an example. If the term "public key cryptography" was narrowed since the publication of this paper, then surely it should be possible to give a citation for this. 2A02:120B:2C4F:7900:2C92:4337:230B:F9F8 (talk) 14:33, 5 April 2015 (UTC)

To reply to a few points by Vroo above:

• The quote from the Public-key cryptography page makes an incorrect statement, and should be fixed. It describes public-key encryption, a particular instance of public-key cryptography.
• Forget the dictionary definition. Because confidentiality has historically been the first (and until comparatively recently, the only) application, and even today texts use this as an introductory example of cryptography, a misconception exists that this is the extent of the field. The second paragraph of the lead of Cryptography speaks of this change. Rather consider a more notable source than a dictionary, and remember that dictionaries are sometimes slow to track changes. Here is a quote from Menenzes et al:

  Definition Cryptography is the study of mathematical techniques related to aspects of information security such as confidentiality, data integrity, entity authentication, and data origin authentication.

• D–H key agreement is a technique for providing confidentiality – of the agreed result – but is not encryption because that result is not explicitly chosen by either party. It can be used as a building block in a larger protocol for encryption. In particular, it seems to fit the description of the techniques in Menenzes's definition (and incidentally, that list is not exhaustive). By your criterion (that no encryption or decryption occurs), you would presumably argue for exclusion of digital signatures, message authentication and many of the other facets regarded to be part of cryptography.
• And finally, with reference to your frustration, it is easy to understand it; we've all experienced the same, I'm sure, as it is natural in collaborative efforts such as WP. Yet, we are not here to frustrate each other, but rather to work towards a shared goal, and learning to manage your own frustration is essential. It might help to review WP:EQ and WP:ACM#Taking it too seriously.

—Quondum 16:54, 5 April 2015 (UTC)

A nice quote from Menendes et al: "A concise and elegant way to describe cryptography was given by Rivest [1054]: Cryptography is about communication in the presence of adversaries." —Quondum 17:03, 5 April 2015 (UTC)

I agree with Vroo that no communication is possible by DH alone, and that it is merely a way for exchanging keys. But the question is: Is DH public-key cryptography, or not? It can only be used to exchange symmetric keys, and cannot be used to encrypt/decrypt data. Why is it considered public-key cryptography? The only case it is used in public-key crypto is when it is combined with RSA (such as DHE-RSA used in TLS) so that one party can verify the identity of the other party and prevent MITM attacks. Tony Tan⁹⁸ · talk 17:18, 5 April 2015 (UTC)

Interestingly, Diffie–Hellman_key_exchange#Public_key states that DH actually can be used to encrypt/decrypt messages. We may have been wrong. Tony Tan⁹⁸ · talk 17:22, 5 April 2015 (UTC)

You too seem to be confusing the meaning of "cryptography". It includes many techniques that have nothing to do with encryption, for example digital signatures. It would help if you read the points being made.

The example you refer to that presents D–H being used for encryption is misleading. Here, D–H is still only used for key agreement; the only difference is that instead of an ephemeral key, Alice uses her static identity key. —Quondum 17:59, 5 April 2015 (UTC)

Quondum: I agree that cryptography is more than just encryption. But you seem to be confused on what the word public means in public-key crypto. Suppose Alice and Bob use DH to agree on a secret key. Then they proceed to use that secret key to encrypt their communication. They do this by XORing the key into the contents of their messages. Admittedly the XOR cipher isn't a very good one, but I choose it because no one would ever claim it is an instance of public-key encryption. Yet you claim this system constitutes public-key cryptography because each party has some secrets not known to the other. But in fact, the DH algorithm doesn't depend on a and b remaining private. It only requires that they be temporarily secret from the other party and that they be permanently secret from adversaries. Conversely, what you call public keys in DH must be shared with the other party and must not be shared with an adversary. If an adversary acquires both parties' public keys, then the game is over. In true PK crypto, the private keys must remain private and the public keys can be shared with anyone, even adversaries.

For comparison, consider the following algorithm for generating a new shared secret between two parties that already have a shared key (k1). We want to generate a new key that neither party can choose unilaterally yet is in no way dependent on our existing key. Here's the algorithm: Alice generates two secret values a1 and a2. She encrypts a1 using a2 as the key. Sending E_a1(k1, now, a2) to Bob. Likewise, Bob generates b1 and b2 and sends E_b1(k1, now, b2) to Alice. Once Alice receives this from Bob, she sends Bob back a1, and Bob likewise sends Alice b1. Each can decrypt, verify that the first part of the encrypted data is the old shared key, the time value is sufficiently recent that this is not a replay and derive a2 and b2 respectively. They then generate k2 = a2 XOR b2. Is this also public-key crypto? It relies on the fact that a1 and b1 are initially private (just as a and b in DH) but they must be exposed for the algorithm to work.

(Yes, I glossed over details here, like requirements on the encryption algorithm and size of k, a1, a2, b1, b2 that make it infeasible for Alice to generate a post-hoc a1 value in order to choose a particular value of a2 after decrypting b1. I'm sure you can fill in the blanks.) --- Vroo (talk) 01:34, 16 April 2015 (UTC)

To repeat what I said above:

Perhaps the choice of names is part of what causes confusion. The terms public-key cryptography and asymmetric cryptography are synonyms, and the latter is possibly the better one to avoid confusion, though the former is more widely used.

The fact that the term "public" is used in one version of the term should not mislead you; your arguments here seem intrinsically linked to an inappropriate interpretation of the meaning of the phrase based on the words. What elements of the system are or become public or private has little to do with the meaning. Your statement "Yet you claim this system constitutes public-key cryptography because each party has some secrets not known to the other" confuses me: I do not see such a claim by me. And now, please consider WP:TALK#USE – I think that this has gone far beyond discussing corrections to the content of the article, and has veered into a debate of your beliefs about the meaning of how the terminology is (or perhaps should be) applied. I'd suggest that you familiarize yourself with appropriate texts on the subject in a way that allows you to substantiate or modify these beliefs for encyclopaedic use before changing the interpretation in the article. —Quondum 03:50, 16 April 2015 (UTC)

justification for (g^a mod p)^b mod p = (g^a)^b mod p)

The equality:

 (g^a mod p)^b mod p = (g^a)^b mod p) 

was given on the page, but no justification was given. I've googled many places, but found no justification.

It was repeated here:

http://security.stackexchange.com/questions/45963/diffie-hellman-key-exchange-in-plain-english

but that also failed to provide justification.

The, maybe closest, to a justification was here:

   http://math.stackexchange.com/questions/360248/does-ga-mod-pb-equiv-gab-mod-p-hold-true

but that just gave a hint on how to derive the equality, but not a strong enough hint for me.

Could someone please provide a link to a justification of provide a justification?

TIA.

Cppljevans (talk) 18:32, 5 May 2015 (UTC)

I don’t have a citable source for it, but it’s a well-known property of modular arithmetic that addition and multiplication commute with modulus-taking. Given that multiplication commutes, it’s pretty easy to convince yourself that exponentiation commutes too: $((A\mod M)\times (B\mod M))\mod M=(A\times B)\mod M$, therefore $((A\mod M)\times (A\mod M))=A^{2}\mod M$, so $(A\mod M)^{2}\mod M=A^{2}\mod M$, and then you can carry that forward to other exponents. You might find some more information, or even citable sources, on this page. Hawk777 (talk) 05:01, 6 May 2015 (UTC)

Hawk777 (talk) 05:01, 6 May 2015 (UTC)

Thanks very much Hawk777. To be more specific, the

following table shows the correspondence between your:

$((A\mod M)\times (A\mod M))=A^{2}\mod M$

and my:

(g^a mod p)^b mod p = (g^a)^b mod p)

Correspondence table:

Cppljevans	Hawk777
g^a	A
p	M
b	2
(g^a)^b	$A^{2}$

Cppljevans (talk) 19:03, 6 May 2015 (UTC)

Yes, that is roughly what I was thinking of. Obviously it’s not a full proof since $b\not =2$, but it was a rough sketch of some of the pieces of the puzzle. I’m not a mathematician so it would take me far more time than I have available to turn this into anything formal. Hawk777 (talk) 04:48, 9 May 2015 (UTC)