In Teleport 17 we made the switch from RSA to ECDSA and Ed25519, and it paid off with improved security and significant performance benefits. This was a major undertaking; Teleport has used 2048-bit RSA keys for just about everything since our initial release. Switching to new key types and signature algorithms came with serious compatibility concerns given the broad range of environments Teleport is deployed in and the number of third party tools that use or trust Teleport-issued certificates. In this post I’ll explain how we navigated this change and how we were able to reduce benchmarked CPU usage by 77% and latency by 37%.
The modern signature algorithm landscape
When it comes to choosing a key type and signature algorithm, whether you are generating an SSH keypair to authenticate to GitHub, getting a new TLS certificate for your website, or building an application that issues JWTs, there are three main contenders: RSA, ECDSA, and Ed25519. These are all public-key cryptography systems that can be used for encrypting or signing messages. In this post I’ll focus on their applications for signing X.509 and SSH certificates, which is most relevant to what we do at Teleport.
RSA was the first widely-used asymmetric-key cryptography system. Ron Rivest, Adi Shamir and Leonard Adleman first published the algorithm in 1977, the name “RSA” comes from their initials. It’s based on the computational difficulty of factoring the product of two large prime numbers that are used to derive the public and private key pair. It was the only supported signature algorithm in the first versions of SSL and SSH, both of which were released in the mid-1990s, and it still has the most widespread support for certificate signatures today.
ECDSA is a newer signature algorithm based on elliptic-curve cryptography. ECDSA keys are much smaller than RSA keys with equivalent security properties, and generating new ECDSA keys is orders of magnitude faster than RSA. While the algorithm was originally published in 1992, TLS and SSH didn’t support it until the mid-2000s, and it didn’t gain mass adoption until the early 2010s. Today, support for ECDSA signatures on TLS and SSH certificates is almost universal and many of the major websites you visit will be serving TLS certificates signed with ECDSA.
Ed25519 is also based on elliptic-curve cryptography. It has similar key size and performance characteristics to ECDSA, and it was designed so that implementations never depend on secret data for branch conditions or array indices in order to avoid timing or side-channel attacks. The algorithm was published in 2011 and OpenSSH added support for Ed25519 keys and certificates in 2014. While SSH support is generally quite good, the CA/Browser forum has not approved it for use in publicly trusted TLS certificates and Ed25519-based certificates are not accepted by any major web browser.
Problems with RSA
Performance
RSA keys are big, unwieldy, and slow. The bare-minimum acceptable RSA key size is 2048 bits, and generating an RSA keypair of that size takes about 10000x longer than an Ed25519 or ECDSA keypair with an equivalent (or better) level of security. The large keys make certificates larger and handshakes slower. While most apps don’t need to generate new keypairs at runtime, Teleport does, and generating RSA keys became a significant bottleneck.
Security
RSA implementations have been plagued with security vulnerabilities from the very beginning. While the underlying math still holds up, implementations have to make multiple decisions when it comes to generating a key pair and then computing a signature, and every decision is an opportunity to make the wrong choice and fundamentally compromise the security of your system.
First is the key size. While it’s possible for RSA to be perfectly secure when used with keys >=2048 bits in length, it is completely insecure when used with smaller keys (a 512-bit key can easily be broken on a laptop). If the RSA implementation doesn’t force this choice, it is often left up to users who don’t really know what they’re doing. While choosing a key size may seem simple, small RSA keys are still seen in the wild. The Go crypto/rsa implementation started rejecting keys smaller than 1024 bits in 2024.
Next, when you compute an RSA signature, you usually sign a hash of the message instead of the full message. RSA was commonly used with the SHA-1 hash, which is now considered cryptographically broken. You may recall GitHub removing support for RSA with the SHA-1 hash in 2021 (they finally added Ed25519 and ECDSA host keys around the same time).
Another common footgun is the choice of signature padding scheme. PKCS#1 (RFC 8017) defines two signature schemes for RSA: RSASSA-PKCS1-v1_5 and RSASSA-PSS. While it’s still mostly good enough for certificate signatures, Bleichenbacher’s attacks broke RSA key exchanges based on PKCS#1 v1.5 in 1999. RSASSA-PSS was also commonly paired with the now-broken SHA-1 hash, but with the SHA-256 hash it is still considered secure.
There are multiple other decisions that have to be made very carefully to avoid completely compromising your RSA cryptosystem, including the choice of prime and public and private exponents. The point is, most developers can’t seriously be expected to know all of this, and all these decisions have repeatedly led to implementations and end users getting things wrong.
The case for Ed25519
As I’ve already mentioned, Ed25519 offers very small keys that are fast to generate and use. The other big upside is that there’s nothing to get wrong: there’s no need to pick and choose a curve and a hash algorithm, the designers already made all those choices. There’s only one way to generate and use an Ed25519 keypair.
The downside is the lack of support. No major browsers accept Ed25519-based certificates, most OIDC and SAML implementations don’t support it, and neither do most database protocols. The majority of hardware keys, HSMs and cloud KMS systems also don’t support Ed25519.
For SSH, however, Ed25519 actually has better support than RSA. How is that possible when RSA support has been around much longer and is still supported today? Well, the initial versions of OpenSSH only supported RSA with a SHA-1 hash, which is now considered cryptographically broken. Support for RSA signatures with the improved SHA-2 hash was added in OpenSSH 7.2 in 2016, with SHA-1 later being deprecated and unsupported by default in the 2021 release of OpenSSH 8.8. This means OpenSSH clients on version 8.8 or newer can’t communicate with OpenSSH servers running version 7.1 or older by default. Other SSH implementations added support for SHA-2 and dropped SHA-1 at different times, adding to the confusion.
Meanwhile, OpenSSH added support for Ed25519 in version 6.5, released back in 2014. This means that Ed25519 has actually been supported for longer than RSA has had a secure implementation, and there are no hash algorithms or specific version constraints to worry about. As long as you’re not trying to connect to an ancient OpenSSH server with a completely insecure RSA+SHA-1 certificate, Ed25519 is actually more likely to work.
The case for ECDSA
ECDSA has similar size and speed characteristics when compared to Ed25519, the main difference for users is that you have to pick a curve and a hash to use with it. The most common choices with widespread support are one of NIST’s P-256, P-384, or P-521 curves. In fact, these are the only curves allowed by the CA/Browser forum’s baseline requirements for public certificates authorities. The P-256 curve with a 256-bit SHA-2 hash offers a similar security level as Ed25519 or RSA with 2048-bit keys.
It’s almost impossible for me to mention these curves, though, without discussing the controversy surrounding them. If you go looking for curve recommendations online, you’re very likely to find someone suggesting that the NIST curves may have been nefariously influenced by the NSA, possibly with the goal of introducing a backdoor. I don’t put much stock into these claims, and cryptography engineer Filippo Valsorda (who maintains the cryptography standard library of the Go programming language) has an excellent post explaining why they are not well-founded. He has even offered up a $12k bounty to anyone who can crack the five hashes used to derive the NIST curves.
Modern signature algorithms in Teleport
First of all, what is Teleport? Our customers use Teleport to solve a wide range of problems:
- They access their infrastructure remotely without passwords or shared secrets, and replace shared credentials in CI/CD systems and workloads with mTLS.
- They eliminate the need for VPNs and enable Just-In-Time Access to web apps, cloud consoles, databases, and more.
Teleport features include:
- An identity-aware access proxy.
- A Certificate Authority (CA) that issues short-lived certificates.
- A unified access control system.
- A tunneling system to access resources behind firewalls.
- Access requests and reviews.
- Integrations with cloud services and tools.
It’s safe to say Teleport generates a lot of keys and makes even more signatures. The performance of the signature algorithm that we use matters a lot, and we refuse to compromise on security.
Teleport has supported RSA 2048 keys since our initial release. Like everyone else, we had to scramble to drop support for SHA-1 when the weaknesses became clear, while juggling the compatibility requirements of different SSH clients and servers we integrate with. We’ve known for a while that we need to migrate away from RSA to something better, but such a change comes with a number of challenges, particularly with regards to compatibility.
After researching the current cryptography landscape and consulting with security experts, we came up with an approach to start using Ed25519 for all SSH certificates and ECDSA for (almost) all TLS certificates going forward.
Starting in Teleport 17, all new Teleport clusters use the new signature algorithms by default. For existing clusters, we decided to make the change opt-in. Teleport provides access to a wide variety of customer infrastructure, and silently changing the signature algorithm and potentially breaking access was too big of a risk for us to take.
Decision fatigue
We know that decision fatigue too often leads to bad outcomes, as we’ve seen with all of RSA’s implementation woes. When we have to make a series of important decisions, each one can feel like a chore and represent a new opportunity to choose wrong. We knew that if we forced Teleport users to choose the signature algorithm for every category of certificate that Teleport issues, each choice with the potential for security and compatibility impact, we wouldn’t be setting them up for success. So we decided to boil all this down to one option we’re calling the “signature algorithm suite”. Teleport cluster administrators can choose a single algorithm suite for their entire cluster based on their needs, and get a suite of signature algorithms that our team has carefully chosen to maximize security, performance, compliance and compatibility. The options today are “legacy” (sticking with RSA), “balanced-v1” (the new default), “fips-v1” (for our customers in regulated government environments), and “hsm-v1” (for customers using our HSM or KMS integrations).
Impact
With the number of different ways that our customers use Teleport, it’s difficult to quantify how much of an impact this change has had on average. One immediate effect we felt was a drastic reduction in the amount of RSA keys we were generating in CI. Before this change, our unit and integration tests were generating 4022 RSA keys per run. This amounted to 962 total CPU-seconds for every single CI run on every pull request, just to generate throwaway RSA keys. Now, these changes didn’t eliminate all RSA keys being generated, and we still intentionally test with RSA because the new key algorithms are opt-in. After flipping the defaults to use the new algorithms, our tests now generate 1557 RSA keys per run - a 61% reduction.
I wanted to find the potential impact our customers might feel from this change in a real Teleport deployment, so I came up with a benchmark where a Teleport server component is generating a lot of keys. This is kind of cheating, since generating new keys is the worst-case scenario for RSA, but I think it illustrates the scale of impact that something as simple as switching key algorithms can have.
There are two cases where a Teleport server may be generating a lot of new keypairs. The first is if a lot of users are logging in to the web UI at once. We create a new TLS and SSH certificate with a unique keypair for each web session, and these certificates are later used to authenticate to Teleport-protected resources. The other case is if users are creating a lot of new database connections. Currently the Teleport Proxy service generates a new keypair and TLS certificate for each database connection that it uses to create a TLS tunnel to the Database service. Because web logins are difficult to automate, I opted to benchmark a case where a user creates many database connections.
Here’s the setup:
- I deployed a Teleport Auth and Proxy service to an EC2 instance to create a new Teleport cluster.
- I deployed a Postgres server alongside a Teleport Database service that would join my Postgres instance to my Teleport cluster so that I could connect to it from anywhere.
- I added a local user to my Teleport cluster with the appropriate permissions for connecting to my Postgres instance.
- I logged in to my Teleport cluster from my laptop and started a script that sustained a constant 10 concurrent database connections, each executing a simple query and then exiting.
I first tested this with my cluster configured to use the “legacy” signature algorithm suite, where all new keys would be RSA. I compared the results after switching to the new “balanced-v1” suite where the new keys are ECDSA. The results were pretty staggering:
- CPU usage on my Proxy dropped from 71% to 16%.
- Average latency to run the full query from my laptop dropped from 1.27 seconds to 0.8 seconds.
Keep in mind, there is a lot more happening in this benchmark than just key generation. Every single one of these database connections was recorded and logged, I can play back every database query that was executed. This demonstrates just how much of a CPU-hog RSA key generation is and why we desperately needed to make this change.
Looking forward
The “v1” suffix on our initial set of signature algorithm suites gives us the ability to introduce new algorithm suites in response to changes in the cryptography landscape, new signature algorithms, and new attacks. For example, since we released these changes in Teleport 17, NIST has published their draft for a Transition to Post-Quantum Cryptography Standards signalling that ECDSA and Ed25519 will both be disallowed after 2035. When quantum-resistant signatures are available and supported for SSH and TLS, the work we did to support configurable signature algorithms will pave the way for us to quickly add support in a backward-compatible way.