Try   HackMD

Identity is the Key

or: what I learned from working on decentralized identity and some future research directions

Intro

I have worked in ZenGo, a crypto wallet company, for several years. My role was to explore and expand the boundaries of key management for wallets, that is, the custody, safe usage, and applications of permissionless, ledger-based, crypto-currencies. Recently, I started looking at the design principles of a somewhat related kind of system for self-sovereign identity, or as I will refer to it in this blog - decentralized identity (DID).
My initial instinct was to apply the familiar frameworks of crypto wallets, yet quickly I realized that there is much more to DID systems: despite similarities at the key management level, there are in addition many unique features to DID.
In this write-up, I will try to account for my humble journey going from a crypto wallet to a DID system, while uncovering some new, at least for me, research questions in DID.

The Rabbit Hole

In September 2021 I was supposed to present my work on DID recovery using a timestamping service in the Future of Personal Identification workshop (FoPI). The paper was accepted after shepherding and later I withdrew it.
Why?
The first signal for me was a reviewer that offered an alternative protocol that is supposed to be simpler and safer than the one I presented in the paper. It took me a lot of time and sweat to explain why the two ideas differ and mine is better. I was not fully convinced. I, therefore, decided that in my talk I will present both ideas. Still, I wasn’t satisfied, so I decided to dig further. Two books and one project later I found out that my “simple” protocol was not novel as I thought. For sure, it was reassuring to learn that I rediscovered a valid and strong idea. But to my dismay, I also neglected many details in my protocol and model, rendering my work incomplete. At that point, for the first time in my life, I withdrew a paper.

With this out of the system, I asked myself: what DID (😉) I learn?
To answer,Let's start with taking one step back.

What is DID?

I will be honest, I have no good definition for decentralized identity. When trying to reason about DID my first reaction was to try to think of a simple model that will capture the high-level idea. In my original model, I had two kinds of actors: Users and Nodes. The Users represent physical owners of identities. The Nodes represent a network, responsible for message transfer between users. In practice, the nodes can be implemented using some hierarchical structure with different types of nodes and routing, or just a blockchain :)

What can be achieved when connecting owners of physical IDs in a network? Quite a lot!

  • Crypto-wallet: we can bind the ID to a unique wallet address and let IDs transact. We will touch more on this later

  • Verifiable credentials: an ID can issue statements attesting to some physical/digital property of another ID (aka a credential). On the other hand, an ID can present proof for some credential given to it by another ID. Simple example:

    ID1 represents a city, giving a certificate with a social security number to
    ID2    .
    ID2     can later prove it was issued a social security number to
    ID3

  • Storage. In the broader sense. an ID can encrypt any data using a unique key and define an access policy to let different IDs access (decrypt) different parts of the data. Take for example

    ID1 that encrypts its user owner's credit card number. The user goes on to buy groceries at Walmart. When the user finishes the user gives time-sensitive read permissions to Walmart ID.

This is just the tip of the iceberg. What if we allow some “partially” trusted parties into the model? What about group IDs? Personally, my opinion is that DID can impact almost any aspect of our life.

DID cryptography

All of the goodness we mentioned above comes with a price: it requires sophisticated cryptography. Naively, my first thought was to use crypto-wallet keys for DID. As part of a wallet setup, a key generation protocol is run. After keygen, the wallet owner has a secret key and public key - perfect to represent identities. For example, statements can be issued and verified on the blockchain using digital signatures. Encapsulating DID inside a crypto wallet is fantastic because it gives us off-the-shelf solutions for important key management problems such as key recovery and key refresh.
Sadly, this idea will likely not work. For once, in DID we need secret keys both for encryption (e.g. storage permissions) and for signing (e.g. wallets, credentials, certificates). It is unclear if the same key can be used both for encryption and signing. Some research was done on the topic but nothing specific. Second, the meaning of key as identity opens up questions about the meaning of certain protocols in this context, for example, while in crypto-wallet you can simply refresh your key by sending funds to a new address from the old address (and some more advanced options using threshold cryptography), it is unclear how to do a key refresh for DID, what happens with the old ID - is it still valid?

More cryptography

Some of the applications described above may be secure only if we use nonstandard public key cryptography. To name a few examples: Permissions system for decrypting segments of a ciphertext sounds a lot like something that will require identity/attribute-based encryption (ABE), perhaps functional encryption (FE) is also relevant. Verifiable credentials may be used with zero-knowledge (ZK) proofs for anonymity. Crypto-wallets are no stranger to advanced cryptography. Threshold wallets based on threshold keygen and threshold signing became a popular way for key management in recent years. DID can benefit from threshold cryptography but will require even more cutting-edge cryptography to unlock its full decentralized potential.

