Diffie-Hellman group key exchange

Asked

Viewed 445 times

1

How to make a key exchange Diffie Hellman with 10-20 people for example, has as?

cryptography

  • Apparently this is an open problem, but there are studies/proposals to carry out this extension [from 2 to N participants]. I cannot say anything about the soundness of these proposals, however...

  • P.S. That question on the Soen seems to suggest that the absence of such protocols is in part due to the little practical need for it - since Alice has established a secure channel of communication with Bob, and Bob another with Charlie, Bob can create a new secret (i.e. a new key) and share it with both Alice and Charlie. These can then communicate directly - without involving Bob - using this secret. If Dave does DH then with any of them, Dave can also receive the secret and communicate with all others. Etc.

2 answers

3

That’s an open problem. While doing with two participants is trivial, and with three possible (although it involves a little more advanced mathematics), there is no known way to do this for four or more participants.

Two participants, generalized

The operations of Diffie-Hellman are made not in the set of Natural numbers, Integers, Real, etc, but in a cyclic group with generator g. Suppose Alice, Bob, Charlie and Dave each publish their own public component in the protocol:

A = gto, B = gb, C = gc, D = gd

Like a, b, c and d are kept secret, the other participants can not use it in any calculation. For Alice and Bob to create a common key, they both need to calculate:

Kab = ga*b

What is simple: Alice knows a and B = g^b, then all she has to do is B^a = (g^b)^a = g^(a*b) = Kab. Bob knows b and A = g^a, then A^b = (g^a)^b = g^(a*b) = Kab. But what if the four participants want to create a common key? A natural candidate would be:

Kabcd = ga*b*c*d

But then we have a problem: Alice only knows a, B = g^b, C = g^c and D = g^d; she doesn’t know b, c and d, nor does it have the means to obtain them (if it did, the DH would be totally unsafe, as the attacker would also be able to calculate these values based on A, B, C and D).

The only way to calculate this would be with the help of the other participants:

  1. Alice calculates Kab = B^a, Kac = C^a and Kad = D^a; she sending Kac to Bob (publicly, or privately with the help of Kab);

  2. Bob now knows Kac = g^(a*c), and can calculate Kabc = Kac ^ b = (g^(a*c))^b = g^(a*b*c); He sends this to Dave;

  3. Dave now knows Kabc = g^(a*b*c), and can calculate Kabcd = Kabc^d = (g^(a*b*c))^d = g^(a*b*c*d).

Etc. If each participant sends the intermediate results to the others, in the end everyone can calculate the common key.

The problem is, isn’t it a waste of messaging? Now, if each participant were to reveal part of the computation to others, so that everyone could calculate the final result, it would not be simpler instead:

  1. Alice calculates Kab = B^a, Kac = C^a and Kad = D^a;
  2. Alice creates a new key K random;
  3. Alice sending K for each other, using Kab, Kac and Kad.

The supposed advantage of Diffie-Hellman in a group would be for each participant to publish their "public key" only once, and for any participant to be able to calculate a key common to the entire group without any additional message exchange. So that this scheme would not be a solution to the proposed problem.

Three participants

With only three participants, it is possible to do this without any additional exchange of messages, but it is necessary to establish some additional parameters, and the way of calculation is somewhat more complex. The mathematics involved is beyond my reach, but an explanation of the technique can be seen in that answer in Crypto.SE.

In summary, an operation is described e(P, Q) such that e(P^a, Q^b) = e(P, Q)^(a*b), so that if Alice, Bob and Charlie publish:

A = gto, B = gb, C = gc

So Alice can calculate:

Kabc = e(B, C)^a = e(g^b, g^c)^a = (e(g, g)^(b*c))^a = e(g, g)^(a*b*c)

Bob can calculate:

Kabc = e(A, C)^b = e(g^a, g^c)^b = (e(g, g)^(a*c))^b = e(g, g)^(a*b*c)

and Charlie can calculate:

Kabc = e(A, B)^c = e(g^a, g^b)^c = (e(g, g)^(a*b))^c = e(g, g)^(a*b*c)

Note: In some scenarios, the "key confirmation" step (i.e. each participant proves to others that he has computed the correct key, that an opponent has not interfered in the process) may be necessary, as in the DH of two participants. In this case, the benefits of this technique are nullified (since additional exchanges of messages are necessary), being one more reason why this is little used in practice.

0

There are actually several proposals for group key agreements. Of course it’s all very academic so there are no standards or ready products, but the protocols exist.

Some are quite complicated, the simplest I found was this, here is paper file.

It’s a short paper published on the IEEE Communication Letters, it’s very clear in the description of the protocol, so I don’t think you’ll have any problems understanding.

Any doubt in the notation, or even in the mathematical part just ask. ;)

Browser other questions tagged cryptography

You are not signed in. Login or sign up in order to post.