Digital Signatures - Introduction to Cryptography with Maple - page 546

Z p and, to evaluate the cost of this attack, the relevant parameter is the
size of the prime q . Fortunately for the DSA user, the only DL algorithms that work
directly in this smaller subgroup are the generic ones which, as we have seen in
Chap. 6 , run in fully exponential time in contrast to the subexponential time of index
calculus. The number of operations required by the generic methods is of the order
of the square root of q and so, for q a 160-bit prime, which is the recommended
size when p is a 1024-bit prime, we obtain that this attack would also require about
2 80 operations. Thus, in the concrete case in which

order q of

, both
approaches present approximately the same degree of difficulty and the remaining
approved values of

( L , N ) = ( 1024 , 160 )

are also obtained by trying to balance the algorithm
strength against both methods, as well as against attacks on the hash function H .
When

( L , N )

the hash function of choice is SHA-1 which, as it has
a 160-bit length, also requires about 2 80 operations to find a collision due to the
birthday paradox. In fact, as we have mentioned in Chap. 5 , the 'Chinese attacks'
against SHA-1 require only about 2 63 operations to find a collision and, from this
point of view, the weakest link in the

( L , N ) = ( 1024 , 160 )

( 1024 , 160 )/ SHA-1 combination is, precisely,

the hash function SHA-1.
From these remarks it is clear that amore reasonable choice from the security point
of view is the

( 2048 , 224 ) /SHA-224 combination and the remaining stronger ones.

We use together with SHA-256 in the Maple implementation

that follows. Unless some new attacks are discovered—which is certainly possible—
this combination seems safe for years to come.
Apart from preventing DL attacks and attacks against the hash function, other
practical aspects must also be taken in consideration when implementing DSA, in
order to prevent certain specific attacks. For example, reuse of the 'ephemeral key'
k is strictly forbidden for the same reasons explainedwhen discussing hashedElgamal
signatures.
Summarizing the previous discussions, we can say that DSA looks, for now,
secure, because no feasible attacks against it have been discovered. There is, however,
no security reduction for DSA which, even if not giving an absolute guarantee of
security in the practical sense, would provide additional assurance. As on other
similar occasions, we must warn that the fact that no decisive attacks have been
found so far does not offer any guarantee for the future.
To close these remarks we mention that Pointcheval and Stern proved that a
variant of Elgamal signatures with a randomly chosen generator g is UF-CMA secure
assuming that the hash function H is a random oracle (so that this is a proof in the
random oracle model). This proof, however, does not extend to the original Elgamal
nor to DSA, see [155] details. We will consider later on some other UF-CMA secure
signature schemes.

( L , N ) = ( 2048 , 256 )