Use of a third party to unlock the maker's trade reserve

[stejbac]

This is a Bisq Network proposal. Please familiarize yourself with the submission and review process.

The Bisq app currently allows the user to encrypt their wallet with a password, which is stretched to a temporary AES key and used to encrypt their seed phrase and private keys, avoiding them being stored to disc in plaintext. However, since access is needed to the maker's wallet to fund trade deposits when they are away from their machine, it needs to be kept unlocked by holding the AES key in RAM throughout the lifetime of the Bisq instance, weakening the user's security.

We could improve things a little by only holding the unencrypted EC key of the trade reserve UXTO and forgetting the wallet AES key at rest, but that still puts some of the maker's funds at risk. It also does not interact well with #265, which would do away with the maker fee tx and would thus requires a bunch of EC keys to be held unencrypted (of some current wallet UXTOs and reserved change addresses), putting a potentially much larger pool of wallet funds at risk.

This proposal describes a way to hold a maker's EC key in an encrypted state, using a long term public key (say an RSA key) belonging to a third party server. When the time comes to sign a deposit tx + delayed payout tx when someone takes the maker's offer, the third party is used to authorise access to the required encrypted EC keys, conditional on what exactly is being signed. This isn't done by simply sending the EC key to the third party to decrypt, as that would give them custody over (some of) the user's funds, putting an inappropriate amount of trust in them. Instead, a special kind of secure 2-party computation is done which allows neither the maker's computer nor the third party direct access to the unencrypted EC key at any point, and so that they individually learn nothing about it.

Only collusion between a compromised maker's computer and the third party could expropriate the funds, with the third party on its own only having the power of veto. Moreover, when the maker returns to their computer they can unlock their wallet with their password as before, without involving the third party, thus they have strictly better security than before and retain full custody over their funds at all times.

Details of a possible cryptographic scheme

