The Evolution of Signature Algorithms

Public key cryptography deals with finding mathematical operations for a key pair that are easy to calculate with part of the key pair but hard to reverse without. Such an operation is called the trapdoor function. 

Signature Algorithms use the private key from the key pair and a message in some form as an input to the trapdoor function. The outcome is the signature. Normally, the message passes a hashing function before it gets signed. The signature is easy to calculate using the private key and easy to validate with the public key. Thus everybody with the public key can validate a signed message, verify that it comes from the expected sender (verify the message authenticity) and verify that it was not tampered with (verify the message integrity).

Because of the underlying mathematical operation, it is practically infeasible to create a valid signature without the private key. Further, the private key cannot be recalculated from the public key or any other public information of the system, such as the message, hash value, or signature. However, if used in the wrong context, it is possible to retrieve the private key from signatures or even create valid signatures without it despite the trapdoor function. To avoid such pitfalls and security incidents, it's essential to familiarize yourself with the different algorithms.

RSA

Not many people have had such a significant impact on modern life as Rivest, Shamir, and Adleman. In 1977, these researchers published the description of a public-key algorithm that became known as the RSA algorithm. Even now, about 45 years later, RSA is still widely used.

It's impressive that RSA is still considered relatively safe after so many years. Yet, as great as RSA is, it has its limitations. Over the years, researchers, cryptographers, and attackers have found vulnerabilities and impracticalities in the algorithm (mainly concerning RSA encryption and not the signature). Therefore, it's best practice not to use textbook RSA but rather RSASSA-PKCS1-v1_5 (RS256, RS384, or RS512) or RSASSA-PSS (PS256, PS384, or PS512) for your signatures. These are the versions of RSA that we use in the Curity Identity Server.

The underlying trapdoor function in RSA relies on the factoring problem. There is no efficient algorithm known that breaks an integer in its prime factors. Finding the prime factors becomes especially hard when the integer is composed of two large prime numbers (as is the case in all variants of RSA). However, with processing power getting stronger and cheaper, attacks on the factoring problem are becoming more concerning.

To mitigate the risk of cracked keys, we simply increase the size of the RSA key. This way, it becomes harder and harder to guess the prime factors of the public key, which would further reveal the corresponding private key. However, that strategy comes with a drawback and cost: considering that RSA signatures have the same size as the key, a system using large keys consumes more storage for the keys. It also consumes greater processing power for calculations and bandwidth for transporting the messages.

Practically speaking, we cannot continue increasing the key size indefinitely. This is especially relevant for systems like small Internet of Things devices with limited resources. They simply do not have the capacity to increase the keys. At some point, the processing power will catch up, and RSA keys might be broken before they are invalidated. That is where elliptic curves come into play.

Elliptic Curves

With Elliptic Curve Cryptography (ECC), researchers have found algorithms for signing and encryption that work with small keys and are hard to break. The algorithms are based on a problem called the Elliptic Curve Discrete Logarithm Problem (ECDLP). The trapdoor function in ECDSA is more secure than in RSA, but it makes the algorithm slower.

There is a range of different curves, that is, named sets of defined parameters and formulas. P-256 is one example, Curve25519 another. The security of elliptic curves depends on the characteristics, the parameters, and the formulas of the definition. However, more often, security relies on the implementation details. For example, algorithms for digital signatures based on elliptic curves (ECDSA) require a random, single-use nonce. Consequently, the nonce becomes a weak point. A bad random generator or the reuse of a nonce eventually allows an attacker to calculate the private key — a problem that previously affected YubiKeys and Sony's PlayStation 3.

ECDSA is complex, and it's difficult to correctly implement elliptic curves. If done wrong, elliptic curves may result in a security risk rather than a benefit. For example, the ECDSA implementation in Java had a serious flaw that allowed an attacker to easily forge signatures. In addition, vulnerabilities for side-channel attacks are a known problem in ECDSA. So make sure you select the right curve and a secure implementation when using ECDSA. If in doubt, choose EdDSA if you can.

EdDSA

EdDSA is an evolved version of the elliptic curves Curve25519 and Curve448. A smart combination of parameters and formulas eliminates two main problems with (other) elliptic curve signatures: the requirement for a random nonce and the vulnerability for side-channel attacks. Actually, the latter depends on the implementation and is theoretically possible.

Side-channel attacks are a category of attacks that don't target vulnerabilities of the algorithm itself but of its implementation by analyzing system characteristics such as power consumption, electromagnetic leaks in caches or memory, or timing information. EdDSA uses complete formulas, which means that the rules apply to all points on the elliptic curve. As a result, no edge cases need expensive parameter validation and exception handling. Consequently, EdDSA is easier to implement and less prone to side-channel attacks compared to other elliptic curve signature algorithms.

Nowadays, there are even complete formulas for Weierstrass curves, meaning that it's now easier to implement elliptic curve algorithms. However, the problem with the nonce in ECDSA remains. EdDSA is not dependent on a random number generator for the nonce and is, therefore, more secure. In addition, EdDSA was designed with high performance in mind. Since the keys are small and the operations are fast, EdDSA saves time, money, and resources. As a result, EdDSA is a green computing alternative that reduces the environmental impact of cryptography.

Although the industry now has this progressive technology, some software providers have been slow to adopt it. When switching to EdDSA, you may experience limited support from languages, libraries, and frameworks. However, the Curity Identity Server does not contain such an obstacle. Not only does the Curity Identity Server support EdDSA out of the box, but Curity also provides resources to help you along the way. The right choice should be easy. Choose EdDSA and make a difference for the security and future of your system!

If you want to learn more about signature algorithms and why EdDSA is the optimal choice for securing tokens, watch our webinar - An Engineer's Guide to Signature Algorithms and EdDSA. It is available on-demand.