Cryptography Reference
In-Depth Information
from the signature itself, the so-called
digital signatures with message recovery
(cf.
[MOV], Chapter 11, [ISO2], and [ISO3]). Digital signatures with message recovery
based on the RSA algorithm are particularly suited for short messages with a
binary length less than one-half the binary length of the modulus.
However, in every case the security properties of redundancy functions
should be carefully examined, such as is demonstrated by the procedure
published in 1999 by Coron, Naccache, and Stern for attacking such schemes.
The procedure is based on an attacker having access to a large number of
RSA signatures attached to messages whose representation as an integer is
divisible exclusively by small primes. Based on such a makeup of the messages
it is possible under favorable conditions, without knowledge of the signature
key, to construct additional signatures to additional messages, which would
amount to counterfeiting these signatures (cf. [Coro]). The ISO has reacted to this
development: In October 1999 the workgroup SC 27 removed the standard [ISO2]
from circulation and published the following announcement:
Based on various attacks on RSA digital signature schemes
...
,itisthe
consensus of ISO/IEC JTC 1/SC 27 that IS 9796:1991 no longer provides
sufficient security for application-independent digital signatures and
is recommended to be withdrawn.
8
The withdrawn standard refers to digital signatures for which the RSA function is
applied directly to a short message. Signatures with appendix, which arise by way
of a hash function, are not included.
A widely distributed redundancy scheme for which the attack of Coron,
Naccache, and Stern has at best a theoretical significance and represents no real
threat is set by the PKCS #1 format of RSA laboratories (cf. [RDS1], [Coro], pages
11-13, and [RDS2]). The PKCS #1 format specifies how a so-called
encryption
block
EB
should appear as input value to an encryption or signing operation:
EB=00
BT
PS
1
...
PS
00
D
1
...
D
n
.
At the head, after the introductory 00 byte, is a byte
BT
that describes the block
type (01 for private key operations, that is, signatures; 02 for public key operations,
that is, encryption) and then at least eight filler bytes
PS
1
...
PS
,
≥
8
,with
the value FF (hex) in the case of signing and nonzero random values in the case
of encryption. There follows
00
as separator byte, and then come finally the
data bytes
D
1
...
D
n
: the payload, so to speak. The number
of filler bytes
PS
i
depends on the size of the modulus
m
and the number
n
of data bytes: If
k
is
defined by
2
8(
k
−
1)
≤ m<
2
8
k
,
(17.6)
8
ISO/IEC JTC 1/SC27:
Recommendation on the withdrawal of IS 9796:1991
, 6 October 1991.