To protect a given EC key e when the maker is away from their machine, the wallet is first unlocked with their password to give direct unencrypted access to it. (The maker's computer is in a trusted state at this point.)

Initial EC key encryption

We take a fresh random number e₁ from the field GF(N) of integers modulo N, where N is the secp256k1 elliptic curve order, and compute:

e₂ = e - e₁

e₁ will be the (untrusted) maker's computer's EC key share and e₂ will be the third party's EC key share, when the time comes to sign a tx. Note that individually they tell you nothing about e and there is no interaction with the third party at this point.

We tag e₂ with optional auxilliary data D, specifying any extra ad-hoc restrictions on the use of e we may want the third party to enforce and optionally specifying the public key P = e . G of the wallet address, where G is the curve generator. This is then encrypted with the long term RSA public key TP_pub of the third party, to give:

f₂ = Encrypt_{TP_pub}(e₂||D)

It is important that the public key encryption done above is not malleable, so an appropriate MAC-based encryption mode with a nonce should be used, rather than direct RSA encryption. The wallet AES key and e₂ are then forgotten, leaving behind the pair (e₁, f₂) which are held on the (now untrusted) maker's computer to do the signing.

Authorised signing with the encrypted EC key

When the time comes to sign a message m, with Sha256 hash z, the maker's computer (say Alice) needs to compute the ECDSA signature (r, s) where:

s = (z + r * (e₁ + e₂)) / k

and r is the x-component of the curve point R = k . G, for some random nonce k. She will do this in collaboration with the third party (say Bob) as follows:

Alice chooses a random k₁ in GF(N) and sends R₁ = k₁ . G to Bob, along with m, f₂ and the private 2-vector:

u^T = (1 / k₁, e₁ / k₁)

to Bob, with the latter in an encrypted form to be described below.

Bob first of all decrypts f₂ using his private RSA key TP_priv as follows:

e₂||D = Decrypt_{TP_priv}(f₂)

and checks the message m against the auxilliary data D to make sure it is good to sign. Bob then chooses a random k₂ in GF(N) and computes R = k₂ . R₁ = k₂ . k₁ . G_ to give the x-component r. Thus we take the nonce k of final signature (r, s) to be k₁ * k₂, which neither Alice nor Bob know directly but instead have a multiplicative share of, like the additive shares they have of e. Bob also computes a private 2-vector:

v^T = ((z + r * e₂) / k₂, r / k₂)

This is then combined with Alice's encrypted vector u in a special way and sent back to Alice, along with r, who is then able to compute the inner product u^Tv. Now observe that:

u^Tv = (z + r * e₂) / (k₁ * k₁) + r * e₁ / (k₁ * k₂) = (z + r * (e₁ + e₂)) / k = s

So the problem of jointly computing an ECDSA signature (r, s) reduces to that of Alice and Bob securely computing an inner product of their respective private vectors u and v over a finite field. We describe an encoding scheme for doing this below.

Note that the above is intended to be secure in the semi-honest model. If Alice or Bob are actively subverting the protocol with maliciously chosen data, then a few extra minor steps need to be taken. For example Alice can easily trick Bob into helping her sign m with e + e' instead of e, for an arbitrary offset e' of her choosing (although it's doubtful if she could exploit that). Likewise, Bob can exert some malicious influence over r and need not choose k₂ to be random, in the unmodified scheme as described, possibly leaking information about e in the final signature.

Securely computing the inner product of two private vectors

Suppose that Alice has a private vector u and Bob has a private vector v over a large finite field. Then the task of securely computing the inner product u^Tv can be seen as a generalisation of 1-out-of-n oblivious transfer, where n is dimension of the vectors. Indeed, Alice may set all but one of the components of her vector to zero, and the remaining component to some random secret. If Bob sets the components of his vector to secrets v₁,...,v_n, of which Alice is supposed to learn exactly one, then computing the inner product and revealing the result to both sides (or just Alice) obliviously transfers exactly one component v_i to Alice, of her choosing. Accordingly, we shall go the other way and attempt to build a secure 2-party inner product computation protocol from k-out-of-n oblivious transfer.

Concretely, take the 2-dimensional case as needed above. Fix a public 256 * 2 random matrix A over the (256-bit) finite field GF(N) of EC keys. This could be known in advance or a fresh matrix could be generated each time by Alice (say from a random seed) and sent to Bob, for slightly better security.

Take a [256,127,130] Reed-Solomon code C over the finite field. Then there is a fixed linear dependency between any given 128 components of its 256-component codewords. That is, for any choice S of 128 indices from the 256 available, there is exactly one 256-dimensional vector f, up to a scalar multiple, such that f annihilates C (i.e. f^Tc = 0 for every c in C) and f has support S (i.e. the set of indices of nonzero components of f is precisely S).

Now Alice makes a completely random choice of the set S above and computes the corresponding vector f. Note that this choice has a little under 256 bits of entropy. The security of the scheme depends upon the following (hopefully quite mild) hardness assumption:

• For a fixed random matrix A, known in advance by both parties, the 2-vector A^Tf is computationally indistinguishable from a fresh pair of random numbers. That is, Bob would not be able to tell it apart from a totally random 2-vector.

Assuming both components of Alice's private vector u are always nonzero, she may find a diagonal matrix D such that:

u = DA^Tf

and then send it to Bob, who won't be able to tell it apart from random or learn anything about u from it.

Bob then takes a random codeword c from C and computes the 256-dimensional vector:

d = ADv + c

Now by the properties of the Reed-Solomon code C, any 127 components of d on their own will be indistinguishable from independent random variables, but adding a 128th component will start to leak information about v. So Bob obliviously transfers exactly 128 of the 256 components of d to Alice, specified by Alice's secret choice S of indices. This allows Alice to compute:

f^Td = (DA^Tf)^Tv + f^Tc = u^Tv

since the known components of d exactly align with the nonzero components of f. Thus Alice learns the inner product u^Tv and precisely no more information about v from Bob.

Carrying out the oblivious transfer itself can be done basically by Alice sending 128 (EC or RSA) public encryption keys to Bob, along with 128 random decoys, such that it is provably impossible for Bob to tell the decoys apart from the actual keys and provably impossible for Bob to receive more than 128 keys from Alice without realising. (This can also be achieved using Reed-Solomon codes, plus some symmetric cryptography.) Bob then encrypts and sends the 256 components of d back using the respective keys/decoys, but those encrypted with decoys will be completely unintelligible to Alice.

Cost estimate and comparison with other schemes

The entire 2-party authorisation and signing scheme for a given EC key & message, including the oblivious transfer step above, can be accomplished with a single round of communication between Alice (the maker's computer) and Bob (the third party), where Alice sends Bob some data, including the message to sign, Bob checks it, computes and sends some data back, then Alice is able to complete the calculation of the signature. The most expensive part of the computation and network use is the oblivious transfer, requiring 128 (say EC) key pair generations by Alice and 256 public key encryptions by Bob. I doubt that would take more than a second or two to compute. I estimate that with some optimisation using random seeds and random data elision, Alice would need to send Bob a little over 4 KiB and Bob would need to send Alice a little over 16 KiB to authorise signing with a single EC key - those estimates may however turn out to be out by a factor of two.

Realistically, half a dozen or so of the maker's encrypted EC keys may need to be signed with to start a trade (i.e. sign the deposit tx and delayed payout tx). It would be nice to extend the scheme above to support batch signing with different keys. I believe this can be done with only a small growth in the total size of the data sent, by using bigger (i.e. > 2 dimensional) vectors and revealing multiple inner products of Bob's secret vector v to Alice. So there should be a much smaller than linear growth in the bandwidth required with the number of EC keys used. Also, with the upgrade of the trade protocol to SegWit, the delayed payout tx should have input depending only on the unsigned deposit tx, so it should be possible to sign both in a single round of communication between Alice and Bob.

I found a couple of interesting papers describing similar 2-out-of-2 distributed ECDSA signing schemes: https://eprint.iacr.org/2018/499.pdf and https://eprint.iacr.org/2017/552.pdf. They both use multiplicative instead of additive shares e₁ and e₂ of e, that is they set e = e₁ * e₂, but that would make little high-level difference to our scheme.

The former also makes use of oblivious transfer and describes a scheme using a single round in the 2-out-of-2 case, like the above. (They also support 2-out-of-n signing and conveniently provide a Rust implementation.) The 2-out-of-2 case requires 169.8 KiB of communication and it's unclear if any savings could be made by batching. However, the main advantage over my scheme is a provable security reduction to standard EC assumptions, in contrast to the nonstandard hardness assumption made above (which needs to be suitably generalised to longer vectors in the batch signing case).

The scheme described in the latter paper uses Paillier homomorphic encryption to achieve very low total communication costs, at the expense of heavier computation and the extra security assumptions the Paillier encryption brings, although it's probably still fast enough for our purposes, taking perhaps seconds per EC key. However, it appears to require multiple communication rounds between Alice and Bob and it's also unclear to me if batching could be used to reduce costs.

Optional storage of the delayed payout tx to prevent blackmail attacks

The basic scheme described above for protecting the maker's EC keys involves a completely stateless third party, with no communication prior to the actual signing required. While it should prevent outright theft of the funds, there is nothing the third party can do to prevent the compromised maker's computer from simply throwing away the delayed payout tx, where it is assumed that the hacker is colluding with the taker (or they are one and the same). This could open the maker to a blackmail attack when they finally regain control of their computer.

To prevent this, the third party could optionally store the delayed payout tx, pre-signed by the taker (but not the maker, so the third party couldn't publish it himself). This would then be returned to the maker when he regains control of his computer. However, now the third party would no longer be stateless. (Although perhaps the delayed payout tx could be public key encrypted and stored by the third party in a mailbox on the P2P network, accessible only via the maker's password-derived AES key.)

Optional use of a secure enclave by the third party

To further reduce the level of trust in the third party, and mainly to help prevent insider attacks, the cryptographic algorithm described above could be made to run in a secure enclave on the third party computer, perhaps using an Intel SGX enclave or a standalone HSM. The former has the advantage of providing some kind of remote + local attestation features (which I would need to look into further), possibly eliminating the need of a trusted admin to set up the enclave in the first place. It would also probably be much cheaper and easier to develop for. However, great care is required when writing the enclave code, to prevent cache-timing / SPECTRE-like attacks, and I don't suppose the enclave is completely impregnable because it's not running on a cryptoprocessor, but merely expensive to breach.

A standalone HSM would probably provide a much stronger enclave if it could be set up properly, but custom firmware might be required for that, which I guess would be rather expensive and difficult to write (perhaps requiring expensive SDK licenses). It could be a longer term option, however.

Optional use of a custom third party server by the user

A power user could choose to run their own tx signing veto service, with a custom list of TP_pub public keys provided to their Bisq instance, to tag and encrypt the EC keys of their trade reserve with. They could even run it on the same computer, as a daemon, as a separate user + group talking over localhost to Bisq. This would still provide good protection in case the attacker can't gain full root access. If the daemon detected the presence of SGX and then auto-enabled it's use, the user would gain almost as high a level of security as with the default third-party, but with possibly better privacy.

For this reason, I think it would be best to make the third party service executable as lightweight as possible, to minimise attack surface and so that an individual user could run it as a daemon on their own computer if they wished. Perhaps we could consider writing it in Rust or C++ instead of Java, especially since the cryptographic module would possibly be designed to run in an SGX enclave where it is available.

Future integration of a second factor for more complete wallet protection

The threat model implicit in the above scheme is rather narrow, since it assumes the user's computer was in a good state when he first enters his wallet password and only later gets compromised, while he is waiting for an offer to be taken. It also assumes that he is somehow able to realise it was compromised (or the malware failed to persist itself) before he next enters his wallet password. More realistically I think, if an attacker gains access to the Bisq instance, he will try to plant persistent, silent malware. Or the Bisq binary would be tainted so that the app was compromised before it was even launched, perhaps before the wallet was even set up or encrypted.

So ideally the Bisq instance (on its own) would be considered untrustworthy from the moment the wallet seed is first (re)created and the user would use a second factor, either a hardware wallet or a smartphone, whenever any activity on their wallet requiring private keys needs to be authorised.

In the case of a hardware wallet, like a Trezor, instead of using it to directly hold funds, we would use its ability to sign human-readable messages which can be verified against tampering on the Trezor screen. The third party would then check the Trezor's signature to itself authorise a particular use of a bunch of encrypted wallet EC keys held by the Bisq instance. This solves the major problem with hardware wallet integration which is that the Bisq instance can't fund a trade for a taken offer while the maker is away from his computer, since all wallet activity has to be authorised explicitly by the user via the hardware wallet.

In the case of a smartphone second factor, the user would scan a QR code which would show the activity being authorised on the smartphone screen. A 6 or 8 digit one-time numeric passcode, derived from a hash of the message and a smartphone-held secret, would be generated by the app which the user would then type into their Bisq instance. The message, encrypted secret, passcode and encrypted EC keys would be sent to the third party, who would then be able to check the passcode is valid against the message to complete the authorisation. This setup enables the smartphone to be used offline as a dedicated second factor, for extra security.

Initial seed phrase setup

To ensure the user retails full custody of their funds at all times, the entire Bisq wallet should continue to be derived from a seed phrase which is known only to them, so the wallet can be recreated in, say, Electrum or another Bisq installation at any time. However, the user's computer shouldn't be completely trusted at any point, when setting up a seed phrase in Bisq.

To solve this problem, we could follow something like Trezor's seed phrase recovery procedure: the Bisq instance learns the words of the phrase but not the order, while the second factor (say smartphone) learns the correct order of the words but not the words themselves. So neither device on its own can recover the seed phrase to unilaterally access the wallet. (At this point, we should probably use 24 rather than 12 word seed phrases for sufficient entropy.)

A secure 2-party computation is then done to derive the (TP_pub-encrypted) master private key of the wallet, which is then stored by the Bisq instance for all future wallet access. This would probably require a generic 2-party computation using garbled circuits, so it's likely to be quite a heavyweight operation, unlike the above cryptographic scheme, but would only need to be done once.

The 2-party computation is either done directly between the smartphone and the Bisq instance (which would require the former to be online) or it could be done between the third party and Bisq instance (following instructions on the smartphone screen) in such a way that the third party learns nothing - not even the order of the words since it shouldn't be necessary to tell that to them directly. A somewhat more elaborate and complicated-to-follow procedure could be similarly devised for the Trezor, I think, where the user would need to manually check the third party's public key against messages shown on the Trezor's screen (as I believe the Trezor can verify messages signed by others).

Threat model and security of the two factor scheme

We now have three entities: the user's smartphone or Trezor, their computer running the Bisq instance and the third party (which could later be extended to a network of servers). The wallet funds can be stolen if and only if either the first two devices are compromised or the last two devices are compromised. So this doesn't provide quite as good security as a hardware wallet but I think still quite good security, especially if the network of third party servers could later be made to use SGX or HSMs and perhaps even some threshold signing scheme.

[chimp1984]

I am impressed by the scheme but it is unfortunately beyond my skill level to be able to comment.

[cbeams]

I'll just note that I read through this several times as well, am also impressed by the ideas, and am also unable to evaluate the cryptographic aspects. I wonder if this scheme might better be floated elsewhere as a general solution to the problem of storing unencrypted keys in memory to facilitate event-based signing. Somewhere that it could get attention from those with the requisite expertise who might in turn get interested in collaborating on implementing it here in Bisq.

From a strategic / timing perspective, having this kind of thing on the roadmap in relation to the release of the Bisq API would make sense, as a successful API launch should eventually result in many more long-running Bisq nodes out there, and therefore a greater need for this kind of protection.

[chimp1984]

@cd2357 @battleofwizards @sgeisler might be interested in that idea and more competent to add inputs.

[stejbac]

Thinking a bit more about some of the proposal details, it may be a bit more serious than I thought if the maker's computer can trick the third party into helping them sign a message with the private key e plus an arbitrary offset e'. This is because in BIP32, every non-hardened private key has a known, public offset from its parent, so potentially a transaction could be signed with the wrong private key in the wallet (say outside the user's trade reserve) - a kind of related key attack. But as I mentioned, there should be fairly easy techniques to prevent this.

Also, I thought a bit further about the seed phrase setup idea, where the user's Bisq instance knows the words but not the order and his smartphone knows the order but not the words. As mentioned, this probably requires the use of garbled circuits to jointly derive the master private key in a secure 2-party computation. Unfortunately, it turns out that BIP39 key generation from a seed phrase uses password stretching internally - specifically PBKDF2 with HMAC-SHA512 and an iteration count of 2048. This would make running it inside a garbled circuit very expensive - I estimated roughly 700 million garbled AND-gates would be required, making the circuit (which is strictly single-use, like a one-time pad) about 35GB in size for 128 bits of security, which would need to somehow be transferred between either the smartphone and the Bisq instance (say using an SD card) or the Bisq instance and the third party. Even though generating and running the circuit is very fast, that is hardly practical for most users.

Luckily, due to some of the details of the iterative PBKDF2 stretching algorithm (namely that it XORs all its intermediates together to form the final result), it should be possible to carry out most of the computation outside the garbled circuit if an alternative wallet setup procedure is used: The Bisq instance inputs/creates a full, in-order 12-word seed phrase as it does currently. The smartphone (or other 2nd factor) inputs/creates a BIP39 passphrase of high entropy (say 80-128 bits) to use with the seed phrase. This is then encrypted (to a numeric code, say) and the user enters it into his Bisq instance to complete the wallet setup. It's vital that the BIP39 passphrase (which is distinct from the current optional BitcoinJ wallet encryption password) has very high entropy, as it won't benefit from the PBKDF2 stretching, due to the bulk of the 2-party computation taking place directly on the user's computer, outside the garbled circuit. This should result in a much reduced garbled circuit, say a few 10s of MB, which is hopefully small enough to practically transfer from the 3rd party server to the user's computer.

It's also much better I think, for maximal security, that the user verifies externally (say using Electrum or a hardware wallet) that his BIP39/BIP32-derived Bisq wallet actually corresponds to the written-down seed-phrase+passphrase, say by checking the chain codes or first few generated addresses. This is because a hacker could potentially control what's seen on the screen (of either device but not both) and trick the user into generating a wallet with the wrong seed-phrase/passphrase. This could open the user up to a blackmail attack, even though the attacker couldn't directly steal funds this way. I thought of a rather elaborate procedure by which the user could validate the wallet using both devices together (neither of which is trusted on its own), by doing some simple sums manually using pencil and paper, to transfer certain sensitive numbers from one device to the other in an one-time-pad-encrypted form. In this way, no device learns more about the seed-phrase+passphrase than it knew to begin with but is still able to validate the whole thing. (A validation from both devices means the wallet is correctly set up in our threat model.) However, that procedure is probably a bit much to expect most users to follow, but could possibly be added as a special feature later.

[pazza83]

Hi @stejbac thanks for the proposal. I am doing some housekeeping on the proposals. Please can you take steps to move this forward or alternatively close the proposal.

Many thanks.

Ref: https://bisq.wiki/Proposals

[pazza83]

Hi @stejbac thanks for creating this proposal. I will close this proposal as stalled. Please feel free to reopen in the future.