Case study: DID Recovery

It was easiest for me to start my DID journey with a well-familiar problem: secret key recovery. At ZenGo, I spent years on this problem which gave me enough tools and confidence to approach it under the context of DID. To further simplify the problem, I assumed DID is based only on a single secret signing key. Using the secret key, the identity holder can issue statements (digital signatures) that are verifiable using the ID public key.

The threats that may trigger a DID key recovery are two-fold:

  1. The Key is lost → identity becomes inactive (ghost)
  2. Key is stolen → attacker now controls the identity

Our requirements from a recovery scheme thus are:

  1. Create a new secret key
  2. Revoke the old secret key - should happen atomically with 1
  3. The new secret key should continue to represent the same ID

As specified before, this is a rather unique set of requirements. I surveyed key management systems (KMS), both in production and in literature, and was surprised to not be able to find an existing KMS that can be both described using my general model of Users and Nodes and fully satisfy the above requirements. Let me give you 3 examples from 3 different applications. In appendix A I provide a more complete description of the systems :

KMS used for Backup/Recovery concept
Tor.us Password management Shamir Secret Sharing of the secret key + Distributed (encryption) Key Generation
CanDID DID MPC between nodes (called committee). ID is managed by the committee
Signal Communication User PIN/password. Node assistance required. Each node runs a TEE that must be in Consensus with other nodes

The examples above are state of the art, each from a different lineage but overall converges nicely in the properties they offer as KMS. We found that in all three, and other KMSs as well, ZenGo (crypto-wallet example) included, the case of recovery from a key theft is not well defined or missing. This is subtle. Good KMS makes it harder for attackers to get full access to the key. If an attacker penetrated the system security, it is understandable that whatever was protected by the secret key (e.g. money) is now lost and the system needs a reboot - meaning, recovery is useless. This is not the case for DID. Identity theft must be handled, otherwise, the User loses her identity, which cannot be replaced. We note that CanDID, the only KMS listed above that is designed for DID, mentions identity theft in the paper along with some informal discussion on mitigation.

Lesson learned and what can be done from here

As I already stated, this is not a story with an ending, just a snapshot in time.
I challenged myself to come up with a solution for the DID recovery problem above. My first solution required: distributed key generation (DKG), threshold signatures scheme (TSS), and biometric threshold authentication. Biometric authentication seems the most natural approach in the context of decentralized ID as biometrics are unique physical identifiers. In Appendix B I provide some more background on biometric authentication.
This first attempt required complex cryptography. Something we often wish to avoid. My next attempt was to slightly expand my basic model to trade off the cryptography with simpler methods. I ended up introducing a notion of time, leading to my time-stamping-based recovery idea. I later found out that I re-discovered ideas from an existing protocol. In the process, I noticed that by making subtle changes in the model, we can enable powerful concepts in the system, e.g. by allowing small out-of-band channels between users, we can bring up the notions of social recovery and web of trust.

Concluding

Looking forward, I am a believer in a unified approach to key management - DID seem to be closest to a “complete” KMS: a digitally unique identity that is managed in a decentralized manner may provide a root for all other sensitive systems that connect the physical us to digital and physical assets. In the last few years, there has been a healthy body of research involving key management systems. Reactive Key-Loss Protection and Paralysis proofs to name a couple of emerging ideas around recovery alone. I will not be surprised if the foundations of DID key management will be based on the work done today for popular KMS such as crypto-wallets.

Appendix A

Here I give details on some key management systems that we mentioned in the blog :

Tor.us

Torus provides a secret-sharing based approach to key management:

  • A user generates a secret key
  • User secret-shares the key using Shamir secret sharing. A common scheme is 2 out of 3
  • The user keeps one share locally on his device
  • A second share is used for backup and can be stored on another offline device.
  • This share can be user-generated with entropy coming from security questions
  • The third share (in torus docs this is the second) is encrypted by the user and stored in a storage layer.
  • The encryption key is generated using distributed key generation by torus nodes.
  • The nodes generate these keys preprocessing and assign them to users based on Oauth login authentication (e.g. google authentication)
  • The secret key can be refreshed

