43

I recently generated a new SSH key in the ed25519 format. The public key is only 69 bytes long while my old RSA key is 373 bytes.

From my perception ed25519 is the more recent and secure format.

So why isn't longer better here?

  • 7
    It is a completely different type of cryptography and therefore has same security at different keysizes. – Martin Ueding Sep 24 '15 at 14:26
  • 10
    It's not really about the length. It's how you use it. – a20 Sep 25 '15 at 3:14
63

No, longer is not better.

Let me explain. In symmetric cryptography, keys are just bunches of bits, and all sequences of bits are valid keys. They have no internal structure. Provided that you use decent algorithms, the best possible attack on a key for symmetric encryption is brute force: the attacker tries all possible keys until he finds the right one. If the key has n bits, then there are 2n possible keys, and the attacker, on average, will find the right one after trying half of them, i.e. 2n-1. Longer keys thus make brute force harder; in that case, longer is better.

(Note that there is a limit to that; when keys are sufficiently long that brute force is no longer feasible, increasing the key length does not make things "more secure" in any meaningful way. So, for symmetric keys, longer is better until they are long enough, at which point longer is just longer.)

RSA and EdDSA relate to asymmetric cryptography where things are completely different. A key for asymmetric cryptography is a mathematical object that has a specific internal structure; breaking the key consists in unravelling that structure, and can be done a lot more efficiently than trying out all possible private keys. Note the two points:

  • Against brute force, what matters is not the length of the public key, but that of the private key, since what the attacker wants is the private key, not the public key.

  • Brute force is not the most efficient attack against keys used in asymmetric cryptography.

For RSA keys, attack succeeds by factoring the modulus. Integer factorization is a long-studied problem; with the best known algorithm, breaking a 2048-bit RSA key (i.e., a RSA public key whose modulus is a 2048-bit integer) requires about 2110 or so elementary operations.

For EdDSA keys, the public key is a point P on an elliptic curve, such that P = xG where x is the private key (a 256-bit integer) and G is a conventional curve point. The best known algorithm for recovering x from P and G requires about 2128 elementary operations, i.e. more than for a 2048-bit RSA key. In general, to break a n-bit elliptic curve public key, the effort is 2n/2.

Breaking either key is way beyond that which is feasible with existing or foreseeable technology. But in an "academic" viewpoint, the EdDSA key is somewhat stronger than the RSA key; also, elliptic curves give you more security per bit (technically, we say that integer factorization is a sub-exponential problem).

See this site for more information on that subject.

  • 1
    "the best possible attack on a key for symmetric encryption is brute force" I know this wasn't the main point of your answer, but there are no algorithms for which this is proven true, merely algorithms for which no better attacks are known. In fact if someone did manage to prove it, it would immediately imply that P!=NP. – David Sep 24 '15 at 22:00
  • 1
    Note that P != NP is about asymptotic behaviour, so it would not be proven even if there was, at some point, a symmetric encryption algorithm with keys of a given, specific size n and ideal security (i.e. no better attack than brute force). For it to demonstrate that P != NP, the proof would have to be valid for arbitrarily large values of n. – Tom Leek Sep 25 '15 at 0:00
  • That's true, but an ideal cipher with an n-bit key can be extended to an ideal cipher with arbitrary key size, by simply breaking the key into blocks and running the cipher multiple times. So I believe the statement still holds. – David Sep 25 '15 at 1:41
  • 1
    Interestingly, it turns out that also, should large-scale quantum computers be feasible in practice, then they too will reduce the security of a n-bit key symmetric cipher where exhaustive key search (brute force) is the currently best known or near best known attack, to 2^(n/2) using Grover's algorithm. Thus, in a post-quantum world, common advice is to simply double symmetric key lengths: use 256 bits rather than 128 with AES, for example, for an effectively 128-bit security level. – a CVn Sep 25 '15 at 8:14
10

I'm not satisfied with my previous answer that lead to confusing assumption about compression method used in ed25519, so I will try one more time for those who won't to jump on EC (Elliptic Curve further) math to be able to understand why EC keys is so short to compare with RSA keys.

Since my English is far from perfect, I better drop here IMHO pretty good links to this subject.

For those who really want to understand "magic" of EC (but still want to avoid to fall deeply in love with math) and be able to understand - "why EC can manage more stronger encryption than RSA using much smaller keys", - I advise to read full article on arstechnica.com "A relatively easy to understand primer on elliptic curve cryptography"

Author illustrate there gist of EC with images that helps to understand concept in a few steps.

ec

BTW, interesting excerpt about EC:

You can compute how much energy is needed to break a cryptographic algorithm and compare that with how much water that energy could boil. This is a kind of a cryptographic carbon footprint. By this measure, breaking a 228-bit RSA key requires less energy than it takes to boil a teaspoon of water. Comparatively, breaking a 228-bit elliptic curve key requires enough energy to boil all the water on earth. For this level of security with RSA, you'd need a key with 2,380 bits.

For those, who don't want to dig internals of EC under the hood, I advise at least to read and follow pretty good practical summarization on encryption in SSH that worth of spending time on reading that. Link is here: secure-secure-shell

Ready to copy/paste solutions (provided by community of github) for various OS is here: WiKi of Secure-Secure-Shell (but I highly advise to read previuos article on github before you go there)


Previous answer:

Q: "The public key is only 69 bytes long while my old RSA key is 373 bytes. So why isn't longer better here?"

In addition to Tom's explanation "why the keys are shorter while at least equally secure" - according to original paper from those who created ed25519 from here: http://ed25519.cr.yp.to/ed25519-20110926.pdf :

Besides of "equally secure" ed25519's short keys are "internally" compressed. Uncompressed ed25519 key would be almost twice longer.

P.S.

To avoid confuse or misinterpretation of point compression used in ed25519, it is NOT regular compression like in a zip archive(!!!). Thanks to @diagprov for helping correct my answer in the comments with good and simple explanation of point compression and for the link describing point compression

Reference from document above (Page#2):

  • Small keys. Public keys consume only 32 bytes. The times for compression and decompression are again included.
  • This it not the answer. How could you not have seen the answer by Tom? It explains everything. – Tobi Nary Apr 8 '16 at 7:10
  • I don't have anything against perfect Tom's answer that describing deeply internals of cryptography in common, but people often asking when they start using particular ed25519(OP-question) in SSH why ed25519 public key in authorized_keys looks much smaller than RSA-based keys. My addition is to point that ed25519 using de/compression of keys that's why small size of keys doesn't effect effectiveness/strongest of algorithm in a simple, short sentence about asked by OP ed25519 format. – Alex Apr 8 '16 at 7:51
  • 1
    That is just not true. See Toms answer for why the keys are shorter while at least equally secure. – Tobi Nary Apr 8 '16 at 7:55
  • I absolutely agree with Tom's explanation and your statement about "why the keys are shorter while at least equally secure". I just pointed out that besides of that ability to be equally secure with shorter keys in elliptic curve cryptography, ed25519 in addition using key compression. That's all I added. – Alex Apr 8 '16 at 8:54
  • 2
    @Alex I think you're confusing point compression with the more usual form of compression - point compression as used in EC essentially means "work out what you need to as you go", usually the y co-ordinate. Furthermore, the security bit sizes are not computed on points, but on the secret "x", an integer "power term" if you like (it's not a point and isn't compressed). This is what I think everyone is objecting to. I hope this helps. – diagprov Apr 8 '16 at 9:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.