Cryptography Reference
In-Depth Information
10.2.4
Attack on the ISO/IEC 9796 Signature Scheme
A first surprising attack has been found by Jean-Sebastien Coron, David Naccache,
and Julien Stern in Ref. [51] on a slightly modified variant of the ISO/IEC 9796 norm:
let us assume that we remove the XOR to
r
in the third step of the signature. Let us
further assume that
k
is a multiple of 64. For an original message of
d
k
2
=
bits, we
k
have
t
=
z
=
16
. We write
m
=
m
z
···
m
2
m
1
.If
m
1
=
m
1
H
m
1
L
is the least significant
byte, we write
u
=
m
1
L
||
6 in hexadecimal. The formatted string is
((
S
(
m
z
)
⊕
1) OR 80)
||
m
z
||
S
(
m
z
−
1
)
||
m
z
−
1
||···||
S
(
m
2
)
||
m
2
||
S
(
m
1
)
||
u
.
With the XOR to
r
removed, following our assumption, the formatted string is
(
S
(
m
z
)OR80)
||
m
z
||
S
(
m
z
−
1
)
||
m
z
−
1
||···||
S
(
m
2
)
||
m
2
||
S
(
m
1
)
||
u
.
Now if
m
z
is chosen so that the leftmost bit of
S
(
m
z
) is set to 1, and if we choose
m
1
=
66, the formatted string is
S
(
m
z
)
||
m
z
||
S
(
m
z
−
1
)
||
m
z
−
1
||···||
S
(
m
2
)
||
m
2
||
S
(
m
1
)
||
m
1
.
We notice that
z
is a multiple of 4. So we can choose a special message
m
of the form
=
m
4
m
3
m
2
m
1
||
m
4
m
3
m
2
m
1
||···||
m
4
m
3
m
2
m
1
.
m
We still assume that
m
4
is such that the leftmost bit of
S
(
m
4
) is set to 1, and that
m
1
=
66. The formatted string is now
S
(
m
4
)
||
m
4
||
S
(
m
3
)
||
m
3
||
S
(
m
2
)
||
m
2
||
2266
||···||
S
(
m
4
)
||
m
4
||
S
(
m
3
)
||
m
3
||
S
(
m
2
)
||
m
2
||
2266
.
Let us write
x
=
S
(
m
4
)
||
m
4
||
S
(
m
3
)
||
m
3
||
S
(
m
2
)
||
m
2
||
2266
2
64
2
128
2
k
−
64
. The formatted string is nothing but
x
and
=
1
+
+
+···+
×
,
where
x
is a 64-bit integer. We have 2
23
messages
m
i
of this type for which the
formatted string is
x
i
×
. We can estimate the probability that all prime factors of
x
i
are less than 2
16
to be 2
−
7
.
7
. Therefore, we may have more than 2
15
messages for
which the
x
i
factorizes into primes which are less than 2
16
. We can prove that with less
than 200 such messages, we are likely to find four messages
m
g
,
m
h
,
m
i
,
m
j
such that
x
g
×
x
j
. In this case, the signature of message
m
j
is simply the multiplica-
tion of the signatures of
m
g
and
m
h
divided by the signature of
m
i
. We can thus forge
a new signature with the signature of
m
g
,
x
h
=
x
i
×
m
h
,
m
i
!
This attack was later transformed and improved into an attack against the real
ISO/IEC 9796 norm (see Refs. [51, 81]).
Search WWH ::
Custom Search