Cryptography Reference
In-Depth Information
Alternatively, instead of computing Bob's secret exponent
d
, Oscar could attempt
to recover Alice's random exponent
i
:
i
= log
k
mod
p
.
α
Again, this step is solving the discrete logarithm problem. Should Oscar succeed
with it, he can compute the plaintext as:
i
)
−
1
x
≡
y
·
(
β
mod
p
.
Z
p
.In
contrast to elliptic curves, the more powerful index-calculus method (Section 8.3.3)
can be applied here. Thus, in order to guarantee the security of the Elgamal scheme
over
In both cases Oscar has to solve the DL problem in the finite cyclic group
Z
p
today,
p
should at least have a length of 1024 bits.
Just as in the DHKE protocol, we have to be careful that we do not fall vicitim to
what is a called a
small subgroup attack
. In order to counter this attack, in practice
primitive elements
are used which generate a subgroup of prime order. In such
groups, all elements are primitive and small subgroups do not exist. One of the
problems illustrates the pitfalls of a small subgroup attack with an example.
α
Active Attacks
Like in every other asymmetric scheme, it must be assured that the public keys are
authentic. This means that the encrypting party, Alice in our example, in fact has
the public key that belongs to Bob. If Oscar manages to convince Alice that his key
is Bob's, he can easily attack the scheme. In order to prevent the attack, certificates
can be used, a topic that is discussed in Chapter 13.
Another weakness, if not necessarily an attack that requires any direct action by
Oscar, of the Elgamal encryption is that the secret exponent
i
should not be reused.
Assume Alice used the value
i
for encrypting two subsequent messages,
x
1
and
x
2
.
In this case, the two masking keys would be the same, namely
k
M
=
i
. Also, the
two ephemeral keys would be identical. She would send the two ciphertexts (
y
1
,
k
E
)
and (
y
1
,
k
E
) over the channel. If Oscar knows or can guess the first message, he can
compute the masking key as
k
M
≡
β
y
1
x
−
1
mod
p
. With this, he can decrypt
x
2
:
1
y
2
k
−
M
x
2
≡
mod
p
Any other message encrypted with the same
i
value can also be recovered this way.
As a consequence of this attack, one has to take care that the secret exponent
i
does not repeat. For instance, if one would use a cryptographically secure PRNG,
as introduced in Section 2.2.1, but with the same seed value every time a session
is initiated, the same sequence of
i
values would be used for every encryption, a
fact that could be exploited by Oscar. Note that Oscar can detect the re-use of secret
exponents because they lead to identical ephemeral keys.
