Are the DSA keys breakable? If so, what is the maximum key size that is breakable with the latest technology ?
Why are DSA keys not used during authentication?
Can we use DSA keys for encryption?
Asked
Active
Viewed 2,134 times
1 Answers
8
To our knowledge, DSA keys of adequate size cannot be broken with existing technology. There are, as usual, details.
A DSA key lives in a group which is incarnated by three big integers, called p, q and g. These are called the "DSA parameters" and may be shared between public keys from distinct people; however, Tradition is that everybody has his own parameters. Security will depend on the sizes of p and q.
p is a big prime. It must be so that discrete logarithm is hard modulo p. Theory has it that breaking discrete logarithm has roughly the same cost as breaking a RSA key if the same size; in fact, DL may be a bit harder. Current World record on DL is for a 530-bit modulus, to be compared with the 768 bits for the current RSA record (but the latter used more computers). Therefore, a 1024-bit prime is currently in the "grey zone" of "not breakable yet, but this seems reachable with existing technology, provided that we build a very specific custom machine which will cost a pretty penny" (rumour has it that it can be done for less than a billion dollars, but not substantially less). A 2048-bit DSA public key will be fine (not breakable with todays nor tomorrow's technology).
q is a smaller prime; it must be so that q divides p-1. The DL is for a subgroup of size q. While we know of sub-exponential algorithms for breaking DL when considering the size of p (which is why we want a p of 1024 bits or more), the same cannot be said for the size of q. To make the story short, a q of 224 bits or more will put you way beyond any break.
In most key strength estimates, DSA and RSA keys of the same size are assumed to offer similar levels of protection.
It so happens that for quite a long time, the DSA standard specified that the size of p and q had to be exactly 1024 bits and 160 bits, respectively (an older version of the standard mandated a size of p between 512 and 1024 bits, which was then changed to "just 1024 bits"). While the current standard allows for longer keys (e.g. 2048/224, which is good), there are a lot of deployed implementations which won't accept anything else than 1024 bits.
1024/160 is still unbroken, but "barely" (breaking such a key requires an awful lot of money, but not sci-fi level technological advances).
An extra point is that actual weaknesses very rarely stem from the key size. Usually, systems are broken through implementation flaws, not through brutally breaking the key. In particular, DSA requires, for each signature, the generation of a new random value (called k) which must be unpredictable and uniform in the 1..q-1 range. Such a process can be botched (Sony reused the same value for several signatures in the PS3 system, thus revealing their private key). DSA signatures require some care. There are solutions but they are not widely deployed yet.
In practice nobody uses DSA; everybody does RSA, and when they switch to something else, they go straight to ECDSA, the elliptic-curve variant of DSA (elliptic curves are very trendy). There still are many software who support DSA, because there was a time when it was mandated for interoperability with US federal systems (that was when RSA was still patented; the US government standardized on DSA to avoid the patent issues).
A DSA key, by definition, is suitable only for DSA, which is a digital signature algorithm.
Mathematically, a DSA public key could also be used with Diffie-Hellman, which is an asymmetric key exchange algorithm, i.e. as good as asymmetric encryption in practice (because everybody does hybrid encryption). However, standardization committees have so erred that DSA and DH public keys don't get encoded the same way. The DH standard is not freely available, so many opensource software don't implement it (because most opensource software is developed by people who devote their time but not their money to the task). This discrepancy is resolved for the elliptic-curve variants (a certificate with a public key for ECDSA actually contains an "EC public key" which is not specific to ECDSA; the same format is used for a public key for ECDH).
Note, though, that you should normally keep signature and encryption keys apart from each other (see this answer).
