Cryptography Reference
In-Depth Information
10.3.2
The Bleichenbacher Attack against the ElGamal Signature
We describe here an attack against the ElGamal signature which works for special
public parameters. The attack is due to Daniel Bleichenbacher (see Ref. [33]).
Let
p
and
g
be the parameters in the ElGamal signature. Let us assume that
bw
with an integer
b
which is smooth (namely such that all its prime factors
are small). As an example, we can just have
b
p
−
1
=
2, which works for every odd prime
p
. Let us further assume that we know some relation
g
1
/
t
=
mod
p
=
cw
. This is a
reasonable assumption if we have
g
=
b
(note that the complexity of the exponentiation
≡
is decreased if
g
is small) and
p
1 (mod 4) since we can check that the relation holds
p
−
3
2
=
=
for
t
and
c
1: we have
p
p
−
1
2
−
1
1)
p
−
1
−
1
g
(
−
2
(
cw
)
t
≡
≡−
≡
g
(mod
p
)
g
g
p
−
1
2
since
g
p
−
1
is a square root of 1 which is not 1 (otherwise
g
would not be a generator)
2
1)
p
−
1
and (
−
=
1 due to the assumption on
p
mod 4.
2
p
−
1
w
=
b
is smooth and
g
1
/
t
We will show now that with the assumption that
mod
=
p
cw
, anyone can forge a signature for any message digest
h
.
First take
r
cw
.
Find
z
such that
y
wc
=
g
wcz
(mod
p
). This is nothing but the discrete loga-
rithm of
y
wc
mod
p
, in basis
g
wc
mod
p
, which spans a group of order fac-
tor of
b
. Thus the Pohlig-Hellman algorithm works, thanks to the assumption
on
b
.
Take
s
≡
=
t
(
h
−
cwz
) mod (
p
−
1).
Yield the signature (
r
,
s
).
We only have to prove that the signature is valid. First we check that 0
≤
r
<
p
.Next
we have
y
r
r
s
y
cw
(
cw
)
t
(
h
−
cwz
)
y
cw
g
h
−
cwz
g
h
≡
≡
≡
(mod
p
)
.
Therefore the signature is valid.
The main idea here is to simplify the discrete logarithm problem by rais-
ing
everything
to
the
power
w
,
so
that
the
underlying
subgroup
becomes
smooth.
We can get rid of this kind of attack by using subgroups of prime order.
Search WWH ::
Custom Search