ECDSA (Elliptic Curve Digital Signature Algorithm)

Backdoors….

Now I’ll discuss on how and why the ECDSA signatures that Sony used in the PS3 were faulty and how it allowed us to gain access to their private key.
So you remember the equations needed to generate a signature.

R = k*G and S= k^-1 (z + d_A*R) mod p..

well this equation’s strength is in the fact that you have one equation with two unknowns ( k and d_A) so there is no way to determine either one of those. However, the security of the algorithm is based on its implementation and it’s important to make sure that ‘k‘ is randomly generated and that there is no way that someone can guess, calculate, or use a timing attack or any other type of attack in order to find the random value ‘k‘. But Sony made a huge mistake in their implementation, they used the same value for ‘k‘ everywhere, which means that if you have two signatures, both with the same k, then they will both have the same R value, and it means that you can calculate k using two S signatures of two files with hashes z and z’ and signatures S and S’ respectively :

S – S’ = k^-1 (z + d_A*R) – k^-1 (z’ + d_a*R)

= k^-1 (z + d_a*R – z’ -d_A*R) = k^-1 (z – z’)

So : k = (z – z’) / (S – S’)

Once you know k, then the equation for S because one equation with one unknown and is then easily resolved for d_A :

d_A = (S*k – z) / R

Once you know the private key d_A, you can now sign your files and the PS3 will recognize it as an authentic file signed by Sony. This is why it’s important to make sure that the random number used for generating the signature is actually “cryptographically random”. This is also the reason why it is impossible to have a custom firmware above 3.56, simply because since the 3.56 version, Sony have fixed their ECDSA algorithm implementation and used new keys for which it is impossible to find the private key.. if there was a way to find that key, then the security of every computer, website, system may be compromised since a lot of systems are relying on ECDSA for their security, and it is impossible to crack.

ECDSA: Public Key Recovery from Signature

It is important to know that the ECDSA signature scheme allows the public key to be recovered from the signed message together with the signature. The recovery process is based on some mathematical computations (described in the SECG: SEC 1 standard) and returns 0, 1 or 2 possible EC points that are valid public keys, corresponding to the signature. To avoid this ambiguity, some ECDSA implementations add one additional bit v to the signature during the signing process and it takes the form {r, s, v} . From this extended ECDSA signature {r, s, v} + the signed message, the signer's public key can be restored with confidence.

The public key recovery from the ECDSA signature is very useful in bandwidth constrained or storage constrained environments (such as blockchain systems), when transmission or storage of the public keys cannot be afforded. For example, the Ethereum blockchain uses extended signatures {r, s, v} for the signed transactions on the chain to save storage and bandwidth. Public key recovery is possible for signatures, based on the ElGamal signature scheme (such as DSA and ECDSA).

Comparing ECDSA vs RSA

ECC provides a way of exchanging encryption keys (which is hugely necessary on the Internet these days), and it does it much more efficiently than RSA. This allows for lower CPU utilization, less memory usage, faster key generation, faster certificate processing, etc. The following table shows a comparison between RSA key sizes and ECC key sizes that provide the same level of security.

Notice a couple of things. First, the key size for ECC is significantly smaller than that of RSA for the equal level of security. Second, the key size for RSA gets proportionately much larger as increased strength is needed compared to ECC. For example, if you want triple the level of security for RSA, you have to triple the key size (1024 to 3072). But, for ECC if you want triple the level of security, you only have to increase the key size by 1.6 times (160 to 256). These are the primary reasons ECC is so desirable in web application security today.

Parameters	RSA	ECDSA
	1024	160
secp192kl	1536	192
secp192rl	1536	192
secp224kl	2048	224
secp224rl	2048	224
secp256kl	3072	256
secp256rl	3072	256
secp384rl	7680	384
secp512rl	15360	512

The downside

