PART 2: Genesis of Ledger Recover – Securely distributing the shares

Author: Sandra Rasoamiaramanana, Firmware Engineer - Cryptography at Ledger. Original post here.

Welcome back to the second part of our blog series on Ledger Recover’s genesis! Our goal is to explore the many technical hurdles encountered when building a seed recovery service, and how Ledger Recover solves them with a secure design and infrastructure.

In the previous part, we examined how to backup a Secret Recovery Phrase by splitting it, and how Ledger Recover does it for you using Pedersen Verifiable Secret Sharing.

Now that you have three shares, the next question is: how can you securely distribute them to your backup providers? Indeed, if a malicious party intercepts all the shares while you are transmitting them, it defeats the purpose of splitting the seed in the first place. In cybersecurity, this is called a Man-in-the-Middle attack, where an attacker stands between you and your recipient, and tampers with the communication to try and uncover secrets.

When using Ledger Recover, the transmission of your seed is performed through a secure distribution mechanism. It relies on several cryptographic tools and mathematical concepts that we will explain thoroughly.

We will start by describing the problem at hand in more detail. Then we will introduce several cryptographic tools and mathematical concepts that Ledger Recover leverages to securely distribute your seed shares to backup providers.

Courier-In-The-Middle: A real world example

The most obvious way to protect yourself from an ill-intentioned intermediary is to have none at all. You could walk to your friends’ houses yourself or gather them in the same, closed-off location to deliver the shares. But this becomes much harder if you are not collocated and want to send the shares to a long-distance acquaintance.

Assuming that the network we communicate over (e.g. the postal service) is inherently untrustworthy, how can we guarantee that eavesdroppers never get a glimpse of our secret shares?

It’s time to introduce Alice and Bob, and the infamous Eve, three well-known cryptography personas. Alice has a secret she wants to share with Bob, and has no choice but to send it through Eve, their untrustworthy courier. In cryptographic words, Alice and Bob want to establish a secure communication channel with each other to exchange their secret safely.

Here is what Alice and Bob could do:

• Alice puts her secret in a box, locks it with her personal padlock, before sending it to Bob.
• When Bob receives the box, he adds his own padlock, and sends it back.
• Alice can now use her key to remove her padlock from the box before sending it one last time.
• To finish the process, Bob simply uses his key to remove his padlock and retrieve – at last – the secret from Alice.

All through the exchange, whenever Eve has had the box in her hands, it was always protected, either by Alice’s lock, or Bob’s, or both.

While this is an excellent start, there are several issues left to be solved in this scenario:

• Mutual authentication: Alice and Bob need foolproof ways to check that each padlock genuinely comes from the other party. Otherwise, Eve could swap it with her own box and padlock and fool Alice or Bob into believing she is the other party.
• Forward secrecy: If Eve stole the locked box, and later stole Alice or Bob’s key, she could recover the original secret. Instead we want to ensure that future leaks of long-term keys cannot compromise older stolen packets.
• Preserving privacy: In this scenario, Alice and Bob’s addresses get disclosed to the courier. In the digital equivalent of this process, we want a protocol that does not disclose anything about the recipients.

Securing digital messages

In digital security, a secure channel is a way of transferring data between two authenticated parties such that data confidentiality and integrity are guaranteed. When you use a secure channel, attackers cannot eavesdrop or tamper with your communication.

Ledger Recover’s protocol for both backup and restore is based on a Secure Channel Protocol, or SCP. It uses multiple tools of the modern cryptography toolbox, such as symmetric and asymmetric encryption, certificates, and digital signatures.
The next sections will give you a quick primer on all these concepts, which will allow you to understand the whole security scheme used in Ledger Recover.

Symmetric cryptography: A powerful, but limited tool

To guarantee the confidentiality of the data exchanged between two parties, the data is usually encrypted and decrypted with the same secret key.
This process is referred to as symmetric cryptography, which is the study of primitives that involve a single secret key to guarantee one or more of the properties of a secure channel.

While being a powerful tool to protect your communications, symmetric cryptography has some obvious limitations: Assume that Alice wants to exchange several encrypted messages with Bob. She first chooses a secret key, then shares it with Bob, before starting to send messages.
Of course the problem now becomes: How does Alice share the secret key securely with Bob? If anyone gets hold of the key, Alice and Bob’s communication will no longer be confidential.
Alice could meet Bob in person to give him the key, but in this case why not have their discussion then, away from prying ears?

For digital communications, we need a secure method to share the symmetric key and initiate the protected data exchange. It’s time to introduce the work of two titans of modern cryptography, Whitfield Diffie and Martin Hellman.

