ZeroWallet: A ZKP based Wallet Authentication Mechanism

How can low entropy passwords be used to secure sensitive private keys? Read ahead!

ZeroWallet is a protocol that uses Zero-Knowledge Proofs to secure private keys with low-entropy passwords. It provides the convenience of brain wallets with a security guarantee comparable to third party multi-sig setups.

Rationale Behind ZeroWallet

To understand why ZeroWallet is different from other services, it is important to consider the strengths and drawbacks of popular wallet recovery protocols. These are discussed below briefly.

Plain Wallets and Brain Wallets

Plain wallets refer to ordinary wallets that use full entropy private keys. These include ones that use a random 256-bit string as a private key or those that use a random combination of 12 seed phrases to secure a wallet. While such wallets have good resistance to brute force attacks, they can be extremely difficult to remember (unless you’re endowed with a photographic memory or are willing to patiently commit seemingly useless information to memory).

Brain wallets refer to those where the private key is generated from a relatively short seed phrase (like a password) which can be easily remembered and recalled. But brute forcing such wallets is especially easy, making them a hard sell even for hot wallets.

Multi-Sig Protocols

Over the past few years, multi-sig wallets have gained popularity as the industry standard for security as far as crypto wallets are concerned. Most multi-sig setups are based on a 2/3 signing scheme i.e. there exist three private keys, of which any two can be used to sign transactions.

With typical services like BitGo or Green Address, one key is held readily by the user, another by the server, and a third ‘backup’ key is stored safely by the user. When a transaction needs to be sent, the user signs the transaction with their private key, before requesting the service to complete the multisig with their server key. The service typically has a scanning algorithm in place that uses a set of parameters to check whether the transaction is legitimate (low value, transfer to known addresses etc.) before signing the transaction and completing the multisig process. In cases like these, the user depends on the service to check whether a transaction is fraudulent. This gives rise to two limitations: (a) the user must make use of the service every time they send a transaction, which exposes them to privacy risks; (b) if the private key is password derived (for easy remembrance), there is a risk of brute force attacks either by a malicious service or any adversary who views the transaction from a password derived wallet to a multi-sig smart contract on the public blockchain.

Threshold Multi-Sig Protocols

To avoid the risk of public brute force (as is the case with password derived multi-sig protocols), threshold multi-sig protocols make use of secret sharing schemes that allow for the recovery of a private key using a threshold number of secret shares.

ZeroWallet — A Threshold Multi-Sig Protocol with Privacy

As an alternative to these services, I created a protocol — named Zero Wallet — which uses a similar 2/3 secret sharing setup as threshold multi-sig protocols without the need to authenticate with the server each time a transaction needs to be signed. I was particularly fascinated by the OPAQUE Password Authenticated Key Exchange (PAKE) protocol, which has been adapted to a cryptocurrency setting in this project. This approach avoids any censorship potential on the part of the third party whilst providing a convenient way for users to recover a private key using only passwords. It should be noted that the low entropy of passwords means that a server brute force attack is still possible, but a public one isn’t. The comparison of ZeroWallet with other wallet recovery protocols is as below:

An Overview of the Product

The solution developed by me consists of a webpage that uses a user name and two corresponding passwords to securely generate a private key which can then be used to unlock a corresponding cryptocurrency wallet.

There are a few points that make this service distinct. Your private key is split into three shares (see fig. below). You always hold two shares (one of your passwords and a backup share). The server holds no share but retains a secret key which can transform your second password into another share. So, with this protocol, you can generate two shares and use them to retrieve your private key on the go.

Splitting your private key into three shares

We make use of Zero-knowledge Proofs to ensure that the server never learns the output of share 2. Share 1 and share 3 are computed client end without server interaction. It should also be noted that the server’s secret key is computed randomly and independently from share 2, making it impossible to derive the share from only the secret key. The protocol is designed such that even though the same username and password combinations result in the same decrypted private key each time, the data transmitted to the server is indistinguishable from random. This means that the server learns nothing even if it collects multiple interactions with the user.

We recognize that storing the private key is risky; instead, the user stores the ‘backup share’. This, in conjunction with their fist password, can be used to recover the private key without the need of the server. However, the private share alone (without the password) reveals no meaningful information about the private key.

Visit the project website at zerowallet.me and view the complete demo at app.zerowallet.me.

Key Cryptographic Concepts

Password Authenticated Key Exchange (PAKE)

PAKE, specifically a type of PAKE called OPAQUE, served as the inspiration for this project. PAKE is an absolutely fascinating method of key exchange that allows authentication with simply a password.

Most server-based authentication schemes involve using a random ‘salt’ value to increase the entropy of passwords. For every user, the server stores a random salt, which is appended to the password, the result hashed and stored on the server. The problem with such a scheme is that (a) the user often sends the password in clear text to the server (this Twitter breach explains the problem with this) or (b) the server sends the user the salt every time a login attempt is made (which means any adversary can retrieve the salt by spoofing a login attempt).

This is where OPAQUE comes in. The protocol makes use of Zero-Knowledge crypto primitives called Oblivious Pseudo-Random Functions (OPRFs) to ensure that the password never has to be sent to the server in clear, and the salt never needs to be handed down to the user. Plus, most of the computation takes place on the client’s end, a plus point for security even if the server is compromised.

With OPAQUE, a client and a server can participate in secure Diffie Hellman Key Exchange with simply a password as a seed. This solution adopts this approach, except instead of carrying out a key exchange, it uses the OPRF construction to securely generate a share which can then be used to compute the user’s private key.

Oblivious Pseudo-Random Functions (OPRFs)

At the core of this solution lies the construction of an Oblivious Pseudo-Random Function (OPRF).

In cryptography, a pseudorandom function family, abbreviated PRF, is a collection of efficiently-computable functions which emulate a random oracle in the following way: no efficient algorithm can distinguish between a function chosen randomly from the PRF family and a random oracle.

A regular PRF has uses two inputs: a key and some data. The output of a PRF is a string that is indistinguishable from random. Oblivious PRFs work much the same way as regular PRFs, except that the key for the OPRF is supplied by one party and the data input by another. The interesting point to capture is that neither party sees the other’s inputs and only one of the two parties learns the result.

The following OPRF implementation is drawn from the OPAQUE protocol and makes use of elliptic curve cryptography:

1. First, users pick a random value r and a password pw.
2. They calculate H(pw), where H represents a one-way hash function
3. They use H(pw) to calculate a point P on the elliptic curve. This point serves as the generator for an exponentiation function.
4. They calculate ∝ = (P)ʳ and send ∝ to the server.
5. The server then calculates β = ∝ᴷˢ where Ks is a random, private value held by the server for each registered user. Ks is the only information stored by the server for each user and is generated upon registration.
6. β is then sent back to the user. The user first calculates m = ModInv(r)and then rw = βᵐ.
7. H(pw, βᵐ) is the randomized output of the OPRF.

A few points that highlight the qualities of this OPRF:

• The password is low entropy, and hence brute-forcing H(pw) would be relatively easy for the server. This is why the hash of the password serves only as a generator point which is multiplied by a large scalar r. Deriving the generator point from the output without knowing the random scalar r is a hard problem.
• Similarly, for the user to calculate the value of Ks from β and the generator point ∝ is hard as well.
• m is the modulo inverse of the random scalar r, which the user can easily compute knowing r. This makes calculating rw easy for the user.
• As rw=H(pw)ᴷˢ and H(pw, βᵐ) is the output of the OPRF, for the same pw, Ks pair, the output of the OPRF is always the same despite the application of a random, different r each time the OPRF is run.

Shamir’s Secret Sharing Scheme

In a secret sharing scheme there is one dealer and n players. The dealer gives a secret to the players, but only when specific conditions are fulfilled. The dealer accomplishes this by giving each player a share in such a way that any group of t (for threshold) or more players can together reconstruct the secret but no group of less than t players can. Such a system is called a (t,n)-threshold scheme.

Shamir’s Secret Sharing Scheme is one such (t,n)-threshold scheme. The scheme relies on the Polynomial Interpolation property that an n degree polynomial can be reconstructed from (n+1) points on the curve of the polynomial.

This (t,n)-threshold scheme is implemented by constructing a polynomial of degree (t-1) and choosing n points on the polynomial as shares to distribute to players.

How it Works

The operation of this service can be broken into three steps.

Step 1: Client-side hashing and OPRF initialisation

1. The user types in their user name (usr), 1st password (pw1) and 2nd password (pw2).
2. pw1, pw2 and usr are hashed. ∝ is calculated based on H(pw1) and a random 256-bit string r.
3. H(usr) and ∝ are transmitted to the server as a POST request.

Step 2: Server-side OPRF

1. The server uses H(usr) to retrieve the random Ks associated with the user attempting to login from a MySQL database. If no such user exists, a random Ks is generated and inserted into the MySQL database.
2. The server uses the Ks to calculate β and send it back as a response to the POST request.

Step 3: Client-side Calculation and Completion

1. The client uses the obtained β from the server to first calculate m = ModInv(r)and then rw = βᵐ. H(pw1, rw) is the final output of the OPRF.
2. It uses H(pw2) and H(pw1, rw) as two shares for a (2, 3) Shamir’s Secret Sharing Scheme. It generates the secret based on these two shares and hashes it to make it a valid 256-bit Ethereum private key.
3. It uses this secret to generate a third secret share.
4. Both the private key and secret share are output, along with corresponding bar codes for easy scanning.

The user can then proceed to unlock their wallet with the private ket and store the secret share safely in case the server ever goes offline and their unique Ks is lost.

Conclusion and Future Possibilities

Hopefully, this tutorial was able to demonstrate the construction and working of a mechanism to use low entropy passwords to secure private keys. As the code demonstrates, the server stores no information that can be used to derive the private key — and in the absence of the user’s passwords, a malicious server would have a very difficult time cracking the two passwords needed to unlock the account.

There are a few aspects of this project I feel could be improved. In this tutorial, I used SHA-256 hashes, which are now brute-forced easily with the help of Hardware ASICs. Instead, a slower hashing algorithm like BCrypt should be used to slow down the attacker’s brute force.

The project, in its current implementation, does not take care of multiple users with the same user name. One idea to overcome this is the use of email-based authentication during the registration process to ensure that multiple people cannot use the service with the same user name/email address.

Rekeying is an interesting avenue to explore. Currently, the user has no way to alter the private key attached to their account without changing their passwords. The service could benefit from the ability to be able to rekey the private key associated with a particular username-password combination.

The reason for two passwords is to improve security; it adds extra entropy to work with. If there was a way to eliminate the second password by somehow limiting the ability of the server to simulate client interactions, the system’s user-friendliness would be increased significantly.

Looking for a more technical explanation? Check out ZeroWallet’s GitHub page for a line by line code explanation in the readme.