The essential parts of Torus' approach can be described using our simplified model. However, we claim that torus approach is not optimal against key theft:

  1. A persistent attacker will wait for the key owner to recover the key from the shares and then steal it. This will happen each time the owner wants to use her key
  2. Once an attacker gets access to the owner device (she will immediately get access to the first secret share and) it is with high chances she will be able to access one of the other secret shares and recover the secret key:
    a) For the third share that requires web2 auth: this is because the user will likely be already logged in to most online services that require authentication (e.g. when was the last time you authenticated to Gmail/Twitter/Facebook on your mobile).
    b) For the second share: torus is not clear how this share is protected: using security questions (e.g. name your mother last name before marriage) might prove easy to crack

CanDID

Candid is an academic work that aims at the practical deployment of decentralized ID. The system bootstraps using existing identity infrastructure. The actual identity is managed by a committee of nodes, running MPC. Key recovery is relying on the same committee and existing infrastructure as well:
Roughly speaking, the committee will identify the user based on an MPC of a pseudorandom function that takes as input the user credentials from web2 authentication providers and the committee distributed key. The user will secret-share her secret key. The committee members will store the shares with the unique identifier. Recovery simply requires the user to provide web2 auth as secret input to the MPC, from which an identifier can be computed which the committee members use to retrieve the correct secret shares of the secret key to the user.
We first note that using a centralized service to recover is done also in Tor.us, as discussed above. We believe Tor.us improved over CanDID in this aspect as tor.us can recover without centralized authentication providers in case it needs to, which provides a higher level of decentralization.
In CanDID all statements are issued by the committee. If a master context credential does not contain enough attributes, a new context credential is issued, bound to the master credential in a privacy-preserving manner. Because there is still a single master credential managed by the user, an attacker can compromise the system by stealing the master credential from the user. This kind of identity theft is mentioned in the paper along with some informal discussion on mitigation: having the ID owner issue a new master credential with more attributes than the stolen one. This solution and in general identity theft is missing a formal analysis.

Signal

Signal is a messaging platform native to mobile with a focus on privacy. In particular, the Signal server holds only encrypted user data. This means that the server cannot assist in the case of backup. The responsibility of account backup and recovery is in the hands of the user itself. Signal uses the following method:

Backup:

  • The user picks a password or Pincode
  • The password is stretched using a KDF
  • The resulted key is used in HMAC-SHA256 to output auth-key
  • The resulted key is used in another HMAC-sha256 to output a key c1
  • HMAC-SHA256 is used with key c1 and random string c2 to output master-key
  • HMAC-SHA256 is used with key master-key to output application key
  • C2 is being sent to Signal server

Recovery :

  • The user uses his password to recover the auth_key and c1
  • The user uses his password to contact the server and recover c2
  • The user uses c1,c2 to recover the master_key

The Signal recovery system is described here. A strength of this system is that it relies on a short easy to remember pin/passphrase for recovery. To make sure an attacker is not able to brute force the pin/passphrase Signal server cleverly enforces a limit on the number of calls to the server to get c2. This eliminates brute force attacks however it requires heavy engineering to safely implement this mechanism which is based on SGX (secure enclave) + RAFT (consensus protocol) + some tricks.
The Signal solution is not handling the case of pin/passphrase theft. On the contrary, because the PIN can be very short, it should be very easy for an attacker to steal it, e.g. capture a recording of the user inputting his PIN.

Appendix B - biometric security

Biometric data is valuable for authentication because as opposed to passwords, it can never get lost. On the other hand, it can get stolen. Even worse, once stolen, it cannot be replaced by the owner, same as what we expect from passwords. Therefore it is crucial to maintain a high level of privacy around biometric data. Ideally, we would like to have an authentication system such that only the biometric data owner is dealing with the raw biometric data and all the other participants should be able to only learn one bit of yes/no authenticated user. This turns out to be a difficult challenge. The reason is simple: in a closed system, the biometric data must be accessed at least once for each authentication request. It means that some participants will have to expose the existing data (template) and new data and match it. To minimize risk as much as possible, modern systems that use biometric authentication are doing the matching client side. The server that requested the authentication will send a fresh token that will be signed by a key that is accessible only if the client passes local authentication. This approach requires secure hardware on the device, which is something we cannot assume in our model (as opposed to Apple for example who manufactures the iPhones and controls the hardware). The other option is that the “server-side” will have access to the biometric data. In this case, there is a potential risk even for data at rest because even if encrypted, the server must have access to the decryption key, therefore the attacker's job is only slightly more involved. To solve this problem there are several theoretical and even some practical ideas, all based on advanced cryptography. Here we present two ideas:

  • Anonybit is a company that developed a way to dissect the biometric data and distribute it across a network of many nodes. Each node will run its matching on a segment of the data. Authentication requires a large portion of the nodes to approve. This solution makes sure the biometric data is never at one place, not while at rest and not while at use.
  • BETA: Biometric Enabled Threshold Authentication: This work led by VISA research is one of the latest in a line of works that aspire to achieve privacy by running the biometric matching computation over encrypted data. In this particular paper, MPC and homomorphic encryption are utilized to compute specific relevant math functions in a threshold setting that can sustain a high number of corruptions.
