Re: [Bitcoin-development] CoinShuffle: decentralized CoinJoin without trusted third parties
You are raising valid questions and one goal of our posting here is indeed to discuss exactly these system issues. On Thursday 07 August 2014 15:00:11 you wrote: I think the description at your website leaves out the truly interesting part: How do you decentralize this securely? - How do Alice, Bob, Charlie and Dave communicate, i.e. which network is used for communication and how? The simplest approach is obviously to use direct connections to a randomly elected leader, who is also responsible for the broadcasts. One advantage of CoinShuffle is that the unlinkability between input and output addresses is guaranteed, no matter which underlying network you use. (Still, it is a good idea in general to hide your IP address but we can let the user decide here.) Of course, there would be other possibilities, such as overlay networks. Coinmux, a CoinJoin prototype by Michael Pearce (http://coinmux.com/) uses TomP2P, a distributed hash table, for communication. Do you have any hints regarding this point? - How does Alice know that Bob, Charlie and Dave are not the same person? (= how do you prevent a Sybil attack?) Because thats the real problem with mixing it seems - ensuring that your mixing partners are actually 100 people and not just 1 attacker. There are probably many mixing algorithms which work if you solve that problem, but I don't see how you offer a solution for it :( It's true that there are a few proposals for mixing protocols which all have their advantages and disadvantages. However, it's not true that the mixing itself becomes simple if you solve the problem of Sybil attacks. Still, mixing is difficult to get right: Even if there are no Sybil attacks, you have to ensure that the participants (or a server) cannot break unlinkability or steal money. Actually that's why there are several proposals for mixing protocols, because there is no obvious perfect solution. Regarding your question: It is indeed very important to get this right. Fundamentally, there is nothing that prevents the attacker from creating a lot of identities participating in a lot of CoinJoins. However, there are ways that make it hard for the attacker to put an honest user together only with malicious users. For a moment, assume that you can reliably establish a pool of users that would like to participate in the protocol. (I will discuss this later.) You have to divide the users to individual groups, i.e., CoinJoins runs. If the assignment cannot be influenced by the attacker, then the probability that there are also honest users in a run is quite high. Of course, the attacker is able to reduce your anonymity set but they cannot just put you together only with their malicious identities. Note that the attacker has to pay transaction fees for joining many transaction. One could even increase the required fee depending on the number of users in the pool (enforced by honest CoinShuffle participants that would not accept CoinJoins that pay a lower transaction fee). And making sure that the attacker cannot influence the assignment is simple: One can use the hash of all users' public keys in the pool to determine the assignment for example. For the initial setup step, i.e., creating the pool of participants, you need some kind of bulletin board. One possibility is to use an underlying peer-to-peer network. Bitcoin itself is the first that comes to the mind but it does not allow arbitrary messages. So if we do not want to change the Bitcoin protocol, chans in Bitmessage are a very promising possibility. Bitmessage relies basically on the same broadcast mechanism as Bitcoin. If you as a peer use enough outgoing connections to other peers, it's very difficult for an attacker to ensure that your message will not be spread among the network. (Btw, people have used this to do CoinJoin manually already https://forum.namecoin.info/viewtopic.php?f=2t=1694 .) Solutions like distributed hashtables (TomP2P again) are another possibility. We are not sure which of those approaches provides the best robustness against malicious nodes that try to stop single participants from reaching the network. For the setup step, latency is not an issue, so Bitmessage is indeed a promising candidate here. I think that in general, P2P is the way to go here, but there are other approaches as well: - A possibility is to have a lot of servers acting as bulletin boards. The user sends his announcement message to all of the servers and the user waits until at some of the servers send back a guarantee to include the user. After some time, the servers agree on the pool of the users just by taking all the users that have registered with at least one of the servers. There are well-understood protocols to achieve this goal or similar goals, because essentially the same problem arises in e-voting (see http://arxiv.org/pdf/1401.4151 for just one example. this paper provides also a detailed
Re: [Bitcoin-development] Miners MiTM
Since the information exchanged between the pool and the miner is public, all that's needed is a mutual private MAC key that authenticates messages. This requires a registration step, that can be done only once using a simple web interface over https to the miner website. But the miner website is not the miner server, so the worst DoS would be preventing new miners to join the pool, which is not very often. The MAC key can be provided directly by the miner. And the pool associates the MAC key with a Bitcoin public address. The overhead would be minimal. -Sergio. -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] CoinShuffle: decentralized CoinJoin without trusted third parties
Hi Tim, It's clear from the paper that the second party in the protocol can de-anonymize the first party. So it's seems that dishonest shufflers would prefer to be in that position in the queue. There are two possible solutions to this: 1. Derive the first order of parties in the shuffle from the hash of all inputs provided (as a seed for a pseudo-random number generator). 2. Repeat the shuffle several times with an different party order (e.g. an order that is deterministically derived from the hash of all the outputs) Best regards, Sergio/ On 09/08/2014 07:04 a.m., Tim Ruffing wrote: You are raising valid questions and one goal of our posting here is indeed to discuss exactly these system issues. On Thursday 07 August 2014 15:00:11 you wrote: I think the description at your website leaves out the truly interesting part: How do you decentralize this securely? - How do Alice, Bob, Charlie and Dave communicate, i.e. which network is used for communication and how? The simplest approach is obviously to use direct connections to a randomly elected leader, who is also responsible for the broadcasts. One advantage of CoinShuffle is that the unlinkability between input and output addresses is guaranteed, no matter which underlying network you use. (Still, it is a good idea in general to hide your IP address but we can let the user decide here.) Of course, there would be other possibilities, such as overlay networks. Coinmux, a CoinJoin prototype by Michael Pearce (http://coinmux.com/) uses TomP2P, a distributed hash table, for communication. Do you have any hints regarding this point? - How does Alice know that Bob, Charlie and Dave are not the same person? (= how do you prevent a Sybil attack?) Because thats the real problem with mixing it seems - ensuring that your mixing partners are actually 100 people and not just 1 attacker. There are probably many mixing algorithms which work if you solve that problem, but I don't see how you offer a solution for it :( It's true that there are a few proposals for mixing protocols which all have their advantages and disadvantages. However, it's not true that the mixing itself becomes simple if you solve the problem of Sybil attacks. Still, mixing is difficult to get right: Even if there are no Sybil attacks, you have to ensure that the participants (or a server) cannot break unlinkability or steal money. Actually that's why there are several proposals for mixing protocols, because there is no obvious perfect solution. Regarding your question: It is indeed very important to get this right. Fundamentally, there is nothing that prevents the attacker from creating a lot of identities participating in a lot of CoinJoins. However, there are ways that make it hard for the attacker to put an honest user together only with malicious users. For a moment, assume that you can reliably establish a pool of users that would like to participate in the protocol. (I will discuss this later.) You have to divide the users to individual groups, i.e., CoinJoins runs. If the assignment cannot be influenced by the attacker, then the probability that there are also honest users in a run is quite high. Of course, the attacker is able to reduce your anonymity set but they cannot just put you together only with their malicious identities. Note that the attacker has to pay transaction fees for joining many transaction. One could even increase the required fee depending on the number of users in the pool (enforced by honest CoinShuffle participants that would not accept CoinJoins that pay a lower transaction fee). And making sure that the attacker cannot influence the assignment is simple: One can use the hash of all users' public keys in the pool to determine the assignment for example. For the initial setup step, i.e., creating the pool of participants, you need some kind of bulletin board. One possibility is to use an underlying peer-to-peer network. Bitcoin itself is the first that comes to the mind but it does not allow arbitrary messages. So if we do not want to change the Bitcoin protocol, chans in Bitmessage are a very promising possibility. Bitmessage relies basically on the same broadcast mechanism as Bitcoin. If you as a peer use enough outgoing connections to other peers, it's very difficult for an attacker to ensure that your message will not be spread among the network. (Btw, people have used this to do CoinJoin manually already https://forum.namecoin.info/viewtopic.php?f=2t=1694 .) Solutions like distributed hashtables (TomP2P again) are another possibility. We are not sure which of those approaches provides the best robustness against malicious nodes that try to stop single participants from reaching the network. For the setup step, latency is not an issue, so Bitmessage is indeed a promising candidate here. I think that in general, P2P is
Re: [Bitcoin-development] Miners MiTM
On Thu, Aug 07, 2014 at 11:45:44PM +, Luke Dashjr wrote: On Thursday, August 07, 2014 11:02:21 PM Pedro Worcel wrote: Hi there, I was wondering if you guys have come across this article: http://www.wired.com/2014/08/isp-bitcoin-theft/ The TL;DR is that somebody is abusing the BGP protocol to be in a position where they can intercept the miner traffic. The concerning point is that they seem to be having some degree of success in their endeavour and earning profits from it. I do not understand the impact of this (I don't know much about BGP, the mining protocol nor anything else, really), but I thought it might be worth putting it up here. This is old news; both BFGMiner and Eloipool were hardened against it a long time ago (although no Bitcoin pools have deployed it so far). I'm not aware of any actual case of it being used against Bitcoin, though - the target has always been scamcoins. That statement right there is all the evidence I need to convince myself that Bitcoin is under continuous and active BGP feed manipulation by organized crime elements. Just the phrase of referring to !bitcoin as 'scamcoins' is a signal of an organized marketing/psychological operations effort to marginalize other competitors, and the documented altcoin BGP highjacks were most likely testing of the system to confirm both a) that it works b) how to hide it below the detection threshhold -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Miners MiTM
On Fri, Aug 08, 2014 at 11:42:52AM +0200, Mike Hearn wrote: AFAIK the only protection is SSL + certificate validation on client side. However certificate revocation and updates in miners are pain in the ass, that's why majority of pools (mine including) don't want to play with that... Why would miners need updates? If they implement the standard SSL infrastructure you can change certificates and keys without needing to update miners. Besides, when it comes to financial services SSL is essential, I'm kind of surprised it wasn't already used everywhere. I wouldn't use an online bank that didn't support SSL, I would see it as a a sign of serious problems. Heck I wouldn't even use webmail that didn't support SSL these days. Because turning on SSL gives pool operators a way to hack your miners. http://www.symantec.com/connect/blogs/openssl-patches-critical-vulnerabilities-two-months-after-heartbleed Just because SSL is the answer for financial services regulated security theatre, where fraud means you just roll-back the transaction, it does not mean it is actually a good cryptographic solution. There are far better mechanisms that could be implemented using ECDSA keys (aka bitcoin addresses) to authenticate both miners and pools, but the problem is there zero economic incentive to do so. As long as the BGP/SSL/zero-day-of-the-week man-in-the middle fraud cost is lower than the engineering cost to do some real cryptography and code audits, we'll keep having new 'security patches' every couple of months. -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] CoinShuffle: decentralized CoinJoin without trusted third parties
On Sat, Aug 9, 2014 at 6:10 AM, Sergio Lerner sergioler...@certimix.com wrote: Hi Tim, It's clear from the paper that the second party in the protocol can de-anonymize the first party. So it's seems that dishonest shufflers would prefer to be in that position in the queue. That's not clear to me. The 2nd party doesn't know how the 3rd, 4th, 5th, etc. parties shuffled the outputs, since it doesn't have their decryption keys. -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
[Bitcoin-development] BIP32 - invalidation
Does anyone see any concerns when it comes to security of the proposed change? Yes. This proposal is less secure. It is incompatible in theory with existing implementations of the specification. The incompatibility is also a potentially a security problem because it may cause users to believe a key is worthless when it is not or to lose funds when they are unable to spend them. It is also an untimely proposal and would be inconsiderate other parties who have done the work to produce correct and compatible implementations. In case I_L = n assign I_L := I_L mod n. This will make the selection of private keys uneven. The unevenness is small and it is unlikely to very matter much but it is objectively less secure. Future advances in cryptography may make the distinction more important. The change would eliminate any hope of the specification ever having provable security equal to random keys. The bignum modulo operation also requires complex additional logic and is just as likely to remain untested in implementations, though unit-testing can test these cases by replacing the hash function. Because of layering no suitable modulo may be available and an incorrect implementation could create a devastating weakness, like reflecting a large class of keys to a small number of values. A similar error would be unlikely for an incorrect implementation of skipping and someone who managed to still fail would likely have failed either way. most of the implementations don't do the checking at all, because tjen it's rather hard at application level to implement skipping logic. OTOH There are many corner cases which must be handled in cryptographic software. You must handle the point at infinity cases, you must handle the signature having a value of zero (or you leak the private key), in the point arithemetics you must handle the special case of adding colinear points. If someone is unprepared to deal with these and many other complications they may want to leave writing this kind of software for other people. -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] BIP32 - invalidation
Does bitcoin properly handle the case of a hash collision? no - because it is considered too unlikely. The case of I_L = n is also astronomically unlikely, so it's more a matter of improved performance and simpler data structures under expected circumstances and taking that less than 1 in 2^127 chance that it will fail, in which case we can recover by moving everything over to a new tree. -Eric Lombrozo On Aug 9, 2014, at 5:34 PM, second isogeny secondisog...@gmail.com wrote: Does anyone see any concerns when it comes to security of the proposed change? Yes. This proposal is less secure. It is incompatible in theory with existing implementations of the specification. The incompatibility is also a potentially a security problem because it may cause users to believe a key is worthless when it is not or to lose funds when they are unable to spend them. It is also an untimely proposal and would be inconsiderate other parties who have done the work to produce correct and compatible implementations. In case I_L = n assign I_L := I_L mod n. This will make the selection of private keys uneven. The unevenness is small and it is unlikely to very matter much but it is objectively less secure. Future advances in cryptography may make the distinction more important. The change would eliminate any hope of the specification ever having provable security equal to random keys. The bignum modulo operation also requires complex additional logic and is just as likely to remain untested in implementations, though unit-testing can test these cases by replacing the hash function. Because of layering no suitable modulo may be available and an incorrect implementation could create a devastating weakness, like reflecting a large class of keys to a small number of values. A similar error would be unlikely for an incorrect implementation of skipping and someone who managed to still fail would likely have failed either way. most of the implementations don't do the checking at all, because tjen it's rather hard at application level to implement skipping logic. OTOH There are many corner cases which must be handled in cryptographic software. You must handle the point at infinity cases, you must handle the signature having a value of zero (or you leak the private key), in the point arithemetics you must handle the special case of adding colinear points. If someone is unprepared to deal with these and many other complications they may want to leave writing this kind of software for other people. -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development signature.asc Description: Message signed with OpenPGP using GPGMail -- ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development