Cryptography Reference
In-Depth Information
There is a subtler variant of the man-in-the-middle (or, rather, woman-in-the-
middle in this example) attack that allows Eve to learn the common key that Alice
and Bob share after the protocol and hence to passively eavesdrop all the messages
computing discrete logarithms in a group whose order
t
is known to be a product of
powers of small primes is easy because of the Pohlig-Hellman algorithm.
Suppose then that the order of
G
can be written in the form
t
t
r
, where
r
has
=
only small prime factors (a trivial way to do this is to take
r
=
1).When Eve intercepts
v
t
,
and sends these values to Bob and Alice, respectively. Following the DH protocol,
Alice computes
k
u
t
and
v
=
g
x
and
v
g
y
, she replaces them by
u
=
the group elements
u
=
=
g
xt
y
, so that they
share this key
k
. But Eve knows
u
and
g
t
and hence she only has to solve the equation
u
g
yt
x
and Bob computes
k
v
)
x
u
)
y
=
(
=
=
(
=
x
.Now
g
t
is, by
Proposition 2.5, an element of
G
of order
r
and hence the cyclic group
g
t
x
v
)
=
(
)
to find
x
, which will allow her to find
k
as
k
=
(
g
t
has order
g
t
r
. The equation
u
=
(
x
lives in this group, whose order is a product of small prime
factors, and the Pohlig-Hellman algorithm will allow Eve to compute the discrete
logarithm of
u
to the base
g
t
. Observe, however, that this discrete logarithm will
not, in general, be equal to
x
. Indeed, the discrete logarithm
l
)
log
g
t
u
is defined
as the smallest (positive) integer solution of the above equation, and is an integer
<
=
r
while
x
is, in general, much larger since we only know that
x
<
t
. However,
it is clear that
x
is also a solution of the equation and hence
l
x
mod
r
.From
this it follows that knowing
l
is sufficient for Eve to get hold of the key
k
because
k
=
v
)
x
and, since the order of
v
=
(
is, by Proposition 2.4, a divisor of
r
,wehave
v
)
l
v
)
x
(
=
(
=
that
k
. Thus, finding
k
essentially reduces to just solving an instance
of the discrete logarithm problem in a group of order
r
and the Pohlig-Hellman
algorithm allows Eve to do it. We use Maple to give a concrete demonstration of this
attack in Sect.
7.2.4
.
Note that if
r
1 then both
u
and
v
are equal to 1 and the key that Alice and
=
Bob will share is
k
1. Even if Alice and Bob do not detect anything wrong when
running the protocol, this is easy to prevent by just checking whether the element
received is 1. More generally, Alice and Bob may prevent this attack by checking
that the elements they receive do not have an order that is a product of small primes
or, to eliminate this possibility altogether, they can use a group
G
whose order does
not have small prime factors, for example, a group of prime order. This precaution
is helpful not only against an active adversary but also against a passive one who
tries to find the key by solving a discrete logarithm; next we will indicate how to
find adequate groups for the protocol. We also remark that if the channel used for the
DH protocol is authenticated, then active attacks like these would not be successful
because Eve's manipulations would be detected.
=
7.2.3 Groups for the DH Protocol
In order to implement the DH protocol one must be careful when choosing the group
G
; here we will present some of the most common solutions. As we have seen, a
