10

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?

iconoclast
  • 407
  • 5
  • 10
  • 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](http://crypto.stackexchange.com/questions/851/can-ecdsa-signatures-be-safely-made-deterministic), while remaining compatible with normal implementations. – CodesInChaos Jan 18 '13 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 '13 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 '13 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 '13 at 16:07
  • 1
    Just a quick update - Snowden revealed the extent of NSA knobling RNG's to be enormous, including paying RSA $10M and infiltrating official standards etc. Best to assume your RNG is compromised, since for about half the world or more, it definitely is. – anon Jan 14 '14 at 05:41
  • Since this appears to actually be about SSH though not stated or tagged, belated neardupe https://security.stackexchange.com/questions/29262/disabling-authentication-via-dsa-keys-in-openssh – dave_thompson_085 Apr 26 '19 at 06:51

2 Answers2

13

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.

Thomas Pornin
  • 322,884
  • 58
  • 787
  • 955
  • Technically there are much bigger DL breaks, but not against the prime fields typically used in DSA. http://eprint.iacr.org/2012/720 – CodesInChaos Jan 18 '13 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 '13 at 16:30
  • The second webpage in the Q is dated 2007, before FIPS 186-3. And _for SSH_ even after 186-3 came out in 2008, and OpenSSL 1.0.0 implemented it (fully) in 2010, OpenSSH didn't use it perhaps because rfc4253 fixed the hash at SHA1 (with nominal strength 80 bits), and OpenSSH has since deprecated DSA entirely rather than improve it; see https://security.stackexchange.com/questions/146379/does-ssh-support-dsa-with-2048-bit-keys (mine) and links there. (It does now support ECDSA and djb's Ed25519.) – dave_thompson_085 Apr 26 '19 at 06:57
3

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.

CodesInChaos
  • 11,964
  • 2
  • 40
  • 50