Last changed by 
 
Omer Shlomovits
1
5
1698

Read more

Hardware-friendliness of HyperPlonk

In this note we provide the hardware perspective on HyperPlonk. We focus on the main building block, the Multivariate SumCheck protocol and compare its computational and memory complexity to that of an NTT (Number Theoretic Transform). Background - HyperPlonk Plonk is one of the most widely adopted SNARKs in the industry. In vanilla Plonk after arithmetization, the resulting execution trace is interpolated into univariate polynomials and thus the resulting protocol relies heavily on NTTs. HyperPlonk is a new adaptation of Plonk, where the execution trace is interpolated on a boolean hypercube. Thus the polynomial representation of the trace is a multivariate polynomial with linear degree in each variable. This is known as an MLE (MultiLinear Extension). A good overview of Hyperplonk can be found in Benedikt Bunz ZKSummit8 talk. One key advantage of HyperPlonk is the elimination of large NTTs, a major computational bottleneck in Plonk over large-circuits. By moving to the boolean hypercube, we no longer need univariate polynomials. Instead, HyperPlonk relies on multivariate polynomial arithemetic. Section 3 in the Hyperplonk paper is devoted to developing the toolbox for working with multivariate polynomials. The figure below, taken from the paper, shows how HyperPlonk is built out of this toolbox. As can be seen, at the root of it all we have the classical SumCheck protocol, which is bound to become the main computational problem in HyperPlonk (polynomial commitments aside), replacing NTTs all together. Sumcheck in HyperPlonk A toy example Consider an execution trace unrolled in the form of a vector. We illustrate the general idea using a vector of length $8$, constituted of the polynomial evaluations $\left{ f_{i}\right} _{i=0}^{7}$, where $f_i\in \mathbb{F}$. We interpolate these values using a multivariate polynomial $F(X_3,X_2,X_1)$ as follows

Dec 28, 2022
"Alpha-Rays" behind the scenes

In a recently published paper, we describe two attacks on threshold ECDSA implementations. The uniqueness of the attacks is that they are rooted in issues found in the protocol itself. We hereby describe the events that surrounded the discovery, handling, and patching of the impacted code. Intro March 1, 2018. Ariel Gabizon, a cryptographer employed by the Zcash Company at the time, discovered a subtle cryptographic flaw in the BCTV14 paper that describes the zk-SNARK construction used in the original launch of Zcash. This vulnerability is so subtle that it evaded years of analysis by expert cryptographers focused on zero-knowledge proving systems and zk-SNARK. The vulnerability could have allowed for infinite counterfeiting. October 1, 2021. GG18, a paper published in CCS 2018, described a protocol for t out of n threshold ECDSA. This protocol, together with a follow-up work by the same authors, GG20, became a popular choice for implementation by many custody operators and protocols, securing equivalent of billions worth of USD. Moreover, cited more than 100 times and considered the first practical multiparty ECDSA protocol, GG18 is a cornerstone in the evolution of threshold ECDSA protocols. As a result, the paper has gone through intensive peer review and multiple independent audits, receiving the attention that only a select few papers, that ever crossed from academy to industry, get. While implementation bugs, some critical, had been found in the wild, GG18 construction remained flawless. Until now. What we have found

Dec 18, 2021
FS-DKR: One Round Distributed Key Rotation

Intro In this note we aim to re-purpose the Fouque-Stern Distributed Key Generation (DKG) to support a secure Distributed Key Refresh (DKR). As we claim, FS-DKR is well suited for rotation of threshold ECDSA keys. Background The FS-DKG protocol is a one round DKG based on Publicly Verifiable Secret Sharing (PVSS) and the Paillier cryptosystem. There are two major security shortcomings to FS-DKG: It introduces a factoring assumptions (DCRA) it is insecure against rushing adversary Rushing adversary is a common assumption in Multiparty Computation (MPC). In FS-DKG, an adversary waiting to receive messages from all other parties will be able to decide on the final public key. In the worst case it can lead to a rouge-key attack, giving full control of the secret key to the attacker. This is the main reason, in our opinion, why FS-DKG, altough with prominent features, was over-looked for the past 20 years.

Aug 29, 2021
Read more from Omer Shlomovits
Published on HackMD