Cryptography Reference
In-Depth Information
8.4 Security of the Diffie-Hellman Key Exchange
After the introduction of the discrete logarithm problem, we are now well prepared
to discuss the security of the DHKE from Section 8.1. First, it should be noted that a
protocol that uses the basic version of the DHKE is not secure against active attacks.
This means if an attacker Oscar can either modify messages or generate false mes-
sages, Oscar can defeat the protocol. This is called
man-in-the-middle attack
and is
described in Section 13.3.
Let's now consider the possibilities of a passive adversary, i.e., Oscar can only
listen but not alter messages. His goal is to compute the session key
k
AB
shared
by Alice and Bob. Which information does Oscar get from observing the proto-
col? Certainly, Oscar knows
and
p
because these are public parameters chosen
during the set-up protocol. In addition, Oscar can obtain the values
A
=
k
pub
,
A
and
B
=
k
pub
,
B
by eavesdropping on the channel during an execution of the key-exchange
protocol. Thus, the question is whether he is capable of computing
k
=
α
ab
α
from
b
mod
p
. This problem is called the
Diffie-Hellman
problem
(DHP). Like the discrete logarithm problem it can be generalized to arbi-
trary finite cyclic groups. Here is a more formal statement of the DHP:
a
α
,
p
,
A
≡
α
mod
p
and
B
≡
α
Definition 8.4.1
Generalized Diffie-Hellman Problem (DHP)
Given is a finite cyclic group G of order n, a primitive element
α
∈
a
b
G and two elements A
=
α
and B
=
α
in G. The Diffie-
ab
.
Hellman problem is to find the group element
α
One general approach to solving the Diffie-Hellman problem is as follows. For il-
lustration purposes we consider the DHP in the multiplicative group
Z
p
. Suppose—
and that's a big “suppose”—Oscar knows an efficient method for computing discrete
logarithms in
Z
p
. Then he could also solve the Diffie-Hellman problem and obtain
the key
k
AB
via the following two steps:
1. Compute Alice's private key
a
=
k
pr
,
A
by solving the discrete logarithm problem:
a
log
α
A
mod
p
.
2. Compute the session key
k
AB
≡
≡
B
a
mod
p
.
But as we know from Section 8.3.3, even though this looks easy, computing the
discrete logarithm problem is infeasible if
p
is sufficiently large.
At this point it is important to note that it is not known whether solving the DLP
is the only way to solve the DHP. In theory, it is possible that there exists another
method for solving the DHP
without
computing the discrete logarithm. We note that
the situation is analogous to RSA, where it is also not known whether factoring is the
best way of breaking RSA. However, even though it is not proven in a mathematical
sense, it is often assumed that solving the DLP efficiently is the only way for solving
the DHP efficiently.
Hence, in order to assure the security of the DHKE in practice, we have to ascer-
tain that the corresponding DLP cannot be solved. This is achieved by choosing
p
