New Explorations in Secret Recovery

Microsoft

Jun 17, 2020

Hi everyone - I'm excited to have Daniel Buchner (one of my team members who works on Decentralized Identity) talk about an initiative we've been working on, in partnership with Microsoft Research, to help advance user-friendly recovery of cryptographic keys and identity data.

Cheers,

Pamela

------

The rise of cryptographically secured decentralized systems has excited a new generation of users, developers, and businesses about applications that can radically change our daily lives. While it’s easy to get caught up in what could be, our work on decentralized identity is motivating us to tackle tough challenges (some decades old) that hinder adoption.

We believe empowering users with ownership and control over their digital identities could better the lives of everyone on the planet by unlocking new applications and services that are more private and secure. As we strive to realize this ideal, the decentralized systems we’re leveraging face many of the same challenges users, developers, and businesses in the cryptocurrency ecosystem have struggled with in the decade since Satoshi’s first transaction on Bitcoin.

One of the more significant challenges of these decentralized systems is their reliance on users retaining private keys and other secrets to realize the unique benefits they provide, as is the case with owning and controlling a Decentralized Identifier (DID). The long-standing problem of users retaining cryptographic secrets has led to the adoption of several schemes (largely driven by the cryptocurrency community) that attempt to provide a somewhat better experience than raw private key retention. Software and hardware wallets use two primary recovery schemes today: BIP 39 mnemonic phrases and Shamir Secret Sharing constructions. In the next section, we’ll shed light on how these two commonly used schemes work before contrasting them with the scheme we’ve been working on.

Recovery schemes commonly used today

Mnemonic phrase schemes (e.g., BIP 39) generate a set of 12-24 randomly selected words from a corpus that form a secret seed. While these mnemonic schemes map an unmemorable secret to words, affording some degree of memorability and human error correction (e.g., illegibly written words can be deduced), successful regeneration of the secret requires the user to produce all the words in their exact form and order. These requirements make mnemonic schemes rather unwieldy in practice.

Mnemonic phrase schemes result in the following feature profile (green = positive, red = negative):

Shamir secret sharing schemes use polynomial interpolation as a basis for dividing a secret into N shares, wherein some subset threshold of T shares must be recombined in any order to regenerate the secret. The user can distribute the resulting shares in different ways, for example, storing shares on different devices, hiding paper printouts of shares in different physical locations, or sending shares to a set of collaborators for future retrieval. Typically, this scheme is used for what’s known as ‘social recovery’ models, where you use an app to distribute shares to selected friends or contacts. While this common secret sharing scheme affords the user some flexibility by only requiring them to reproduce a subset of shares, in any order, the shares themselves are long, cryptographically random strings, which makes human recollection of shares impossible.

Shamir secret sharing schemes result in the following feature profile (green = positive, red = negative):

Both schemes provide various advantages over simply attempting to remember or store long, unmemorable secret strings of random numbers and letters, but the approaches come with almost diametrically opposed trade-offs. With mnemonic phrases, inputs are words, which increases memorability, but users must correctly reproduce all words in the exact order in which they were generated. Secret sharing schemes, on the other hand, only require the user to reproduce a threshold subset of shares, in any order. Unlike mnemonic phrases, however, the shares are long, random strings of letters and numbers, not words or other human-friendly inputs.

Venturing beyond the status quo

The Standards & Open Source team in Microsoft's Identity division has been working with cryptographers in Microsoft Research to explore schemes that can deliver the desirable features of both schemes described above in a single mechanism. Our goal is to enable users to encrypt a secret with a wide, flexible array of N inputs (words, images, etc.) and recover their encrypted secrets using only a T threshold subset of those inputs. We also want to include all other desirable features and characteristics from the schemes in use today. Ideally, the scheme we produce should exhibit the following feature profile:

I’m excited to share our first output of this exploration: a whitepaper describing our construction of a ‘Fuzzy Vault’ scheme that fulfills the feature requirements listed above. Esha Ghosh and other contributors from Microsoft Research developed the construction and subsequently produced a working implementation internally at Microsoft. Along with the whitepaper, we’re announcing our commitment to developing an open source implementation of the scheme in the Decentralized Identity Foundation, based on the white paper you can read here: Fuzzy Encryption.

The ‘Fuzzy Vault’ construction we developed relies on elements of schemes previously described in literature. This encryption scheme uses polynomial encoding to generate an encrypted payload of secrets (or other data) using a set of selected inputs, requiring only a subset to decrypt the payload. The scheme provides information theoretic security similar to that of Shamir secret sharing, and incorporates the following features and attributes:

It’s an encryption scheme – unlike a BIP39 mnemonic, the scheme isn’t a direct representation of a seed/key. Since it actually encrypts data, it can protect more than just private keys. This means the scheme includes a two-factor assumption, where an attacker must not only guess the correct inputs, but also possess the encrypted file to use them.
Inputs can be anything – you can use a traditional word-based corpus (Diceware’s 7776 word list) and randomly select from it, or create your own corpuses composed of any mix of stringifiable values, like words, images, GPS coordinates, etc.
It tolerates an error threshold – unlike a BIP39 mnemonic, you don’t need all inputs to decrypt the encrypted vault file. The scheme supports the same threshold feature as Shamir secret sharing schemes. For example, you may configure the scheme to select 16 inputs and set a threshold of 4 errors, meaning only 12 of the inputs would be required to decrypt the vault file.
Inputs are order agnostic – unlike a BIP39 mnemonic, you don’t need to recombine inputs in the same order in which they were generated.
It supports enhanced social recovery – the scheme can still be used in ‘social recovery’ implementations, but the shares can be human-friendly inputs, which makes it easier for share recipients to retain them.

To get a sense of the entropy hardness the scheme produces, assume you used the scheme to encrypt secret data with 20 randomly selected words from the EFF Diceware Long List of 7776 words and set a threshold tolerance of 5 errors (meaning 15 of the 20 words are required to decrypt). Under this configuration, the scheme would produce an encrypted payload with 90 bits of security, which is outside the attack range of any known computational system.

We’d like to thank everyone in DIF, the wider Identity community, and the cryptocurrency ecosystem who have highlighted the critical need for user-friendly secret recovery. Please join us in DIF and contribute to our open source effort to address the ecosystem-wide challenge of secret recovery.

Daniel Buchner
Decentralized Identity / Microsoft Identity