2

Does the brute force speed vary significantly between 1024-bit RSA and DSA SSH keys? DSA like gpu keypairs are probably DSA/Elgamal? (Can't find docs)

EDIT: The reason I ask is an instructor that "has been involved with computer security for 10+ years" reported that DSA was much faster to brute force than RSA which I find suspect.

I understand brute forcing keys on average you need to test half of the possible keys. Of course brute-forcing keys is not generally practical and not the best attack vector if you have any other options.

StackAbstraction
  • 143
  • 1
  • 8
  • Are you talking about a pure brute force attack, iterating every possible key? Because that's one of those things that's [actually a physical impossibility](http://crypto.stackexchange.com/questions/3043/how-much-computing-resource-is-required-to-brute-force-rsa) and/or devolves into discussions about how long we have until the heat death of the universe. – HopelessN00b Jun 17 '16 at 18:47
  • Agreed, an instructor claimed DSA was much faster to brute force which I think may be backwards and am trying to disprove. Either way we agree in practically it does not matter. – StackAbstraction Jun 17 '16 at 18:54
  • 2
    Seems like he may be right, but I'm not sure it's really an apples-to-apples comparison, since DSA is used for signing, rather than encryption, and RSA's commonly used for asymmetrical encryption. `A note about speed: DSA is faster at signing, slow at verifying. RSA is faster at verifying, slow at signing. The significance of this is different from what you may think. Signing can be used to sign data, it can also be used for authentication. [...]` http://rakhesh.com/infrastructure/notes-on-cryptography-ciphers-rsa-dsa-aes-rc4-ecc-ecdsa-sha-and-so-on/ – HopelessN00b Jun 17 '16 at 20:06
  • 2
    @HopelessN00b _in SSH_ (precisely, current SSHv2 as actually practiced) RSA is used only for signature (for authentication) not encryption. That said, I agree 'brute force' doesn't really make sense here. – dave_thompson_085 Jun 18 '16 at 10:44
  • Related discussion (maybe no a duplicate though since it is not dealing with the "brute-force" aspect explicitly but it compares both algorithms security): [RSA vs. DSA for SSH authentication keys](https://security.stackexchange.com/q/5096/32746) – WhiteWinterWolf Jun 19 '16 at 10:26
  • @dave_thompson_085 This is asked in the context of DSA SSH keys. The documentation only refers to them as RSA or DSA keyspairs. I welcome more details documentation. Is this like GPG a DSA and Elgamal keypair? – StackAbstraction Jun 23 '16 at 03:27
  • It seems strange to me that there is a significant difference. If there was, then [these kind of stats (NIST @ keylength.com)](https://www.keylength.com/en/3/) would require an update. I presume here that we're talking about the best attack on the underlying mathematical problem; brute forcing a 1024 bit key is of course completely idiotic in the first place. The answer is probably found in the underlying documents leading to the stats in keylength.com; the site should have links to those. – Maarten Bodewes Jun 23 '16 at 10:01
  • This is probably better asked at crypto.stackexchange.com come to think of it. – Maarten Bodewes Jun 23 '16 at 10:02
  • StackAbs: no. First DSA and EG in GPG is not 'a' keypair; they are different algorithms and different keypairs used for different purposes, although often on the same message(s). PGP uses EG as one option for key transport, for encryption; SSH(v2) is online and does key agreement with DH (either classic or EC) instead. The definitive details of SSHv2 are of course RFCs 4250 et al, for this area particularly 4253 4419 5656; the (open) source code for openssh can also be helpful. – dave_thompson_085 Jun 23 '16 at 11:19

1 Answers1

2

Trying to brute force either a RSA or DSA key would be a losing proposition, there are far too many possibilities and there are far better attacks known.

For properly implemented RSA the best-known attack is factoring the modulus. For properly implemented DSA the best-known attack is solving the discrete log problem.

For a given key size the discrete log problem is believed to be somewhat harder than the factoring problem.

However DSA has a couple of practical problems.

  1. DSA keys were conventionally limited to 1024 bit which is considered dangerously low nowadays.
  2. Traditional DSA implementations are very sensitive to random number generator quality. Making signatures with a broken random number generator can compromise the key.
forest
  • 65,613
  • 20
  • 208
  • 262
Peter Green
  • 4,968
  • 1
  • 22
  • 26