Asymmetric cryptography: Hiding your private parts

Diffie-Hellman key agreement

With Public Key Cryptography, Diffie and Hellman came up with a novel approach to securing communications. They defined a protocol with two distinct keys for encryption and decryption. The two keys are commonly called public and private keys, forming a pair which can be used to encrypt/decrypt and sign/verify data.

Public and Private keys
Public key cryptography is the basis of most of our digital security. It is used to protect you on the web, and is also how you prove ownership of coins and tokens on all public blockchains.

Learn more about this topic on Ledger Academy!

What is really compelling for us is how Diffie and Hellman suggested using public key cryptography to distribute symmetric keys. Their method, known as Diffie-Hellman key exchange, consists of back and forth exchanges between two parties to ultimately agree on a shared secret. If performed properly, eavesdroppers are not able to compute the same shared secret from the information they overhear.

The TL;DR is that in the above diagram Eve is mathematically unable to figure out the secret k even though she has access to all of Alice and Bob’s communications. To understand why this shared secret is safe from any eavesdropper, we need to dig into a bit of group theory. 

The security of the Diffie-Hellman key exchange relies on the complexity of the discrete logarithm problem over a cyclic group. A cyclic group is a group generated by a single element.
In a nutshell, Alice and Bob execute the following steps to agree on a shared secret k:

1. Alice and Bob agree on a cyclic group G of order n generated by an element g
2. Alice draws at random a number 0 < a < n and sends ga ∈ G to Bob
3. Bob draws at random a number 0 < b < n and sends gb ∈ G to Alice
4. Alice computes the shared secret k =(gb )a ∈ G
5. Bob computes the shared secret k =(ga )b ∈ G

The security of the protocol depends on the hardness of finding k =ga.b given g, ga, gb. This is called the Computation Diffie-Hellman assumption (CDH). The hypothesis that CDH is hard to solve supposes that the discrete logarithm problem is hard to solve.

In this scheme, while the shared secret is safe from eavesdropping, there is no guarantee on the origin of the data that is exchanged. For the interaction to be secure, Alice and Bob need to somehow prove their identity to each other.

Mutual Authentication and Digital Signature

A handwritten signature is usually used to acknowledge and accept the content of a document. Only the signer is able to produce the signature but anyone who “knows” what the signature looks like can verify that the document has been signed by the right person.

While having similar properties, a digital signature provides additional strong guarantees by leveraging asymmetric cryptography:

• Authenticity: anyone can verify that the message was signed with the private key corresponding to the specified public key.
• Non-repudiation: the signer cannot deny having signed and sent the message.
• Integrity: the message was not altered during transmission.

Now, as long as we know and trust the public key of our correspondent, we can check the authenticity of all messages by verifying their digital signature.
In most real-world cases however, we either do not know our correspondent intimately, or they may need to regularly change their private/public key pair for security reasons. This calls for an extra layer of verification and trust in the form of Certificates, which contain the description of an entity and their public key.

 

Each certificate is signed by a parent public key. By having a Root Certificate Authority (or Root CA) that we always trust, we can create a chain of trust using successive digital signatures.

Elliptic Curves: Next level public key cryptography

Elliptic curve cryptography (ECC) is a subarea of Public Key Cryptography which consists in using elliptic curves for cryptographic applications, e.g. for encryption or signature schemes. 
Based on currently understood mathematics, ECC provides a significantly more secure foundation than earlier public key cryptography systems like RSA.

With the same security level, ECC involves smaller key lengths compared to other asymmetric cryptosystems, which makes it a good choice for embedded systems with limited resources.
If you would like to know more, this article can help better understand Elliptic Curves.

Order of an Elliptic Curve
The order of an element g of a group is an important parameter of the Diffie-Hellman key exchange. When the group is an Elliptic Curve, that element is a point, and its order is the number of times it can be added to itself before looping around on its initial value. Note that this addition has nothing to do with your usual sum over real numbers, but has similar properties of additivity.
Let’s take the Elliptic Curve E: y2 = x3 + 2x + 3 over the field 𝔽97 as an example. As a discrete function, it is represented by the points in the figure below. We will focus on the point P =(3, 6) and all its multiples.

We see that after 5.P, we are back at the beginning and we hit the same points as before. No matter what the value of the scalar P is multiplied by, we will always hit one of our 5 initial points. Thus the order of P is 5, and the subgroup it generates contains exactly 5 points. For cryptographic applications however, the order is way bigger than 5, increasing the randomness.

