Author Topic: $500 BitUSD Bounty - ECC Blinded Signatures  (Read 10343 times)

0 Members and 1 Guest are viewing this topic.

Offline roadscape

Thanks @arhag for looking out for potential flaws!

Is there an update as to how blinded transactions are actually implemented now?

+5%.. I hope this feature will be disabled on the main chain until we are sufficiently confident about it (even if it means it won't be available on Day 1)
http://cryptofresh.com  |  witness: roadscape

Offline xeroc

  • Board Moderator
  • Hero Member
  • *****
  • Posts: 12922
  • ChainSquad GmbH
    • View Profile
    • ChainSquad GmbH
  • BitShares: xeroc
  • GitHub: xeroc
Is there an update as to how blinded transactions are actually implemented now?

Offline arhag

  • Hero Member
  • *****
  • Posts: 1214
    • View Profile
    • My posts on Steem
  • BitShares: arhag
  • GitHub: arhag
Okay, this is my second attempt at coming up with a blinded signature algorithm that (attempts to) solve what I consider two problems with Oleg Andreev's algorithm. The first is the fact that the nonce is determined at the time the public key is determined (which I discussed in my previous post). The second is the unsolicited fund problem (which means that the balance remains unprotected by two-factor authentication from the time the sender sends it until the time the receiver moves it into a new balance that is protected by the public key derived from the blinded signature algorithm).

I believe I have come up with a solution (although for all I know it might be flawed like my first attempt which allowed colluding attackers to gain access to the user's private key) that solves both of those problems while generating a standard Schnorr signature. I had to give up on ECDSA since I'm not sure if it is even possible to do a blinded signature algorithm that satisfies these two requirements. Schnorr signatures have a lot of advantages over ECDSA anyway, like making threshold signatures really easy.

Again I assume there are three parties: Alice, Bob and Carol. Carol is sending unsolicited funds to Alice and Bob is Alice's designated blind signer. This time Bob does not need to have a public key specific to each of his customers. (Not true. See edit.) I believe the protocol I lay out below allows Bob to protect his private key even though it is being used to service all customers (meaning his customers cannot trick him to generate and return values that allow them to recover his private key... I hope). Bob's blind-signing private key is b and his published blind-signing public key is B = b*G. Alice's blind-receiving private key is a and her published blind-receiving public key is A. (Note I use blind-signing and blind-receiving rather than just active as an added security precaution. If I am wrong and there is a way to determine Alice's or Bob's private key, at least the damage is contained only to balances designated for blind signing rather than everything. This of course assumes that the blind-signing/blind-receiving private keys are determined through hardened child derivation from the corresponding active private keys, rather than normal child derivation.)

When Carol wants to send funds to Alice all she needs is the share secret z derived from Diffie-Hellman key exchange, Alice's blind-receiving public key A (which is published in her account metadata), and the blind-signing public key B of Alice's blind signer (Carol looks up in Alice's account metadata that Alice's blind signer is Bob, and then looks up in Bob's account metadata that his blind-signing public key is B). Carol then computes f = HMAC256(z, SHA256("blind")), and then the public key T = A + B + f*G. She sends the funds to a balance that can be withdrawn using a Schnorr signature corresponding to public key T (the full public key T is included rather than the address since Schnorr signatures do not allow recovering the public key from the signature) and also includes in the transaction the one-time public key that Alice needs to derive the shared secret z. When Alice receives the transaction, she can compute the shared secret z, then f, and then T, and verify that the transaction is valid before accepting it as payment for goods and services.

Later, when Alice wants to actually withdraw the funds, she creates a withdraw transaction which has digest h. She then connects to Bob with a secure connection, authenticates herself to Bob, and then they go through the following procedure (all operations are modulo the group order):
  • Bob generates a random value r. Then, he computes P = (b + r)-1*G. Then, he sends (r, P) to Alice.
  • Alice computes u = HMAC256(a, SHA256(h || r || P || "one")), v = HMAC256(a, SHA256(h || r || P || "two")), Q = P + u*G - v*(B + r*G), e = SHA256(h || Q), and w = -(e + v). Then, she sends w to Bob.
  • Bob computes y = (b + r)*w + (b+r)-1. Then, he sends y to Alice.
  • Alice computes s = y + u - e*(a + f - r), and she verifies that SHA256(h || (s*G + e*T)) == e.
Then (s, e) is the Schnorr signature on digest h with public key T. The blockchain can verify the signature is valid by verifying that SHA256(h || (s*G + e*T)) == e.

Bob only has access to r, P, w, and y. Since v is a pseudo-random number that Bob does not know, he cannot relate w to e. If Bob suspects a particular spent balance belongs to Alice, he can compute F1 = s*G + e*T - P - (w+e)*(B + r*G) which should be u*G if it is in fact Alice's balance. He can also compute F2 = s*G - y*G + e*A - e*r*G which should be u*G - e*f*G. Therefore, even though Bob cannot know the pseudo-random number u, if e-1*(F1 - F2) ==  f*G, then Bob can know the balance does in fact belong to Alice. However, Bob also does not know f because he does not know the shared secret z. While Carol does know the shared secret z, if Bob and Carol were colluding, she could just trivially tell Bob that the balance does in fact belong to Alice. I don't believe there is any way for Bob alone to link the balance to Alice by following this protocol.

The remaining questions are: if Bob and Carol colluding together can generate a valid Schnorr signature on an arbitrary digest or even discover Alice's private key a; and, if Alice can trick Bob into revealing his private key b. While I don't have any proof that these two things are impossible, I haven't yet been able to figure out a way that it could be done. Of course, a review of the protocol is highly appreciated.

Edit: Once again a flaw. Though I still think users cannot trick Bob into revealing his key with the above protocol, it is still broken because users sharing the same blind signer essentially are not protected by two-factor authentication with respect to each other. Eve can legitimately authenticate with Bob and get him to blind sign a digest that allows her to steal Alice's balances if she also knows Alice's private keys. The whole point of this is to provide two-factor authentication so the above protocol is broken if they use a universal public key B (and Bob uses the corresponding universal private key b). Instead B should be specific to each customer where its private key b is for example determined using hardened child private key derivation with SHA256(A) as the index. Alice could have Bob generate that public key for her once and then she would post it on her public metadata. Unsolicited transactions would still work fine. I will have to update the details of this protocol more formally to reflect these changes, but I have other changes planned with this protocol such as:
  • Incorporating multiple blind signers (basically an n-of-n multisig) but with still only one final signature.

  • Blind threshold signatures (of the t-of-n variety where t and n are both integers) with of course again one final signature. (A combination of item 1 and item 2 should also be possible where there are m different ti-of-ni threshold public keys for i = 1, ..., m, and the requirement is that all m of those produced a valid partial threshold signature.)

  • Blind weighted signatures in which the sum of the prescribed weights of each key (these can also be t-of-n style threshold public keys à la item 2) in the set of signers needs exceed the prescribed threshold in order to be valid, but done in a way that doesn't reveal to the public or to the blind signers who the keys actually belong to and without revealing the weights nor threshold values, thus better protecting privacy (however it does necessarily reveal some structural information like the total number of keys in the set of possible signers and the indices of the signers in the set of possible signers that make up the subset of actual signers). This is done through the use of Pedersen commitments and range proofs from the blinded amount cryptography. Transaction size requirements are not trivial but are typically smaller than existing alternatives trying to do the same thing without blinding: one final signature on the overall transaction is necessary and only one range proof is necessary and can usually be very small since it only needs to hide the delta amount of (sum of weights of signers - threshold value) and even then may not be all that important to privacy, and roughly somewhere between (66+34*t) to (66+54*t) additional bytes are needed where t is the number of actual signers (which is quite good when you consider that a regular t-of-n multisig would have 20*n bytes for the n addresses and then t*64 bytes for the t signatures). The compactness comes from the fact that only one final signature is necessary and from the fact that the sender commits to the transaction withdraw condition the list of (public key, weight) commitments as a Merkle tree.

  • Allowing the blind signers to force certain assertions (like setting a maximum allowed dollar value of funds transferred in the transaction and/or that the difference between the expiration time and the timestamp of the TaPoS referenced block be less than some prescribed value) to exist in the transaction they are blind signing while still not knowing the exact transaction they are signing. This is incredibly useful to people using blind signatures whose clients might be compromised. The user can verify out-of-band (say through an SMS, or via the class of one-time code they used to authenticate with the blind signer) the assertions that the blind signer is applying to their signature. So, if using SMS, they will know something is wrong if the assertion class displayed in the SMS doesn't match what their client UI said it was telling the blind signer to apply and thus the user won't type in the one-time code. If they are using a one-time code generated on a separate device and sending it with their request to the blind signer, they can know that worst case the attacker can only do the damage allowed by that assertion class and not any more. This way a hacker can't just wait until the user enters the one-time code for a transaction that is meant to be of the <$50 class and use it to steal their entire balance which is worth much much more than $50. Keep in mind that although this is still blind signing, adding unique assertions on transactions can compromise privacy with respect to the blind signer. For this reason, it is best if people followed a policy that kept the number of unique assertion class variations to just a handful of popular ones and if the client waited before broadcasting the final signed transaction until a random number (selected uniformly from some client-prescribed interval) of transactions with the same assertion class were confirmed in the blockchain starting from the time when the last blind signer sent their partial signature to the user (these are statistics the wallet host can provide to the wallet client).
So I will eventually post an upgraded version of the protocol some time later with all of those changes included.
« Last Edit: July 30, 2015, 04:44:56 am by arhag »

Offline arhag

  • Hero Member
  • *****
  • Posts: 1214
    • View Profile
    • My posts on Steem
  • BitShares: arhag
  • GitHub: arhag
There is a potential flaw with this algorithm. At the moment that the user stores their balance on the blockchain with a particular blind public key T, they are also forced to commit to a particular nonce k = (c*p*a)-1. The final signature s(h) on any given hash h is s(h) = (c*p*a)*h + (c*p*b + c*q + d) = y1*h + y2, where y1 and y2 are values that neither the user nor the blind signer alone know but are nevertheless fixed given a fixed blind public key T. If the user wants to spend the balance, they craft a transaction with digest h1, go through the blind signature process and generate the signature s1 = s(h1) which they include with the signed transaction they broadcast to the network. So far no problem.

But what happens if for whatever reason that signed transaction is not included in the blockchain before the transaction expires? The user is then forced to craft a new transaction with a new expiration time, and thus necessarily a new digest h2, go through the blind signature process again and generate the signature s2 = s(h2) which they include with the new signed transaction they broadcast to the network. This is where we have a problem. Anyone with access to those two signed transactions can then calculate k through k = (s1 - s2)-1 * (h1 - h2), and with k known they can then calculate r = x-coordinate of the point (k*G), and x = r-1*(s1*k - h1)). The value x is the private key of the public key T (i.e. T = x*G). With x known, an attacker can then craft another transaction spending that balance to their own account and try to get that transaction into the blockchain before the user's second transaction. This is quite easy to do if many of the witnesses are colluding in the attack OR if the attacker controls all the nodes that the user's client happens to be connected to.

One quick fix to this problem is to not require withdraw operations signed by blinded signatures to be indistinguishable from regular signatures. We could decouple the blinded signature from the signature that signs the transaction (this is something that might be a problem for this algorithm on the Bitcoin network, but fortunately we have the flexibility to modify our blockchain protocol). The withdraw condition of the balance would no longer be that it requires the transaction to be signed by public key T. Instead it would require that the transaction include a special operation whose validity is determined by public key T and that the transaction be signed by public key Y, where Y = z*G and z is a hardened child private key determined using index Hash(T) (it is important for it to be hardened so that the public cannot check if this balance is associated with the user's account). This special operation would include a signature embedded inside of it and for the operation to be valid it would require the signature be a valid signature on the digest Hash(Y) using public key T.

So the way this would work is that when the user is storing the balance on the blockchain, their client first goes through the regular procedure to calculate T and then it would use Hash(T) to calculate z and thus Y. It would then create, sign, and broadcast the transaction that initially stores the balance on the blockchain using the values of the address of T and the address of Y in the transaction.

Later when the user wants to spend that balance, the user's client would again generate Y = z*G , go through the blind signature process using the digest Hash(Y), and keep the resulting unblinded signature s in memory (if necessary, say the client crashes and s is lost, the user can repeat the process, meaning re-authenticate with the blind signer, and recalculate s). The user can then generate as many transactions as they want (with unique nonces each time of course) by including the special operation (which contains s) in the transaction and signing it with private key z. Once the transaction is confirmed in the blockchain, the user's client can then delete s from memory.

It is important to understand that from the time that the user receives s and keeps it in memory until the time that the balance has been fully spent on the blockchain, the user is no longer protected with two-factor authentication. If their client gets compromised in that time in such a way that an attacker can get access to the client's memory, the attacker will be able to spend that balance without needing to authenticate to the blind signer at all. Fortunately, it is more difficult to compromise the memory of the client rather than just the user's private key and the window of attack opportunity should normally be very short. Alternatively, the attacker can also compromise the user within the attack window if they know the user's private key AND are able to get access to plain-text communication between user and blind signer such that they can grab (p*a*Hash(Y) + p*b + q) while it is in transit over the network from blinded signer to user (I am of course assuming the attacker with the user's private key is not in collusion with the blind signer, since in that case it is trivial to compromise the balance). For this reason, it is important that the session between the user's client and the blind signer be encrypted (i.e. use TLS), so that the attacker really does need to compromise the client's memory to succeed in the attack.
« Last Edit: July 29, 2015, 04:05:52 am by arhag »

Offline alt

  • Hero Member
  • *****
  • Posts: 2821
    • View Profile
  • BitShares: baozi
Got a working version - https://github.com/cryptonomex/fc/pull/46

Notes:
* The call interface is slightly different from the suggestion in the OP.
* The generated signatures will fail the public_key::is_canonical test in slightly more than 50% of the cases. Callers must check and retry with the next i. IMO is_canonical is much more restrictive than required.
* libsecp256k1 does not export all required primitives, so I had to fall back on openssl in some cases.
it's great to have you on board!!

 +5% good work @pc
+5%

Offline bytemaster

For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Offline cass

  • Hero Member
  • *****
  • Posts: 4311
  • /(┬.┬)\
    • View Profile
Got a working version - https://github.com/cryptonomex/fc/pull/46

Notes:
* The call interface is slightly different from the suggestion in the OP.
* The generated signatures will fail the public_key::is_canonical test in slightly more than 50% of the cases. Callers must check and retry with the next i. IMO is_canonical is much more restrictive than required.
* libsecp256k1 does not export all required primitives, so I had to fall back on openssl in some cases.
it's great to have you on board!!

 +5% good work @pc
█║▌║║█  - - -  The quieter you become, the more you are able to hear  - - -  █║▌║║█

Offline xeroc

  • Board Moderator
  • Hero Member
  • *****
  • Posts: 12922
  • ChainSquad GmbH
    • View Profile
    • ChainSquad GmbH
  • BitShares: xeroc
  • GitHub: xeroc
Got a working version - https://github.com/cryptonomex/fc/pull/46

Notes:
* The call interface is slightly different from the suggestion in the OP.
* The generated signatures will fail the public_key::is_canonical test in slightly more than 50% of the cases. Callers must check and retry with the next i. IMO is_canonical is much more restrictive than required.
* libsecp256k1 does not export all required primitives, so I had to fall back on openssl in some cases.
it's great to have you on board!!

Offline pc

  • Hero Member
  • *****
  • Posts: 1530
    • View Profile
    • Bitcoin - Perspektive oder Risiko?
  • BitShares: cyrano
Got a working version - https://github.com/cryptonomex/fc/pull/46

Notes:
* The call interface is slightly different from the suggestion in the OP.
* The generated signatures will fail the public_key::is_canonical test in slightly more than 50% of the cases. Callers must check and retry with the next i. IMO is_canonical is much more restrictive than required.
* libsecp256k1 does not export all required primitives, so I had to fall back on openssl in some cases.
« Last Edit: July 19, 2015, 09:31:08 pm by pc »
Bitcoin - Perspektive oder Risiko? ISBN 978-3-8442-6568-2 http://bitcoin.quisquis.de

Offline arhag

  • Hero Member
  • *****
  • Posts: 1214
    • View Profile
    • My posts on Steem
  • BitShares: arhag
  • GitHub: arhag
Is anyone actually working on this bounty?

I am, but at a very low pace.

Glad to hear someone is working on it.  :)

Offline pc

  • Hero Member
  • *****
  • Posts: 1530
    • View Profile
    • Bitcoin - Perspektive oder Risiko?
  • BitShares: cyrano
Is anyone actually working on this bounty?

I am, but at a very low pace.
Bitcoin - Perspektive oder Risiko? ISBN 978-3-8442-6568-2 http://bitcoin.quisquis.de

Offline arhag

  • Hero Member
  • *****
  • Posts: 1214
    • View Profile
    • My posts on Steem
  • BitShares: arhag
  • GitHub: arhag
We had extended public/private keys but they were in bitshares not fc.   I would like to keep fc "application neutral" and general purpose.

Oh no wonder I couldn't find it. It isn't in the Graphene toolkit first of all. And while it is in the old BitShares codebase, it isn't in fc like you said. Are you guys planning on adding hierarchical deterministic wallet support into Graphene?

Well if you don't want to put that in fc, then either there is a weird dependency issue if you want this blinded signature algorithm in fc OR the interface of the algorithm needs to change to not depend on extended private/public keys OR the blinded signature algorithm should just be put into the Graphene toolkit and not fc (but if you go that route I would argue you should strip all ECC out of fc).
« Last Edit: July 03, 2015, 05:10:07 am by arhag »

Offline bytemaster

Now that fc defaults to libsecp256k we might as well embrace it and clean up the wrapping of it.
I am also in favor of using libsec256k bignum support where possible.   

We had extended public/private keys but they were in bitshares not fc.   I would like to keep fc "application neutral" and general purpose.

Generally speaking I don't have the money to improve something that isn't broken, but I will award major BROWNIE.PTS for anyone who wants to take on these tasks. 
For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Offline arhag

  • Hero Member
  • *****
  • Posts: 1214
    • View Profile
    • My posts on Steem
  • BitShares: arhag
  • GitHub: arhag
Is anyone actually working on this bounty? Here are my thoughts on how this bounty should be restructured.

I think wrapping the crypto primitives from secp256k1-zkp in a nice friendly C++ interface that we can use to intuitively do crypto math (adding/multiplying 256-bit numbers modulo order of the curve, adding curve points together, and multiplying a 256-bit scalar with a curve point, etc.) is a project of its own that could act as a prerequisite to this blinded signature project. It should also implement or wrap HMAC-SHA512 as that is needed for BIP32, which as far as I am aware libsecp256k1 does not implement but OpenSSL might. (By the way, why do we bother with a choice in the fc library between an OpenSSL implementation for the ECC math versus the libsecp256k1 one? At this point can't we just commit to the libsecp256k1 one? The secp256k1-zkp dependency is needed anyway for the Confidential Transaction stuff, right? It's also a bit frustrating seeing the public_key and private_key implementations depend on OpenSSL's bignum while libsecp256k1 apparently implements its own bignum stuff in order to do the ECC math.)

Then after that, those crypto primitives could be used to build extended_private_key and extended_public_key which can be used for proper BIP32 hierarchical deterministic wallets (honestly I was surprised to find out that wasn't already implemented in BitShares).

Then finally, the crypto primitives and extended_private_key/extended_public_key classes can all be used to implement Oleg's algorithm in a pretty straightforward and easy way. In fact at that point I would be interested in implementing my own modified version just to see how it works.

So I see this bounty broken down into those three separate projects. I think it would make this task more accessible for people. And in my opinion, the first one should be worth more than the second, and the second worth more than the third.

Offline Ander

  • Hero Member
  • *****
  • Posts: 3506
    • View Profile
  • BitShares: Ander
Glad to see this is being discussed, even if technically it is a bit over my head. +5%
Arhag's post was more than just 'a bit' over my head.

:D
https://metaexchange.info | Bitcoin<->Altcoin exchange | Instant | Safe | Low spreads