|
Some SSH2 implementations, including OpenSSH, can
apparently generate and use DSA keys larger than 1024 bits. I'm not sure
about other implementations, but at least with OpenSSH, there are two major
problems with the way this works.
1. This violates FIPS 186-2, the DSS standard,
which limits the key size to 1024.
2. Even though the size of the prime modulus, p,
can exceed 1024, the size of the subgroup order, q, is still limited to 160
bits. (OpenSSH can not interoperate with other implementations that use larger
subgroups and complains about invalid signature size.) But this implies 80 bit
security no matter how big the key is, because there is an attack whose running
time depends exponentially on the size of sqrt(q), but only polynomially on the
size of p. [1] To increase security, the
sizes of p and q must both be increased. In Crypto++, by default the size of q
is chosen as 2*DiscreteLogWorkFactor(modulusSize), where DiscreteLogWorkFactor
is:
unsigned int DiscreteLogWorkFactor(unsigned int
n)
{ // extrapolated from the table in Odlyzko's "The Future of Integer Factorization" // updated to reflect the factoring of RSA-130 // assuming discrete log takes about the same time as factoring if (n<5) return 0; else return (unsigned int)(2.4 * pow((double)n, 1.0/3.0) * pow(log(double(n)), 2.0/3.0) - 5); } This translates to q sizes of 226 and 304 for p
sizes of 2048 and 4096 respectively.
To fix these problems, I suggest the
following:
1. Stop using "ssh-dss" with non-standard DSA
key sizes. 2. Create a new algorithm name for non-standard DSA
key sizes.
3. For the new algorithm, allow arbitrary key sizes
as long as p and q are at least 1024 and 160 bits
respectively.
4. When generating new keys, use something like the
above DiscreteLogWorkFactor function to derive the size of q from
p.
|