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.

Improve this question
9
  • 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 and/or devolves into discussions about how long we have until the heat death of the universe.
    – HopelessN00b
    Jun 17, 2016 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, 2016 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. <shrug> 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. [...] rakhesh.com/infrastructure/…
    – HopelessN00b
    Jun 17, 2016 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, 2016 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
    – WhiteWinterWolf
    Jun 19, 2016 at 10:26

1 Answer 1

Reset to default
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.
Improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .