0

I'm trying to find a basis for comparing key pair based authentication with password based authentication, and their relative resistance to guessing / brute force attacks.

I appreciate that a user-chosen password will likely have a lot less entropy than a random one - has there been any attempt to measure the difference?

For a brute force attack, I expect the cost of generating a key pair will be much higher than for generating a password, but is there much of a difference in the cost for validating the key pair compared with validating a password?

A password of a given length could potentially be any string of characters of that length, so a simple incrementing counter converted to a string of character codes would give every possible password. However the same does not apply to a key pair - indeed the number of possible values appears to be very sparse. Are there any estimates of how many key pairs exist for a given algorithm / key size?

symcbean
  • 18,278
  • 39
  • 73
  • You appear to be thinking only of RSA, which is slightly sparse; DSA/DH/IES/etc and the EC variants use _any_ (randomly-chosen) number in (1,order) as the privatekey, albeit a larger image as the publickey. For currently-popular 2048-bit (2-prime) RSA, the prime number theorem tells us the number of 2048-bit semiprimes is about 2^2046 / ln(2^1024)^2 which is about 10^1400, whereas the number of atoms in the universe is much less than 10^100, so you would need to replace every atom with an entire other universe _more than 14 times_. – dave_thompson_085 Sep 19 '18 at 19:05

2 Answers2

2

A start would be comparing password entropy to symmetric key size. A random password of 13 characters has approximately 80 bits of entropy, thus is comparable in security as a 1024 bit RSA key pair.

However, this is mostly theoretical since users typically choose insecure passwords, while key pairs are almost always random.

I would say key pairs always offer better security against brute force, but whether they should be used in your situation depends on other factors.

table

Sjoerd
  • 28,707
  • 12
  • 74
  • 102
  • This looks exactly like the answer I was looking for to the third part of my question - have you got a URL for the table above? Is this backed up by any jutification? – symcbean Sep 19 '18 at 11:16
  • [For anyone](https://crypto.stackexchange.com/q/6219) wondering why ECC key size is 2 * symmetric key size _except_ for 521. – AndrolGenhald Sep 19 '18 at 14:04
  • 2
    @symcbean: https://www.keylength.com and links there; compare to https://tools.ietf.org/html/rfc3766 also https://crypto.stackexchange.com/questions/1978/how-big-an-rsa-key-is-considered-secure-today and https://security.stackexchange.com/questions/4518/how-to-estimate-the-time-needed-to-crack-rsa-encryption/ – dave_thompson_085 Sep 19 '18 at 19:07
  • @AndrolGenhald More directly, these are the bit sizes of the P-X NIST curves, and P-521 (identical to secp521r1) is the one with the highest bit count. Actually, a 512 bit curve would have the recommended security strength, so in that sense the table is incorrect. Maybe it was a stab to the brainpool specs, which does specify a 512 bit prime curve. – Maarten Bodewes Sep 21 '18 at 10:52
1

To answer just the second question:

Technically "validation" of a key pair would require less overhead as explained in the following link: RSA Brute Force

However just to clarify, it is not merely much more difficult, but likely that the heat death of the universe will occur before anyone would be able to obtain a key pair through a brute force method as explained here:

https://crypto.stackexchange.com/questions/3043/how-much-computing-resource-is-required-to-brute-force-rsa

Not to say it can't be cracked of course, simply that this method of cracking is actually impossible.

Thunderwood
  • 111
  • 5
  • @symcbean In rereading your question I believe I may have misunderstood what it was asking. Could you clarify if this answers your second question or should I remove it? – Thunderwood Sep 19 '18 at 13:04
  • I was specifically wondering about the effort, I guess its a silly question if people are picking sensible sized keys - I did consider that if a vulnerability emerged in the underlying algorithms, the effort of brute forcing might be significantly reduced. On reflection making choices on such a hypthetical and therefore unquantifiable situation is not a very pratical approach. Thank you for highlighting this. – symcbean Sep 20 '18 at 15:34