Editor’s note: This post is part of our series for cybersecurity professionals and hobbyists, written by Tim T., a penetration tester on ExpressVPN’s cybersecurity team.
Since their emergence, digital certificates have played a pivotal role in ensuring the privacy of communications and the authenticity of software and applications.
Digital certificates are how computers know to trust a website, file, or email. Some of the more prominent use cases include the TLS protocol and the practice of code signing. Although there are many different applications for digital certificates, the underlying infrastructure that governs the provisioning and revocation of certificates is largely the same.
This article aims to provide a better understanding of the security considerations behind the public-key infrastructure that supports the digital-certificate ecosystem. We are then able to explore Shamir’s Secret Sharing, a secure method for storing private keys—one that is used by ExpressVPN.
As the threat landscape evolves, with fresh and sophisticated attacks surfacing frequently, this article also explores how security is provisioned across the internet and the areas that can be improved.
Public-key cryptography
To better understand digital certificates, let’s start with some public-key cryptography fundamentals. Each digital certificate contains a digital signature, which is provisioned based on the core principles of public-key cryptography.
Public-key cryptography, also commonly referred to as asymmetric key cryptography, is the concept of using a pair of keys to perform encryption and decryption. Unlike symmetric key cryptography, which only requires a single key, public-key cryptography requires two corresponding keys that are mathematically derived and linked to perform their intended cryptographic functions.
Over the years, cryptographers have devised different methods of generating key pairs. These methods all share the same characteristic, which is that if given a public key, it would be infeasible to computationally derive the corresponding private key. This unique property has allowed public-key cryptography to be used for conducting integrity checks on data through the provisioning of digital signatures. When given a private and public key pair, the private key is used to provide a digital signature, and the public key is then used to verify that signature.
In line with how the keys are named, a private key is meant to be kept securely, with access limited to authorized parties, and its corresponding public key made available to parties that have a need to verify signatures. Assuming that a private key has been kept securely, we can have full confidence on the origin of any piece of information that has been digitally signed.
Digital certificates
Digital certificates contain various pieces of information, with the most important being a digital signature to verify the authenticity of the certificate-issuing authority. The verification process is essentially how we establish identities and trust over the internet. Before we connect to a website or download software/applications, our devices perform identity checks in the background by validating the digital certificates presented. Should this validation process fail, it is common to see warnings flagged out on our devices letting us know that the connection is insecure or the software integrity is not trusted. In terms of a client-server communication model, the onus is on the server to provide a digital certificate for clients to authenticate the identity of the server.
The importance of digital certificates cannot be understated as this is how organizations identify themselves to customers when providing services over the internet. Without the existence of digital certificates, threat actors essentially have free reign on impersonating legitimate entities for nefarious purposes over the internet.
What is a Public Key Infrastructure (PKI)?
The next area to explore is the infrastructure behind the management of digital certificates. Digital certificates are the embodiment of trust over the internet, hence the need to go through a trusted certificate authority (CA) to obtain one. The infrastructure setup by a trusted certificate authority is known as a public key infrastructure and is mainly responsible for the issuing and revoking of digital certificates.
The modern PKI model adopted by trusted certificate authorities is known as the distributed trust model. By design, the root CA, which is the start of the chain of trust, has its own private and public key pair and it signs intermediary certificates which are issued to branched out intermediary CAs. The intermediary CAs in turn have their own private and public key pair and issue signed leaf certificates to entities that present them to requesting clients such as a web browser.
By having the main bulk of the signing responsibility passed on to an intermediary CA, the use of the root CA’s private key is greatly minimized and this helps to preserve the security of the root CA’s private key. In the event of an intermediary CA’s private key getting compromised, the leaf certificates extending from that branch can be easily revoked and the overall impact on the PKI is limited as compared with having the root CA’s private key compromised. Preserving the secrecy of the root certificate’s private key is one of the most important aspects of PKI, as it is the secret that underpins the entire model of trust.
Can we trust the CAs?
Although the notion of a trusted CA provides a certain degree of security, it does not mean that these CAs are not susceptible to having their root/intermediate certificate’s private keys compromised. This is of course likened to a doomsday scenario for the CA as certificates can now be fraudulently issued and misused. The point we have to bear in mind is that these trusted CAs are usually well established with a strong reputation built over years, and this places them right in the crosshair of malicious attackers.
A notable example of such an occurrence is when DigiNotar, a now defunct trusted CA, had their intermediate CA’s private key compromised back in 2011. A certificate issuing server for DigiNotar was compromised and the attackers were able to generate fraudulent certificates. According to this article, a total of 531 rogue certificates were issued for renowned domains such as microsoft.com, google.com and even the domains of government agencies around the world. The post-incident review noted that DigiNotar had in place a mix of virtual and physical safeguards to protect their private keys, but their defences were breached ultimately through an unpatched web server. This gave attackers an inlet to navigate through DigiNotar’s network and eventually worked their way to the certificate issuing server. Speculation over how this could have occurred was rife, with many wondering how the attackers managed to bypass the physical controls. The possible scenarios that were discussed include DigiNotar’s employees negligently leaving access cards in their terminals for prolonged periods of time.
Incidents similar to the DigiNotar case have surfaced sporadically over the years which certainly shows that trusted CAs are not impregnable. Even with the backing of heavy investment into security measures, CAs can still fall foul to cybercriminals. This then leads us to question what more can be done to reduce the chances of these events from occurring.
PKI considerations for ExpressVPN
At ExpressVPN, digital certificates are used in a multitude of areas. For instance, our application and software releases are packaged with a certificate for customers to validate the authenticity of the releases. This is very much in line with code-signing best practices within the technology industry.
Conventionally, the provisioning of digital certificates as described in the section above is handled by certificate authorities and their intermediaries. After much consideration, we decided to go with our very own public-key infrastructure to handle the distribution of certificates instead.
The choice to channel resources behind setting up our very own PKI came with its fair share of risks and challenges, though at the same time gave us the opportunity to shift control of security solely into our hands. Setting up a PKI instead of going through a recognized certificate authority entails both taking on the responsibility of the provisioning and revocation of certificates and also the safeguarding of the root certificate private key. With proper threat modeling and design considerations, the route we have chosen helps eliminate the reliance on a third-party vendor for the security of our products.
Private key safeguarding
Now that we have a baseline understanding of the importance of securing private keys, let’s discuss the methods adopted for securing root certificate private keys. This topic is rarely discussed, and we hope to shed some light on the importance of this consideration.
Prevailing methods
Since the inception of public key cryptography in the mid 1970s, there have been numerous ways devised to safeguard private keys. The de facto methods revolve around the concept of having the private key stored offline in a hardware security module (HSM) such as an encrypted USB drive. Some variations include having the private key stored physically on a piece of paper and having it locked in a secure room with strict access controls.
These methods have proved to withstand the test of time to a large extent, and incidents involving private keys being compromised are few and far between. In theory however, having the private key stored as a whole introduces a single point of failure. In the event of insider attacks, especially from someone with access to private keys, the prevailing methods offer little to no protection at all. Although this scenario is highly unlikely, it is definitely worth taking a look at other possible alternatives which could help mitigate this risk.
Shamir’s Secret Sharing
This is where Shamir’s Secret Sharing enters the picture. Shamir’s Secret Sharing was invented by Adi Shamir, the very same cryptographer who played a key role in the development of the widely adopted RSA public-key encryption algorithm. The generalized idea for Shamir’s Secret Sharing is to split a secret into n number of shares and have them stored separately. These shares are linked together mathematically via a polynomial equation, and reconstructing the secret requires a threshold number of shares to be present.
You can think of each individual share as a piece of a puzzle, but in this case not all the pieces are required to reconstruct the puzzle. As long as you have the threshold number of pieces, you can reconstruct the puzzle successfully.
Let’s give an example using polynomial equations. Going back to the fundamentals of polynomial equations, we recall that it takes k points to define a polynomial of degree k-1. For example:
- Only one line can be drawn between 2 given points ( x1 curve )
- Only one parabola can be drawn between 3 given points ( x2 curve )
- Only one cubic curve can be drawn between 4 given points ( x3 curve )
For any polynomial equation that we choose to define how we split our secret, the split shares will be points on the graph of the plotted polynomial equation. To take a closer look at the mathematical intricacies of Shamir Secret Sharing, let’s attempt to split a secret into 5 shares, but with a threshold of only 3 shares required to reconstruct the secret. Each share will be represented by a point on the graph of the polynomial function and the secret will be represented by the point where the plotted graph intersects the y-axis.
Secret = 1954 , Threshold = 3
The polynomial equation would have to be to the degree of k-1 which is 2
Curve equation: f(x) = ax2 + bx + c
Constants a and b can be random, whereas c will be 1954 as that is going to be where the curve intersects the y-axis of the graph when x = 0. Identifying where the curve intersects with the y-axis is the key to reconstructing the secret. Let’s choose values for a and b as follows:
a = 12, b = 43
f(x) = 12x2 + 43x + 1954
Using random constants as shown above, we would end up with the resulting equation to guide the splitting of the secret into the 5 shares that we desire. For this illustration, these 5 points have been chosen:
x =1, f(1) = 12(1)2 + 43(1) + 1954 = 2009 → (1, 2009)
x =2, f(2) = 12(2)2 + 43(2) + 1954 = 2088 → (2, 2088)
x =3, f(3) = 12(3)2 + 43(3) + 1954 = 2191 → (3, 2191)
x =4, f(4) = 12(4)2 + 43(4) + 1954 = 2318 → (4, 2318)
x =5, f(5) = 12(5)2 + 43(5) + 1954 = 2469 → (5, 2469)
From the graph above, we can see that each of the points lie on the parabola which is the expected shape of a polynomial function with degree 2. The parabola cuts the y-axis at (0, 1954), which is the coordinates of our secret value.
For the premise of reconstructing the secret, we will assume that the exact function of the curve is unknown to us and we are only provided with 3 random shares of the 5 in existence, as 3 is the threshold.
Known variables:
- Share 1, (1, 2009)
- Share 2, (3, 2191)
- Share 3, (5, 2469)
- f(x) = ax2 + bx + c
From the 3 shares available to us, we can form 3 separate equations and attempt to resolve the value for the constant c to retrieve the secret by using the principles of resolving simultaneous equations.
Equation 1: 2009 = a(1)2 + b(1) + c , 2009 = a + b + c
Equation 2: 2191 = a(3)2 + b(3) + c , 2191 = 9a + 3b + c
Equation 3: 2469 = a(5)2 + b(5) + c , 2469 = 25a + 5b + c
Step 1
Equation 1 multiplied by 9 and subtracting Equation 2 from the resulting equation
9a + 9b + 9c = 18081
(9a+9b+9c) – (9a + 3b + c) = 18081 – 2088
Equation 4: 6b + 8c = 15890
Step 2
Equation 1 multiplied by 25 and subtracting equation 3 from the resulting equation
25a + 25b + 25c = 50225
(25a + 25b + 25c) – (25a+5b+c) = 50225 – 2469
Equation 5: 20b + 24c = 47756
Step 3
Use Equation 4 and 5 to eliminate the constant b by finding a common multiple between 20 and 6
60b + 80c =158900 → Equation 4 multiplied by 10
60b + 72c =143268 → Equation 5 multiplied by 3
8c = 158900 – 143268 = 15632
c = 15632/8 = 1954
The secret has been reconstructed and found to be 1954 using 3 random shares. The steps can be repeated with any combination of 3 out of the 5 available shares and your calculations should yield 1954 as the secret.
The example above demonstrates how a secret can be split into shares, with each share given to a different person for safe-keeping. The secret can then be reconstructed when a predetermined number of people provide their shares when required. Thus no one person holds the entire secret, nor can they recover it. The mathematical properties behind Shamir’s Secret Sharing allows it to be malleable for specific use cases as you can choose the degree of a polynomial equation based on the number of shares a secret is going to be split into. For our implementation, we have also gone a step further to have each share encrypted with the share owner’s public key for confidentiality when safekeeping the share.
Compared with the common methods of storing private keys, Shamir’s Secret Sharing addresses the main drawback of having a single point failure. Insider attacks would now require the cooperation of a threshold number of share owners before the private key can be compromised. This applies the same to external threat actors, as the compromise of a single share would not be sufficient to acquire the private key. This added layer of security has given us a higher degree of confidence when issuing digital certificates and our customers can have that peace of mind that the certificates were not fraudulently issued.
The example shown above is merely an illustration of how Shamir’s Secret Sharing works; real world implementations are much more complex, with other factors to consider. Actual implementation of Shamir’s Secret Sharing also involves the principles of finite field arithmetic. If the polynomial equation was plotted over an infinite field, there would be security concerns as an attacker could possibly resolve the pathing of the underlying function and reconstruct the secret without the threshold number of shares. In theory, a polynomial equation plotted on a finite field would end up being more disjointed, which would add to the mathematical complexity of rebuilding the secret without the threshold number of shares.
Final thoughts
Over the years, ExpressVPN has built a sizable customer base, and software updates are being pushed to devices frequently. Safeguarding our products from the threat of attackers targeting our applications as an entry point for propagating malicious software is one of our top priorities. Aside from adhering to industry security standards for releasing software publicly, we also conduct threat models regularly and add security enhancements where we deem fit. Implementing Shamir’s Secret Sharing is one such example where we have assessed that it would provide additional layers of security and mitigate the risks brought upon by existing methods.
As the digital world rapidly evolves, it is also important for us as an organization to review our processes regularly and consider the options available to improve our public key infrastructure. Historically, threat actors have repeatedly devised cutting-edge methods to circumvent the latest security practices, and we should always be on our toes to stay abreast with them. Industry standards can always be improved upon through the amalgamation of different techniques, as this places additional hurdles for threat actors to overcome before a full compromise.