Mash it all up: ECDH with authentication

We now have all the tools we need to create a great key exchange protocol:  Elliptic Curve Diffie-Hellman (ECDH).

ECDH is a standardized cryptographic scheme that implements the Diffie-Hellman key exchange we described above, by using Elliptic Curve cryptography to generate the key pairs and the shared secret.

It starts by selecting an Elliptic Curve and its generating point. The two parties then exchange trusted certificates, which allows them to verify the authenticity of their respective public keys. Once authenticated, they can generate a shared secret k which is computed as:

k = dA . dB . G
dA: Alice’s Private Key
dB: Bob’s Private Key
G: EC point

To achieve the forward secrecy property, the pair of keys of both Alice and Bob should be ephemeral, i.e. they are generated on the spot and used for a single execution of the protocol. We talk about an Elliptic Curve Diffie-Hellman Ephemeral (ECDHE). In this scenario, the ephemeral keys signed by both the static keys on the device and the HSMs, enabling a strong authentication of the keys. Even if unauthorized access to the static keys were to occur in the future, it would not grant decryption capabilities for the exchanges protected by the ephemeral keys.

Furthermore, we have implemented a notable enhancement to the protocol by concealing the static keys of the devices within the secure channel. This precautionary measure prevents attackers from obtaining visibility on the static certificate of the devices, which, in turn, could lead to the leakage of unique identifiers used during backup/restore operations.

Back to Ledger Recover: A seed’s journey

Alright, time to pause for a minute.

We have covered a lot of topics, pertaining to both security and mathematics, and the result is a protocol to safely communicate over any insecure network. Let’s summarize what we have seen so far:

Two entities can have secure communication over an insecure channel by agreeing on a unique secret thanks to the ECDHE, which is an implementation of the Diffie-Hellman key agreement protocol that uses ephemeral keys to protect forward secrecy. Each entity is able to verify the authenticity of their correspondent thanks to an initial Certificate verification.

In the case of Ledger Recover, we have established four secure channels utilizing the Secure Channel Protocol. These channels connect the device to each of the backup providers and the orchestrator, all of which are equipped with Hardware Security Modules (HSMs).

Each actor holds onto its personal certificate, signed by a Ledger Certificate which acts as the root of the trust chain. When the user’s device first transmits its intention of performing a backup to the Orchestrator, it initiates an authenticated ECDHE. Under these mTLS sessions, the Orchestrator transmits information that will tie future secure channels to the user’s particular backup request, along with the user’s identity that will be requested for validation when performing a later restore of the seed.

Safeguarding secrets with HSMs
As much as we try to avoid it, it is at times required to store and process secrets on servers. This can be risky as protecting servers and their access is a non-trivial task. To mitigate this risk, companies and industries that value security use Hardware Security Modules. They are specialized hardware that protect cryptographic keys and provide cryptographic processing. We will talk more about HSMs in later parts of this blog series.

Everything is ready to finally perform the most critical part of the whole operation: transmitting the three shares of the user’s seed.

Once again, we create new secure channels, but this time between the user’s Ledger device and the Backup Providers’ HSMs directly. The seed shares are transmitted in an end-to-end encrypted channel to their final place of storage, while guaranteeing that they are reaching the correct destination (this is where the verifiability of Pedersen Secret Sharing introduced in part 1 is useful).
The user’s device authenticates the Backup Providers’ HSMs one by one, and the Backup Providers know they are exchanging with the unique official Ledger device that initiated this specific backup request.
No one besides the user’s device and the Backup Providers’ HSMs ever see the seed shares encrypted by these mutually-authenticated secure channels’ symmetric keys, not even the Orchestrator.

Securely received… and stored?

In this part, we have introduced several new concepts, some of which are quite technical. Each one of these concepts is required to establish a secure transmission that guarantees the confidentiality and integrity of the exchange. Regardless of the network’s safety, we can now send our secret shares without fear that they may be tampered with or intercepted. That’s quite the upgrade!

The whole process is backed by sound cryptography and secure hardware, in the form of your Ledger hardware device and HSMs owned by each backup provider.

It is now time to move on to recovering the seed shares! All we have to do is ask the backup providers to send us back the shares that they are storing on their infrastructure…

But wait: How exactly are they storing this very sensitive data? It wouldn’t do us any good if we had the most secure communication channels, but our backup providers were just keeping the shares in plaintext, begging to be stolen.

So before we talk about recovery – we will get there, I promise! –, we have to take a quick detour in Part 3 to discuss the security of our seed shares at rest. Stay tuned!