It is not all roses in the world of elliptic curves, there have been some questions and uncertainties that have held them back from being fully embraced by everyone in the industry.
One point that has been in the news recently is the Dual Elliptic Curve Deterministic Random Bit Generator (Dual_EC_DRBG). This is a random number generator standardized by the National Institute of Standards and Technology (NIST), and promoted by the NSA. Dual_EC_DRBG generates random-looking numbers using the mathematics of elliptic curves. The algorithm itself involves taking points on a curve and repeatedly performing an elliptic curve "dot" operation. After publication it was reported that it could have been designed with a backdoor, meaning that the sequence of numbers returned could be fully predicted by someone with the right secret number. Recently, the company RSA recalled several of their products because this random number generator was set as the default PRNG for their line of security products. Whether or not this random number generator was written with a backdoor or not does not change the strength of the elliptic curve technology itself, but it does raise questions about the standardization process for elliptic curves. As we've written about before, it's also part of the reason that attention should be spent to ensuring that your system is using adequately random numbers.

Some of the more skeptical cryptographers in the world now have a general distrust for NIST itself and the standards it has published that were supported by the NSA. Almost all of the widely implemented elliptic curves fall into this category. There are no known attacks on these special curves, chosen for their efficient arithmetic, however bad curves do exist and some feel it is better to be safe than sorry. There has been progress in developing curves with efficient arithmetic outside of NIST, including curve 25519 created by Daniel Bernstein (djb) and more recently computed curves by Paulo Baretto and collaborators, though widespread adoption of these curves are several years away. Until these non-traditional curves are implemented by browsers, they won't be able to be used for securing cryptographic transport on the web.

Another uncertainty about elliptic curve cryptography is related to patents. There are over 130 patents that cover specific uses of elliptic curves owned by BlackBerry (through their 2009 acquisition of Certicom). Many of these patents were licensed for use by private organizations and even the NSA. This has given some developers pause over whether their implementations of ECC infringe upon this patent portfolio. In 2007, Certicom filed suit against Sony for some uses of elliptic curves, however that lawsuit was dismissed in 2009. There are now many implementations of elliptic curve cryptography that are thought to not infringe upon these patents and are in wide use.

The ECDSA digital signature has a drawback compared to RSA in that it requires a good source of entropy. Without proper randomness, the private key could be revealed. A flaw in the random number generator on Android allowed hackers to find the ECDSA private key used to protect the bitcoin wallets of several people in early 2013. Sony's Playstation implementation of ECDSA had a similar vulnerability. A good source of random numbers is needed on the machine making the signatures. Dual_EC_DRBG is not recommended.

Even with the above cautions, the advantages of elliptic curve cryptography over traditional RSA are widely accepted. Many experts are concerned that the mathematical algorithms behind RSA and Diffie-Hellman could be broken within 5 years, leaving ECC as the only reasonable alternative. Elliptic curves are supported by all modern browsers, and most certification authorities offer elliptic curve certificates. Every SSL connection for a CloudFlare protected site will default to ECC on a modern browser. Soon, CloudFlare will allow customers to upload their own elliptic curve certificates. This will allow ECC to be used for identity verification as well as securing the underlying message, speeding up HTTPS sessions across the board. More on this when the feature becomes available.

Real Life Curves

Remember how I mentioned that you shouldn’t create an elliptic curve on your own because it probably wouldn’t actually be secure and efficient? Well, the good news is that other really smart people have already created a bunch of curves for you. The National Institute of Standards and Technology (NIST) has developed five recommended “prime” curves called: p192, p224, p256, p384, and p521. Other curves are also recommended by Certicom in the Standards for Efficient Cryptography (SEC2) in which the curves are named secp192r1, secp224r1, secp256r1, secp384r1, secp521r1.

With any of these curves, a good random number generator is needed to provide proper security. It’s interesting to me that all these curves and sophisticated cryptography is in place only to fully rely on the need for a quality random number generator. Be sure your cryptosystem is using a good one!