Take the tour ×

According to the answers on this question the differences between RSA and DSA would seem to be trivial. However, according to this page DSA compromises your security if anyone is sniffing your packets when you use the key. And according to this page, DSA is limited to 1024 bits.

If those claims are true, I can't see any reason to ever use DSA keys. The policy of the company I'm working at, however, will only allow DSA keys.

What is the truth? Is the use of DSA really reducing security as much as it appears to me?

share|improve this question
The second one says "on a system with a flawed pRNG". It's also possible to implement DSA in a way that doesn't suffer from this, while remaining compatible with normal implementations. –  CodesInChaos Jan 18 at 15:52
It says "just using it on a system with a flawed pRNG". Given that RSA does not have this problem, shouldn't this be taken seriously as a downside of DSA? –  iconoclast Jan 18 at 15:54
Sounds to me (forgive the extreme metaphor!) like saying "but Ford Pintos can be made safe". It's undoubtedly true, but it's much easier to just avoid them. I'm not losing anything by not driving a Pinto, so why bother. Again I know this is extreme, but it should make my point clear. –  iconoclast Jan 18 at 15:57
IMO there is little reason to use (finite field) DSA over RSA. But there is a good reason for using ECDSA over RSA even though ECDSA has the same randomness issues. –  CodesInChaos Jan 18 at 16:07
add comment

2 Answers

You misread the page about sniffing packets; it is already paranoid and alarmist, but not to that point.

When producing a DSA signature, the signature engine works in a group which is embodied by a modulus p (a big prime number) and a group order q (a smaller prime, divisor of p-1). These values are part of the public key. For each signature, the signature engine must use a random number generator to produce a random value k which MUST be chosen uniformly in the 1..q-1 range. The "uniformly" term is very important. If the choice of k is biased, then it allows for key recovery after observing a number of signatures. Whether this is critical or not depends on the bias. A relatively small bias (e.g. k is generated as a sequence of bits of the size of q, then reduced modulo q) will incur an "academic" break with key recovery after about 263 signatures: an attack, yes, but not practical. On the other hand, if the random generator is so botched that it always outputs the same value for k, then two signatures are sufficient to recompute the private key. Sony deployed such an utterly failed RNG/signing system.

What this amounts to is that if the implementation of a signature algorithm is bogus, well, it may leak important data, including the private key. This is true of any cryptographic algorithm, and RSA is not exempt. Singling out DSA is unwarranted.

(What can be said in all neutrality is that DSA and ECDSA require a source of randomness for each signature, which is a relatively heavy requirement for embedded systems such as smartcards. Solutions exist; when I have time, I work on the issue. Edit: this is now a published RFC.)

As for key size, the current standard specifies sizes of 1024, 2048 and 3072 bits (that's the size of p). An older version of the standard allowed only 1024 bits, while an even older allowed all sizes multiple of 64 from 512 to 1024 bits. A number of deployed implementations of DSA are a bit lagging behind the 2009 standard, and thus allow only 1024-bit keys.

A 1024-bit DSA key is not a critical risk. As far as we know, DSA appears to be at least as strong as RSA with the same key size, and in practice a bit stronger. DSA relies on discrete logarithm and the current DL-break record is for 530 bits, while the current record for factorization (RSA) is 768 bits. Best known algorithms for factorization and DL have a lot of similarities, but the final step (where a lot of fast RAM is needed) appears to be more expensive with DL than with factorization. Thus, right now, a 1024-bit DSA key is not a true security risk. Especially since, for signatures, we have less to worry about future break than for encryption; and DSA is signature-only.

The main issue with DSA is that it is not as widely supported as RSA; when it is supported, it may have limitations (e.g. limited to 1024-bit keys, or usable in conjunction of only a limited set of other cryptographic algorithms). These limitations are not intrinsic to the algorithm, but reflect the state of the market, which is dominated by RSA. However, it is currently quite fashionable to switch to elliptic curve variants of DSA and, correspondingly, the market is slowly (very slowly) shifting towards more support for (EC)DSA.

share|improve this answer
Technically there are much bigger DL breaks, but not against the prime fields typically used in DSA. eprint.iacr.org/2012/720 –  CodesInChaos Jan 18 at 16:29
@CodesInChaos: well, yes, I am talking about the cases which map to actual practice. Similarly, there are much higher factorization breaks, but only with some numbers with special structure. –  Thomas Pornin Jan 18 at 16:30
add comment

Looking at your two issues:

  1. Using a bad RNG leaks the private key

    This is a problem with the way DSA is usually described and implemented, but not an inherent problem of DSA. You can implement DSA deterministically avoiding this problem.
    I think it's a flaw in typical implementations, and should be fixed. But apparently those who work on these implementations disagree, or want to follow some flawed standard procedures.

    Systems with a broken RNG are a big problem, no matter which crypto you use. For example it will often totally break confidentiality of your encrypted connections because the session keys are bad. Avoid these systems at all cost.

    Matthew Green wrote a blog-post on the issues a bad RNG causes: Surviving a bad RNG

  2. DSA is limited to 1024 bits

    Some older standards(FIPS 186-2) mandate 1024 bit keys, and some implementations might be limited to that size. But the newer standard FIPS 186-3 allows them, and many implementations support 2048 bit keys.

    So I don't think this is relevant anymore.

If those claims are true, I can't see any reason to ever use DSA keys [over RSA keys]

There is little reason to use finite field DSA over RSA. They have similar performance at similar security levels. But ECDSA, which is DSA on elliptic curves offers better performance (at least for signing) at high security levels. So there are reasons for using it, despite weakness to broken RNGs.

share|improve this answer
add comment

Your Answer


